00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026 #ifndef MLN_CORE_SITE_SET_P_QUEUE_FAST_HH
00027 # define MLN_CORE_SITE_SET_P_QUEUE_FAST_HH
00028
00035
00036 # include <mln/core/site_set/p_array.hh>
00037
00038
00039 namespace mln
00040 {
00041
00042
00043 template <typename P> class p_queue_fast;
00044
00045
00046
00047 namespace trait
00048 {
00049
00050 template <typename P>
00051 struct site_set_< p_queue_fast<P> >
00052 {
00053 typedef trait::site_set::nsites::known nsites;
00054 typedef trait::site_set::bbox::unknown bbox;
00055 typedef trait::site_set::contents::growing contents;
00056 typedef trait::site_set::arity::multiple arity;
00057 };
00058
00059 }
00060
00061
00062
00066
00071 template <typename P>
00072 class p_queue_fast : public internal::site_set_base_< P, p_queue_fast<P> >
00073 {
00074 typedef p_queue_fast<P> self_;
00075 public:
00076
00078 typedef P element;
00079
00081 typedef p_indexed_psite<self_> psite;
00082
00084 typedef p_indexed_fwd_piter<self_> fwd_piter;
00085
00087 typedef p_indexed_bkd_piter<self_> bkd_piter;
00088
00090 typedef fwd_piter piter;
00091
00092
00094 p_queue_fast();
00095
00097 void reserve(typename p_array<P>::size_type n);
00098
00100 bool has(const psite& p) const;
00101
00103 bool has(const util::index& i) const;
00104
00106 bool is_valid() const;
00107
00109 bool compute_has(const P& p) const;
00110
00112 unsigned nsites() const;
00113
00114
00116 void push(const P& p);
00117
00119 typedef P i_element;
00120
00122 void insert(const P& p);
00123
00124
00127 void pop();
00128
00131 const P& front() const;
00132
00136 const P& pop_front();
00137
00138
00140 void purge();
00141
00143 void clear();
00144
00145
00147 const P& operator[](unsigned i) const;
00148
00150 const std::vector<P>& std_vector() const;
00151
00153 std::size_t memory_size() const;
00154
00155 protected:
00156
00157 p_array<P> q_;
00158 unsigned begin_;
00159 unsigned end_;
00160 };
00161
00162
00163
00164 # ifndef MLN_INCLUDE_ONLY
00165
00166 template <typename P>
00167 inline
00168 p_queue_fast<P>::p_queue_fast()
00169 {
00170 begin_ = 0;
00171 end_ = 0;
00172 }
00173
00174 template <typename P>
00175 inline
00176 void
00177 p_queue_fast<P>::reserve(typename p_array<P>::size_type n)
00178 {
00179 q_.reserve(n);
00180 }
00181
00182 template <typename P>
00183 inline
00184 void
00185 p_queue_fast<P>::purge()
00186 {
00187 std::vector<P>& v = q_.hook_std_vector_();
00188 std::copy(v.begin() + begin_,
00189 v.begin() + end_,
00190 v.begin());
00191 v.resize(end_ - begin_);
00192 end_ -= begin_;
00193 begin_ = 0;
00194 }
00195
00196 template <typename P>
00197 inline
00198 bool
00199 p_queue_fast<P>::has(const psite& p) const
00200 {
00201 mln_precondition(p.target_() == this);
00202 if (p.index() < 0 || unsigned(p.index()) >= nsites())
00203 return false;
00204
00205 mln_invariant(p.to_site() == (*this)[p.index()]);
00206 return true;
00207 }
00208
00209 template <typename P>
00210 inline
00211 bool
00212 p_queue_fast<P>::has(const util::index& i) const
00213 {
00214 return i >= 0 && unsigned(i) < nsites();
00215 }
00216
00217 template <typename P>
00218 inline
00219 bool
00220 p_queue_fast<P>::compute_has(const P& p) const
00221 {
00222 for (unsigned i = begin_; i < end_; ++i)
00223 if (q_[i] == p)
00224 return true;
00225 return false;
00226 }
00227
00228 template <typename P>
00229 inline
00230 bool
00231 p_queue_fast<P>::is_valid() const
00232 {
00233 return true;
00234 }
00235
00236 template <typename P>
00237 inline
00238 unsigned
00239 p_queue_fast<P>::nsites() const
00240 {
00241 mln_invariant(end_ >= begin_);
00242 return end_ - begin_;
00243 }
00244
00245 template <typename P>
00246 inline
00247 void
00248 p_queue_fast<P>::push(const P& p)
00249 {
00250 q_.append(p);
00251 ++end_;
00252 }
00253
00254 template <typename P>
00255 inline
00256 void
00257 p_queue_fast<P>::pop()
00258 {
00259 mln_precondition(! this->is_empty());
00260 ++begin_;
00261 }
00262
00263 template <typename P>
00264 inline
00265 const P&
00266 p_queue_fast<P>::front() const
00267 {
00268 mln_precondition(! this->is_empty());
00269 return q_[begin_];
00270 }
00271
00272 template <typename P>
00273 inline
00274 const P&
00275 p_queue_fast<P>::pop_front()
00276 {
00277 mln_precondition(! this->is_empty());
00278 const P& res = this->front();
00279 this->pop();
00280 return res;
00281 }
00282
00283 template <typename P>
00284 inline
00285 void
00286 p_queue_fast<P>::clear()
00287 {
00288 end_ = begin_;
00289 }
00290
00291 template <typename P>
00292 inline
00293 const P&
00294 p_queue_fast<P>::operator[](unsigned i) const
00295 {
00296 mln_precondition(i < nsites());
00297 return q_[begin_ + i];
00298 }
00299
00300 template <typename P>
00301 inline
00302 void
00303 p_queue_fast<P>::insert(const P& p)
00304 {
00305 this->push(p);
00306 }
00307
00308 template <typename P>
00309 inline
00310 const std::vector<P>&
00311 p_queue_fast<P>::std_vector() const
00312 {
00313 return q_.std_vector();
00314 }
00315
00316 template <typename P>
00317 inline
00318 std::size_t
00319 p_queue_fast<P>::memory_size() const
00320 {
00321 return q_.memory_size() + 2 * sizeof(unsigned);
00322 }
00323
00324 # endif // ! MLN_INCLUDE_ONLY
00325
00326 }
00327
00328
00329 #endif // ! MLN_CORE_SITE_SET_P_QUEUE_FAST_HH