---

CompactColl.h

/*
        Copyright (c) 2003 Michael Carrato. All rights reserved.        

        Permission to use, modify, copy, and distribute this software 
        and its documentation is hereby granted without fee, 
        provided that the above copyright notice appears in all copies.
        This software is provided "as is" without express or implied 
    warranty.
*/

#if !defined(AFX_COMPACTCOLL_H__D6BBCFE2_D17F_45C8_867D_7B2A4137A3F4__INCLUDED_)
#define AFX_COMPACTCOLL_H__D6BBCFE2_D17F_45C8_867D_7B2A4137A3F4__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

#ifdef __BORLANDC__
//disable inline functions warnings
#pragma warn -8027
#endif

#ifdef _MSC_VER
#if _MSC_VER <= 1200
#define _COMPACT_SET_NO_POLICIES
#endif 
#endif

#include "IterAdapter.h"

#include <vector>
#include <deque>
#include <algorithm>
#include <assert.h>
#include <iterator>

template <class T>
class AdaptPol
{
};

template <class VT,class VEC>
class SortedArrayBase
{
    typedef SortedArrayBase ThisType;
public:
    typedef typename VT::key_type key_type;
    typedef typename VT::value_type value_type;
    typedef typename VT::allocator_type allocator_type;
    typedef typename VT::size_type size_type;
    typedef typename VT::key_compare key_compare;
    typedef typename VT::value_compare value_compare;
    
    typedef typename VEC::iterator VecIterator;
    
    //declare the iterators.
    class Iter;
    friend class Iter;
    //define const_iterator class, which skips over deleted items during 
    //traversal
    class Iter
    {
                friend class SortedArrayBase<VT,VEC>;
                bool vecAtBegin() const
                {
                        return vit_ == collection_->vec_.begin();
                }
                bool isDeleted() const
                {
                        return collection_->deleted_[vit_ - collection_->vec_.begin()];
                }
        void decrementOverDeleted()
        {
            if(atEnd())
                return;
            for( ; !vecAtBegin(); --vit_)
            {
                if(!isDeleted())
                    return;
            }
            //we're at the beginning, and it still could be on an invalid iterator, 
                        //so ensure it's valid by incrementing over deleted.
            incrementOverDeleted();
        }
        void incrementOverDeleted()
        {
            for( ; !atEnd(); ++vit_)
            {
                if(!isDeleted())
                    return;
            }
        }
        bool atEnd() const
        {
            return vit_ == collection_->vec_.end();
        }
    public:
        Iter(ThisType* coll, VecIterator vit)
            :vit_(vit)
            ,collection_(coll)
        { }
        typedef std::bidirectional_iterator_tag iterator_category;
        typedef typename VT::value_type value_type;
        typedef typename allocator_type::size_type size_type;
        typedef ptrdiff_t difference_type;
        Iter()
            : collection_(0)
        { }
        void decrement()
        {
            --vit_;
            decrementOverDeleted();
        }
        void increment()
        {
            ++vit_;
            incrementOverDeleted();
        }
        value_type& dereference() const
        {
            assert(!atEnd());
            return *vit_;
        }
        bool equals(const Iter& rhs) const
        {
            return vit_ == rhs.vit_;
        }
    private:
        VecIterator vit_;
        ThisType* collection_;
    }; 
    typedef IterAdapter<Iter> iterator;
    typedef CIterAdapter<Iter> const_iterator;    
    SortedArrayBase()
        : deletedCount_(0)
        , smallVectorThreshold_(200)
        , compactionFactor_(0.2)
    {
        autoSetThreshold();
    }
    SortedArrayBase(const VT& vt)
        : deletedCount_(0)
        , smallVectorThreshold_(200)
        , compactionFactor_(0.2)
    {
        autoSetThreshold();
        setValueTraits(vt);
    }
    void setValueTraits(const VT& vt)
    {
        valueTraits_ = vt;
    }
    const VT& getValueTraits() const
    {
        return valueTraits_;
    }
    
    void setCompactionFactor(double cf)
    {
        assert(cf > 0.0);
        compactionFactor_ = cf;
    }
    double getCompactionFactor() const
    {
        return compactionFactor_;
    }

