rangemap.hpp

ncbi源码

                m_SelectIterEnd = selectIterEnd;
                m_LevelIter = levelIter;
                return;
            }
        }
    }
    // not found
    m_Range = range_type::GetEmpty();
    m_SelectIter = m_SelectIterEnd = selectIterEnd;
}

// range map
template<class Traits>
class CRangeMapBase
{
public:
    // standard typedefs
    typedef Traits TRangeMapTraits;
    typedef CRangeMapIteratorTraits<TRangeMapTraits> TIteratorTraits;
    typedef CRangeMapConstIteratorTraits<TRangeMapTraits> TConstIteratorTraits;

    typedef size_t size_type;
    typedef typename TRangeMapTraits::position_type position_type;
    typedef typename TRangeMapTraits::range_type range_type;
    typedef typename TRangeMapTraits::mapped_type mapped_type;
    typedef typename TRangeMapTraits::value_type value_type;
    typedef range_type key_type;

    typedef typename TRangeMapTraits::TRangeMap TThisType;
    typedef typename TIteratorTraits::iterator iterator;
    typedef typename TConstIteratorTraits::iterator const_iterator;

protected:
    // internal typedefs
    typedef typename TRangeMapTraits::TSelectMap TSelectMap;
    typedef typename TSelectMap::value_type select_value;
    typedef typename TSelectMap::iterator TSelectMapI;
    typedef typename TRangeMapTraits::TLevelMap TLevelMap;
    typedef typename TLevelMap::iterator TLevelMapI;

    // constructor
    CRangeMapBase(void)
        {
#if defined(_RWSTD_VER) && !defined(_RWSTD_STRICT_ANSI)
            m_SelectMap.allocation_size(8);
#endif
        }

    TSelectMapI insertLevel(position_type key)
        {
            TSelectMapI iter = m_SelectMap.lower_bound(key);
            if ( iter == m_SelectMap.end() || iter->first != key ) {
                iter = m_SelectMap.insert(iter,
                                          select_value(key, TLevelMap()));
            }
            return iter;
        }
public:
    // capacity
    bool empty(void) const
        {
            return m_SelectMap.empty();
        }
    size_type size(void) const
        {
            typedef typename TSelectMap::const_iterator TSelectMapCI;

            size_type size = 0;
            for ( TSelectMapCI i = m_SelectMap.begin(),
                      end = m_SelectMap.end(); i != end; ++i ) {
                size += i->second.size();
            }
            return size;
        }
    pair<double, size_type> stat(void) const
        {
            return make_pair(0.0, size_type(0));
        }
    
    // iterators
    const_iterator end(void) const
        {
            const_iterator iter;
            iter.SetEnd(m_SelectMap);
            return iter;
        }
    const_iterator begin(void) const
        {
            const_iterator iter;
            iter.SetBegin(m_SelectMap);
            return iter;
        }
    const_iterator begin(const range_type& range) const
        {
            const_iterator iter;
            iter.SetBegin(range, m_SelectMap);
            return iter;
        }

    iterator end(void)
        {
            iterator iter;
            iter.SetEnd(m_SelectMap);
            return iter;
        }
    iterator begin(void)
        {
            iterator iter;
            iter.SetBegin(m_SelectMap);
            return iter;
        }
    iterator begin(const range_type& range)
        {
            iterator iter;
            iter.SetBegin(range, m_SelectMap);
            return iter;
        }

    // element search
    const_iterator find(const key_type& key) const
        {
            const_iterator iter;
            iter.Find(key, m_SelectMap);
            return iter;
        }
    iterator find(const key_type& key)
        {
            iterator iter;
            iter.Find(key, m_SelectMap);
            return iter;
        }

    // modification
    void erase(iterator iter)
        {
            _ASSERT(iter != end());

            // get element's level
            TLevelMap& level = iter.GetSelectIter()->second;

            // erase element on level
            level.erase(iter.GetLevelIter());

            if ( level.empty() ) // end of level
                m_SelectMap.erase(iter.GetSelectIter()); // remove level
        }
    size_type erase(const key_type& key)
        {
            size_type count = 0;
            iterator iter = find(key);
            while ( iter && iter.GetInterval() == key ) {
                iterator toErase = iter;
                ++iter;
                ++count;
                erase(toErase);
            }
            return count;
        }

