Main Page   Class Hierarchy   File List  

CompactColl.h

00001 /*
00002         Copyright (c) 2003 Michael Carrato. All rights reserved.        
00003 
00004         Permission to use, modify, copy, and distribute this software 
00005         and its documentation is hereby granted without fee, 
00006         provided that the above copyright notice appears in all copies.
00007         This software is provided "as is" without express or implied 
00008     warranty.
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 //disable inline functions warnings
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     //declare the iterators.
00284     class Iter;
00285     friend class Iter;
00286     //define const_iterator class, which skips over deleted items during 
00287     //traversal
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             //we're at the beginning, and it still could be on an invalid iterator, 
00309                         //so ensure it's valid by incrementing over deleted.
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     //tryInsert(): attempt to insert an element. If successful, return 0 if the element 
00427     //already existed, 1 if it is a new element. Store the iterator for the inserted
00428     //element in the reference parameter iter
00429     //If the element cannot be inserted, return -1 (iter is unchanged)
00430     int tryInsert(const value_type& val, iterator& iter)
00431     {
00432         //locate the position where this value would be inserted
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             //assert that the count is one, and only one
00438             assert(vecRange.first + 1 == vecRange.second);
00439             //vecRange.first points to the value.
00440             iter = Iter(this,vecRange.first);
00441             //If it is deleted, un-delete it.
00442             if(deleted_[vecRange.first - vec_.begin()])
00443             {
00444                 //unset the deleted flag and adjust count
00445                 deleted_[vecRange.first - vec_.begin()] = false;
00446                 deletedCount_--;
00447                 valueTraits_.assign(*vecRange.first,val);
00448                 //element was previously deleted, therefore it didn't technically "exist",
00449                 //so return 1
00450                 return 1;
00451             }
00452             //element was pre-existing
00453             return 0;
00454         }
00455         else
00456         {
00457             //The value was not found. However, IF there is a gap in the collection
00458             //(i.e. a deleted value), we can re-use the slot
00459             if(vecRange.first != vec_.end() && deleted_[vecRange.first - vec_.begin()])
00460             {
00461                 //assign to the value
00462                 //valueTraits_.assign(*vecRange.first,val);
00463                 valueTraits_.assign(*(vecRange.first),val);
00464                 iter = Iter(this,vecRange.first);
00465                 //unset the deleted flag and adjust count
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                 //assign to the value
00473                 //valueTraits_.assign(*(vecRange.first-1) ,val);
00474                 valueTraits_.assign(*(vecRange.first-1),val);
00475                 iter = Iter(this,vecRange.first-1);
00476                 //unset the deleted flag and adjust count
00477                 deleted_[vecRange.first - vec_.begin() - 1] = false;
00478                 --deletedCount_;
00479                 return 1;
00480             }
00481             else if(vec_.size() < smallVectorThreshold_ && deletedCount_ == 0)
00482             {
00483                 //small vector optimization
00484                 //if the vector is very small, just take the hit and do the insert directly
00485                 iter = Iter(this,vec_.insert(vecRange.first,val));
00486                 deleted_.push_back(false);
00487                 return 1;
00488             }
00489         }
00490         //if we got this far, it can't be inserted
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         //locate the value
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             //assert that the count is one, and only one
00509             assert(vecRange.first + 1 == vecRange.second);
00510             //vecRange.first points to the value.
00511             //If it is deleted, return 0
00512             if(deleted_[vecRange.first - vec_.begin()])
00513             {
00514                 return 0;
00515             }
00516             else
00517             {
00518                 //set the deleted flag and adjust count
00519                 deleted_[vecRange.first - vec_.begin()] = true;
00520                 ++deletedCount_;
00521                 //element was previously deleted, therefore it didn't technically "exist",
00522                 //so return 1
00523                 return 1;
00524             }
00525         }
00526         else
00527         {
00528             //element does not exist
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         //declare a new vector to contain the expanded collection
00565         VEC newVec(vec_.get_allocator());
00566         //reserve enough space
00567         newVec.reserve(newSz);
00568         //merge the two sorted collections. begin() and end() are used, which
00569         //will automatically skip over deleted elements.
00570         std::set_union(coll.begin(),coll.end(),begin(),end(),std::back_inserter(newVec),valueTraits_.kc);
00571         //clear the source collection
00572         coll.clear();
00573         //declare a new deleted flag vector
00574         std::vector<bool> newDeleted(newSz,false);
00575         //swap the old with the new
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 //simple tag class for Policy specification
00630 class MinimizeSpacePolicy
00631 {
00632 };
00633 
00634 //simple tag class for Policy specification
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         //declare a new deque to contain the expanded collection
00680         VecImplType newVec(vec_.get_allocator());
00681         //merge the two sorted collections. begin() and end() are used, which
00682         //will automatically skip over deleted elements.
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         //declare a new deleted flag vector
00724         std::vector<bool> newDeleted(newSz,false);
00725         //swap the old with the new
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     //    typedef CompactColl CollType;
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         //TODO the allocator below is wrong! But is there any way to fix it?
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             //archiveIsCurr_ is irrelevant for end(), but initialize it to false anyway
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                         //automatically set the archiveIsCurr_ member.
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             //                  assertValid();
00981             if(archiveIsCurr_)
00982             {
00983                 assert(!archiveAtEnd());
00984                 return *ait_;
00985             }
00986             else
00987             {
00988                 assert(!dynamicAtEnd());
00989                 //for some reason, G++ 2.95 needs a cast
00990 //                return reinterpret_cast<value_type&>(*iit_);
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     //    typedef ArchiveMapType::allocator_type::rebind<value_type>::other::const_reference reference;
01023     //    typedef ArchiveMapType::allocator_type::rebind<value_type>::other::const_reference const_reference;
01024     //    typedef typename ArchiveMapType::reference reference;
01025     //    typedef typename ArchiveMapType::const_reference const_reference;
01026     const CompactPolicyType& getCompactPolicy() const
01027     {
01028         //policy is actually just the archive set...
01029         return archive_;
01030     }
01031     CompactPolicyType& getCompactPolicy()
01032     {
01033         //policy is actually just the archive set...
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     //CompactColl(const CompactColl& x);
01047     //template constructor from iterator pair missing due to visual studio limitations
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                 //fall through
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                 //hint not used in this implementation
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                 //Need to be able to re-initialize the iterator if a compaction occurs,
01154                 //so hold onto the value of the return iterator
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                 //this does not violate const-ness in any way, and
01214                 //is only done to avoid duplication of the non-const algorithm.
01215                 return const_cast<CompactColl*>(this)->find(key);
01216     }
01217     size_type count(const key_type& key) const
01218     {
01219                 //this will always return 0 or 1 for collections with unique keys
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                 //this does not violate const-ness in any way, and
01233                 //is only done to avoid duplication of the non-const algorithm.
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                 //this does not violate const-ness in any way, and
01247                 //is only done to avoid duplication of the non-const algorithm.
01248                 return const_cast<CompactColl*>(this)->upper_bound(key);
01249         }
01250     std::pair<iterator, iterator>
01251     equal_range(const key_type& key)
01252     {
01253                 //equal_range returns the equivalent of 
01254                 //(lower_bound(key), upper_bound(key))
01255                 //however, because this collection has unique
01256                 //keys, we can optimize so that only 
01257                 //lower_bound() is called.
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                         //if key is less than the value returned by lower_bound(),
01268                         //then the lower bound is also the upper bound.
01269                         return std::make_pair(lb,lb);
01270                 }
01271                 else
01272                 {
01273                         //the key must be equal to the lower bound, so 
01274                         //the upper bound is one past the lower bound.
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                 //this does not violate const-ness in any way, and
01286                 //is only done to avoid duplication of the non-const algorithm.
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 /*    key_compare key_comp() const
01302     {
01303     return pred_;
01304     }
01305     value_compare value_comp() const
01306     {
01307     return pred_;
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                         //then the lower bound is also the upper bound.
01319                         return std::make_pair(lb,lb);
01320                 }
01321                 else
01322                 {
01323                         //the key must be equal to the lower bound, so 
01324                         //the upper bound is one past the lower bound.
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                 //this does not violate const-ness in any way, and
01336                 //is only done to avoid duplication of the non-const algorithm.
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 /*    key_compare key_comp() const
01352     {
01353     return pred_;
01354     }
01355     value_compare value_comp() const
01356     {
01357     return pred_;
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_)

Generated on Wed May 28 12:44:07 2003 for Compact Associative Collections by doxygen1.2.18