    void setSmallVectorThreshold(size_type svt)
    {
        smallVectorThreshold_ = svt;
    }
    size_type getSmallVectorThreshold() const
    {
        return smallVectorThreshold_;
    }

    const_iterator begin() const
    {
        ThisType* ncThis = const_cast<ThisType*>(this);
        Iter it(ncThis,ncThis->vec_.begin());
        it.incrementOverDeleted();
        return it;
    }
    const_iterator end() const
    {
        ThisType* ncThis = const_cast<ThisType*>(this);
        return Iter(ncThis,ncThis->vec_.end());
    }
    iterator begin()
    {
        Iter it(this,vec_.begin());
        it.incrementOverDeleted();
        return it;
    }
    iterator end()
    {
        return Iter(this,vec_.end());
    }
    //tryInsert(): attempt to insert an element. If successful, return 0 if the element 
    //already existed, 1 if it is a new element. Store the iterator for the inserted
    //element in the reference parameter iter
    //If the element cannot be inserted, return -1 (iter is unchanged)
    int tryInsert(const value_type& val, iterator& iter)
    {
        //locate the position where this value would be inserted
        std::pair<VecIterator,VecIterator> vecRange
            = std::equal_range(vec_.begin(),vec_.end(),val,valueTraits_.kc);
        if(vecRange.first != vecRange.second)
        {
            //assert that the count is one, and only one
            assert(vecRange.first + 1 == vecRange.second);
            //vecRange.first points to the value.
            iter = Iter(this,vecRange.first);
            //If it is deleted, un-delete it.
            if(deleted_[vecRange.first - vec_.begin()])
            {
                //unset the deleted flag and adjust count
                deleted_[vecRange.first - vec_.begin()] = false;
                deletedCount_--;
                valueTraits_.assign(*vecRange.first,val);
                //element was previously deleted, therefore it didn't technically "exist",
                //so return 1
                return 1;
            }
            //element was pre-existing
            return 0;
        }
        else
        {
            //The value was not found. However, IF there is a gap in the collection
            //(i.e. a deleted value), we can re-use the slot
            if(vecRange.first != vec_.end() && deleted_[vecRange.first - vec_.begin()])
            {
                //assign to the value
                //valueTraits_.assign(*vecRange.first,val);
                valueTraits_.assign(*(vecRange.first),val);
                iter = Iter(this,vecRange.first);
                //unset the deleted flag and adjust count
                deleted_[vecRange.first - vec_.begin()] = false;
                --deletedCount_;
                return 1;
            }
            else if(vecRange.first != vec_.begin() && deleted_[vecRange.first - vec_.begin() - 1])
            {
                //assign to the value
                //valueTraits_.assign(*(vecRange.first-1) ,val);
                valueTraits_.assign(*(vecRange.first-1),val);
                iter = Iter(this,vecRange.first-1);
                //unset the deleted flag and adjust count
                deleted_[vecRange.first - vec_.begin() - 1] = false;
                --deletedCount_;
                return 1;
            }
            else if(vec_.size() < smallVectorThreshold_ && deletedCount_ == 0)
            {
                //small vector optimization
                //if the vector is very small, just take the hit and do the insert directly
                iter = Iter(this,vec_.insert(vecRange.first,val));
                deleted_.push_back(false);
                return 1;
            }
        }
        //if we got this far, it can't be inserted
        return -1;
    }
        iterator erase(iterator it)
        {
                assert(!deleted_[it.getImpl_().vit_ - vec_.begin()]);
                deleted_[it.getImpl_().vit_ - vec_.begin()] = true;
                ++deletedCount_;
                it.getImpl_().incrementOverDeleted();
                return it;
        }
    size_type erase(const key_type& val)
    {
        //locate the value
        std::pair<VecIterator,VecIterator> vecRange
            = std::equal_range(vec_.begin(),vec_.end(),val,valueTraits_.kc);
        if(vecRange.first != vecRange.second)
        {
            //assert that the count is one, and only one
            assert(vecRange.first + 1 == vecRange.second);
            //vecRange.first points to the value.
            //If it is deleted, return 0
            if(deleted_[vecRange.first - vec_.begin()])
            {
                return 0;
            }
            else
            {
                //set the deleted flag and adjust count
                deleted_[vecRange.first - vec_.begin()] = true;
                ++deletedCount_;
                //element was previously deleted, therefore it didn't technically "exist",
                //so return 1
                return 1;
            }
        }
        else
        {
            //element does not exist
            return 0;
        }
    }
    size_type size() const
    {
        return vec_.size() - deletedCount_;
    }
    iterator find(const key_type& key)
    {
        VecIterator found = std::lower_bound(vec_.begin(),vec_.end(),key,valueTraits_.kc);
        if(found == vec_.end())
            return end();
        if(deleted_[found - vec_.begin()])
            return end();
        if(valueTraits_.kc(key,valueTraits_.extractKey(*found)))
            return end();
        return iterator(Iter(this,found));
    }
    iterator upper_bound(const key_type& key)
    {
        VecIterator found = std::upper_bound(vec_.begin(),vec_.end(),key,valueTraits_.kc);
        Iter it(this,found);
        it.incrementOverDeleted();
        return iterator(it);
    }
    iterator lower_bound(const key_type& key)
    {
        VecIterator found = std::lower_bound(vec_.begin(),vec_.end(),key,valueTraits_.kc);
        Iter it(this,found);
        it.incrementOverDeleted();
        return iterator(it);
    }
    void compact(typename VT::DynSetType& coll)
    {
       size_type newSz = size() + coll.size();
        //declare a new vector to contain the expanded collection
        VEC newVec(vec_.get_allocator());
        //reserve enough space
        newVec.reserve(newSz);
        //merge the two sorted collections. begin() and end() are used, which
        //will automatically skip over deleted elements.
        std::set_union(coll.begin(),coll.end(),begin(),end(),std::back_inserter(newVec),valueTraits_.kc);
        //clear the source collection
        coll.clear();
        //declare a new deleted flag vector
        std::vector<bool> newDeleted(newSz,false);
        //swap the old with the new
        std::swap(vec_,newVec);
        std::swap(deleted_,newDeleted);
        deletedCount_ = 0;
        autoSetThreshold();
    }
    bool autoCompact(typename VT::DynSetType& coll)
    {
        if(coll.size() >= threshold_ || deletedCount_ >= threshold_)
        {
            compact(coll);
            return true;
        }
        return false;
    }
    void swap(SortedArrayBase& rhs)
    {
        vec_.swap(rhs.vec_);
        valueTraits_.swap(rhs.valueTraits_);
        deleted_.swap(rhs.deleted_);
        std::swap(deletedCount_,rhs.deletedCount_);
        std::swap(smallVectorThreshold_,rhs.smallVectorThreshold_);
        std::swap(threshold_,rhs.threshold_);
        std::swap(compactionFactor_,rhs.compactionFactor_);
    }
    void clear()
    {
        vec_.clear();
        deleted_.clear();
        deletedCount_ = 0;
        autoSetThreshold();
    }
protected:
    void autoSetThreshold()
    {
        if(size() < smallVectorThreshold_)
        {
            threshold_ = (size_type) (smallVectorThreshold_ * compactionFactor_);
        }
        else
        {
            threshold_ = (size_type) (size() * compactionFactor_);
        }
    }

