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
00115 bool empty() const;
00116
00118 void push(const P& p);
00119
00121 typedef P i_element;
00122
00124 void insert(const P& p);
00125
00126
00129 void pop();
00130
00133 const P& front() const;
00134
00138 const P& pop_front();
00139
00140
00142 void purge();
00143
00145 void clear();
00146
00147
00149 const P& operator[](unsigned i) const;
00150
00152 const std::vector<P>& std_vector() const;
00153
00155 std::size_t memory_size() const;
00156
00157 protected:
00158
00159 p_array<P> q_;
00160 unsigned begin_;
00161 unsigned end_;
00162 };
00163
00164
00165
00166 # ifndef MLN_INCLUDE_ONLY
00167
00168 template <typename P>
00169 inline
00170 p_queue_fast<P>::p_queue_fast()
00171 {
00172 begin_ = 0;
00173 end_ = 0;
00174 }
00175
00176 template <typename P>
00177 inline
00178 void
00179 p_queue_fast<P>::reserve(typename p_array<P>::size_type n)
00180 {
00181 q_.reserve(n);
00182 }
00183
00184 template <typename P>
00185 inline
00186 void
00187 p_queue_fast<P>::purge()
00188 {
00189 std::vector<P>& v = q_.hook_std_vector_();
00190 std::copy(v.begin() + begin_,
00191 v.begin() + end_,
00192 v.begin());
00193 v.resize(end_ - begin_);
00194 end_ -= begin_;
00195 begin_ = 0;
00196 }
00197
00198 template <typename P>
00199 inline
00200 bool
00201 p_queue_fast<P>::has(const psite& p) const
00202 {
00203 mln_precondition(p.target_() == this);
00204 if (p.index() < 0 || unsigned(p.index()) >= nsites())
00205 return false;
00206
00207
00208 return true;
00209 }
00210
00211 template <typename P>
00212 inline
00213 bool
00214 p_queue_fast<P>::has(const util::index& i) const
00215 {
00216 return i >= 0 && unsigned(i) < nsites();
00217 }
00218
00219 template <typename P>
00220 inline
00221 bool
00222 p_queue_fast<P>::compute_has(const P& p) const
00223 {
00224 for (unsigned i = begin_; i < end_; ++i)
00225 if (q_[i] == p)
00226 return true;
00227 return false;
00228 }
00229
00230 template <typename P>
00231 inline
00232 bool
00233 p_queue_fast<P>::is_valid() const
00234 {
00235 return true;
00236 }
00237
00238 template <typename P>
00239 inline
00240 unsigned
00241 p_queue_fast<P>::nsites() const
00242 {
00243 mln_invariant(end_ >= begin_);
00244 return end_ - begin_;
00245 }
00246
00247 template <typename P>
00248 inline
00249 bool
00250 p_queue_fast<P>::empty() const
00251 {
00252 mln_invariant(end_ >= begin_);
00253 return end_ == begin_;
00254 }
00255
00256 template <typename P>
00257 inline
00258 void
00259 p_queue_fast<P>::push(const P& p)
00260 {
00261 q_.append(p);
00262 ++end_;
00263 }
00264
00265 template <typename P>
00266 inline
00267 void
00268 p_queue_fast<P>::pop()
00269 {
00270 mln_precondition(! this->is_empty());
00271 ++begin_;
00272 }
00273
00274 template <typename P>
00275 inline
00276 const P&
00277 p_queue_fast<P>::front() const
00278 {
00279 mln_precondition(! this->is_empty());
00280 return q_[begin_];
00281 }
00282
00283 template <typename P>
00284 inline
00285 const P&
00286 p_queue_fast<P>::pop_front()
00287 {
00288 mln_precondition(! this->is_empty());
00289 const P& res = this->front();
00290 this->pop();
00291 return res;
00292 }
00293
00294 template <typename P>
00295 inline
00296 void
00297 p_queue_fast<P>::clear()
00298 {
00299 end_ = begin_;
00300 }
00301
00302 template <typename P>
00303 inline
00304 const P&
00305 p_queue_fast<P>::operator[](unsigned i) const
00306 {
00307 mln_precondition(i < nsites());
00308 return q_[begin_ + i];
00309 }
00310
00311 template <typename P>
00312 inline
00313 void
00314 p_queue_fast<P>::insert(const P& p)
00315 {
00316 this->push(p);
00317 }
00318
00319 template <typename P>
00320 inline
00321 const std::vector<P>&
00322 p_queue_fast<P>::std_vector() const
00323 {
00324 return q_.std_vector();
00325 }
00326
00327 template <typename P>
00328 inline
00329 std::size_t
00330 p_queue_fast<P>::memory_size() const
00331 {
00332 return q_.memory_size() + 2 * sizeof(unsigned);
00333 }
00334
00335 # endif // ! MLN_INCLUDE_ONLY
00336
00337 }
00338
00339
00340 #endif // ! MLN_CORE_SITE_SET_P_QUEUE_FAST_HH