    void clear(void)
        {
            m_SelectMap.clear();
        }
    void swap(TThisType& rangeMap)
        {
            m_SelectMap.swap(rangeMap.m_SelectMap);
        }

protected:
    // data
    TSelectMap m_SelectMap;
};

// range map
template<typename Mapped, typename Position = int>
class CRangeMap : public CRangeMapBase< CRangeMapTraits<Position, Mapped> >
{
    typedef CRangeMapBase< CRangeMapTraits<Position, Mapped> > TParent;
public:
    // standard typedefs
    typedef typename TParent::size_type size_type;
    typedef typename TParent::position_type position_type;
    typedef typename TParent::range_type range_type;
    typedef typename TParent::mapped_type mapped_type;
    typedef typename TParent::value_type value_type;
    typedef typename TParent::key_type key_type;

    typedef typename TParent::iterator iterator;
    typedef typename TParent::const_iterator const_iterator;

    typedef typename TParent::TRangeMapTraits TRangeMapTraits;
    typedef typename TParent::TSelectMap TSelectMap;
    typedef typename TParent::select_value select_value;
    typedef typename TParent::TSelectMapI TSelectMapI;
    typedef typename TParent::TLevelMap TLevelMap;
    typedef typename TParent::TLevelMapI TLevelMapI;

    // constructor
    explicit CRangeMap(void)
        {
        }

    pair<iterator, bool> insert(const value_type& value)
        {
            if ( value.first.Empty() ) {
//                THROW1_TRACE(runtime_error, "empty key range");
                NCBI_THROW(CUtilException,eWrongData,"empty key range");
            }

            // key in select map
            position_type selectKey =
                TRangeMapTraits::get_max_length(value.first);

            // get level

            // insert element
            TSelectMapI selectIter = insertLevel(selectKey);
            pair<TLevelMapI, bool> levelIns = selectIter->second.insert(value);
            
            pair<iterator, bool> ret;
            ret.second = levelIns.second;
            ret.first.m_Range = range_type::GetWhole();
            ret.first.m_SelectIter = selectIter;
            ret.first.m_SelectIterEnd = this->m_SelectMap.end();
            ret.first.m_LevelIter = levelIns.first;
            return ret;
        }

    // element access
    mapped_type& operator[](const key_type& key)
        {
            return insert(value_type(key, mapped_type())).first->second;
        }
};

// range map
template<typename Mapped, typename Position = int>
class CRangeMultimap : public CRangeMapBase< CRangeMultimapTraits<Position, Mapped> >
{
    typedef CRangeMapBase< CRangeMultimapTraits<Position, Mapped> > TParent;
public:
    // standard typedefs
    typedef typename TParent::size_type size_type;
    typedef typename TParent::position_type position_type;
    typedef typename TParent::range_type range_type;
    typedef typename TParent::mapped_type mapped_type;
    typedef typename TParent::value_type value_type;
    typedef typename TParent::key_type key_type;

    typedef typename TParent::iterator iterator;
    typedef typename TParent::const_iterator const_iterator;

    typedef typename TParent::TRangeMapTraits TRangeMapTraits;
    typedef typename TParent::TSelectMap TSelectMap;
    typedef typename TParent::select_value select_value;
    typedef typename TParent::TSelectMapI TSelectMapI;
    typedef typename TParent::TLevelMap TLevelMap;
    typedef typename TParent::TLevelMapI TLevelMapI;

    // constructor
    explicit CRangeMultimap(void)
        {
        }