    VEC vec_;
    VT valueTraits_;
    std::vector<bool> deleted_;
    size_type deletedCount_;
    size_type smallVectorThreshold_;
    size_type threshold_;
    double compactionFactor_;
};

//simple tag class for Policy specification
class MinimizeSpacePolicy
{
};

//simple tag class for Policy specification
class MaximizeSpeedPolicy
{
};

#ifndef _COMPACT_SET_NO_POLICIES

template <>
class AdaptPol<MaximizeSpeedPolicy>
{
public:
    template <class VT>
        class Impl
        : public SortedArrayBase<VT,std::vector<typename VT::AssignableValueType,typename VT::AssignableAllocatorType> >
    {
        typedef SortedArrayBase<VT,std::vector<typename VT::AssignableValueType,typename VT::AssignableAllocatorType> > SAType;
public:
    Impl(const VT& vt)
    {
        setValueTraits(vt);
    }
    };
};

template <>
class AdaptPol<MinimizeSpacePolicy>
{
public:
    template <class VT>
        class Impl
        : public SortedArrayBase<VT,std::deque<typename VT::AssignableValueType,typename VT::AssignableAllocatorType> >
    {
        typedef std::deque<typename VT::AssignableValueType,typename VT::AssignableAllocatorType> VecImplType;
        typedef SortedArrayBase<VT,VecImplType> SAType;
public:
    typedef typename SAType::size_type size_type;
    typedef typename SAType::value_type value_type;
    typedef typename SAType::allocator_type allocator_type;
    Impl(const VT& vt)
    {
        setValueTraits(vt);
    }
    void compact(typename VT::DynSetType& coll)
    {
        size_type newSz = size() + coll.size();
        //declare a new deque to contain the expanded collection
        VecImplType newVec(vec_.get_allocator());
        //merge the two sorted collections. begin() and end() are used, which
        //will automatically skip over deleted elements.
        typename VT::DynSetType::iterator collIt = coll.begin();
        typename VecImplType::iterator deqIt = vec_.begin();
        size_type deqOffset = 0;
        while(collIt != coll.end() && deqIt != vec_.end())
        {
            if(valueTraits_.kc(*collIt, *deqIt))
            {
                newVec.push_back(*collIt);
                coll.erase(collIt);
                collIt = coll.begin();
            }
            else
            {
                assert(valueTraits_.kc(*deqIt, *collIt));
                if(!deleted_[deqOffset])
                {
                    newVec.push_back(*deqIt);
                }
                vec_.pop_front();
                deqIt = vec_.begin();
                ++deqOffset;
            }
        }
        while(collIt != coll.end())
        {
            newVec.push_back(*collIt);
            coll.erase(collIt);
            collIt = coll.begin();
        }
        while(deqIt != vec_.end())
        {
            if(!deleted_[deqOffset])
            {
                newVec.push_back(*deqIt);
            }
            vec_.pop_front();
            deqIt = vec_.begin();
            ++deqOffset;
        }
        assert(newSz == newVec.size());
        //declare a new deleted flag vector
        std::vector<bool> newDeleted(newSz,false);
        //swap the old with the new
        std::swap(vec_,newVec);
        std::swap(deleted_,newDeleted);
        deletedCount_ = 0;
        autoSetThreshold();
    }
    bool autoCompact(typename VT::DynSetType& coll)
    {
        if(coll.size() >= threshold_ || deletedCount_ >= threshold_)
        {
            compact(coll);
            return true;
        }
        return false;
    }
    };
};
#endif //#ifndef _COMPACT_SET_NO_POLICIES

