开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 数值算法/人工智能 > 生物技术 > 查看源码
itree.hpp
资源名称：ncbi_cxx_win--Jul_08_2004.zip　[点击查看]
上传用户：yhdzpy8989
上传日期：2007-06-13
资源大小：13604k
文件大小：15k
源码类别：

生物技术

开发平台：

C/C++

itree.hpp：源码内容
  1. /*
  2.  * ===========================================================================
  3.  * PRODUCTION $Log: itree.hpp,v $
  4.  * PRODUCTION Revision 1000.0  2003/10/29 15:29:42  gouriano
  5.  * PRODUCTION PRODUCTION: IMPORTED [ORIGINAL] Dev-tree R1.6
  6.  * PRODUCTION
  7.  * ===========================================================================
  8.  */
  10. #ifndef ITREE__HPP
  11. #define ITREE__HPP
  13. /*  $Id: itree.hpp,v 1000.0 2003/10/29 15:29:42 gouriano Exp $
  14. * ===========================================================================
  15. *
  16. *                            PUBLIC DOMAIN NOTICE
  17. *               National Center for Biotechnology Information
  18. *
  19. *  This software/database is a "United States Government Work" under the
  20. *  terms of the United States Copyright Act.  It was written as part of
  21. *  the author's official duties as a United States Government employee and
  22. *  thus cannot be copyrighted.  This software/database is freely available
  23. *  to the public for use. The National Library of Medicine and the U.S.
  24. *  Government have not placed any restriction on its use or reproduction.
  25. *
  26. *  Although all reasonable efforts have been taken to ensure the accuracy
  27. *  and reliability of the software and data, the NLM and the U.S.
  28. *  Government do not and cannot warrant the performance or results that
  29. *  may be obtained by using this software or data. The NLM and the U.S.
  30. *  Government disclaim all warranties, express or implied, including
  31. *  warranties of performance, merchantability or fitness for any particular
  32. *  purpose.
  33. *
  34. *  Please cite the author in any work or product based on this material.
  35. *
  36. * ===========================================================================
  37. *
  38. * Author: Eugene Vasilchenko
  39. *
  40. * File Description:
  41. *   Implementation of interval search tree based on McCreight's algorithm.
  42. *
  43. * ===========================================================================
  44. */
  46. #include <corelib/ncbistd.hpp>
  47. #include <corelib/ncbiobj.hpp>
  48. #include <corelib/ncbiutil.hpp>
  49. #include <corelib/ncbi_limits.hpp>
  50. #include <util/range.hpp>
  51. #include <util/linkedset.hpp>
  54. /** @addtogroup IntervalTree
  55.  *
  56.  * @{
  57.  */
  60. BEGIN_NCBI_SCOPE
  62. // forward declarations
  63. class CIntervalTreeTraits;
  64. template<class Traits> class CIntervalTreeConstIteratorTraits;
  65. template<class Traits> class CIntervalTreeIteratorTraits;
  67. class CIntervalTree;
  69. template<class Traits> struct SIntervalTreeNode;
  70. template<class Traits> struct SIntervalTreeNodeIntervals;
  71. template<class Traits> class CIntervalTreeIterator;
  73. // parameter class for CIntervalTree
  74. class NCBI_XUTIL_EXPORT CIntervalTreeTraits
  75. {
  76. public:
  77.     typedef CIntervalTreeTraits TTraits;
  78.     typedef CIntervalTreeIteratorTraits<TTraits> TIteratorTraits;
  79.     typedef CIntervalTreeConstIteratorTraits<TTraits> TConstIteratorTraits;
  81.     typedef CIntervalTree TMap;
  82.     typedef CIntervalTreeIterator<TIteratorTraits> TNCIterator;
  84.     typedef int coordinate_type;
  85.     typedef CRange<coordinate_type> interval_type;
  86.     typedef CConstRef<CObject> mapped_type;
  88.     typedef SLinkedSetValue<coordinate_type> TMapValue;
  89.     struct STreeMapValue : public TMapValue
  90.     {
  91.         STreeMapValue(coordinate_type key, coordinate_type y,
  92.                       const mapped_type& value)
  93.             : TMapValue(key), m_Y(y), m_Value(value)
  94.             {
  95.             }
  97.         coordinate_type m_Y;
  98.         mapped_type m_Value;
  100.         interval_type GetInterval(void) const
  101.             {
  102.                 return interval_type(GetKey(), m_Y);
  103.             }
  104.     };
  105.     typedef STreeMapValue TTreeMapValue;
  106.     typedef CLinkedMultiset<TTreeMapValue> TTreeMap;
  107.     typedef TTreeMap::iterator TTreeMapI;
  108.     typedef TTreeMap::const_iterator TTreeMapCI;
  110.     struct SNodeMapValue : public TMapValue
  111.     {
  112.         SNodeMapValue(coordinate_type key, TTreeMapI value)
  113.             : TMapValue(key), m_Value(value)
  114.             {
  115.             }
  117.         TTreeMapI m_Value;
  118.     };
  119.     typedef SNodeMapValue TNodeMapValue;
  120.     typedef CLinkedMultiset<TNodeMapValue> TNodeMap;
  121.     typedef TNodeMap::iterator TNodeMapI;
  122.     typedef TNodeMap::const_iterator TNodeMapCI;
  124.     typedef SIntervalTreeNode<TTraits> TTreeNode;
  125.     typedef SIntervalTreeNodeIntervals<TTraits> TTreeNodeInts;
  127.     static coordinate_type GetMax(void);
  128.     static coordinate_type GetMaxCoordinate(void);
  129.     static bool IsNormal(const interval_type& interval);
  130. };
  132. // parameter class for CIntervalTree
  133. template<class Traits>
  134. class CIntervalTreeIteratorTraits : public Traits
  135. {
  136.     typedef Traits TParent;
  137. public:
  138.     typedef TParent TTreeTraits;
  140.     typedef typename TParent::mapped_type& reference;
  142.     typedef typename TParent::TTreeNode* TTreeNodeP;
  143.     typedef typename TParent::TTreeNodeInts* TTreeNodeIntsP;
  144.     typedef typename TParent::TMapValue* TMapValueP;
  145.     typedef typename TParent::TTreeMapValue* TTreeMapValueP;
  146.     typedef typename TParent::TNodeMapValue* TNodeMapValueP;
  147. };
  149. template<class Traits>
  150. class CIntervalTreeConstIteratorTraits : public Traits
  151. {
  152.     typedef Traits TParent;
  153. public:
  154.     typedef TParent TTreeTraits;
  156.     typedef const typename TParent::mapped_type& reference;
  158.     typedef const typename TParent::TTreeNode* TTreeNodeP;
  159.     typedef const typename TParent::TTreeNodeInts* TTreeNodeIntsP;
  160.     typedef const typename TParent::TMapValue* TMapValueP;
  161.     typedef const typename TParent::TTreeMapValue* TTreeMapValueP;
  162.     typedef const typename TParent::TNodeMapValue* TNodeMapValueP;
  163. };
  165. // interval search tree structures
  166. template<typename Traits>
  167. struct SIntervalTreeNode
  168. {
  169.     typedef Traits TTraits;
  170.     typedef typename TTraits::coordinate_type coordinate_type;
  171.     typedef typename TTraits::interval_type interval_type;
  172.     typedef typename TTraits::mapped_type mapped_type;
  174.     typedef typename TTraits::TTreeNode TTreeNode;
  175.     typedef typename TTraits::TTreeNodeInts TTreeNodeInts;
  177.     coordinate_type m_Key;
  179.     TTreeNode* m_Left;
  180.     TTreeNode* m_Right;
  182.     TTreeNodeInts* m_NodeIntervals;
  183. };
  185. template<typename Traits>
  186. struct SIntervalTreeNodeIntervals
  187. {
  188.     typedef Traits TTraits;
  189.     typedef typename TTraits::coordinate_type coordinate_type;
  190.     typedef typename TTraits::interval_type interval_type;
  191.     typedef typename TTraits::mapped_type mapped_type;
  193.     typedef typename TTraits::TTreeNode TTreeNode;
  194.     typedef typename TTraits::TTreeNodeInts TTreeNodeInts;
  196.     typedef typename TTraits::TNodeMap TNodeMap;
  197.     typedef typename TTraits::TNodeMapValue TNodeMapValue;
  198.     typedef typename TTraits::TNodeMapI TNodeMapI;
  199.     typedef typename TTraits::TTreeMapI TTreeMapI;
  201.     bool Empty(void) const;
  202.     
  203.     void Insert(const interval_type& interval, TTreeMapI value);
  204.     bool Delete(const interval_type& interval, TTreeMapI value);
  206.     static void Delete(TNodeMap& m, const TNodeMapValue& v);
  207.     
  208.     TNodeMap m_ByX;
  209.     TNodeMap m_ByY;
  210. };
  212. template<class Traits>
  213. class CIntervalTreeIterator
  214. {
  215. public:
  216.     typedef Traits TTraits;
  217.     typedef CIntervalTreeIterator<TTraits> TThis;
  219.     typedef typename TTraits::coordinate_type coordinate_type;
  220.     typedef typename TTraits::interval_type interval_type;
  221.     typedef typename TTraits::reference reference;
  223.     typedef typename TTraits::TMapValueP TMapValueP;
  224.     typedef typename TTraits::TTreeMapValueP TTreeMapValueP;
  225.     typedef typename TTraits::TNodeMapValueP TNodeMapValueP;
  227.     typedef typename TTraits::TTreeNodeP TTreeNodeP;
  228.     typedef typename TTraits::TTreeNodeIntsP TTreeNodeIntsP;
  230.     typedef typename TTraits::TMap TMap;
  231.     typedef typename TTraits::TNCIterator TNCIterator;
  233.     CIntervalTreeIterator(coordinate_type search_x = 0,
  234.                           coordinate_type searchLimit = 0,
  235.                           TMapValueP currentMapValue = 0,
  236.                           TTreeNodeP nextNode = 0);
  237.     CIntervalTreeIterator(const TNCIterator& iter);
  239.     bool Valid(void) const;
  240.     operator bool(void) const;
  241.     bool operator!(void) const;
  243.     void Next(void);
  244.     TThis& operator++(void);
  246.     // get current state
  247.     interval_type GetInterval(void) const;
  249.     reference GetValue(void) const;
  251. protected:
  252.     bool InAuxMap(void) const;
  254.     friend class CIntervalTree;
  256.     TTreeMapValueP GetTreeMapValue(void) const;
  258.     void NextLevel(void);
  260. private:
  261.     // iterator can be in four states:
  262.     // 1. scanning auxList
  263.     //      m_SearchX == X of search interval (>= 0)
  264.     //      m_SearchLimit == Y of search interval (> X)
  265.     //      m_CurrentMapValue = current node in AuxMap (!= 0)
  266.     //      m_NextNode == root node pointer (!= 0)
  267.     // 2. scanning node by X
  268.     //      m_SearchX == X of search interval (>= 0)
  269.     //      m_SearchLimit == X of search interval (>= 0)
  270.     //      m_CurrentMapValue = current node in NodeMap (!= 0)
  271.     //      m_NextNode == next node pointer (may be 0)
  272.     // 3. scanning node by Y
  273.     //      m_SearchX == X of search interval (>= 0)
  274.     //      m_SearchLimit = -X of search interval (<= 0)
  275.     //      m_CurrentMapValue = current node in NodeMap (!= 0)
  276.     //      m_NextNode == next node pointer (may be 0)
  277.     // 4. end of scan
  278.     //      m_CurrentMapValue == 0
  280.     // So state determination will be:
  281.     // if ( m_CurrentMapValue == 0 ) state = END
  282.     // else if ( m_SearchLimit > m_SearchX ) state = AUX
  283.     // else if ( m_SearchLimit >= 0 ) state = NODE_BY_X
  284.     // else state = NODE_BY_Y
  286.     coordinate_type m_SearchX;
  287.     coordinate_type m_SearchLimit;
  288.     TMapValueP m_CurrentMapValue;
  289.     TTreeNodeP m_NextNode;
  290. };
  292. // deal with intervals with coordinates in range [0, max], where max is
  293. // CIntervalTree constructor argument.
  294. class NCBI_XUTIL_EXPORT CIntervalTree
  295. {
  296. public:
  297.     typedef CIntervalTreeTraits TTraits;
  298.     typedef TTraits::TIteratorTraits TIteratorTraits;
  299.     typedef TTraits::TConstIteratorTraits TConstIteratorTraits;
  301.     typedef size_t size_type;
  302.     typedef TTraits::coordinate_type coordinate_type;
  303.     typedef TTraits::interval_type interval_type;
  304.     typedef TTraits::mapped_type mapped_type;
  306.     typedef TTraits::TTreeMap TTreeMap;
  307.     typedef TTraits::TTreeMapI TTreeMapI;
  308.     typedef TTraits::TTreeMapCI TTreeMapCI;
  309.     typedef TTraits::TTreeMapValue TTreeMapValue;
  311.     typedef TTraits::TTreeNode TTreeNode;
  312.     typedef TTraits::TTreeNodeInts TTreeNodeInts;
  314.     typedef CIntervalTreeIterator<TIteratorTraits> iterator;
  315.     typedef CIntervalTreeIterator<TConstIteratorTraits> const_iterator;
  317.     CIntervalTree(void);
  318.     ~CIntervalTree(void);
  320.     // check state of tree
  321.     bool Empty(void) const;
  322.     size_type Size(void) const;
  323.     pair<double, size_type> Stat(void) const;
  325.     // remove all elements
  326.     void Clear(void);
  328.     // insert
  329.     iterator Insert(const interval_type& interval, const mapped_type& value);
  331.     // set value in tree independently of old value in slot
  332.     // return true if element was added to tree
  333.     bool Set(const interval_type& interval, const mapped_type& value);
  334.     // remove value from tree independently of old value in slot
  335.     // return true if id element was removed from tree
  336.     bool Reset(const interval_type& interval);
  338.     // add new value to tree, throw runtime_error if this slot is not empty
  339.     void Add(const interval_type& interval, const mapped_type& value);
  340.     // replace old value in tree, throw runtime_error if this slot is empty
  341.     void Replace(const interval_type& interval, const mapped_type& value);
  342.     // delete existing value from tree, throw runtime_error if slot is empty
  343.     void Delete(const interval_type& interval);
  345.     // versions of methods without throwing runtime_error
  346.     // add new value to tree, return false if this slot is not empty
  347.     bool Add(const interval_type& interval, const mapped_type& value,
  348.              const nothrow_t&);
  349.     // replace old value in tree, return false if this slot is empty
  350.     bool Replace(const interval_type& interval, const mapped_type& value,
  351.                  const nothrow_t&);
  352.     // delete existing value from tree, return false if slot is empty
  353.     bool Delete(const interval_type& interval,
  354.                 const nothrow_t&);
  356.     // end
  357.     const_iterator End(void) const;
  358.     iterator End(void);
  360.     // find
  361.     const_iterator Find(void) const;
  362.     iterator Find(void);
  364.     // list intervals containing specified point
  365.     const_iterator AllIntervals(void) const;
  366.     iterator AllIntervals(void);
  367.     // list intervals containing specified point
  368.     const_iterator IntervalsContaining(coordinate_type point) const;
  369.     iterator IntervalsContaining(coordinate_type point);
  370.     // list intervals overlapping with specified interval
  371.     const_iterator IntervalsOverlapping(const interval_type& interval) const;
  372.     iterator IntervalsOverlapping(const interval_type& interval);
  374.     static void Assign(const_iterator& dst, const iterator& src);
  375.     static void Assign(iterator& dst, const iterator& src);
  377. private:
  378.     void Init(void);
  379.     void Destroy(void);
  381.     struct SStat {
  382.         size_type count;
  383.         size_type total;
  384.         size_type max;
  385.     };
  386.     void Stat(const TTreeNode* node, SStat& stat) const;
  388.     void DoInsert(const interval_type& interval, TTreeMapI value);
  389.     bool DoDelete(TTreeNode* node, const interval_type& interval, TTreeMapI value);
  391.     // root managing
  392.     coordinate_type GetMaxRootCoordinate(void) const;
  393.     coordinate_type GetNextRootKey(void) const;
  395.     // node allocation
  396.     TTreeNode* AllocNode(void);
  397.     void DeallocNode(TTreeNode* node);
  399.     // node creation/deletion
  400.     TTreeNode* InitNode(TTreeNode* node, coordinate_type key) const;
  401.     void ClearNode(TTreeNode* node);
  402.     void DeleteNode(TTreeNode* node);
  404.     // node intervals allocation
  405.     TTreeNodeInts* AllocNodeIntervals(void);
  406.     void DeallocNodeIntervals(TTreeNodeInts* nodeIntervals);
  408.     // node intervals creation/deletion
  409.     TTreeNodeInts* CreateNodeIntervals(void);
  410.     void DeleteNodeIntervals(TTreeNodeInts* nodeIntervals);
  412.     TTreeNode m_Root;
  413.     TTreeMap m_ByX;
  415. #if defined(_RWSTD_VER) && !defined(_RWSTD_ALLOCATOR)
  416.     // BW_1: non standard Sun's allocators
  417.     typedef allocator_interface<allocator<TTreeNode>,TTreeNode> TNodeAllocator;
  418.     typedef allocator_interface<allocator<TTreeNodeInts>,TTreeNodeInts> TNodeIntervalsAllocator;
  419. #else
  420.     typedef allocator<TTreeNode> TNodeAllocator;
  421.     typedef allocator<TTreeNodeInts> TNodeIntervalsAllocator;
  422. #endif
  424.     TNodeAllocator m_NodeAllocator;
  425.     TNodeIntervalsAllocator m_NodeIntervalsAllocator;
  426. };
  429. /* @} */
  432. #include <util/itree.inl>
  434. END_NCBI_SCOPE
  436. /*
  437. * ---------------------------------------------------------------------------
  438. * $Log: itree.hpp,v $
  439. * Revision 1000.0  2003/10/29 15:29:42  gouriano
  440. * PRODUCTION: IMPORTED [ORIGINAL] Dev-tree R1.6
  441. *
  442. * Revision 1.6  2003/04/17 17:50:16  siyan
  443. * Added doxygen support
  444. *
  445. * Revision 1.5  2003/02/07 16:54:01  vasilche
  446. * Pass all structures with size > sizeof int by reference.
  447. * Move cvs log to the end of files.
  448. *
  449. * Revision 1.4  2002/12/19 14:51:00  dicuccio
  450. * Added export specifier for Win32 DLL builds.
  451. *
  452. * Revision 1.3  2001/05/17 15:01:19  lavr
  453. * Typos corrected
  454. *
  455. * Revision 1.2  2001/01/29 15:18:38  vasilche
  456. * Cleaned CRangeMap and CIntervalTree classes.
  457. *
  458. * Revision 1.1  2001/01/11 15:00:37  vasilche
  459. * Added CIntervalTree for seraching on set of intervals.
  460. *
  461. * ===========================================================================
  462. */
  464. #endif  /* ITREE__HPP */