linkedset.hpp
上传用户:yhdzpy8989
上传日期:2007-06-13
资源大小:13604k
文件大小:12k
源码类别:

生物技术

开发平台:

C/C++

  1. /*
  2.  * ===========================================================================
  3.  * PRODUCTION $Log: linkedset.hpp,v $
  4.  * PRODUCTION Revision 1000.0  2003/10/29 15:30:28  gouriano
  5.  * PRODUCTION PRODUCTION: IMPORTED [ORIGINAL] Dev-tree R1.2
  6.  * PRODUCTION
  7.  * ===========================================================================
  8.  */
  9. #ifndef LINKEDSET__HPP
  10. #define LINKEDSET__HPP
  11. /*  $Id: linkedset.hpp,v 1000.0 2003/10/29 15:30:28 gouriano Exp $
  12. * ===========================================================================
  13. *
  14. *                            PUBLIC DOMAIN NOTICE
  15. *               National Center for Biotechnology Information
  16. *
  17. *  This software/database is a "United States Government Work" under the
  18. *  terms of the United States Copyright Act.  It was written as part of
  19. *  the author's official duties as a United States Government employee and
  20. *  thus cannot be copyrighted.  This software/database is freely available
  21. *  to the public for use. The National Library of Medicine and the U.S.
  22. *  Government have not placed any restriction on its use or reproduction.
  23. *
  24. *  Although all reasonable efforts have been taken to ensure the accuracy
  25. *  and reliability of the software and data, the NLM and the U.S.
  26. *  Government do not and cannot warrant the performance or results that
  27. *  may be obtained by using this software or data. The NLM and the U.S.
  28. *  Government disclaim all warranties, express or implied, including
  29. *  warranties of performance, merchantability or fitness for any particular
  30. *  purpose.
  31. *
  32. *  Please cite the author in any work or product based on this material.
  33. *
  34. * ===========================================================================
  35. *
  36. * Author: Eugene Vasilchenko
  37. *
  38. * File Description:
  39. *   !!! PUT YOUR DESCRIPTION HERE !!!
  40. *
  41. * ---------------------------------------------------------------------------
  42. * $Log: linkedset.hpp,v $
  43. * Revision 1000.0  2003/10/29 15:30:28  gouriano
  44. * PRODUCTION: IMPORTED [ORIGINAL] Dev-tree R1.2
  45. *
  46. * Revision 1.2  2003/04/17 17:50:19  siyan
  47. * Added doxygen support
  48. *
  49. * Revision 1.1  2001/01/29 15:18:39  vasilche
  50. * Cleaned CRangeMap and CIntervalTree classes.
  51. *
  52. * ===========================================================================
  53. */
  54. #include <corelib/ncbistd.hpp>
  55. #include <set>
  56. /** @addtogroup LinkedSet
  57.  *
  58.  * @{
  59.  */
  60. BEGIN_NCBI_SCOPE
  61. template<typename Key> struct SLinkedSetValue;
  62. template<typename Key> class CLinkedMultisetBase;
  63. template<typename Key>
  64. struct SLinkedSetValue
  65. {
  66.     typedef Key key_type;
  67.     typedef SLinkedSetValue<Key> value_type;
  68.     SLinkedSetValue(const key_type& key, value_type* next = 0)
  69.         : m_Key(key), m_Next(next)
  70.         {
  71.         }
  72.     const key_type& GetKey(void) const
  73.         {
  74.             return m_Key;
  75.         }
  76.     value_type* GetNext(void)
  77.         {
  78.             return m_Next;
  79.         }
  80.     const value_type* GetNext(void) const
  81.         {
  82.             return m_Next;
  83.         }
  84.     bool operator<(const value_type& value) const
  85.         {
  86.             return GetKey() < value.GetKey();
  87.         }
  88. private:
  89.     friend class CLinkedMultisetBase<key_type>;
  90.     const key_type m_Key;
  91.     value_type* m_Next;
  92. };
  93. #if 0
  94. template<typename Value, typename Compare>
  95. class CLinkedSetBase
  96. {
  97. public:
  98.     struct SValue
  99.     {
  100.         typedef Value value_type;
  101.         Value value;
  102.         SValue* Next(void) const
  103.             {
  104.                 return m_Next;
  105.             }
  106.     private:
  107.         friend class CLinkedSetBase<Value, Compare>;
  108.         SValue* m_Next;
  109.     };
  110.     typedef set<Value, Compare> TSet;
  111.     typedef typename TSet::iterator iterator;
  112.     typedef typename TSet::const_iterator const_iterator;
  113.     typedef SValue* TForwardIterator;
  114.     CLinkedSetBase(void)
  115.         : m_Start(0)
  116.         {
  117.         }
  118.     CLinkedSetBase(Compare comp)
  119.         : m_Set(comp), m_Start(0)
  120.         {
  121.         }
  122.     bool empty(void) const
  123.         {
  124.             return m_Start == 0;
  125.         }
  126.     TForwardIterator ForwardBegin(void) const
  127.         {
  128.             return m_Start;
  129.         }
  130.     TForwardIterator ForwardEnd(void) const
  131.         {
  132.             return 0;
  133.         }
  134.     iterator begin(void)
  135.         {
  136.             return m_Set.begin();
  137.         }
  138.     iterator end(void)
  139.         {
  140.             return m_Set.end();
  141.         }
  142.     iterator find(const Value& value)
  143.         {
  144.             return m_Set.find(value);
  145.         }
  146.     iterator lower_bound(const Value& value)
  147.         {
  148.             return m_Set.lower_bound(value);
  149.         }
  150.     const_iterator begin(void) const
  151.         {
  152.             return m_Set.begin();
  153.         }
  154.     const_iterator end(void) const
  155.         {
  156.             return m_Set.end();
  157.         }
  158.     const_iterator find(const Value& value) const
  159.         {
  160.             return m_Set.find(value);
  161.         }
  162.     const_iterator lower_bound(const Value& value) const
  163.         {
  164.             return m_Set.lower_bound(value);
  165.         }
  166. protected:
  167.     void clear(void)
  168.         {
  169.             m_Start = 0;
  170.         }
  171.     void insertAfter(const SValue& prevValue, const SValue& newValue)
  172.         {
  173.             _ASSERT(!newValue.m_Next);
  174.             newValue.m_Next = prevValue.m_Next;
  175.             prevValue.m_Next = &newValue;
  176.         }
  177.     void insertToStart(const SValue& newValue)
  178.         {
  179.             _ASSERT(!newValue.m_Next);
  180.             newValue.m_Next = m_Start;
  181.             m_Start = &newValue;
  182.         }
  183.     void removeAfter(const SValue& prevValue, const SValue& value)
  184.         {
  185.             prevValue.m_Next = value.m_Next;
  186.             
  187.         }
  188.     void removeFromStart(const SValue& value)
  189.         {
  190.             m_Start = value.m_Next;
  191.         }
  192. private:
  193.     TSet m_Set;
  194.     SValue* m_Start;
  195. };
  196. template<typename Mapped>
  197. class CLinkedSet : public CLinkedSetBase<typename Mapped::key_type>
  198. {
  199.     typedef CLinkedSetBase<typename Mapped::key_type> TParent;
  200. public:
  201.     typedef set<Mapped> TContainer;
  202.     typedef typename TContainer::size_type size_type;
  203.     typedef typename TContainer::value_type value_type;
  204.     typedef typename TContainer::iterator iterator;
  205.     typedef typename TContainer::const_iterator const_iterator;
  206.     
  207.     size_type size(void) const
  208.         {
  209.             return m_Container.size();
  210.         }
  211.     void clear(void)
  212.         {
  213.             m_Container.clear();
  214.             TParent::clear();
  215.         }
  216.     const_iterator begin(void) const
  217.         {
  218.             return m_Container.begin();
  219.         }
  220.     const_iterator end(void) const
  221.         {
  222.             return m_Container.end();
  223.         }
  224.     const_iterator find(const value_type& value) const
  225.         {
  226.             return m_Container.find(value);
  227.         }
  228.     const_iterator lower_bound(const value_type& value) const
  229.         {
  230.             return m_Container.lower_bound(value);
  231.         }
  232.     const_iterator upper_bound(const value_type& value) const
  233.         {
  234.             return m_Container.upper_bound(value);
  235.         }
  236.     iterator begin(void)
  237.         {
  238.             return m_Container.begin();
  239.         }
  240.     iterator end(void)
  241.         {
  242.             return m_Container.end();
  243.         }
  244.     iterator find(const value_type& value)
  245.         {
  246.             return m_Container.find(value);
  247.         }
  248.     iterator lower_bound(const value_type& value)
  249.         {
  250.             return m_Container.lower_bound(value);
  251.         }
  252.     iterator upper_bound(const value_type& value)
  253.         {
  254.             return m_Container.upper_bound(value);
  255.         }
  256.     pair<iterator, bool> insert(const value_type& value)
  257.         {
  258.             pair<iterator, bool> ins = m_Container.insert(value);
  259.             if ( ins.second ) {
  260.                 if ( ins.first == begin() )
  261.                     insertToStart(*ins.first);
  262.                 else {
  263.                     iterator prev = ins.first;
  264.                     insertAfter(*--prev, *ins.first);
  265.                 }
  266.             }
  267.             return ins;
  268.         }
  269.     void erase(iterator iter)
  270.         {
  271.             if ( iter == begin() )
  272.                 removeFromStart(*iter);
  273.             else {
  274.                 iterator prev = iter;
  275.                 removeAfter(*--prev, *iter);
  276.             }
  277.             m_Container.erase(iter);
  278.         }
  279. private:
  280.     TContainer m_Container;
  281. };
  282. #endif
  283. template<typename Key>
  284. class CLinkedMultisetBase
  285. {
  286. public:
  287.     typedef Key key_type;
  288.     typedef SLinkedSetValue<key_type> value_type;
  289.     CLinkedMultisetBase(void)
  290.         : m_Start(0)
  291.         {
  292.         }
  293.     bool empty(void) const
  294.         {
  295.             return m_Start == 0;
  296.         }
  297.     value_type* GetStart(void)
  298.         {
  299.             return m_Start;
  300.         }
  301.     const value_type* GetStart(void) const
  302.         {
  303.             return m_Start;
  304.         }
  305. protected:
  306.     void clear(void)
  307.         {
  308.             m_Start = 0;
  309.         }
  310.     void insertAfter(value_type& prevValue, value_type& newValue)
  311.         {
  312.             _ASSERT(!newValue.m_Next);
  313.             newValue.m_Next = prevValue.m_Next;
  314.             prevValue.m_Next = &newValue;
  315.         }
  316.     void insertToStart(value_type& newValue)
  317.         {
  318.             _ASSERT(!newValue.m_Next);
  319.             newValue.m_Next = m_Start;
  320.             m_Start = &newValue;
  321.         }
  322.     void removeAfter(value_type& prevValue, value_type& value)
  323.         {
  324.             _ASSERT(prevValue.m_Next == &value);
  325.             prevValue.m_Next = value.m_Next;
  326.             value.m_Next = 0;
  327.         }
  328.     void removeFromStart(value_type& value)
  329.         {
  330.             _ASSERT(m_Start == &value);
  331.             m_Start = value.m_Next;
  332.             value.m_Next = 0;
  333.         }
  334. private:
  335.     value_type* m_Start;
  336. };
  337. template<typename Mapped>
  338. class CLinkedMultiset : public CLinkedMultisetBase<typename Mapped::key_type>
  339. {
  340.     typedef CLinkedMultisetBase<typename Mapped::key_type> TParent;
  341. public:
  342.     typedef multiset<Mapped> TContainer;
  343.     typedef typename TContainer::size_type size_type;
  344.     typedef typename TContainer::value_type value_type;
  345.     typedef typename TContainer::iterator iterator;
  346.     typedef typename TContainer::const_iterator const_iterator;
  347.     
  348.     size_type size(void) const
  349.         {
  350.             return m_Container.size();
  351.         }
  352.     void clear(void)
  353.         {
  354.             m_Container.clear();
  355.             TParent::clear();
  356.         }
  357.     const_iterator begin(void) const
  358.         {
  359.             return m_Container.begin();
  360.         }
  361.     const_iterator end(void) const
  362.         {
  363.             return m_Container.end();
  364.         }
  365.     const_iterator find(const value_type& value) const
  366.         {
  367.             return m_Container.find(value);
  368.         }
  369.     const_iterator lower_bound(const value_type& value) const
  370.         {
  371.             return m_Container.lower_bound(value);
  372.         }
  373.     const_iterator upper_bound(const value_type& value) const
  374.         {
  375.             return m_Container.upper_bound(value);
  376.         }
  377.     iterator begin(void)
  378.         {
  379.             return m_Container.begin();
  380.         }
  381.     iterator end(void)
  382.         {
  383.             return m_Container.end();
  384.         }
  385.     iterator find(const value_type& value)
  386.         {
  387.             return m_Container.find(value);
  388.         }
  389.     iterator lower_bound(const value_type& value)
  390.         {
  391.             return m_Container.lower_bound(value);
  392.         }
  393.     iterator upper_bound(const value_type& value)
  394.         {
  395.             return m_Container.upper_bound(value);
  396.         }
  397.     iterator insert(const value_type& value)
  398.         {
  399.             iterator iter = m_Container.insert(value);
  400.             if ( iter == begin() )
  401.                 insertToStart(get(iter));
  402.             else {
  403.                 iterator prev = iter;
  404.                 insertAfter(get(--prev), get(iter));
  405.             }
  406.             return iter;
  407.         }
  408.     void erase(iterator iter)
  409.         {
  410.             if ( iter == begin() )
  411.                 removeFromStart(get(iter));
  412.             else {
  413.                 iterator prev = iter;
  414.                 removeAfter(get(--prev), get(iter));
  415.             }
  416.             m_Container.erase(iter);
  417.         }
  418.     static value_type& get(iterator iter)
  419.         {
  420.             return const_cast<value_type&>(*iter);
  421.         }
  422.     
  423. #if defined(_RWSTD_VER) && !defined(_RWSTD_STRICT_ANSI)
  424.     size_type allocation_size(size_type buffer_size)
  425.         {
  426.             return m_Container.allocation_size(buffer_size);
  427.         }
  428. #endif
  429. private:
  430.     TContainer m_Container;
  431. };
  432. /* @} */
  433. //#include <util/linkedset.inl>
  434. END_NCBI_SCOPE
  435. #endif  /* LINKEDSET__HPP */