template<class CT>
class CompactColl
{
    //    typedef CompactColl CollType;
public:
    typedef typename CT::key_type key_type;
    typedef typename CT::value_type value_type;
    typedef typename CT::key_compare key_compare;
    typedef typename CT::value_compare value_compare;
    typedef typename CT::allocator_type allocator_type;
    typedef typename allocator_type::size_type size_type;
    typedef typename allocator_type::difference_type difference_type;
    
    typedef typename CT::DynSetType DynSetType;
#ifdef _COMPACT_SET_NO_POLICIES
        //TODO the allocator below is wrong! But is there any way to fix it?
    typedef typename SortedArrayBase<CT,std::vector<typename CT::AssignableValueType,std::allocator<CT::AssignableValueType> > > CompactPolicyType;
#else
    typedef typename AdaptPol<typename CT::PolicyTagType>::template Impl<CT> CompactPolicyType;
#endif
    typedef typename CompactPolicyType::iterator CPIter;
    typedef typename DynSetType::iterator DSIter;
    class Iter;
    friend class Iter;
    class Iter
    {
                friend class CompactColl<CT>;
        void validate()
        {
            if(archiveIsCurr_)
            {
                assert(!archiveAtEnd());
                iit_ = collection_->dynamic_.upper_bound(collection_->archive_.getValueTraits().extractKey(*ait_));
            }
            else
            {
                assert(!dynamicAtEnd());
                ait_ = collection_->archive_.upper_bound(collection_->archive_.getValueTraits().extractKey(*iit_));
            }     
            isValid_ = true;
        }
        bool archiveAtEnd() const
        {
            return ait_ == collection_->archive_.end();
        }
        bool dynamicAtEnd() const
        {
            return iit_ == collection_->dynamic_.end();
        }
        bool archiveAtBegin() const
        {
            return ait_ == collection_->archive_.begin();
        }
        bool dynamicAtBegin() const
        {
            return iit_ == collection_->dynamic_.begin();
        }
        bool atEnd() const
        {
            return archiveAtEnd() && dynamicAtEnd();
        }
        void assertValid() const
        {
#ifndef NDEBUG
            if(atEnd())
                return;
            assert(isValid_);
            if(archiveIsCurr_)
            {
                assert(!archiveAtEnd());
                if(!dynamicAtEnd())
                {
                    assert(collection_->archive_.getValueTraits().kc(
                            collection_->archive_.getValueTraits().extractKey(*ait_),
                            collection_->archive_.getValueTraits().extractKey(*iit_) ));
                    if(!dynamicAtBegin())
                    {
                        typename DynSetType::iterator tmpIt = iit_;
                        --tmpIt;
                        assert(collection_->archive_.getValueTraits().kc(
                                collection_->archive_.getValueTraits().extractKey(*tmpIt),
                                collection_->archive_.getValueTraits().extractKey(*ait_) ));
                    }
                }
            }
            else
            {
                assert(!dynamicAtEnd());
                if(!archiveAtEnd())
                {
                    assert(collection_->archive_.getValueTraits().kc(
                            collection_->archive_.getValueTraits().extractKey(*iit_),
                            collection_->archive_.getValueTraits().extractKey(*ait_) ));
                    if(!archiveAtBegin())
                    {
                        CPIter tmpIt = ait_;
                        --tmpIt;
                        assert(collection_->archive_.getValueTraits().kc(
                            collection_->archive_.getValueTraits().extractKey(*tmpIt),
                            collection_->archive_.getValueTraits().extractKey(*iit_) ));
                    }
                }
            }
#endif
        }
    public:
        typedef std::bidirectional_iterator_tag iterator_category;
        typedef typename CT::value_type value_type;
        typedef typename CT::size_type size_type;
        typedef ptrdiff_t difference_type;
        
