Milena (Olena)
User documentation 2.0a Id
|
00001 // Copyright (C) 2007, 2008, 2009 EPITA Research and Development Laboratory (LRDE) 00002 // 00003 // This file is part of Olena. 00004 // 00005 // Olena is free software: you can redistribute it and/or modify it under 00006 // the terms of the GNU General Public License as published by the Free 00007 // Software Foundation, version 2 of the License. 00008 // 00009 // Olena is distributed in the hope that it will be useful, 00010 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00011 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00012 // General Public License for more details. 00013 // 00014 // You should have received a copy of the GNU General Public License 00015 // along with Olena. If not, see <http://www.gnu.org/licenses/>. 00016 // 00017 // As a special exception, you may use this file as part of a free 00018 // software project without restriction. Specifically, if other files 00019 // instantiate templates or use macros or inline functions from this 00020 // file, or you compile this file and link it with other files to produce 00021 // an executable, this file does not by itself cause the resulting 00022 // executable to be covered by the GNU General Public License. This 00023 // exception does not however invalidate any other reasons why the 00024 // executable file might be covered by the GNU General Public License. 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 // Forward declaration. 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 } // end of namespace trait 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 // Required by p_double-related classes. 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 // Run invariance tests and return the result. 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 // FIXME 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); // No-op if this priority already exists. 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); // Also test invariants. 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()); // Also test invariants. 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()); // Also test invariants. 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()); // Also test invariants. 00307 // FIXME: can be speeded up, return const& when possible... 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)) // Also test invariants. 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()); // Also test invariants. 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()); // Also test invariants. 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 // Containers p_ and q_ are not consistent in size! 00419 return false; 00420 00421 mln_eiter(util::set<P>) p(p_); 00422 for_all(p) 00423 if (q_.find(p) == q_.end()) 00424 // We have an empty queue (with priority p)! 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 // A priority is unknown (for a known queue)! 00431 return false; 00432 00433 return true; 00434 } 00435 00436 00437 // Operator<<. 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 } // end of namespace mln 00456 00457 00458 #endif // ! MLN_CORE_SITE_SET_P_PRIORITY_HH