00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00238 #if !defined(AFX_COMPACTCOLL_H__D6BBCFE2_D17F_45C8_867D_7B2A4137A3F4__INCLUDED_)
00239 #define AFX_COMPACTCOLL_H__D6BBCFE2_D17F_45C8_867D_7B2A4137A3F4__INCLUDED_
00240
00241 #if _MSC_VER > 1000
00242 #pragma once
00243 #endif // _MSC_VER > 1000
00244
00245 #ifdef __BORLANDC__
00246
00247 #pragma warn -8027
00248 #endif
00249
00250 #ifdef _MSC_VER
00251 #if _MSC_VER <= 1200
00252 #define _COMPACT_SET_NO_POLICIES
00253 #endif
00254 #endif
00255
00256 #include "IterAdapter.h"
00257
00258 #include <vector>
00259 #include <deque>
00260 #include <algorithm>
00261 #include <assert.h>
00262 #include <iterator>
00263
00264 template <class T>
00265 class AdaptPol
00266 {
00267 };
00268
00269 template <class VT,class VEC>
00270 class SortedArrayBase
00271 {
00272 typedef SortedArrayBase ThisType;
00273 public:
00274 typedef typename VT::key_type key_type;
00275 typedef typename VT::value_type value_type;
00276 typedef typename VT::allocator_type allocator_type;
00277 typedef typename VT::size_type size_type;
00278 typedef typename VT::key_compare key_compare;
00279 typedef typename VT::value_compare value_compare;
00280
00281 typedef typename VEC::iterator VecIterator;
00282
00283
00284 class Iter;
00285 friend class Iter;
00286
00287
00288 class Iter
00289 {
00290 friend class SortedArrayBase<VT,VEC>;
00291 bool vecAtBegin() const
00292 {
00293 return vit_ == collection_->vec_.begin();
00294 }
00295 bool isDeleted() const
00296 {
00297 return collection_->deleted_[vit_ - collection_->vec_.begin()];
00298 }
00299 void decrementOverDeleted()
00300 {
00301 if(atEnd())
00302 return;
00303 for( ; !vecAtBegin(); --vit_)
00304 {
00305 if(!isDeleted())
00306 return;
00307 }
00308
00309
00310 incrementOverDeleted();
00311 }
00312 void incrementOverDeleted()
00313 {
00314 for( ; !atEnd(); ++vit_)
00315 {
00316 if(!isDeleted())
00317 return;
00318 }
00319 }
00320 bool atEnd() const
00321 {
00322 return vit_ == collection_->vec_.end();
00323 }
00324 public:
00325 Iter(ThisType* coll, VecIterator vit)
00326 :vit_(vit)
00327 ,collection_(coll)
00328 { }
00329 typedef std::bidirectional_iterator_tag iterator_category;
00330 typedef typename VT::value_type value_type;
00331 typedef typename allocator_type::size_type size_type;
00332 typedef ptrdiff_t difference_type;
00333 Iter()
00334 : collection_(0)
00335 { }
00336 void decrement()
00337 {
00338 --vit_;
00339 decrementOverDeleted();
00340 }
00341 void increment()
00342 {
00343 ++vit_;
00344 incrementOverDeleted();
00345 }
00346 value_type& dereference() const
00347 {
00348 assert(!atEnd());
00349 return *vit_;
00350 }
00351 bool equals(const Iter& rhs) const
00352 {
00353 return vit_ == rhs.vit_;
00354 }
00355 private:
00356 VecIterator vit_;
00357 ThisType* collection_;
00358 };
00359 typedef IterAdapter<Iter> iterator;
00360 typedef CIterAdapter<Iter> const_iterator;
00361 SortedArrayBase()
00362 : deletedCount_(0)
00363 , smallVectorThreshold_(200)
00364 , compactionFactor_(0.2)
00365 {
00366 autoSetThreshold();
00367 }
00368 SortedArrayBase(const VT& vt)
00369 : deletedCount_(0)
00370 , smallVectorThreshold_(200)
00371 , compactionFactor_(0.2)
00372 {
00373 autoSetThreshold();
00374 setValueTraits(vt);
00375 }
00376 void setValueTraits(const VT& vt)
00377 {
00378 valueTraits_ = vt;
00379 }
00380 const VT& getValueTraits() const
00381 {
00382 return valueTraits_;
00383 }
00384
00385 void setCompactionFactor(double cf)
00386 {
00387 assert(cf > 0.0);
00388 compactionFactor_ = cf;
00389 }
00390 double getCompactionFactor() const
00391 {
00392 return compactionFactor_;
00393 }
00394
00395 void setSmallVectorThreshold(size_type svt)
00396 {
00397 smallVectorThreshold_ = svt;
00398 }
00399 size_type getSmallVectorThreshold() const
00400 {
00401 return smallVectorThreshold_;
00402 }
00403
00404 const_iterator begin() const
00405 {
00406 ThisType* ncThis = const_cast<ThisType*>(this);
00407 Iter it(ncThis,ncThis->vec_.begin());
00408 it.incrementOverDeleted();
00409 return it;
00410 }
00411 const_iterator end() const
00412 {
00413 ThisType* ncThis = const_cast<ThisType*>(this);
00414 return Iter(ncThis,ncThis->vec_.end());
00415 }
00416 iterator begin()
00417 {
00418 Iter it(this,vec_.begin());
00419 it.incrementOverDeleted();
00420 return it;
00421 }
00422 iterator end()
00423 {
00424 return Iter(this,vec_.end());
00425 }
00426
00427
00428
00429
00430 int tryInsert(const value_type& val, iterator& iter)
00431 {
00432
00433 std::pair<VecIterator,VecIterator> vecRange
00434 = std::equal_range(vec_.begin(),vec_.end(),val,valueTraits_.kc);
00435 if(vecRange.first != vecRange.second)
00436 {
00437
00438 assert(vecRange.first + 1 == vecRange.second);
00439
00440 iter = Iter(this,vecRange.first);
00441
00442 if(deleted_[vecRange.first - vec_.begin()])
00443 {
00444
00445 deleted_[vecRange.first - vec_.begin()] = false;
00446 deletedCount_--;
00447 valueTraits_.assign(*vecRange.first,val);
00448
00449
00450 return 1;
00451 }
00452
00453 return 0;
00454 }
00455 else
00456 {
00457
00458
00459 if(vecRange.first != vec_.end() && deleted_[vecRange.first - vec_.begin()])
00460 {
00461
00462
00463 valueTraits_.assign(*(vecRange.first),val);
00464 iter = Iter(this,vecRange.first);
00465
00466 deleted_[vecRange.first - vec_.begin()] = false;
00467 --deletedCount_;
00468 return 1;
00469 }
00470 else if(vecRange.first != vec_.begin() && deleted_[vecRange.first - vec_.begin() - 1])
00471 {
00472
00473
00474 valueTraits_.assign(*(vecRange.first-1),val);
00475 iter = Iter(this,vecRange.first-1);
00476
00477 deleted_[vecRange.first - vec_.begin() - 1] = false;
00478 --deletedCount_;
00479 return 1;
00480 }
00481 else if(vec_.size() < smallVectorThreshold_ && deletedCount_ == 0)
00482 {
00483
00484
00485 iter = Iter(this,vec_.insert(vecRange.first,val));
00486 deleted_.push_back(false);
00487 return 1;
00488 }
00489 }
00490
00491 return -1;
00492 }
00493 iterator erase(iterator it)
00494 {
00495 assert(!deleted_[it.getImpl_().vit_ - vec_.begin()]);
00496 deleted_[it.getImpl_().vit_ - vec_.begin()] = true;
00497 ++deletedCount_;
00498 it.getImpl_().incrementOverDeleted();
00499 return it;
00500 }
00501 size_type erase(const key_type& val)
00502 {
00503
00504 std::pair<VecIterator,VecIterator> vecRange
00505 = std::equal_range(vec_.begin(),vec_.end(),val,valueTraits_.kc);
00506 if(vecRange.first != vecRange.second)
00507 {
00508
00509 assert(vecRange.first + 1 == vecRange.second);
00510
00511
00512 if(deleted_[vecRange.first - vec_.begin()])
00513 {
00514 return 0;
00515 }
00516 else
00517 {
00518
00519 deleted_[vecRange.first - vec_.begin()] = true;
00520 ++deletedCount_;
00521
00522
00523 return 1;
00524 }
00525 }
00526 else
00527 {
00528
00529 return 0;
00530 }
00531 }
00532 size_type size() const
00533 {
00534 return vec_.size() - deletedCount_;
00535 }
00536 iterator find(const key_type& key)
00537 {
00538 VecIterator found = std::lower_bound(vec_.begin(),vec_.end(),key,valueTraits_.kc);
00539 if(found == vec_.end())
00540 return end();
00541 if(deleted_[found - vec_.begin()])
00542 return end();
00543 if(valueTraits_.kc(key,valueTraits_.extractKey(*found)))
00544 return end();
00545 return iterator(Iter(this,found));
00546 }
00547 iterator upper_bound(const key_type& key)
00548 {
00549 VecIterator found = std::upper_bound(vec_.begin(),vec_.end(),key,valueTraits_.kc);
00550 Iter it(this,found);
00551 it.incrementOverDeleted();
00552 return iterator(it);
00553 }
00554 iterator lower_bound(const key_type& key)
00555 {
00556 VecIterator found = std::lower_bound(vec_.begin(),vec_.end(),key,valueTraits_.kc);
00557 Iter it(this,found);
00558 it.incrementOverDeleted();
00559 return iterator(it);
00560 }
00561 void compact(typename VT::DynSetType& coll)
00562 {
00563 size_type newSz = size() + coll.size();
00564
00565 VEC newVec(vec_.get_allocator());
00566
00567 newVec.reserve(newSz);
00568
00569
00570 std::set_union(coll.begin(),coll.end(),begin(),end(),std::back_inserter(newVec),valueTraits_.kc);
00571
00572 coll.clear();
00573
00574 std::vector<bool> newDeleted(newSz,false);
00575
00576 std::swap(vec_,newVec);
00577 std::swap(deleted_,newDeleted);
00578 deletedCount_ = 0;
00579 autoSetThreshold();
00580 }
00581 bool autoCompact(typename VT::DynSetType& coll)
00582 {
00583 if(coll.size() >= threshold_ || deletedCount_ >= threshold_)
00584 {
00585 compact(coll);
00586 return true;
00587 }
00588 return false;
00589 }
00590 void swap(SortedArrayBase& rhs)
00591 {
00592 vec_.swap(rhs.vec_);
00593 valueTraits_.swap(rhs.valueTraits_);
00594 deleted_.swap(rhs.deleted_);
00595 std::swap(deletedCount_,rhs.deletedCount_);
00596 std::swap(smallVectorThreshold_,rhs.smallVectorThreshold_);
00597 std::swap(threshold_,rhs.threshold_);
00598 std::swap(compactionFactor_,rhs.compactionFactor_);
00599 }
00600 void clear()
00601 {
00602 vec_.clear();
00603 deleted_.clear();
00604 deletedCount_ = 0;
00605 autoSetThreshold();
00606 }
00607 protected:
00608 void autoSetThreshold()
00609 {
00610 if(size() < smallVectorThreshold_)
00611 {
00612 threshold_ = (size_type) (smallVectorThreshold_ * compactionFactor_);
00613 }
00614 else
00615 {
00616 threshold_ = (size_type) (size() * compactionFactor_);
00617 }
00618 }
00619
00620 VEC vec_;
00621 VT valueTraits_;
00622 std::vector<bool> deleted_;
00623 size_type deletedCount_;
00624 size_type smallVectorThreshold_;
00625 size_type threshold_;
00626 double compactionFactor_;
00627 };
00628
00629
00630 class MinimizeSpacePolicy
00631 {
00632 };
00633
00634
00635 class MaximizeSpeedPolicy
00636 {
00637 };
00638
00639 #ifndef _COMPACT_SET_NO_POLICIES
00640
00641 template <>
00642 class AdaptPol<MaximizeSpeedPolicy>
00643 {
00644 public:
00645 template <class VT>
00646 class Impl
00647 : public SortedArrayBase<VT,std::vector<typename VT::AssignableValueType,typename VT::AssignableAllocatorType> >
00648 {
00649 typedef SortedArrayBase<VT,std::vector<typename VT::AssignableValueType,typename VT::AssignableAllocatorType> > SAType;
00650 public:
00651 Impl(const VT& vt)
00652 {
00653 setValueTraits(vt);
00654 }
00655 };
00656 };
00657
00658 template <>
00659 class AdaptPol<MinimizeSpacePolicy>
00660 {
00661 public:
00662 template <class VT>
00663 class Impl
00664 : public SortedArrayBase<VT,std::deque<typename VT::AssignableValueType,typename VT::AssignableAllocatorType> >
00665 {
00666 typedef std::deque<typename VT::AssignableValueType,typename VT::AssignableAllocatorType> VecImplType;
00667 typedef SortedArrayBase<VT,VecImplType> SAType;
00668 public:
00669 typedef typename SAType::size_type size_type;
00670 typedef typename SAType::value_type value_type;
00671 typedef typename SAType::allocator_type allocator_type;
00672 Impl(const VT& vt)
00673 {
00674 setValueTraits(vt);
00675 }
00676 void compact(typename VT::DynSetType& coll)
00677 {
00678 size_type newSz = size() + coll.size();
00679
00680 VecImplType newVec(vec_.get_allocator());
00681
00682
00683 typename VT::DynSetType::iterator collIt = coll.begin();
00684 typename VecImplType::iterator deqIt = vec_.begin();
00685 size_type deqOffset = 0;
00686 while(collIt != coll.end() && deqIt != vec_.end())
00687 {
00688 if(valueTraits_.kc(*collIt, *deqIt))
00689 {
00690 newVec.push_back(*collIt);
00691 coll.erase(collIt);
00692 collIt = coll.begin();
00693 }
00694 else
00695 {
00696 assert(valueTraits_.kc(*deqIt, *collIt));
00697 if(!deleted_[deqOffset])
00698 {
00699 newVec.push_back(*deqIt);
00700 }
00701 vec_.pop_front();
00702 deqIt = vec_.begin();
00703 ++deqOffset;
00704 }
00705 }
00706 while(collIt != coll.end())
00707 {
00708 newVec.push_back(*collIt);
00709 coll.erase(collIt);
00710 collIt = coll.begin();
00711 }
00712 while(deqIt != vec_.end())
00713 {
00714 if(!deleted_[deqOffset])
00715 {
00716 newVec.push_back(*deqIt);
00717 }
00718 vec_.pop_front();
00719 deqIt = vec_.begin();
00720 ++deqOffset;
00721 }
00722 assert(newSz == newVec.size());
00723
00724 std::vector<bool> newDeleted(newSz,false);
00725
00726 std::swap(vec_,newVec);
00727 std::swap(deleted_,newDeleted);
00728 deletedCount_ = 0;
00729 autoSetThreshold();
00730 }
00731 bool autoCompact(typename VT::DynSetType& coll)
00732 {
00733 if(coll.size() >= threshold_ || deletedCount_ >= threshold_)
00734 {
00735 compact(coll);
00736 return true;
00737 }
00738 return false;
00739 }
00740 };
00741 };
00742 #endif //#ifndef _COMPACT_SET_NO_POLICIES
00743
00744 template<class CT>
00745 class CompactColl
00746 {
00747
00748 public:
00749 typedef typename CT::key_type key_type;
00750 typedef typename CT::value_type value_type;
00751 typedef typename CT::key_compare key_compare;
00752 typedef typename CT::value_compare value_compare;
00753 typedef typename CT::allocator_type allocator_type;
00754 typedef typename allocator_type::size_type size_type;
00755 typedef typename allocator_type::difference_type difference_type;
00756
00757 typedef typename CT::DynSetType DynSetType;
00758 #ifdef _COMPACT_SET_NO_POLICIES
00759
00760 typedef typename SortedArrayBase<CT,std::vector<typename CT::AssignableValueType,std::allocator<CT::AssignableValueType> > > CompactPolicyType;
00761 #else
00762 typedef typename AdaptPol<typename CT::PolicyTagType>::template Impl<CT> CompactPolicyType;
00763 #endif
00764 typedef typename CompactPolicyType::iterator CPIter;
00765 typedef typename DynSetType::iterator DSIter;
00766 class Iter;
00767 friend class Iter;
00768 class Iter
00769 {
00770 friend class CompactColl<CT>;
00771 void validate()
00772 {
00773 if(archiveIsCurr_)
00774 {
00775 assert(!archiveAtEnd());
00776 iit_ = collection_->dynamic_.upper_bound(collection_->archive_.getValueTraits().extractKey(*ait_));
00777 }
00778 else
00779 {
00780 assert(!dynamicAtEnd());
00781 ait_ = collection_->archive_.upper_bound(collection_->archive_.getValueTraits().extractKey(*iit_));
00782 }
00783 isValid_ = true;
00784 }
00785 bool archiveAtEnd() const
00786 {
00787 return ait_ == collection_->archive_.end();
00788 }
00789 bool dynamicAtEnd() const
00790 {
00791 return iit_ == collection_->dynamic_.end();
00792 }
00793 bool archiveAtBegin() const
00794 {
00795 return ait_ == collection_->archive_.begin();
00796 }
00797 bool dynamicAtBegin() const
00798 {
00799 return iit_ == collection_->dynamic_.begin();
00800 }
00801 bool atEnd() const
00802 {
00803 return archiveAtEnd() && dynamicAtEnd();
00804 }
00805 void assertValid() const
00806 {
00807 #ifndef NDEBUG
00808 if(atEnd())
00809 return;
00810 assert(isValid_);
00811 if(archiveIsCurr_)
00812 {
00813 assert(!archiveAtEnd());
00814 if(!dynamicAtEnd())
00815 {
00816 assert(collection_->archive_.getValueTraits().kc(
00817 collection_->archive_.getValueTraits().extractKey(*ait_),
00818 collection_->archive_.getValueTraits().extractKey(*iit_) ));
00819 if(!dynamicAtBegin())
00820 {
00821 typename DynSetType::iterator tmpIt = iit_;
00822 --tmpIt;
00823 assert(collection_->archive_.getValueTraits().kc(
00824 collection_->archive_.getValueTraits().extractKey(*tmpIt),
00825 collection_->archive_.getValueTraits().extractKey(*ait_) ));
00826 }
00827 }
00828 }
00829 else
00830 {
00831 assert(!dynamicAtEnd());
00832 if(!archiveAtEnd())
00833 {
00834 assert(collection_->archive_.getValueTraits().kc(
00835 collection_->archive_.getValueTraits().extractKey(*iit_),
00836 collection_->archive_.getValueTraits().extractKey(*ait_) ));
00837 if(!archiveAtBegin())
00838 {
00839 CPIter tmpIt = ait_;
00840 --tmpIt;
00841 assert(collection_->archive_.getValueTraits().kc(
00842 collection_->archive_.getValueTraits().extractKey(*tmpIt),
00843 collection_->archive_.getValueTraits().extractKey(*iit_) ));
00844 }
00845 }
00846 }
00847 #endif
00848 }
00849 public:
00850 typedef std::bidirectional_iterator_tag iterator_category;
00851 typedef typename CT::value_type value_type;
00852 typedef typename CT::size_type size_type;
00853 typedef ptrdiff_t difference_type;
00854
00855 void increment()
00856 {
00857 assert(!atEnd());
00858 if(!isValid_) validate();
00859 assertValid();
00860 if(archiveIsCurr_)
00861 {
00862 ++ait_;
00863 }
00864 else
00865 {
00866 ++iit_;
00867 }
00868 archiveIsCurr_=(dynamicAtEnd()
00869 || (!archiveAtEnd() && collection_->archive_.getValueTraits().kc(
00870 collection_->archive_.getValueTraits().extractKey(*ait_),
00871 collection_->archive_.getValueTraits().extractKey(*iit_) )));
00872 assertValid();
00873 }
00874 void decrement()
00875 {
00876 if(!isValid_) validate();
00877 assertValid();
00878 if(archiveAtBegin())
00879 {
00880 assert(!dynamicAtBegin());
00881 --iit_;
00882 archiveIsCurr_ = false;
00883 return;
00884 }
00885 if(dynamicAtBegin())
00886 {
00887 --ait_;
00888 archiveIsCurr_ = true;
00889 return;
00890 }
00891 --ait_;
00892 --iit_;
00893 if(collection_->archive_.getValueTraits().kc(
00894 collection_->archive_.getValueTraits().extractKey(*ait_),
00895 collection_->archive_.getValueTraits().extractKey(*iit_) ))
00896 {
00897 archiveIsCurr_ = false;
00898 ++ait_;
00899 }
00900 else
00901 {
00902 archiveIsCurr_ = true;
00903 ++iit_;
00904 }
00905 assertValid();
00906 }
00907 static Iter Begin(const CompactColl* collection_)
00908 {
00909 Iter ret;
00910 CompactColl* ncColl = const_cast<CompactColl*>(collection_);
00911 ret.collection_ = ncColl;
00912 ret.ait_ = ncColl->archive_.begin();
00913 ret.iit_ = ncColl->dynamic_.begin();
00914 ret.archiveIsCurr_=(
00915 ret.dynamicAtEnd() ||
00916 (!ret.archiveAtEnd() &&
00917 collection_->archive_.getValueTraits().kc(
00918 collection_->archive_.getValueTraits().extractKey(*ret.ait_),
00919 collection_->archive_.getValueTraits().extractKey(*ret.iit_) )));
00920 ret.isValid_ = true;
00921 return ret;
00922 }
00923 static Iter End(const CompactColl* collection_)
00924 {
00925 Iter ret;
00926 CompactColl* ncColl = const_cast<CompactColl*>(collection_);
00927 ret.collection_ = ncColl;
00928 ret.ait_ = ncColl->archive_.end();
00929 ret.iit_ = ncColl->dynamic_.end();
00930
00931 ret.archiveIsCurr_ = false;
00932 ret.isValid_ = true;
00933 return ret;
00934 }
00935 Iter()
00936 : collection_(0), archiveIsCurr_(false),isValid_(false)
00937 {
00938 }
00939 Iter(CPIter ait,typename DynSetType::iterator iit,
00940 CompactColl* collection,bool archiveIsCurr)
00941 :ait_(ait)
00942 ,iit_(iit)
00943 ,collection_(collection)
00944 ,archiveIsCurr_(archiveIsCurr)
00945 ,isValid_(true)
00946 {
00947 }
00948 Iter(CPIter ait,typename DynSetType::iterator iit,
00949 CompactColl* collection)
00950 :ait_(ait)
00951 ,iit_(iit)
00952 ,collection_(collection)
00953 ,isValid_(true)
00954 {
00955
00956 archiveIsCurr_=(
00957 dynamicAtEnd() ||
00958 (!archiveAtEnd() &&
00959 collection_->archive_.getValueTraits().kc(
00960 collection_->archive_.getValueTraits().extractKey(*ait_),
00961 collection_->archive_.getValueTraits().extractKey(*iit_) )));
00962 }
00963 Iter(CPIter ait,CompactColl* collection)
00964 :ait_(ait)
00965 ,collection_(collection)
00966 ,archiveIsCurr_(true)
00967 ,isValid_(false)
00968 {
00969 }
00970 Iter(typename DynSetType::iterator iit,CompactColl* collection)
00971 :iit_(iit)
00972 ,collection_(collection)
00973 ,archiveIsCurr_(false)
00974 ,isValid_(false)
00975 {
00976 }
00977
00978 value_type& dereference() const
00979 {
00980
00981 if(archiveIsCurr_)
00982 {
00983 assert(!archiveAtEnd());
00984 return *ait_;
00985 }
00986 else
00987 {
00988 assert(!dynamicAtEnd());
00989
00990
00991 return (value_type&)(*iit_);
00992 }
00993 }
00994 bool equals(const Iter& rhs) const
00995 {
00996 if(atEnd())
00997 {
00998 return ait_ == rhs.ait_ && iit_ == rhs.iit_;
00999 }
01000 return (archiveIsCurr_ && rhs.archiveIsCurr_ && ait_ == rhs.ait_)
01001 || (!archiveIsCurr_ && !rhs.archiveIsCurr_ && iit_ == rhs.iit_);
01002 }
01003 private:
01004 CPIter ait_;
01005 typename DynSetType::iterator iit_;
01006 CompactColl* collection_;
01007 bool archiveIsCurr_;
01008 bool isValid_;
01009 };
01010
01011
01012 typedef IterAdapter<Iter> iterator;
01013 typedef CIterAdapter<Iter> const_iterator;
01014 #ifdef _MSC_VER
01015 typedef std::reverse_bidirectional_iterator<iterator,value_type> reverse_iterator;
01016 typedef std::reverse_bidirectional_iterator<const_iterator,value_type> const_reverse_iterator;
01017 #else
01018 typedef std::reverse_iterator<iterator> reverse_iterator;
01019 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
01020 #endif
01021 public:
01022
01023
01024
01025
01026 const CompactPolicyType& getCompactPolicy() const
01027 {
01028
01029 return archive_;
01030 }
01031 CompactPolicyType& getCompactPolicy()
01032 {
01033
01034 return archive_;
01035 }
01036 void compact()
01037 {
01038 archive_.compact(dynamic_);
01039 }
01040
01041 explicit CompactColl(const CT& ct)
01042 : archive_(ct)
01043 , dynamic_(ct.key_comp(),ct.get_allocator())
01044 {
01045 }
01046
01047
01048 const_iterator begin() const
01049 {
01050 return Iter::Begin(this);
01051 }
01052 const_iterator end() const
01053 {
01054 return Iter::End(this);
01055 }
01056 iterator begin()
01057 {
01058 return Iter::Begin(this);
01059 }
01060 iterator end()
01061 {
01062 return Iter::End(this);
01063 }
01064 const_reverse_iterator rbegin() const
01065 {
01066 return const_reverse_iterator(end());
01067 }
01068 const_reverse_iterator rend() const
01069 {
01070 return const_reverse_iterator(begin());
01071 }
01072 reverse_iterator rbegin()
01073 {
01074 return reverse_iterator(end());
01075 }
01076 reverse_iterator rend()
01077 {
01078 return reverse_iterator(begin());
01079 }
01080 size_type size() const
01081 {
01082 return archive_.size() + dynamic_.size();
01083 }
01084 bool empty() const
01085 {
01086 return size() == 0;
01087 }
01088 allocator_type get_allocator() const
01089 {
01090 return archive_.get_allocator();
01091 }
01092 std::pair<iterator, bool> insert(const value_type& val)
01093 {
01094 CPIter cpit;
01095 bool inserted = false;
01096 iterator returnIt;
01097 DSIter dsit = dynamic_.find(archive_.getValueTraits().extractKey(val));
01098 if(dsit != dynamic_.end())
01099 {
01100 returnIt = iterator(Iter(dsit,this));
01101 }
01102 else
01103 {
01104 switch(archive_.tryInsert(val,cpit))
01105 {
01106 case -1:
01107 {
01108 std::pair<DSIter,bool> ret =
01109 dynamic_.insert(val);
01110 inserted = ret.second;
01111 returnIt = iterator(Iter(ret.first,this));
01112 }
01113 break;
01114 case 1:
01115 inserted = true;
01116
01117 case 0:
01118 returnIt = iterator(Iter(cpit,this));
01119 break;
01120 }
01121 }
01122 if(archive_.autoCompact(dynamic_))
01123 {
01124 return std::make_pair(find(archive_.getValueTraits().extractKey(val)),inserted);
01125 }
01126 return std::make_pair(returnIt,inserted);
01127 }
01128 iterator insert(iterator it, const value_type& val)
01129 {
01130
01131 return insert(val).first;
01132 }
01133 template <class IT>
01134 void insert(IT b, IT e)
01135 {
01136 for(; b != e; ++b)
01137 {
01138 insert(*b);
01139 }
01140 }
01141 iterator erase(iterator it)
01142 {
01143 iterator ret = it;
01144 ++ret;
01145 if(it.getImpl_().archiveIsCurr_)
01146 {
01147 archive_.erase(it.getImpl_().ait_);
01148 }
01149 else
01150 {
01151 dynamic_.erase(it.getImpl_().iit_);
01152 }
01153
01154
01155 if(ret.getImpl_().atEnd())
01156 {
01157 archive_.autoCompact(dynamic_);
01158 return end();
01159 }
01160 else
01161 {
01162 value_type val(*ret);
01163 if(archive_.autoCompact(dynamic_))
01164 {
01165 return find(archive_.getValueTraits().extractKey(val));
01166 }
01167 return ret;
01168 }
01169 }
01170 iterator erase(iterator b, iterator e)
01171 {
01172 while(b != e)
01173 {
01174 b = erase(b);
01175 }
01176 return b;
01177 }
01178 size_type erase(const key_type& key)
01179 {
01180 size_type count=0;
01181 if(archive_.erase(key))
01182 {
01183 count = 1;
01184 }
01185 else
01186 {
01187 count = dynamic_.erase(key);
01188 }
01189 archive_.autoCompact(dynamic_);
01190 return count;
01191 }
01192 iterator find(const key_type& key)
01193 {
01194 typename CompactPolicyType::iterator aFound =
01195 archive_.find(key);
01196 if(aFound != archive_.end())
01197 {
01198 return iterator(Iter(aFound,this));
01199 }
01200 else
01201 {
01202 typename DynSetType::iterator iFound =
01203 dynamic_.find(key);
01204 if(iFound != dynamic_.end())
01205 {
01206 return iterator(Iter(iFound,this));
01207 }
01208 }
01209 return end();
01210 }
01211 const_iterator find(const key_type& key) const
01212 {
01213
01214
01215 return const_cast<CompactColl*>(this)->find(key);
01216 }
01217 size_type count(const key_type& key) const
01218 {
01219
01220 return (find(key) == end() ? 0 : 1);
01221 }
01222 iterator lower_bound(const key_type& key)
01223 {
01224 return iterator(
01225 Iter(
01226 archive_.lower_bound(key),
01227 dynamic_.lower_bound(key),
01228 this));
01229 }
01230 const_iterator lower_bound(const key_type& key) const
01231 {
01232
01233
01234 return const_cast<CompactColl*>(this)->lower_bound(key);
01235 }
01236 iterator upper_bound(const key_type& key)
01237 {
01238 return iterator(
01239 Iter(
01240 archive_.upper_bound(key),
01241 dynamic_.upper_bound(key),
01242 this));
01243 }
01244 const_iterator upper_bound(const key_type& key) const
01245 {
01246
01247
01248 return const_cast<CompactColl*>(this)->upper_bound(key);
01249 }
01250 std::pair<iterator, iterator>
01251 equal_range(const key_type& key)
01252 {
01253
01254
01255
01256
01257
01258 iterator lb(lower_bound(key));
01259 if(lb == end())
01260 {
01261 return std::make_pair(lb,lb);
01262 }
01263 if(archive_.getValueTraits().kc(
01264 key,
01265 archive_.getValueTraits().extractKey(*lb) ))
01266 {
01267
01268
01269 return std::make_pair(lb,lb);
01270 }
01271 else
01272 {
01273
01274
01275 assert(!archive_.getValueTraits().kc(
01276 archive_.getValueTraits().extractKey(*lb),key ));
01277 iterator ub = lb;
01278 ++ub;
01279 return std::make_pair(lb,ub);
01280 }
01281 }
01282 std::pair<const_iterator, const_iterator>
01283 equal_range(const key_type& key) const
01284 {
01285
01286
01287 std::pair<iterator,iterator> ncER =
01288 const_cast<CompactColl*>(this)->equal_range(key);
01289 return std::pair<const_iterator,const_iterator>(ncER.first,ncER.second);
01290 }
01291 void clear()
01292 {
01293 archive_.clear();
01294 dynamic_.clear();
01295 }
01296 void swap(CompactColl& rhs)
01297 {
01298 archive_.swap(rhs.archive_);
01299 dynamic_.swap(rhs.dynamic_);
01300 }
01301
01302
01303
01304
01305
01306
01307
01308
01309
01310 private:
01311 CompactPolicyType archive_;
01312 DynSetType dynamic_;
01313 };
01314
01315
01316 #endif // !defined(AFX_COMPACTCOLL_H__D6BBCFE2_D17F_45C8_867D_7B2A4137A3F4__INCLUDED_)
01317 s than the value returned by lower_bound(),
01318
01319 return std::make_pair(lb,lb);
01320 }
01321 else
01322 {
01323
01324
01325 assert(!archive_.getValueTraits().kc(
01326 archive_.getValueTraits().extractKey(*lb),key ));
01327 iterator ub = lb;
01328 ++ub;
01329 return std::make_pair(lb,ub);
01330 }
01331 }
01332 std::pair<const_iterator, const_iterator>
01333 equal_range(const key_type& key) const
01334 {
01335
01336
01337 std::pair<iterator,iterator> ncER =
01338 const_cast<CompactColl*>(this)->equal_range(key);
01339 return std::pair<const_iterator,const_iterator>(ncER.first,ncER.second);
01340 }
01341 void clear()
01342 {
01343 archive_.clear();
01344 dynamic_.clear();
01345 }
01346 void swap(CompactColl& rhs)
01347 {
01348 archive_.swap(rhs.archive_);
01349 dynamic_.swap(rhs.dynamic_);
01350 }
01351
01352
01353
01354
01355
01356
01357
01358
01359
01360 private:
01361 CompactPolicyType archive_;
01362 DynSetType dynamic_;
01363 };
01364
01365
01366 #endif // !defined(AFX_COMPACTCOLL_H__D6BBCFE2_D17F_45C8_867D_7B2A4137A3F4__INCLUDED_)