        void increment()
        {
            assert(!atEnd());
            if(!isValid_) validate();
            assertValid();
            if(archiveIsCurr_)
            {
                ++ait_;
            }
            else
            {
                ++iit_;
            }
            archiveIsCurr_=(dynamicAtEnd() 
                || (!archiveAtEnd() && collection_->archive_.getValueTraits().kc(
                        collection_->archive_.getValueTraits().extractKey(*ait_),
                        collection_->archive_.getValueTraits().extractKey(*iit_) )));
            assertValid();
        }
        void decrement()
        {
            if(!isValid_) validate();
            assertValid();
            if(archiveAtBegin())
            {
                assert(!dynamicAtBegin());
                --iit_;
                archiveIsCurr_ = false;
                return;
            }
            if(dynamicAtBegin())
            {
                --ait_;
                archiveIsCurr_ = true;
                return;
            }
            --ait_;
            --iit_;
            if(collection_->archive_.getValueTraits().kc(
                        collection_->archive_.getValueTraits().extractKey(*ait_),
                        collection_->archive_.getValueTraits().extractKey(*iit_) ))
            {
                archiveIsCurr_ = false;
                ++ait_;
            }
            else
            {
                archiveIsCurr_ = true;
                ++iit_;
            }
            assertValid();
        }
        static Iter Begin(const CompactColl* collection_)
        {
            Iter ret;
            CompactColl* ncColl = const_cast<CompactColl*>(collection_);
            ret.collection_ = ncColl;
            ret.ait_ = ncColl->archive_.begin();
            ret.iit_ = ncColl->dynamic_.begin();
            ret.archiveIsCurr_=(
                ret.dynamicAtEnd() ||
                (!ret.archiveAtEnd() && 
                collection_->archive_.getValueTraits().kc(
                        collection_->archive_.getValueTraits().extractKey(*ret.ait_),
                        collection_->archive_.getValueTraits().extractKey(*ret.iit_) )));
            ret.isValid_ = true;
            return ret;
        }          
        static Iter End(const CompactColl* collection_)
        {
            Iter ret;
            CompactColl* ncColl = const_cast<CompactColl*>(collection_);
            ret.collection_ = ncColl;
            ret.ait_ = ncColl->archive_.end();
            ret.iit_ = ncColl->dynamic_.end();
            //archiveIsCurr_ is irrelevant for end(), but initialize it to false anyway
            ret.archiveIsCurr_ = false;
            ret.isValid_ = true;
            return ret;
        }          
        Iter()
            : collection_(0), archiveIsCurr_(false),isValid_(false)
        {
        }
        Iter(CPIter ait,typename DynSetType::iterator iit,
            CompactColl* collection,bool archiveIsCurr)
            :ait_(ait)
            ,iit_(iit)
            ,collection_(collection)
            ,archiveIsCurr_(archiveIsCurr)
            ,isValid_(true)
        {
        }
        Iter(CPIter ait,typename DynSetType::iterator iit,
            CompactColl* collection)
            :ait_(ait)
            ,iit_(iit)
            ,collection_(collection)
                        ,isValid_(true)
        {
                        //automatically set the archiveIsCurr_ member.
            archiveIsCurr_=(
                dynamicAtEnd() ||
                (!archiveAtEnd() && 
                                        collection_->archive_.getValueTraits().kc(
                        collection_->archive_.getValueTraits().extractKey(*ait_),
                        collection_->archive_.getValueTraits().extractKey(*iit_) )));
        }
        Iter(CPIter ait,CompactColl* collection)
            :ait_(ait)
            ,collection_(collection)
            ,archiveIsCurr_(true)
            ,isValid_(false)
        {
        }
        Iter(typename DynSetType::iterator iit,CompactColl* collection)
            :iit_(iit)
            ,collection_(collection)
            ,archiveIsCurr_(false)
            ,isValid_(false)
        {
        }
        
