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