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_PRIORITY_HH
00027 # define MLN_CORE_SITE_SET_P_PRIORITY_HH
00028
00032
00033 # include <map>
00034 # include <mln/core/site_set/p_double.hh>
00035 # include <mln/core/internal/site_set_base.hh>
00036 # include <mln/util/set.hh>
00037 # include <mln/util/ord.hh>
00038
00039
00040 namespace mln
00041 {
00042
00043
00044 template <typename P, typename Q> class p_priority;
00045
00046
00047
00048 namespace trait
00049 {
00050
00051 template <typename P, typename Q>
00052 struct site_set_< p_priority<P,Q> >
00053 {
00054 typedef trait::site_set::nsites::known nsites;
00055 typedef trait::site_set::bbox::unknown bbox;
00056 typedef trait::site_set::contents::growing contents;
00057 typedef trait::site_set::arity::multiple arity;
00058 };
00059
00060 }
00061
00062
00063
00064
00068
00075 template <typename P, typename Q>
00076 class p_priority : public internal::site_set_base_< mln_site(Q),
00077 p_priority<P,Q> >,
00078 private mlc_is_a(Q, Site_Set)::check_t
00079 {
00080 typedef p_priority<P,Q> self_;
00081 public:
00082
00084 typedef mln_element(Q) element;
00085
00086
00088 typedef p_double_psite<self_, Q> psite;
00089
00091 typedef p_double_piter< self_,
00092 mln_bkd_eiter(util::set<P>),
00093 mln_fwd_piter(Q) > fwd_piter;
00094
00096 typedef p_double_piter< self_,
00097 mln_fwd_eiter(util::set<P>),
00098 mln_bkd_piter(Q) > bkd_piter;
00099
00101 typedef fwd_piter piter;
00102
00103
00105 p_priority();
00106
00108 bool has(const psite&) const;
00109
00111 bool is_valid() const;
00112
00114 unsigned nsites() const;
00115
00116
00118 void push(const P& priority, const element& e);
00119
00121 typedef std::pair<P, element> i_element;
00122
00124 void insert(const i_element& p_e);
00125
00127 void insert(const p_priority<P,Q>& other);
00128
00129
00133 void pop();
00134
00138 const mln_element(Q)& front() const;
00139
00143 mln_element(Q) pop_front();
00144
00145
00147 void clear();
00148
00149
00153 const Q& operator()(const P& priority) const;
00154
00156 const util::set<P>& priorities() const;
00157
00159 bool exists_priority(const P& priority) const;
00160
00163 const P highest_priority() const;
00164
00167 const P lowest_priority() const;
00168
00169
00170
00171 const util::set<P>& set_1_() const;
00172 const Q& set_2_(const P& priority) const;
00173
00174
00176 std::size_t memory_size() const;
00177
00178
00179 protected:
00180
00181 typedef std::map<P, Q, util::ord<P> > q_type_;
00182
00183 util::set<P> p_;
00184 q_type_ q_;
00185 unsigned n_;
00186
00187
00188 bool run_() const;
00189 };
00190
00191
00192
00193 template <typename P, typename Q>
00194 std::ostream& operator<<(std::ostream& ostr, const p_priority<P,Q>& pq);
00195
00196
00197
00198 # ifndef MLN_INCLUDE_ONLY
00199
00200 template <typename P, typename Q>
00201 inline
00202 p_priority<P,Q>::p_priority()
00203 {
00204 n_ = 0;
00205 mln_invariant(run_());
00206 }
00207
00208 template <typename P, typename Q>
00209 inline
00210 bool
00211 p_priority<P,Q>::has(const psite&) const
00212 {
00213 mln_invariant(run_());
00214
00215 return true;
00216 }
00217
00218 template <typename P, typename Q>
00219 inline
00220 bool
00221 p_priority<P,Q>::is_valid() const
00222 {
00223 mln_invariant(run_());
00224 return true;
00225 }
00226
00227 template <typename P, typename Q>
00228 inline
00229 unsigned
00230 p_priority<P,Q>::nsites() const
00231 {
00232 mln_invariant(run_());
00233 return n_;
00234 }
00235
00236 template <typename P, typename Q>
00237 inline
00238 void
00239 p_priority<P,Q>::push(const P& priority, const element& e)
00240 {
00241 mln_invariant(run_());
00242 p_.insert(priority);
00243 q_[priority].push(e);
00244 ++n_;
00245 mln_invariant(run_());
00246 }
00247
00248 template <typename P, typename Q>
00249 inline
00250 void
00251 p_priority<P,Q>::insert(const i_element& p_e)
00252 {
00253 this->push(p_e.first, p_e.second);
00254 }
00255
00256 template <typename P, typename Q>
00257 inline
00258 void
00259 p_priority<P,Q>::insert(const p_priority<P,Q>& other)
00260 {
00261 mln_invariant(run_());
00262 typename q_type_::const_iterator i;
00263 for (i = other.q_.begin(); i != other.q_.end(); ++i)
00264 {
00265 P priority = i->first;
00266 p_.insert(priority);
00267 const Q& q_p = i->second;
00268 q_[priority] += q_p;
00269 }
00270 n_ += other.n_;
00271 mln_invariant(run_());
00272 }
00273
00274 template <typename P, typename Q>
00275 inline
00276 void
00277 p_priority<P,Q>::pop()
00278 {
00279 mln_precondition(! this->is_empty());
00280 P prior = highest_priority();
00281 q_[prior].pop();
00282 if (q_[prior].is_empty())
00283 {
00284 q_.erase(prior);
00285 p_.remove(prior);
00286 }
00287 --n_;
00288 mln_invariant(run_());
00289 }
00290
00291 template <typename P, typename Q>
00292 inline
00293 const mln_element(Q)&
00294 p_priority<P,Q>::front() const
00295 {
00296 mln_precondition(! this->is_empty());
00297 q_type_& q__ = const_cast< q_type_& >(q_);
00298 return q__[highest_priority()].front();
00299 }
00300
00301 template <typename P, typename Q>
00302 inline
00303 mln_element(Q)
00304 p_priority<P,Q>::pop_front()
00305 {
00306 mln_precondition(! this->is_empty());
00307
00308 mln_element(Q) e = this->front();
00309 this->pop();
00310 return e;
00311 }
00312
00313 template <typename P, typename Q>
00314 inline
00315 void
00316 p_priority<P,Q>::clear()
00317 {
00318 mln_invariant(run_());
00319 p_.clear();
00320 q_.clear();
00321 n_ = 0;
00322 mln_invariant(run_());
00323 }
00324
00325 template <typename P, typename Q>
00326 inline
00327 std::size_t
00328 p_priority<P,Q>::memory_size() const
00329 {
00330 mln_invariant(run_());
00331 std::size_t mem_q = 0;
00332 typename q_type_::const_iterator i;
00333 for (i = q_.begin(); i != q_.end(); ++i)
00334 mem_q += i->second.memory_size();
00335 return p_.memory_size() + sizeof(q_) + sizeof(n_);
00336 }
00337
00338 template <typename P, typename Q>
00339 inline
00340 const Q&
00341 p_priority<P,Q>::operator()(const P& priority) const
00342 {
00343 static const Q nil_ = Q();
00344 if (exists_priority(priority))
00345 {
00346 q_type_& mq = const_cast<q_type_&>(q_);
00347 mln_assertion(mq[priority].nsites() > 0);
00348 return mq[priority];
00349 }
00350 else
00351 return nil_;
00352 }
00353
00354 template <typename P, typename Q>
00355 inline
00356 const util::set<P>&
00357 p_priority<P,Q>::priorities() const
00358 {
00359 mln_invariant(run_());
00360 return p_;
00361 }
00362
00363 template <typename P, typename Q>
00364 inline
00365 bool
00366 p_priority<P,Q>::exists_priority(const P& priority) const
00367 {
00368 mln_invariant(run_());
00369 return p_.has(priority);
00370 }
00371
00372 template <typename P, typename Q>
00373 inline
00374 const P
00375 p_priority<P,Q>::highest_priority() const
00376 {
00377 mln_precondition(! this->is_empty());
00378 return p_.last_element();
00379 }
00380
00381 template <typename P, typename Q>
00382 inline
00383 const P
00384 p_priority<P,Q>::lowest_priority() const
00385 {
00386 mln_precondition(! this->is_empty());
00387 return p_.first_element();
00388 }
00389
00390 template <typename P, typename Q>
00391 inline
00392 const util::set<P>&
00393 p_priority<P,Q>::set_1_() const
00394 {
00395 return p_;
00396 }
00397
00398 template <typename P, typename Q>
00399 inline
00400 const Q&
00401 p_priority<P,Q>::set_2_(const P& priority) const
00402 {
00403 mln_precondition(p_.has(priority));
00404 q_type_& mq = const_cast<q_type_&>(q_);
00405 mln_precondition(mq[priority].nsites() > 0);
00406 return mq[priority];
00407 }
00408
00409 template <typename P, typename Q>
00410 inline
00411 bool
00412 p_priority<P,Q>::run_() const
00413 {
00414 if (! implies(n_ == 0, p_.is_empty()))
00415 return false;
00416
00417 if (! (p_.nelements() == q_.size()))
00418
00419 return false;
00420
00421 mln_eiter(util::set<P>) p(p_);
00422 for_all(p)
00423 if (q_.find(p) == q_.end())
00424
00425 return false;
00426
00427 typename std::map<P,Q>::const_iterator i;
00428 for (i = q_.begin(); i != q_.end(); ++i)
00429 if (! p_.has(i->first))
00430
00431 return false;
00432
00433 return true;
00434 }
00435
00436
00437
00438
00439 template <typename P, typename Q>
00440 std::ostream& operator<<(std::ostream& ostr, const p_priority<P,Q>& pq)
00441 {
00442 ostr << '{';
00443 mln_bkd_eiter(util::set<P>) p(pq.priorities());
00444 for_all(p)
00445 {
00446 ostr << ' ' << p << ':';
00447 ostr << pq.set_2_(p);
00448 }
00449 ostr << '}';
00450 return ostr;
00451 }
00452
00453 # endif // ! MLN_INCLUDE_ONLY
00454
00455 }
00456
00457
00458 #endif // ! MLN_CORE_SITE_SET_P_PRIORITY_HH