        value_type& dereference() const
        {
            //                  assertValid();
            if(archiveIsCurr_)
            {
                assert(!archiveAtEnd());
                return *ait_;
            }
            else
            {
                assert(!dynamicAtEnd());
                //for some reason, G++ 2.95 needs a cast
//                return reinterpret_cast<value_type&>(*iit_);
                return (value_type&)(*iit_);
            }
        }
        bool equals(const Iter& rhs) const
        {
            if(atEnd()) 
            {
                return ait_ == rhs.ait_ && iit_ == rhs.iit_;
            }
            return (archiveIsCurr_ && rhs.archiveIsCurr_ && ait_ == rhs.ait_) 
                || (!archiveIsCurr_ && !rhs.archiveIsCurr_ && iit_ == rhs.iit_);
        }
    private:
        CPIter ait_;
        typename DynSetType::iterator iit_;
        CompactColl* collection_;
        bool archiveIsCurr_;
        bool isValid_;
    }; 
    
    
    typedef IterAdapter<Iter> iterator;
    typedef CIterAdapter<Iter> const_iterator;    
#ifdef _MSC_VER
    typedef std::reverse_bidirectional_iterator<iterator,value_type> reverse_iterator;
    typedef std::reverse_bidirectional_iterator<const_iterator,value_type> const_reverse_iterator;
#else
    typedef std::reverse_iterator<iterator> reverse_iterator;
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
#endif
public:
    //    typedef ArchiveMapType::allocator_type::rebind<value_type>::other::const_reference reference;
    //    typedef ArchiveMapType::allocator_type::rebind<value_type>::other::const_reference const_reference;
    //    typedef typename ArchiveMapType::reference reference;
    //    typedef typename ArchiveMapType::const_reference const_reference;
    const CompactPolicyType& getCompactPolicy() const
    {
        //policy is actually just the archive set...
        return archive_;
    }
    CompactPolicyType& getCompactPolicy()
    {
        //policy is actually just the archive set...
        return archive_;
    }
    void compact()
    {
        archive_.compact(dynamic_);
    }
    
