Milena (Olena)
User documentation 2.0a Id
|
00001 // Copyright (C) 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_KEY_HH 00027 # define MLN_CORE_SITE_SET_P_KEY_HH 00028 00034 00035 # include <map> 00036 # include <mln/core/concept/function.hh> 00037 # include <mln/core/site_set/p_set.hh> 00038 # include <mln/core/site_set/p_double.hh> 00039 # include <mln/core/internal/site_set_base.hh> 00040 # include <mln/util/ord.hh> 00041 00042 00043 namespace mln 00044 { 00045 00046 // Forward declaration. 00047 template <typename K, typename P> class p_key; 00048 00049 00050 00051 namespace trait 00052 { 00053 00054 template <typename K, typename P> 00055 struct site_set_< p_key<K,P> > 00056 { 00057 typedef trait::site_set::nsites::known nsites; 00058 typedef trait::site_set::bbox::unknown bbox; 00059 typedef trait::site_set::contents::growing contents; 00060 typedef trait::site_set::arity::unique arity; 00061 }; 00062 00063 } // end of namespace trait 00064 00065 00066 00067 00071 template <typename K, typename P> 00072 class p_key : public internal::site_set_base_< P, 00073 p_key<K,P> > 00074 { 00075 typedef p_key<K,P> self_; 00076 public: 00077 00079 typedef P element; 00080 00081 00083 typedef p_double_psite< self_, p_set<P> > psite; 00084 00086 typedef p_double_piter<self_, 00087 mln_fwd_eiter(util::set<K>), 00088 mln_fwd_piter(p_set<P>)> fwd_piter; 00089 00091 typedef p_double_piter<self_, 00092 mln_bkd_eiter(util::set<K>), 00093 mln_bkd_piter(p_set<P>)> bkd_piter; 00094 00096 typedef fwd_piter piter; 00097 00098 00100 p_key(); 00101 00102 00104 bool has(const psite&) const; 00105 00107 bool has(const P& p) const; 00108 00109 00111 bool is_valid() const; 00112 00114 unsigned nsites() const; 00115 00116 00118 typedef std::pair<K,P> i_element; 00119 00121 void insert(const i_element& k_p); 00122 00124 void insert(const K& k, const P& p); 00125 00126 00127 void unsafe_insert_(const K& k, const P& p); 00128 00129 00130 00132 typedef P r_element; 00133 00135 void remove(const P& p); 00136 00138 void remove_key(const K& k); 00139 00141 void change_key(const K& k, const K& new_k); 00142 00144 template <typename F> 00145 void change_keys(const Function_v2v<F>& f); 00146 00147 00148 00150 void clear(); 00151 00152 00156 const p_set<P>& operator()(const K& key) const; 00157 00159 const K& key(const P& p) const; 00160 00162 const util::set<K>& keys() const; 00163 00164 00166 bool exists_key(const K& key) const; 00167 00168 00169 // Required by p_double-related classes. 00170 const util::set<K>& set_1_() const; 00171 const p_set<P>& set_2_(const K& key) const; 00172 00173 00175 std::size_t memory_size() const; 00176 00177 protected: 00178 00179 // Bunch of keys. 00180 util::set<K> b_; 00181 00182 // Function: key k -> set of sites {p}. 00183 typedef std::map<K, p_set<P>, util::ord<K> > s_t; 00184 s_t s_; 00185 00186 // Function: site p -> key k. 00187 typedef std::map<P, K, util::ord<P> > k_t; 00188 k_t k_; 00189 00190 // Number of sites. 00191 unsigned n_; 00192 00193 // Run invariance tests and return the result. 00194 bool run_() const; 00195 }; 00196 00197 00198 00199 template <typename K, typename P> 00200 std::ostream& operator<<(std::ostream& ostr, const p_key<K,P>& pk); 00201 00202 00203 00204 # ifndef MLN_INCLUDE_ONLY 00205 00206 template <typename K, typename P> 00207 inline 00208 p_key<K,P>::p_key() 00209 { 00210 n_ = 0; 00211 mln_invariant(run_()); 00212 } 00213 00214 template <typename K, typename P> 00215 inline 00216 bool 00217 p_key<K,P>::has(const psite&) const 00218 { 00219 mln_invariant(run_()); 00220 // FIXME 00221 return true; 00222 } 00223 00224 template <typename K, typename P> 00225 inline 00226 bool 00227 p_key<K,P>::has(const P& p) const 00228 { 00229 mln_invariant(run_()); 00230 return k_.find(p) != k_.end(); 00231 } 00232 00233 template <typename K, typename P> 00234 inline 00235 bool 00236 p_key<K,P>::is_valid() const 00237 { 00238 mln_invariant(run_()); 00239 return true; 00240 } 00241 00242 template <typename K, typename P> 00243 inline 00244 unsigned 00245 p_key<K,P>::nsites() const 00246 { 00247 mln_invariant(run_()); 00248 return n_; 00249 } 00250 00251 00252 template <typename K, typename P> 00253 inline 00254 void 00255 p_key<K,P>::unsafe_insert_(const K& k, const P& p) 00256 { 00257 s_[k].insert(p); 00258 k_[p] = k; 00259 ++n_; 00260 b_.insert(k); 00261 mln_invariant(run_()); 00262 } 00263 00264 00265 template <typename K, typename P> 00266 inline 00267 void 00268 p_key<K,P>::insert(const K& k, const P& p) 00269 { 00270 mln_invariant(run_()); 00271 typename k_t::iterator p_k = k_.find(p); 00272 if (p_k != k_.end()) 00273 // p is already in this set (so n_ is unchanged). 00274 { 00275 K p_key = p_k->second; 00276 mln_assertion(b_.has(p_key)); 00277 mln_assertion(s_[p_key].has(p)); 00278 if (p_key == k) 00279 // No-op. 00280 return; 00281 // p moves from s_[p_key] to s_[k]. 00282 s_[p_key].remove(p); 00283 s_[k].insert(p); 00284 // Update key of p. 00285 p_k->second = k; 00286 } 00287 else 00288 // Actual insertion. 00289 { 00290 s_[k].insert(p); 00291 k_[p] = k; 00292 ++n_; 00293 } 00294 b_.insert(k); 00295 mln_invariant(run_()); 00296 } 00297 00298 template <typename K, typename P> 00299 inline 00300 void 00301 p_key<K,P>::insert(const i_element& k_p) 00302 { 00303 this->insert(k_p.first, k_p.second); // Also test invariants. 00304 } 00305 00306 template <typename K, typename P> 00307 inline 00308 void 00309 p_key<K,P>::remove(const P& p) 00310 { 00311 mln_invariant(run_()); 00312 typename k_t::iterator p_k = k_.find(p); 00313 00314 if (p_k == k_.end()) 00315 // No-op because p does not belong to this site set. 00316 return; 00317 00318 K p_key = p_k->second; 00319 mln_assertion(b_.has(p_key)); 00320 00321 // Update k_. 00322 k_.erase(p_k); 00323 00324 // Update s_. 00325 typename s_t::iterator k_s = s_.find(p_key); 00326 mln_assertion(k_s != s_.end()); // p_key found in s_. 00327 p_set<P>& s = k_s->second; 00328 mln_assertion(s.has(p)); // p is in s_[p_key]. 00329 00330 if (s.nsites() == 1) 00331 { 00332 // Clean up for p is the only site with p_key. 00333 s_.erase(k_s); 00334 b_.remove(p_key); 00335 } 00336 else 00337 { 00338 // Simple removal. 00339 s.remove(p); 00340 } 00341 00342 // Update n_. 00343 --n_; 00344 00345 mln_invariant(run_()); 00346 } 00347 00348 template <typename K, typename P> 00349 inline 00350 void 00351 p_key<K,P>::remove_key(const K& k) 00352 { 00353 mln_invariant(run_()); 00354 typename s_t::iterator k_s = s_.find(k); 00355 00356 if (k_s == s_.end()) 00357 // No-op because key k does not exist. 00358 return; 00359 00360 // Update b_. 00361 b_.remove(k); 00362 00363 // Update k_. 00364 p_set<P>& s = k_s->second; 00365 mln_piter(p_set<P>) p(s); 00366 for_all(p) 00367 k_.erase(p); 00368 00369 // Update n_. 00370 n_ -= s.nsites(); 00371 00372 // Update s_. 00373 s_.erase(k_s); 00374 00375 mln_invariant(run_()); 00376 } 00377 00378 00379 template <typename K, typename P> 00380 inline 00381 void 00382 p_key<K,P>::change_key(const K& k, const K& new_k) 00383 { 00384 mln_invariant(run_()); 00385 00386 if (new_k == k) 00387 // No-op. 00388 return; 00389 00390 typename s_t::iterator k_s = s_.find(k); 00391 if (k_s == s_.end()) 00392 // No-op because key k does not exist. 00393 return; 00394 00395 // Update b_. 00396 b_.remove(k); 00397 b_.insert(new_k); 00398 00399 // Update k_. 00400 p_set<P>& s = k_s->second; 00401 if (s.nsites() < n_ / 10) // Few elements to be moved. 00402 { 00403 // s.nsites() iterations. 00404 mln_piter(p_set<P>) p(s); 00405 for_all(p) 00406 k_[p] = new_k; 00407 } 00408 else 00409 { 00410 // n_ iterations. 00411 typename k_t::iterator p_k; 00412 for (p_k = k_.begin(); p_k != k_.end(); ++p_k) 00413 if (p_k->second == k) 00414 p_k->second = new_k; 00415 } 00416 00417 // Update s_. 00418 s_[new_k] += s; 00419 s_.erase(k_s); 00420 00421 mln_invariant(run_()); 00422 } 00423 00424 template <typename K, typename P> 00425 template <typename F> 00426 inline 00427 void 00428 p_key<K,P>::change_keys(const Function_v2v<F>& f_) 00429 { 00430 mln_invariant(run_()); 00431 00432 const F& f = exact(f_); 00433 std::map<K,K> lut; 00434 00435 // Update b_. 00436 { 00437 util::set<K> new_b; 00438 mln_eiter(util::set<K>) k(b_); 00439 for_all(k) 00440 new_b.insert(lut[k] = f(k)); 00441 b_ = new_b; 00442 } 00443 00444 // Update k_ and s_. 00445 { 00446 s_t new_s; 00447 typename k_t::iterator p_k; 00448 for (p_k = k_.begin(); p_k != k_.end(); ++p_k) 00449 { 00450 p_k->second = lut[p_k->second]; 00451 new_s[p_k->second].insert(p_k->first); 00452 } 00453 s_ = new_s; 00454 } 00455 00456 mln_invariant(run_()); 00457 } 00458 00459 template <typename K, typename P> 00460 inline 00461 void 00462 p_key<K,P>::clear() 00463 { 00464 mln_invariant(run_()); 00465 b_.clear(); 00466 s_.clear(); 00467 k_.clear(); 00468 n_ = 0; 00469 mln_invariant(run_()); 00470 } 00471 00472 template <typename K, typename P> 00473 inline 00474 std::size_t 00475 p_key<K,P>::memory_size() const 00476 { 00477 mln_invariant(run_()); 00478 return 0; // FIXME 00479 // std::size_t mem_q = 0; 00480 // typename std::map<P, Q>::const_iterator i; 00481 // for (i = q_.begin(); i != q_.end(); ++i) 00482 // mem_q += i->second.memory_size(); 00483 // return p_.memory_size() + sizeof(q_) + sizeof(n_); 00484 } 00485 00486 template <typename K, typename P> 00487 inline 00488 const p_set<P>& 00489 p_key<K,P>::operator()(const K& key) const 00490 { 00491 static const p_set<P> nil_ = p_set<P>(); 00492 if (exists_key(key)) // Also test invariants. 00493 return s_.find(key)->second; 00494 else 00495 return nil_; 00496 } 00497 00498 template <typename K, typename P> 00499 inline 00500 const K& 00501 p_key<K,P>::key(const P& p) const 00502 { 00503 mln_invariant(run_()); 00504 mln_precondition(k_.find(p) != k_.end()); 00505 return k_.find(p)->second; 00506 } 00507 00508 template <typename K, typename P> 00509 inline 00510 const util::set<K>& 00511 p_key<K,P>::keys() const 00512 { 00513 mln_invariant(run_()); 00514 return b_; 00515 } 00516 00517 template <typename K, typename P> 00518 inline 00519 bool 00520 p_key<K,P>::exists_key(const K& key) const 00521 { 00522 mln_invariant(run_()); 00523 return b_.has(key); 00524 } 00525 00526 template <typename K, typename P> 00527 inline 00528 const util::set<K>& 00529 p_key<K,P>::set_1_() const 00530 { 00531 return b_; 00532 } 00533 00534 template <typename K, typename P> 00535 inline 00536 const p_set<P>& 00537 p_key<K,P>::set_2_(const K& key) const 00538 { 00539 mln_precondition(b_.has(key)); 00540 return s_.find(key)->second; 00541 } 00542 00543 template <typename K, typename P> 00544 inline 00545 bool 00546 p_key<K,P>::run_() const 00547 { 00548 if (! implies(n_ == 0, b_.is_empty())) 00549 { 00550 std::cerr << "#1" << std::endl; 00551 return false; 00552 } 00553 00554 if (b_.nelements() != s_.size()) 00555 { 00556 // Containers b_ and s_ are not consistent in size! 00557 std::cerr << "#2" << std::endl; 00558 return false; 00559 } 00560 00561 if (k_.size() != n_) 00562 { 00563 // The number of entries in k_ is not n_! 00564 std::cerr << "#3: k_.size=" << k_.size() << " n_=" << n_ << std::endl; 00565 return false; 00566 } 00567 00568 unsigned n = 0; 00569 mln_eiter(util::set<K>) key(b_); 00570 for_all(key) 00571 { 00572 typename s_t::const_iterator k_s = s_.find(key); 00573 00574 if (k_s == s_.end()) 00575 { 00576 // This key is not found in s_! 00577 std::cerr << "#4" << std::endl; 00578 return false; 00579 } 00580 00581 const p_set<P>& s = k_s->second; 00582 00583 if (s.nsites() == 0) 00584 { 00585 // The site set associated with this key is empty! 00586 std::cerr << "#5" << std::endl; 00587 return false; 00588 } 00589 00590 n += s.nsites(); 00591 00592 mln_piter(p_set<P>) p(s); 00593 for_all(p) // For every site p with the current key w.r.t. s_. 00594 { 00595 typename k_t::const_iterator p_k = k_.find(p); 00596 00597 if (p_k == k_.end()) 00598 { 00599 // There is no key entry for p in k_! 00600 std::cerr << "#6" << std::endl; 00601 return false; 00602 } 00603 00604 if (p_k->second != key) 00605 { 00606 // We have an inconsistency for p between s_ and k_! 00607 std::cerr << "#7" << std::endl; 00608 return false; 00609 } 00610 } 00611 } 00612 00613 if (n != n_) 00614 { 00615 // The number of elements in s_ is not n_! 00616 std::cerr << "#8" << std::endl; 00617 return false; 00618 } 00619 00620 return true; 00621 } 00622 00623 00624 00625 00626 00627 // Operator<<. 00628 00629 template <typename K, typename P> 00630 std::ostream& operator<<(std::ostream& ostr, const p_key<K,P>& pk) 00631 { 00632 ostr << '{'; 00633 mln_fwd_eiter(util::set<K>) k(pk.keys()); 00634 for_all(k) 00635 { 00636 ostr << ' ' << k << ':'; 00637 ostr << pk.set_2_(k); 00638 } 00639 ostr << '}'; 00640 return ostr; 00641 } 00642 00643 # endif // ! MLN_INCLUDE_ONLY 00644 00645 } // end of namespace mln 00646 00647 00648 #endif // ! MLN_CORE_SITE_SET_P_KEY_HH