Milena (Olena)
User documentation 2.0a Id
|
00001 // Copyright (C) 2007, 2008, 2009 EPITA Research and Development 00002 // Laboratory (LRDE) 00003 // 00004 // This file is part of Olena. 00005 // 00006 // Olena is free software: you can redistribute it and/or modify it under 00007 // the terms of the GNU General Public License as published by the Free 00008 // Software Foundation, version 2 of the License. 00009 // 00010 // Olena is distributed in the hope that it will be useful, 00011 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00012 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00013 // General Public License for more details. 00014 // 00015 // You should have received a copy of the GNU General Public License 00016 // along with Olena. If not, see <http://www.gnu.org/licenses/>. 00017 // 00018 // As a special exception, you may use this file as part of a free 00019 // software project without restriction. Specifically, if other files 00020 // instantiate templates or use macros or inline functions from this 00021 // file, or you compile this file and link it with other files to produce 00022 // an executable, this file does not by itself cause the resulting 00023 // executable to be covered by the GNU General Public License. This 00024 // exception does not however invalidate any other reasons why the 00025 // executable file might be covered by the GNU General Public License. 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 // Forward declarations. 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 // Used in method has(elt) when v_ holds data. 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 // set_fwd_iter<T> 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 // As a Proxy. 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 // set_bkd_iter<T> 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 // As a Proxy. 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 // util::set<T> 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 // No-op. 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 // util::set_fwd_iter<T> 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 // util::set_bkd_iter<T> 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 // Operators. 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 // Every element of lhs can be found in rhs. 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; // lhs[l] has not been found in rhs. 00772 } 00773 return true; 00774 } 00775 00776 # endif // ! MLN_INCLUDE_ONLY 00777 00778 } // end of namespace mln::util 00779 00780 } // end of namespace mln 00781 00782 00783 #endif // ! MLN_UTIL_SET_HH