    explicit CompactColl(const CT& ct)
        : archive_(ct)
        , dynamic_(ct.key_comp(),ct.get_allocator())
    {
    }
    //CompactColl(const CompactColl& x);
    //template constructor from iterator pair missing due to visual studio limitations
    const_iterator begin() const
    {
        return Iter::Begin(this);
    }
    const_iterator end() const
    {
        return Iter::End(this);
    }
    iterator begin()
    {
        return Iter::Begin(this);
    }
    iterator end()
    {
        return Iter::End(this);
    }
    const_reverse_iterator rbegin() const
    {
        return const_reverse_iterator(end());
    }
    const_reverse_iterator rend() const
    {
        return const_reverse_iterator(begin());
    }
    reverse_iterator rbegin()
    {
        return reverse_iterator(end());
    }
    reverse_iterator rend()
    {
        return reverse_iterator(begin());
    }
    size_type size() const
    {
        return archive_.size() + dynamic_.size();
    }
    bool empty() const
    {
        return size() == 0;
    }
    allocator_type get_allocator() const
    {
        return archive_.get_allocator();
    }
    std::pair<iterator, bool> insert(const value_type& val)
    {
        CPIter cpit;
        bool inserted = false;
        iterator returnIt;
        DSIter dsit = dynamic_.find(archive_.getValueTraits().extractKey(val));
        if(dsit != dynamic_.end())
        {
            returnIt = iterator(Iter(dsit,this));
        }
        else
        {
            switch(archive_.tryInsert(val,cpit))
            {
            case -1:
                {
                    std::pair<DSIter,bool> ret = 
                        dynamic_.insert(val);
                    inserted = ret.second;
                    returnIt = iterator(Iter(ret.first,this));
                }
                break;
            case 1:
                inserted = true;
                //fall through
            case 0:
                returnIt = iterator(Iter(cpit,this));
                break;
            }
        }
        if(archive_.autoCompact(dynamic_))
        {
            return std::make_pair(find(archive_.getValueTraits().extractKey(val)),inserted);
        }
        return std::make_pair(returnIt,inserted);
    }
    iterator insert(iterator it, const value_type& val)
    {
                //hint not used in this implementation
                return insert(val).first;
    }
    template <class IT>
    void insert(IT b, IT e)
    {
                for(; b != e; ++b)
                {
                        insert(*b);
                }
    }
    iterator erase(iterator it)
    {
                iterator ret = it;
                ++ret;
                if(it.getImpl_().archiveIsCurr_)
                {
                        archive_.erase(it.getImpl_().ait_);
                }
                else
                {
                        dynamic_.erase(it.getImpl_().iit_);
                }
                //Need to be able to re-initialize the iterator if a compaction occurs,
                //so hold onto the value of the return iterator
                if(ret.getImpl_().atEnd())
                {
                archive_.autoCompact(dynamic_);
                        return end();
                }
                else
                {
                        value_type val(*ret);
                        if(archive_.autoCompact(dynamic_))
                        {
                                return find(archive_.getValueTraits().extractKey(val));
                        }
                        return ret;
                }
    }
    iterator erase(iterator b, iterator e)
    {
                while(b != e)
                {
                        b = erase(b);
                }
                return b;
    }
    size_type erase(const key_type& key)
    {
        size_type count=0;
        if(archive_.erase(key))
        {
            count = 1;
        }
        else
        {
            count = dynamic_.erase(key);
        }
        archive_.autoCompact(dynamic_);
        return count;
    }
    iterator find(const key_type& key)
    {
        typename CompactPolicyType::iterator aFound = 
            archive_.find(key);
        if(aFound != archive_.end())
        {
            return iterator(Iter(aFound,this));
        }
        else
        {
            typename DynSetType::iterator iFound = 
                dynamic_.find(key);
            if(iFound != dynamic_.end())
            {
                return iterator(Iter(iFound,this));
            }
        }
        return end();
    }
    const_iterator find(const key_type& key) const
    {
                //this does not violate const-ness in any way, and
                //is only done to avoid duplication of the non-const algorithm.
                return const_cast<CompactColl*>(this)->find(key);
    }
    size_type count(const key_type& key) const
    {
                //this will always return 0 or 1 for collections with unique keys
                return (find(key) == end() ? 0 : 1);
        }
    iterator lower_bound(const key_type& key)
    {
                return iterator(
                                        Iter(
                                                archive_.lower_bound(key),
                                                dynamic_.lower_bound(key),
                                                this));
    }
    const_iterator lower_bound(const key_type& key) const
    {
                //this does not violate const-ness in any way, and
                //is only done to avoid duplication of the non-const algorithm.
                return const_cast<CompactColl*>(this)->lower_bound(key);
        }
    iterator upper_bound(const key_type& key)
    {
                return iterator(
                                        Iter(
                                                archive_.upper_bound(key),
                                                dynamic_.upper_bound(key),
                                                this));
        }
    const_iterator upper_bound(const key_type& key) const
    {
                //this does not violate const-ness in any way, and
                //is only done to avoid duplication of the non-const algorithm.
                return const_cast<CompactColl*>(this)->upper_bound(key);
        }
    std::pair<iterator, iterator>
    equal_range(const key_type& key)
    {
                //equal_range returns the equivalent of 
                //(lower_bound(key), upper_bound(key))
                //however, because this collection has unique
                //keys, we can optimize so that only 
                //lower_bound() is called.
                iterator lb(lower_bound(key));
                if(lb == end())
                {
                        return std::make_pair(lb,lb);
                }
                if(archive_.getValueTraits().kc(
                        key,
                                                archive_.getValueTraits().extractKey(*lb) ))
                {
                        //if key is less than the value returned by lower_bound(),
                        //then the lower bound is also the upper bound.
                        return std::make_pair(lb,lb);
                }
                else
                {
                        //the key must be equal to the lower bound, so 
                        //the upper bound is one past the lower bound.
                        assert(!archive_.getValueTraits().kc(
                                archive_.getValueTraits().extractKey(*lb),key ));
                        iterator ub = lb;
                        ++ub;
                        return std::make_pair(lb,ub);
                }
        }
    std::pair<const_iterator, const_iterator>
    equal_range(const key_type& key) const
    {
                //this does not violate const-ness in any way, and
                //is only done to avoid duplication of the non-const algorithm.
                std::pair<iterator,iterator> ncER = 
                        const_cast<CompactColl*>(this)->equal_range(key);
                return std::pair<const_iterator,const_iterator>(ncER.first,ncER.second);
        }
    void clear()
    {
                archive_.clear();
                dynamic_.clear();
    }
    void swap(CompactColl& rhs)
    {
                archive_.swap(rhs.archive_);
                dynamic_.swap(rhs.dynamic_);
    }
/*    key_compare key_comp() const
    {
    return pred_;
    }
    value_compare value_comp() const
    {
    return pred_;
    }
    }*/
private:
    CompactPolicyType archive_;
    DynSetType dynamic_;
};