    iterator insert(const value_type& value)
        {
            if ( value.first.Empty() ) {
//                THROW1_TRACE(runtime_error, "empty key range");
                NCBI_THROW(CUtilException,eWrongData,"empty key range");
            }

            // select key
            position_type selectKey =
                TRangeMapTraits::get_max_length(value.first);

            // insert element
            iterator ret;
            ret.m_Range = range_type::GetWhole();
            ret.m_SelectIter = insertLevel(selectKey);
            ret.m_SelectIterEnd = this->m_SelectMap.end();
            ret.m_LevelIter = ret.m_SelectIter->second.insert(value);
            return ret;
        }
};


/* @} */


//#include <util/rangemap.inl>

END_NCBI_SCOPE

/*
* ---------------------------------------------------------------------------
* $Log: rangemap.hpp,v $
* Revision 1000.2  2004/06/01 19:38:35  gouriano
* PRODUCTION: UPGRADED [GCC34_MSVC7] Dev-tree R1.24
*
* Revision 1.24  2004/04/26 14:52:03  ucko
* Add "this->" as needed to accommodate GCC 3.4's stricter treatment of
* templates.
*
* Revision 1.23  2004/01/13 17:23:14  vasilche
* Performance fix - do not create level node until it's really needed.
*
* Revision 1.22  2003/04/22 17:21:02  ucko
* Clarified comment for get_max_length (taken from an exchange between
* Eugene and Karl).
*
* Revision 1.21  2003/04/17 17:50:26  siyan
* Added doxygen support
*
* Revision 1.20  2003/02/26 21:34:06  gouriano
* modify C++ exceptions thrown by this library
*
* Revision 1.19  2003/02/07 16:54:01  vasilche
* Pass all structures with size > sizeof int by reference.
* Move cvs log to the end of files.
*
* Revision 1.18  2003/01/22 20:05:25  vasilche
* Simplified CRange<> implementation.
* Removed special handling of Empty & Whole bounds.
* Added simplier COpenRange<> template.
*
* Revision 1.17  2002/05/06 20:38:56  grichenk
* Fixed unsigned values handling
*
* Revision 1.16  2002/02/13 22:39:15  ucko
* Support AIX.
*
* Revision 1.15  2001/09/18 16:22:21  grichenk
* Fixed problem with the default constructor for CRangeMapIterator
* (Valid() returned unpredictable value)
*
* Revision 1.14  2001/09/17 18:26:32  grichenk
* Fixed processing of "Whole" ranges in the range map iterator.
*
* Revision 1.13  2001/06/28 12:44:56  grichenk
* Added some comments
*
* Revision 1.12  2001/01/29 15:18:39  vasilche
* Cleaned CRangeMap and CIntervalTree classes.
*
* Revision 1.11  2001/01/16 21:37:22  vasilche
* Fixed warning.
*
* Revision 1.10  2001/01/16 20:52:24  vasilche
* Simplified some CRangeMap code.
*
* Revision 1.9  2001/01/11 15:00:39  vasilche
* Added CIntervalTree for seraching on set of intervals.
*
* Revision 1.8  2001/01/05 20:08:53  vasilche
* Added util directory for various algorithms and utility classes.
*
* Revision 1.7  2001/01/05 16:29:02  vasilche
* Fixed incompatibility with MIPS C++ compiler.
*
* Revision 1.6  2001/01/05 13:59:04  vasilche
* Reduced CRangeMap* templates size.
* Added CRangeMultimap template.
*
* Revision 1.5  2001/01/03 21:29:41  vasilche
* Fixed wrong typedef.
*
* Revision 1.4  2001/01/03 18:58:39  vasilche
* Some typedefs are missing on MSVC.
*
* Revision 1.3  2001/01/03 16:39:18  vasilche
* Added CAbstractObjectManager - stub for object manager.
* CRange extracted to separate file.
*
* Revision 1.2  2000/12/26 17:27:42  vasilche
* Implemented CRangeMap<> template for sorting Seq-loc objects.
*
* Revision 1.1  2000/12/21 21:52:41  vasilche
* Added CRangeMap<> template for sorting integral ranges (Seq-loc).
*
* ===========================================================================
*/

#endif  /* RANGEMAP__HPP */