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
00027 #ifndef MLN_UTIL_SET_HH
00028 # define MLN_UTIL_SET_HH
00029
00037
00038 # include <vector>
00039 # include <set>
00040 # include <iterator>
00041 # include <algorithm>
00042 # include <iostream>
00043
00044 # include <mln/core/concept/proxy.hh>
00045 # include <mln/util/ord.hh>
00046
00047
00048 namespace mln
00049 {
00050
00051 namespace util
00052 {
00053
00054
00055 template <typename T> class set_fwd_iter;
00056 template <typename T> class set_bkd_iter;
00057
00058
00079
00080 template <typename T>
00081 class set : public Object< mln::util::set<T> >
00082 {
00083 public:
00084
00086 typedef T element;
00087
00088
00090 typedef set_fwd_iter<T> fwd_eiter;
00091
00093 typedef set_bkd_iter<T> bkd_eiter;
00094
00096 typedef fwd_eiter eiter;
00097
00098
00107 set<T>& insert(const T& elt);
00108
00109
00116 template <typename U>
00117 set<T>& insert(const set<U>& other);
00118
00119
00128 set<T>& remove(const T& elt);
00129
00130
00138 void clear();
00139
00140
00143 unsigned nelements() const;
00144
00145
00148 bool is_empty() const;
00149
00150
00151
00160 const T& operator[](unsigned i) const;
00161
00164 const T first_element() const;
00165
00168 const T last_element() const;
00169
00170
00177 bool has(const T& elt) const;
00178
00179
00188 const std::vector<T>& std_vector() const;
00189
00190
00192 set();
00193
00194
00196 std::size_t memory_size() const;
00197
00199 bool is_frozen_() const;
00200
00201 private:
00202
00208 mutable std::vector<T> v_;
00209
00214 mutable std::set< T, util::ord<T> > s_;
00215
00216
00220 void freeze_() const;
00221
00224 void unfreeze_() const;
00225
00227 mutable bool frozen_;
00228
00229
00230
00231 bool v_has_(const T& elt) const;
00232 unsigned dicho_(const T& elt, unsigned beg, unsigned end) const;
00233 };
00234
00235
00236 template <typename T>
00237 bool operator == (const set<T>& lhs, const set<T>& rhs);
00238
00239
00240 template <typename T>
00241 bool operator < (const set<T>& lhs, const set<T>& rhs);
00242
00243
00244 template <typename T>
00245 bool operator <= (const set<T>& lhs, const set<T>& rhs);
00246
00247
00248
00249
00250
00251 template <typename T>
00252 class set_fwd_iter : public Proxy< set_fwd_iter<T> >,
00253 public mln::internal::proxy_impl< const T&, set_fwd_iter<T> >
00254 {
00255 public:
00256
00258 set_fwd_iter();
00259
00261 set_fwd_iter(const set<T>& s);
00262
00264 void change_target(const set<T>& s);
00265
00267 void start();
00268
00270 void next();
00271
00273 bool is_valid() const;
00274
00276 void invalidate();
00277
00279 const T& element() const;
00280
00281
00282 const T& subj_();
00283
00285 unsigned index_() const;
00286
00287 protected:
00288 unsigned i_;
00289 const set<T>* s_;
00290 };
00291
00292
00293
00294
00295
00296
00297 template <typename T>
00298 class set_bkd_iter : public Proxy< set_bkd_iter<T> >,
00299 public mln::internal::proxy_impl< const T&, set_bkd_iter<T> >
00300 {
00301 public:
00302
00304 set_bkd_iter();
00305
00307 set_bkd_iter(const set<T>& s);
00308
00310 void change_target(const set<T>& s);
00311
00313 void start();
00314
00316 void next();
00317
00319 bool is_valid() const;
00320
00322 void invalidate();
00323
00325 const T& element() const;
00326
00327
00328 const T& subj_();
00329
00331 unsigned index_() const;
00332
00333 protected:
00334 unsigned i_;
00335 const set<T>* s_;
00336 };
00337
00338
00339
00340 # ifndef MLN_INCLUDE_ONLY
00341
00342
00343
00344
00345
00346 template <typename T>
00347 inline
00348 set<T>::set()
00349 {
00350 frozen_ = false;
00351 }
00352
00353 template <typename T>
00354 inline
00355 set<T>&
00356 set<T>::insert(const T& elt)
00357 {
00358 if (frozen_) unfreeze_();
00359 s_.insert(elt);
00360 return *this;
00361 }
00362
00363 template <typename T>
00364 template <typename U>
00365 inline
00366 set<T>&
00367 set<T>::insert(const set<U>& other)
00368 {
00369 if (other.is_empty())
00370
00371 return *this;
00372 if (frozen_) unfreeze_();
00373 s_.insert(other.std_vector().begin(), other.std_vector().end());
00374 return *this;
00375 }
00376
00377 template <typename T>
00378 inline
00379 set<T>&
00380 set<T>::remove(const T& elt)
00381 {
00382 if (frozen_) unfreeze_();
00383 s_.erase(elt);
00384 return *this;
00385 }
00386
00387 template <typename T>
00388 inline
00389 void
00390 set<T>::clear()
00391 {
00392 if (frozen_)
00393 {
00394 mln_invariant(s_.empty());
00395 v_.clear();
00396 frozen_ = false;
00397 }
00398 else
00399 {
00400 mln_invariant(v_.empty());
00401 s_.clear();
00402 }
00403 mln_postcondition(is_empty());
00404 }
00405
00406 template <typename T>
00407 inline
00408 unsigned
00409 set<T>::nelements() const
00410 {
00411 return frozen_ ? v_.size() : s_.size();
00412 }
00413
00414 template <typename T>
00415 inline
00416 const T&
00417 set<T>::operator[](unsigned i) const
00418 {
00419 mln_precondition(i < nelements());
00420 if (! frozen_) freeze_();
00421 return v_[i];
00422 }
00423
00424 template <typename T>
00425 inline
00426 const T
00427 set<T>::first_element() const
00428 {
00429 mln_precondition(! is_empty());
00430 return frozen_ ? *v_.begin() : *s_.begin();
00431 }
00432
00433 template <typename T>
00434 inline
00435 const T
00436 set<T>::last_element() const
00437 {
00438 mln_precondition(! is_empty());
00439 return frozen_ ? *v_.rbegin() : *s_.rbegin();
00440 }
00441
00442 template <typename T>
00443 inline
00444 bool
00445 set<T>::has(const T& elt) const
00446 {
00447 return frozen_ ? v_has_(elt) : s_.find(elt) != s_.end();
00448 }
00449
00450 template <typename T>
00451 inline
00452 bool
00453 set<T>::is_empty() const
00454 {
00455 return nelements() == 0;
00456 }
00457
00458 template <typename T>
00459 inline
00460 const std::vector<T>&
00461 set<T>::std_vector() const
00462 {
00463 if (! frozen_) freeze_();
00464 return v_;
00465 }
00466
00467 template <typename T>
00468 inline
00469 void
00470 set<T>::freeze_() const
00471 {
00472 mln_precondition(frozen_ == false);
00473 mln_invariant(v_.empty());
00474 std::copy(s_.begin(), s_.end(), std::back_inserter(v_));
00475 s_.clear();
00476 frozen_ = true;
00477 }
00478
00479 template <typename T>
00480 inline
00481 void
00482 set<T>::unfreeze_() const
00483 {
00484 mln_precondition(frozen_ == true);
00485 mln_invariant(s_.empty());
00486 s_.insert(v_.begin(), v_.end());
00487 v_.clear();
00488 frozen_ = false;
00489 }
00490
00491 template <typename T>
00492 inline
00493 std::size_t
00494 set<T>::memory_size() const
00495 {
00496 return nelements() * sizeof(T);
00497 }
00498
00499 template <typename T>
00500 inline
00501 bool
00502 set<T>::is_frozen_() const
00503 {
00504 return frozen_;
00505 }
00506
00507 template <typename T>
00508 inline
00509 bool
00510 set<T>::v_has_(const T& elt) const
00511 {
00512 mln_precondition(frozen_);
00513 if (is_empty() ||
00514 util::ord_strict(elt, v_[0]) ||
00515 util::ord_strict(v_[nelements() - 1], elt))
00516 return false;
00517 return v_[dicho_(elt, 0, nelements())] == elt;
00518 }
00519
00520 template <typename T>
00521 inline
00522 unsigned
00523 set<T>::dicho_(const T& elt, unsigned beg, unsigned end) const
00524 {
00525 mln_precondition(frozen_);
00526 mln_precondition(beg <= end);
00527 if (end - beg <= 1)
00528 return beg;
00529 unsigned med = (beg + end) / 2;
00530 return util::ord_strict(elt, v_[med])
00531 ? dicho_(elt, beg, med)
00532 : dicho_(elt, med, end);
00533 }
00534
00535
00536
00537
00538
00539
00540 template <typename T>
00541 inline
00542 set_fwd_iter<T>::set_fwd_iter()
00543 {
00544 s_ = 0;
00545 }
00546
00547 template <typename T>
00548 inline
00549 set_fwd_iter<T>::set_fwd_iter(const set<T>& s)
00550 {
00551 change_target(s);
00552 }
00553
00554 template <typename T>
00555 inline
00556 void
00557 set_fwd_iter<T>::change_target(const set<T>& s)
00558 {
00559 s_ = &s;
00560 invalidate();
00561 }
00562
00563 template <typename T>
00564 inline
00565 void
00566 set_fwd_iter<T>::start()
00567 {
00568 mln_precondition(s_ != 0);
00569 i_ = 0;
00570 }
00571
00572 template <typename T>
00573 inline
00574 void
00575 set_fwd_iter<T>::next()
00576 {
00577 mln_precondition(is_valid());
00578 ++i_;
00579 }
00580
00581 template <typename T>
00582 inline
00583 bool
00584 set_fwd_iter<T>::is_valid() const
00585 {
00586 return s_ != 0 && i_ != s_->nelements();
00587 }
00588
00589 template <typename T>
00590 inline
00591 void
00592 set_fwd_iter<T>::invalidate()
00593 {
00594 if (s_ != 0)
00595 i_ = s_->nelements();
00596 mln_postcondition(! is_valid());
00597 }
00598
00599 template <typename T>
00600 inline
00601 const T&
00602 set_fwd_iter<T>::element() const
00603 {
00604 mln_precondition(is_valid());
00605 return s_->operator[](i_);
00606 }
00607
00608 template <typename T>
00609 inline
00610 const T&
00611 set_fwd_iter<T>::subj_()
00612 {
00613 mln_precondition(is_valid());
00614 return s_->operator[](i_);
00615 }
00616
00617 template <typename T>
00618 inline
00619 unsigned
00620 set_fwd_iter<T>::index_() const
00621 {
00622 return i_;
00623 }
00624
00625
00626
00627
00628
00629
00630 template <typename T>
00631 inline
00632 set_bkd_iter<T>::set_bkd_iter()
00633 {
00634 s_ = 0;
00635 }
00636
00637 template <typename T>
00638 inline
00639 set_bkd_iter<T>::set_bkd_iter(const set<T>& s)
00640 {
00641 change_target(s);
00642 }
00643
00644 template <typename T>
00645 inline
00646 void
00647 set_bkd_iter<T>::change_target(const set<T>& s)
00648 {
00649 s_ = &s;
00650 invalidate();
00651 }
00652
00653 template <typename T>
00654 inline
00655 void
00656 set_bkd_iter<T>::start()
00657 {
00658 mln_precondition(s_ != 0);
00659 if (! s_->is_empty())
00660 i_ = s_->nelements() - 1;
00661 }
00662
00663 template <typename T>
00664 inline
00665 void
00666 set_bkd_iter<T>::next()
00667 {
00668 mln_precondition(is_valid());
00669 if (i_ == 0)
00670 invalidate();
00671 else
00672 --i_;
00673 }
00674
00675 template <typename T>
00676 inline
00677 bool
00678 set_bkd_iter<T>::is_valid() const
00679 {
00680 return s_ != 0 && i_ != s_->nelements();
00681 }
00682
00683 template <typename T>
00684 inline
00685 void
00686 set_bkd_iter<T>::invalidate()
00687 {
00688 if (s_ != 0)
00689 i_ = s_->nelements();
00690 mln_postcondition(! is_valid());
00691 }
00692
00693 template <typename T>
00694 inline
00695 const T&
00696 set_bkd_iter<T>::element() const
00697 {
00698 mln_precondition(is_valid());
00699 return s_->operator[](i_);
00700 }
00701
00702 template <typename T>
00703 inline
00704 const T&
00705 set_bkd_iter<T>::subj_()
00706 {
00707 mln_precondition(is_valid());
00708 return s_->operator[](i_);
00709 }
00710
00711 template <typename T>
00712 inline
00713 unsigned
00714 set_bkd_iter<T>::index_() const
00715 {
00716 return i_;
00717 }
00718
00719
00720
00721
00722
00723 template <typename T>
00724 std::ostream& operator<<(std::ostream& ostr,
00725 const mln::util::set<T>& s)
00726 {
00727 ostr << '{';
00728 const unsigned n = s.nelements();
00729 for (unsigned i = 0; i < n; ++i)
00730 {
00731 ostr << s[i];
00732 if (i != n - 1)
00733 ostr << ", ";
00734 }
00735 ostr << '}';
00736 return ostr;
00737 }
00738
00739 template <typename T>
00740 bool operator == (const set<T>& lhs, const set<T>& rhs)
00741 {
00742 const unsigned n = lhs.nelements();
00743 if (rhs.nelements() != n)
00744 return false;
00745 for (unsigned i = 0; i < n; ++i)
00746 if (lhs[i] != rhs[i])
00747 return false;
00748 return true;
00749 }
00750
00751 template <typename T>
00752 bool operator < (const set<T>& lhs, const set<T>& rhs)
00753 {
00754 return lhs.nelements() < rhs.nelements() && lhs <= rhs;
00755 }
00756
00757 template <typename T>
00758 bool operator <= (const set<T>& lhs, const set<T>& rhs)
00759 {
00760 const unsigned
00761 nl = lhs.nelements(),
00762 nr = rhs.nelements();
00763 if (nl > nr)
00764 return false;
00765
00766 for (unsigned l = 0, r = 0; l < nl; ++l, ++r)
00767 {
00768 while (rhs[r] != lhs[l] && r < nr)
00769 ++r;
00770 if (r == nr)
00771 return false;
00772 }
00773 return true;
00774 }
00775
00776 # endif // ! MLN_INCLUDE_ONLY
00777
00778 }
00779
00780 }
00781
00782
00783 #endif // ! MLN_UTIL_SET_HH