#endif // !defined(AFX_COMPACTCOLL_H__D6BBCFE2_D17F_45C8_867D_7B2A4137A3F4__INCLUDED_)
s than the value returned by lower_bound(),
                        //then the lower bound is also the upper bound.
                        return std::make_pair(lb,lb);
                }
                else
                {
                        //the key must be equal to the lower bound, so 
                        //the upper bound is one past the lower bound.
                        assert(!archive_.getValueTraits().kc(
                                archive_.getValueTraits().extractKey(*lb),key ));
                        iterator ub = lb;
                        ++ub;
                        return std::make_pair(lb,ub);
                }
        }
    std::pair<const_iterator, const_iterator>
    equal_range(const key_type& key) const
    {
                //this does not violate const-ness in any way, and
                //is only done to avoid duplication of the non-const algorithm.
                std::pair<iterator,iterator> ncER = 
                        const_cast<CompactColl*>(this)->equal_range(key);
                return std::pair<const_iterator,const_iterator>(ncER.first,ncER.second);
        }
    void clear()
    {
                archive_.clear();
                dynamic_.clear();
    }
    void swap(CompactColl& rhs)
    {
                archive_.swap(rhs.archive_);
                dynamic_.swap(rhs.dynamic_);
    }
/*    key_compare key_comp() const
    {
    return pred_;
    }
    value_compare value_comp() const
    {
    return pred_;
    }
    }*/
private:
    CompactPolicyType archive_;
    DynSetType dynamic_;
};


#endif // !defined(AFX_COMPACTCOLL_H__D6BBCFE2_D17F_45C8_867D_7B2A4137A3F4__INCLUDED_)

---