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

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

生物技术

开发平台：

C/C++

itree.inl：源码内容
  1. /*
  2.  * ===========================================================================
  3.  * PRODUCTION $Log: itree.inl,v $
  4.  * PRODUCTION Revision 1000.0  2003/10/29 15:29:49  gouriano
  5.  * PRODUCTION PRODUCTION: IMPORTED [ORIGINAL] Dev-tree R1.6
  6.  * PRODUCTION
  7.  * ===========================================================================
  8.  */
  10. #if defined(ITREE__HPP)  &&  !defined(ITREE__INL)
  11. #define ITREE__INL
  13. /*  $Id: itree.inl,v 1000.0 2003/10/29 15:29:49 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. *   Inline methods of interval search tree.
  42. *
  43. * ===========================================================================
  44. */
  46. inline
  47. CIntervalTreeTraits::coordinate_type
  48. CIntervalTreeTraits::GetMax(void)
  49. {
  50.     return interval_type::GetPositionMax();
  51. }
  53. inline
  54. CIntervalTreeTraits::coordinate_type
  55. CIntervalTreeTraits::GetMaxCoordinate(void)
  56. {
  57.     return GetMax() - 1;
  58. }
  60. inline
  61. bool CIntervalTreeTraits::IsNormal(const interval_type& interval)
  62. {
  63.     return interval.GetFrom() >= 0 &&
  64.         interval.GetFrom() <= interval.GetTo() &&
  65.         interval.GetTo() <= GetMaxCoordinate();
  66. }
  68. template<typename Traits>
  69. inline
  70. CIntervalTreeIterator<Traits>::CIntervalTreeIterator(coordinate_type search_x,
  71.                                                      coordinate_type searchLimit,
  72.                                                      TMapValueP currentMapValue,
  73.                                                      TTreeNodeP nextNode)
  74.     : m_SearchX(search_x),
  75.       m_SearchLimit(searchLimit),
  76.       m_CurrentMapValue(currentMapValue),
  77.       m_NextNode(nextNode)
  78. {
  79. }
  81. template<typename Traits>
  82. inline
  83. CIntervalTreeIterator<Traits>::CIntervalTreeIterator(const TNCIterator& iter)
  84. {
  85.     TMap::Assign(*this, iter);
  86. }
  88. template<typename Traits>
  89. inline
  90. bool CIntervalTreeIterator<Traits>::Valid(void) const
  91. {
  92.     return m_CurrentMapValue != 0;
  93. }
  95. template<typename Traits>
  96. inline
  97. bool CIntervalTreeIterator<Traits>::InAuxMap(void) const
  98. {
  99.     return m_SearchLimit > m_SearchX;
  100. }
  102. template<typename Traits>
  103. inline
  104. CIntervalTreeIterator<Traits>::operator bool(void) const
  105. {
  106.     return Valid();
  107. }
  109. template<typename Traits>
  110. inline
  111. bool CIntervalTreeIterator<Traits>::operator!(void) const
  112. {
  113.     return !Valid();
  114. }
  116. template<typename Traits>
  117. inline
  118. typename CIntervalTreeIterator<Traits>::TTreeMapValueP
  119. CIntervalTreeIterator<Traits>::GetTreeMapValue(void) const
  120. {
  121.     if ( InAuxMap() )
  122.         return static_cast<TTreeMapValueP>(m_CurrentMapValue);
  123.     else
  124.         return &*static_cast<TNodeMapValueP>(m_CurrentMapValue)->m_Value;
  125. }
  127. template<typename Traits>
  128. inline
  129. void CIntervalTreeIterator<Traits>::Next(void)
  130. {
  131.     TMapValueP newMapValue = m_CurrentMapValue->GetNext();
  132.     if ( newMapValue && newMapValue->GetKey() <= m_SearchLimit )
  133.         m_CurrentMapValue = newMapValue;
  134.     else
  135.         NextLevel();
  136. }
  138. template<typename Traits>
  139. inline
  140. typename CIntervalTreeIterator<Traits>::interval_type
  141. CIntervalTreeIterator<Traits>::GetInterval(void) const
  142. {
  143.     return GetTreeMapValue()->GetInterval();
  144. }
  146. template<typename Traits>
  147. inline
  148. CIntervalTreeIterator<Traits>& CIntervalTreeIterator<Traits>::operator++(void)
  149. {
  150.     Next();
  151.     return *this;
  152. }
  154. template<typename Traits>
  155. inline
  156. typename CIntervalTreeIterator<Traits>::reference
  157. CIntervalTreeIterator<Traits>::GetValue(void) const
  158. {
  159.     return *GetTreeMapValue()->m_Value;
  160. }
  162. template<typename Traits>
  163. void CIntervalTreeIterator<Traits>::NextLevel(void)
  164. {
  165.     // get iterator values
  166.     coordinate_type x = m_SearchX;
  167.     TTreeNodeP nextNode = m_NextNode;
  169.     // 
  170.     while ( nextNode ) {
  171.         // get node values
  172.         coordinate_type key = nextNode->m_Key;
  173.         TTreeNodeIntsP nodeIntervals = nextNode->m_NodeIntervals;
  175.         // new iterator values
  176.         TMapValueP firstMapValue;
  177.         coordinate_type searchLimit;
  179.         if ( x < key ) {
  180.             // by X
  181.             if ( x == key )
  182.                 nextNode = 0;
  183.             else
  184.                 nextNode = nextNode->m_Left;
  185.             if ( !nodeIntervals )
  186.                 continue; // skip this node
  187.             firstMapValue = nodeIntervals->m_ByX.GetStart();
  188.             searchLimit = x;
  189.         }
  190.         else {
  191.             // by Y
  192.             nextNode = nextNode->m_Right;
  193.             if ( !nodeIntervals )
  194.                 continue; // skip this node
  195.             firstMapValue = nodeIntervals->m_ByY.GetStart();
  196.             searchLimit = -x;
  197.         }
  199.         _ASSERT(firstMapValue);
  200.         if ( firstMapValue->GetKey() <= searchLimit ) {
  201.             m_CurrentMapValue = firstMapValue;
  202.             m_SearchLimit = searchLimit;
  203.             m_NextNode = nextNode;
  204.             return; // found
  205.         }
  206.     }
  208.     m_CurrentMapValue = 0;
  209. }
  211. template<class Traits>
  212. inline
  213. bool SIntervalTreeNodeIntervals<Traits>::Empty(void) const
  214. {
  215.     return m_ByX.empty();
  216. }
  218. template<class Traits>
  219. void SIntervalTreeNodeIntervals<Traits>::Delete(TNodeMap& m,
  220.                                                 const TNodeMapValue& value)
  221. {
  222.     TNodeMapI it = m.lower_bound(value);
  223.     _ASSERT(it != m.end());
  224.     while ( it->m_Value != value.m_Value ) {
  225.         ++it;
  226.         _ASSERT(it != m.end());
  227.         _ASSERT(it->GetKey() == value.GetKey());
  228.     }
  229.     m.erase(it);
  230. }
  232. template<class Traits>
  233. inline
  234. void SIntervalTreeNodeIntervals<Traits>::Insert(const interval_type& interval,
  235.                                                 TTreeMapI value)
  236. {
  237.     // insert interval
  238.     m_ByX.insert(TNodeMapValue(interval.GetFrom(), value));
  239.     m_ByY.insert(TNodeMapValue(-interval.GetTo(), value));
  240. }
  242. template<class Traits>
  243. inline
  244. bool SIntervalTreeNodeIntervals<Traits>::Delete(const interval_type& interval,
  245.                                                 TTreeMapI value)
  246. {
  247.     // erase interval
  248.     Delete(m_ByX, TNodeMapValue(interval.GetFrom(), value));
  249.     Delete(m_ByY, TNodeMapValue(-interval.GetTo(), value));
  250.     return Empty();
  251. }
  254. inline
  255. bool CIntervalTree::Empty(void) const
  256. {
  257.     return m_ByX.empty();
  258. }
  260. inline
  261. CIntervalTree::const_iterator
  262. CIntervalTree::End(void) const
  263. {
  264.     return const_iterator();
  265. }
  267. inline
  268. CIntervalTree::const_iterator
  269. CIntervalTree::AllIntervals(void) const
  270. {
  271.     if ( Empty() )
  272.         return End();
  274.     return const_iterator(0, TTraits::GetMaxCoordinate(), m_ByX.GetStart());
  275. }
  277. inline
  278. CIntervalTree::const_iterator
  279. CIntervalTree::IntervalsContaining(coordinate_type x) const
  280. {
  281.     const_iterator it(x, TTraits::GetMaxCoordinate(), 0, &m_Root);
  282.     it.NextLevel();
  283.     return it;
  284. }
  286. inline
  287. CIntervalTree::iterator
  288. CIntervalTree::End(void)
  289. {
  290.     return iterator();
  291. }
  293. inline
  294. CIntervalTree::iterator
  295. CIntervalTree::AllIntervals(void)
  296. {
  297.     if ( Empty() )
  298.         return End();
  300.     return iterator(0, TTraits::GetMaxCoordinate(), m_ByX.GetStart());
  301. }
  303. inline
  304. CIntervalTree::iterator
  305. CIntervalTree::IntervalsContaining(coordinate_type x)
  306. {
  307.     iterator it(x, TTraits::GetMaxCoordinate(), 0, &m_Root);
  308.     it.NextLevel();
  309.     return it;
  310. }
  312. inline
  313. void CIntervalTree::Init(void)
  314. {
  315. }
  317. inline
  318. CIntervalTree::size_type CIntervalTree::Size(void) const
  319. {
  320.     return m_ByX.size();
  321. }
  323. inline
  324. void CIntervalTree::DeleteNode(TTreeNode* node)
  325. {
  326.     if ( node ) {
  327.         ClearNode(node);
  328.         DeallocNode(node);
  329.     }
  330. }
  332. inline
  333. void CIntervalTree::Clear(void)
  334. {
  335.     Destroy();
  336.     Init();
  337. }
  339. inline
  340. CIntervalTree::TTreeNode* CIntervalTree::InitNode(TTreeNode* node,
  341.                                                   coordinate_type key) const
  342. {
  343.     node->m_Key = key;
  344.     node->m_Left = node->m_Right = 0;
  345.     node->m_NodeIntervals = 0;
  346.     return node;
  347. }
  349. inline
  350. CIntervalTree::CIntervalTree(void)
  351. {
  352.     InitNode(&m_Root, 2); // should be some power of 2
  353.     Init();
  354. }
  356. inline
  357. CIntervalTree::~CIntervalTree(void)
  358. {
  359.     Destroy();
  360. }
  362. inline
  363. void CIntervalTree::Assign(const_iterator& dst, const iterator& src)
  364. {
  365.     dst.m_SearchX = src.m_SearchX;
  366.     dst.m_SearchLimit = src.m_SearchLimit;
  367.     dst.m_CurrentMapValue = src.m_CurrentMapValue;
  368.     dst.m_NextNode = src.m_NextNode;
  369. }
  371. inline
  372. void CIntervalTree::Assign(iterator& dst, const iterator& src)
  373. {
  374.     dst.m_SearchX = src.m_SearchX;
  375.     dst.m_SearchLimit = src.m_SearchLimit;
  376.     dst.m_CurrentMapValue = src.m_CurrentMapValue;
  377.     dst.m_NextNode = src.m_NextNode;
  378. }
  381. /*
  382. * ---------------------------------------------------------------------------
  383. * $Log: itree.inl,v $
  384. * Revision 1000.0  2003/10/29 15:29:49  gouriano
  385. * PRODUCTION: IMPORTED [ORIGINAL] Dev-tree R1.6
  386. *
  387. * Revision 1.6  2003/02/07 17:37:40  vasilche
  388. * Removed parameters' default values from method definition.
  389. *
  390. * Revision 1.5  2003/02/07 16:54:01  vasilche
  391. * Pass all structures with size > sizeof int by reference.
  392. * Move cvs log to the end of files.
  393. *
  394. * Revision 1.4  2002/04/29 17:33:59  ucko
  395. * Add explicit "typename" in three places.
  396. *
  397. * Revision 1.3  2001/05/17 15:01:19  lavr
  398. * Typos corrected
  399. *
  400. * Revision 1.2  2001/01/29 15:18:39  vasilche
  401. * Cleaned CRangeMap and CIntervalTree classes.
  402. *
  403. * Revision 1.1  2001/01/11 15:00:38  vasilche
  404. * Added CIntervalTree for seraching on set of intervals.
  405. *
  406. * ===========================================================================
  407. */
  409. #endif /* def ITREE__HPP  &&  ndef ITREE__INL */