linkedset.hpp
上传用户:yhdzpy8989
上传日期:2007-06-13
资源大小:13604k
文件大小:12k
- /*
- * ===========================================================================
- * PRODUCTION $Log: linkedset.hpp,v $
- * PRODUCTION Revision 1000.0 2003/10/29 15:30:28 gouriano
- * PRODUCTION PRODUCTION: IMPORTED [ORIGINAL] Dev-tree R1.2
- * PRODUCTION
- * ===========================================================================
- */
- #ifndef LINKEDSET__HPP
- #define LINKEDSET__HPP
- /* $Id: linkedset.hpp,v 1000.0 2003/10/29 15:30:28 gouriano Exp $
- * ===========================================================================
- *
- * PUBLIC DOMAIN NOTICE
- * National Center for Biotechnology Information
- *
- * This software/database is a "United States Government Work" under the
- * terms of the United States Copyright Act. It was written as part of
- * the author's official duties as a United States Government employee and
- * thus cannot be copyrighted. This software/database is freely available
- * to the public for use. The National Library of Medicine and the U.S.
- * Government have not placed any restriction on its use or reproduction.
- *
- * Although all reasonable efforts have been taken to ensure the accuracy
- * and reliability of the software and data, the NLM and the U.S.
- * Government do not and cannot warrant the performance or results that
- * may be obtained by using this software or data. The NLM and the U.S.
- * Government disclaim all warranties, express or implied, including
- * warranties of performance, merchantability or fitness for any particular
- * purpose.
- *
- * Please cite the author in any work or product based on this material.
- *
- * ===========================================================================
- *
- * Author: Eugene Vasilchenko
- *
- * File Description:
- * !!! PUT YOUR DESCRIPTION HERE !!!
- *
- * ---------------------------------------------------------------------------
- * $Log: linkedset.hpp,v $
- * Revision 1000.0 2003/10/29 15:30:28 gouriano
- * PRODUCTION: IMPORTED [ORIGINAL] Dev-tree R1.2
- *
- * Revision 1.2 2003/04/17 17:50:19 siyan
- * Added doxygen support
- *
- * Revision 1.1 2001/01/29 15:18:39 vasilche
- * Cleaned CRangeMap and CIntervalTree classes.
- *
- * ===========================================================================
- */
- #include <corelib/ncbistd.hpp>
- #include <set>
- /** @addtogroup LinkedSet
- *
- * @{
- */
- BEGIN_NCBI_SCOPE
- template<typename Key> struct SLinkedSetValue;
- template<typename Key> class CLinkedMultisetBase;
- template<typename Key>
- struct SLinkedSetValue
- {
- typedef Key key_type;
- typedef SLinkedSetValue<Key> value_type;
- SLinkedSetValue(const key_type& key, value_type* next = 0)
- : m_Key(key), m_Next(next)
- {
- }
- const key_type& GetKey(void) const
- {
- return m_Key;
- }
- value_type* GetNext(void)
- {
- return m_Next;
- }
- const value_type* GetNext(void) const
- {
- return m_Next;
- }
- bool operator<(const value_type& value) const
- {
- return GetKey() < value.GetKey();
- }
- private:
- friend class CLinkedMultisetBase<key_type>;
- const key_type m_Key;
- value_type* m_Next;
- };
- #if 0
- template<typename Value, typename Compare>
- class CLinkedSetBase
- {
- public:
- struct SValue
- {
- typedef Value value_type;
- Value value;
- SValue* Next(void) const
- {
- return m_Next;
- }
- private:
- friend class CLinkedSetBase<Value, Compare>;
- SValue* m_Next;
- };
- typedef set<Value, Compare> TSet;
- typedef typename TSet::iterator iterator;
- typedef typename TSet::const_iterator const_iterator;
- typedef SValue* TForwardIterator;
- CLinkedSetBase(void)
- : m_Start(0)
- {
- }
- CLinkedSetBase(Compare comp)
- : m_Set(comp), m_Start(0)
- {
- }
- bool empty(void) const
- {
- return m_Start == 0;
- }
- TForwardIterator ForwardBegin(void) const
- {
- return m_Start;
- }
- TForwardIterator ForwardEnd(void) const
- {
- return 0;
- }
- iterator begin(void)
- {
- return m_Set.begin();
- }
- iterator end(void)
- {
- return m_Set.end();
- }
- iterator find(const Value& value)
- {
- return m_Set.find(value);
- }
- iterator lower_bound(const Value& value)
- {
- return m_Set.lower_bound(value);
- }
- const_iterator begin(void) const
- {
- return m_Set.begin();
- }
- const_iterator end(void) const
- {
- return m_Set.end();
- }
- const_iterator find(const Value& value) const
- {
- return m_Set.find(value);
- }
- const_iterator lower_bound(const Value& value) const
- {
- return m_Set.lower_bound(value);
- }
- protected:
- void clear(void)
- {
- m_Start = 0;
- }
- void insertAfter(const SValue& prevValue, const SValue& newValue)
- {
- _ASSERT(!newValue.m_Next);
- newValue.m_Next = prevValue.m_Next;
- prevValue.m_Next = &newValue;
- }
- void insertToStart(const SValue& newValue)
- {
- _ASSERT(!newValue.m_Next);
- newValue.m_Next = m_Start;
- m_Start = &newValue;
- }
- void removeAfter(const SValue& prevValue, const SValue& value)
- {
- prevValue.m_Next = value.m_Next;
-
- }
- void removeFromStart(const SValue& value)
- {
- m_Start = value.m_Next;
- }
- private:
- TSet m_Set;
- SValue* m_Start;
- };
- template<typename Mapped>
- class CLinkedSet : public CLinkedSetBase<typename Mapped::key_type>
- {
- typedef CLinkedSetBase<typename Mapped::key_type> TParent;
- public:
- typedef set<Mapped> TContainer;
- typedef typename TContainer::size_type size_type;
- typedef typename TContainer::value_type value_type;
- typedef typename TContainer::iterator iterator;
- typedef typename TContainer::const_iterator const_iterator;
-
- size_type size(void) const
- {
- return m_Container.size();
- }
- void clear(void)
- {
- m_Container.clear();
- TParent::clear();
- }
- const_iterator begin(void) const
- {
- return m_Container.begin();
- }
- const_iterator end(void) const
- {
- return m_Container.end();
- }
- const_iterator find(const value_type& value) const
- {
- return m_Container.find(value);
- }
- const_iterator lower_bound(const value_type& value) const
- {
- return m_Container.lower_bound(value);
- }
- const_iterator upper_bound(const value_type& value) const
- {
- return m_Container.upper_bound(value);
- }
- iterator begin(void)
- {
- return m_Container.begin();
- }
- iterator end(void)
- {
- return m_Container.end();
- }
- iterator find(const value_type& value)
- {
- return m_Container.find(value);
- }
- iterator lower_bound(const value_type& value)
- {
- return m_Container.lower_bound(value);
- }
- iterator upper_bound(const value_type& value)
- {
- return m_Container.upper_bound(value);
- }
- pair<iterator, bool> insert(const value_type& value)
- {
- pair<iterator, bool> ins = m_Container.insert(value);
- if ( ins.second ) {
- if ( ins.first == begin() )
- insertToStart(*ins.first);
- else {
- iterator prev = ins.first;
- insertAfter(*--prev, *ins.first);
- }
- }
- return ins;
- }
- void erase(iterator iter)
- {
- if ( iter == begin() )
- removeFromStart(*iter);
- else {
- iterator prev = iter;
- removeAfter(*--prev, *iter);
- }
- m_Container.erase(iter);
- }
- private:
- TContainer m_Container;
- };
- #endif
- template<typename Key>
- class CLinkedMultisetBase
- {
- public:
- typedef Key key_type;
- typedef SLinkedSetValue<key_type> value_type;
- CLinkedMultisetBase(void)
- : m_Start(0)
- {
- }
- bool empty(void) const
- {
- return m_Start == 0;
- }
- value_type* GetStart(void)
- {
- return m_Start;
- }
- const value_type* GetStart(void) const
- {
- return m_Start;
- }
- protected:
- void clear(void)
- {
- m_Start = 0;
- }
- void insertAfter(value_type& prevValue, value_type& newValue)
- {
- _ASSERT(!newValue.m_Next);
- newValue.m_Next = prevValue.m_Next;
- prevValue.m_Next = &newValue;
- }
- void insertToStart(value_type& newValue)
- {
- _ASSERT(!newValue.m_Next);
- newValue.m_Next = m_Start;
- m_Start = &newValue;
- }
- void removeAfter(value_type& prevValue, value_type& value)
- {
- _ASSERT(prevValue.m_Next == &value);
- prevValue.m_Next = value.m_Next;
- value.m_Next = 0;
- }
- void removeFromStart(value_type& value)
- {
- _ASSERT(m_Start == &value);
- m_Start = value.m_Next;
- value.m_Next = 0;
- }
- private:
- value_type* m_Start;
- };
- template<typename Mapped>
- class CLinkedMultiset : public CLinkedMultisetBase<typename Mapped::key_type>
- {
- typedef CLinkedMultisetBase<typename Mapped::key_type> TParent;
- public:
- typedef multiset<Mapped> TContainer;
- typedef typename TContainer::size_type size_type;
- typedef typename TContainer::value_type value_type;
- typedef typename TContainer::iterator iterator;
- typedef typename TContainer::const_iterator const_iterator;
-
- size_type size(void) const
- {
- return m_Container.size();
- }
- void clear(void)
- {
- m_Container.clear();
- TParent::clear();
- }
- const_iterator begin(void) const
- {
- return m_Container.begin();
- }
- const_iterator end(void) const
- {
- return m_Container.end();
- }
- const_iterator find(const value_type& value) const
- {
- return m_Container.find(value);
- }
- const_iterator lower_bound(const value_type& value) const
- {
- return m_Container.lower_bound(value);
- }
- const_iterator upper_bound(const value_type& value) const
- {
- return m_Container.upper_bound(value);
- }
- iterator begin(void)
- {
- return m_Container.begin();
- }
- iterator end(void)
- {
- return m_Container.end();
- }
- iterator find(const value_type& value)
- {
- return m_Container.find(value);
- }
- iterator lower_bound(const value_type& value)
- {
- return m_Container.lower_bound(value);
- }
- iterator upper_bound(const value_type& value)
- {
- return m_Container.upper_bound(value);
- }
- iterator insert(const value_type& value)
- {
- iterator iter = m_Container.insert(value);
- if ( iter == begin() )
- insertToStart(get(iter));
- else {
- iterator prev = iter;
- insertAfter(get(--prev), get(iter));
- }
- return iter;
- }
- void erase(iterator iter)
- {
- if ( iter == begin() )
- removeFromStart(get(iter));
- else {
- iterator prev = iter;
- removeAfter(get(--prev), get(iter));
- }
- m_Container.erase(iter);
- }
- static value_type& get(iterator iter)
- {
- return const_cast<value_type&>(*iter);
- }
-
- #if defined(_RWSTD_VER) && !defined(_RWSTD_STRICT_ANSI)
- size_type allocation_size(size_type buffer_size)
- {
- return m_Container.allocation_size(buffer_size);
- }
- #endif
- private:
- TContainer m_Container;
- };
- /* @} */
- //#include <util/linkedset.inl>
- END_NCBI_SCOPE
- #endif /* LINKEDSET__HPP */