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_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
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 }
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
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
00180 util::set<K> b_;
00181
00182
00183 typedef std::map<K, p_set<P>, util::ord<K> > s_t;
00184 s_t s_;
00185
00186
00187 typedef std::map<P, K, util::ord<P> > k_t;
00188 k_t k_;
00189
00190
00191 unsigned n_;
00192
00193
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
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
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
00280 return;
00281
00282 s_[p_key].remove(p);
00283 s_[k].insert(p);
00284
00285 p_k->second = k;
00286 }
00287 else
00288
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);
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
00316 return;
00317
00318 K p_key = p_k->second;
00319 mln_assertion(b_.has(p_key));
00320
00321
00322 k_.erase(p_k);
00323
00324
00325 typename s_t::iterator k_s = s_.find(p_key);
00326 mln_assertion(k_s != s_.end());
00327 p_set<P>& s = k_s->second;
00328 mln_assertion(s.has(p));
00329
00330 if (s.nsites() == 1)
00331 {
00332
00333 s_.erase(k_s);
00334 b_.remove(p_key);
00335 }
00336 else
00337 {
00338
00339 s.remove(p);
00340 }
00341
00342
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
00358 return;
00359
00360
00361 b_.remove(k);
00362
00363
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
00370 n_ -= s.nsites();
00371
00372
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
00388 return;
00389
00390 typename s_t::iterator k_s = s_.find(k);
00391 if (k_s == s_.end())
00392
00393 return;
00394
00395
00396 b_.remove(k);
00397 b_.insert(new_k);
00398
00399
00400 p_set<P>& s = k_s->second;
00401 if (s.nsites() < n_ / 10)
00402 {
00403
00404 mln_piter(p_set<P>) p(s);
00405 for_all(p)
00406 k_[p] = new_k;
00407 }
00408 else
00409 {
00410
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
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
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
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;
00479
00480
00481
00482
00483
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))
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
00557 std::cerr << "#2" << std::endl;
00558 return false;
00559 }
00560
00561 if (k_.size() != n_)
00562 {
00563
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
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
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)
00594 {
00595 typename k_t::const_iterator p_k = k_.find(p);
00596
00597 if (p_k == k_.end())
00598 {
00599
00600 std::cerr << "#6" << std::endl;
00601 return false;
00602 }
00603
00604 if (p_k->second != key)
00605 {
00606
00607 std::cerr << "#7" << std::endl;
00608 return false;
00609 }
00610 }
00611 }
00612
00613 if (n != n_)
00614 {
00615
00616 std::cerr << "#8" << std::endl;
00617 return false;
00618 }
00619
00620 return true;
00621 }
00622
00623
00624
00625
00626
00627
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 }
00646
00647
00648 #endif // ! MLN_CORE_SITE_SET_P_KEY_HH