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

生物技术

开发平台:

C/C++

  1. /*
  2.  * ===========================================================================
  3.  * PRODUCTION $Log: handle_range.cpp,v $
  4.  * PRODUCTION Revision 1000.2  2004/06/01 19:23:20  gouriano
  5.  * PRODUCTION PRODUCTION: UPGRADED [GCC34_MSVC7] Dev-tree R1.21
  6.  * PRODUCTION
  7.  * ===========================================================================
  8.  */
  9. /*  $Id: handle_range.cpp,v 1000.2 2004/06/01 19:23:20 gouriano Exp $
  10. * ===========================================================================
  11. *
  12. *                            PUBLIC DOMAIN NOTICE
  13. *               National Center for Biotechnology Information
  14. *
  15. *  This software/database is a "United States Government Work" under the
  16. *  terms of the United States Copyright Act.  It was written as part of
  17. *  the author's official duties as a United States Government employee and
  18. *  thus cannot be copyrighted.  This software/database is freely available
  19. *  to the public for use. The National Library of Medicine and the U.S.
  20. *  Government have not placed any restriction on its use or reproduction.
  21. *
  22. *  Although all reasonable efforts have been taken to ensure the accuracy
  23. *  and reliability of the software and data, the NLM and the U.S.
  24. *  Government do not and cannot warrant the performance or results that
  25. *  may be obtained by using this software or data. The NLM and the U.S.
  26. *  Government disclaim all warranties, express or implied, including
  27. *  warranties of performance, merchantability or fitness for any particular
  28. *  purpose.
  29. *
  30. *  Please cite the author in any work or product based on this material.
  31. *
  32. * ===========================================================================
  33. *
  34. * Author: Aleksey Grichenko, Eugene Vasilchenko
  35. *
  36. * File Description:
  37. *       CHandleRange:
  38. *       Internal class to be used instead of CSeq_loc
  39. *       for better performance.
  40. *
  41. */
  42. #include <ncbi_pch.hpp>
  43. #include <objmgr/impl/handle_range.hpp>
  44. #include <algorithm>
  45. BEGIN_NCBI_SCOPE
  46. BEGIN_SCOPE(objects)
  47. ////////////////////////////////////////////////////////////////////
  48. //
  49. //
  50. //
  51. CHandleRange::CHandleRange(void)
  52. {
  53. }
  54. CHandleRange::CHandleRange(const CHandleRange& hr)
  55. {
  56.     *this = hr;
  57. }
  58. CHandleRange::~CHandleRange(void)
  59. {
  60. }
  61. CHandleRange& CHandleRange::operator=(const CHandleRange& hr)
  62. {
  63.     if (this != &hr) {
  64.         m_Ranges = hr.m_Ranges;
  65.     }
  66.     return *this;
  67. }
  68. void CHandleRange::AddRange(TRange range, ENa_strand strand)
  69. {
  70.     m_Ranges.push_back(TRanges::value_type(range, strand));
  71.     sort(m_Ranges.begin(), m_Ranges.end());
  72. }
  73. void CHandleRange::AddRanges(const CHandleRange& hr)
  74. {
  75.     ITERATE ( CHandleRange, it, hr ) {
  76.         AddRange(it->first, it->second);
  77.     }
  78. }
  79. bool CHandleRange::x_IntersectingStrands(ENa_strand str1, ENa_strand str2)
  80. {
  81.     return
  82.         str1 == eNa_strand_unknown // str1 includes anything
  83.         ||
  84.         str2 == eNa_strand_unknown // str2 includes anything
  85.         ||
  86.         str1 == str2;              // accept only equal strands
  87.     //### Not sure about "eNa_strand_both includes eNa_strand_plus" etc.
  88. }
  89. bool CHandleRange::IntersectingWith(const CHandleRange& hr) const
  90. {
  91.     TRanges::const_iterator it1 = m_Ranges.begin();
  92.     TRanges::const_iterator end1 = m_Ranges.end();
  93.     if ( it1 == end1 ) {
  94.         return false;
  95.     }
  96.     TRanges::const_iterator it2 = hr.m_Ranges.begin();
  97.     TRanges::const_iterator end2 = hr.m_Ranges.end();
  98.     if ( it2 == end2 ) {
  99.         return false;
  100.     }
  101.     for ( ;; ) {
  102.         if ( it2->first.Empty() ||
  103.              it2->first.GetToOpen() <= it1->first.GetFrom() ) {
  104.             if ( ++it2 == end2 ) {
  105.                 break;
  106.             }
  107.         }
  108.         else if ( it1->first.Empty() ||
  109.                   it1->first.GetToOpen() <= it2->first.GetFrom() ) {
  110.             if ( ++it1 == end1 ) {
  111.                 break;
  112.             }
  113.         }
  114.         else if ( x_IntersectingStrands(it1->second, it2->second) ) {
  115.             return true;
  116.         }
  117.         else if ( it1->first.GetToOpen() < it2->first.GetToOpen() ) {
  118.             if ( ++it1 == end1 ) {
  119.                 break;
  120.             }
  121.         }
  122.         else {
  123.             if ( ++it2 == end2 ) {
  124.                 break;
  125.             }
  126.         }
  127.     }
  128.     return false;
  129. }
  130. void CHandleRange::MergeRange(TRange range, ENa_strand /*strand*/)
  131. {
  132.     for ( TRanges::iterator it = m_Ranges.begin(); it != m_Ranges.end(); ) {
  133.         // Find intersecting intervals, discard strand information
  134.         // Also merge adjacent ranges, prevent merging whole-to + whole-from
  135.         if ( !it->first.Empty() &&
  136.              (it->first.IntersectingWith(range) ||
  137.               it->first.GetFrom() == range.GetToOpen() ||
  138.               it->first.GetToOpen() == range.GetFrom()) ) {
  139.             // Remove the intersecting interval, update the merged range.
  140.             // We assume that WholeFrom is less than any non-whole value
  141.             // and WholeTo is greater than any non-whole value.
  142.             range += it->first;
  143.             it = m_Ranges.erase(it);
  144.         }
  145.         else {
  146.             ++it;
  147.         }
  148.     }
  149.     AddRange(range, eNa_strand_unknown);
  150. }
  151. CHandleRange::TRange CHandleRange::GetOverlappingRange(void) const
  152. {
  153.     TOpenRange ret = TOpenRange::GetEmpty();
  154.     ITERATE ( TRanges, it, m_Ranges ) {
  155.         ret += it->first;
  156.     }
  157.     return ret;
  158. }
  159. CHandleRange::TRange
  160. CHandleRange::GetOverlappingRange(const TRange& range) const
  161. {
  162.     TOpenRange ret = TOpenRange::GetEmpty();
  163.     if ( !range.Empty() ) {
  164.         ITERATE ( TRanges, it, m_Ranges ) {
  165.             ret += it->first.IntersectionWith(range);
  166.         }
  167.     }
  168.     return ret;
  169. }
  170. bool CHandleRange::IntersectingWith(const TRange& range,
  171.                                     ENa_strand strand) const
  172. {
  173.     if ( !range.Empty() ) {
  174.         ITERATE ( TRanges, it, m_Ranges ) {
  175.             if ( range.IntersectingWith(it->first) &&
  176.                  x_IntersectingStrands(strand, it->second) ) {
  177.                 return true;
  178.             }
  179.         }
  180.     }
  181.     return false;
  182. }
  183. bool CHandleRange::HasGaps(void) const
  184. {
  185.     return m_Ranges.size() > 1;
  186. }
  187. END_SCOPE(objects)
  188. END_NCBI_SCOPE
  189. /*
  190. * ---------------------------------------------------------------------------
  191. * $Log: handle_range.cpp,v $
  192. * Revision 1000.2  2004/06/01 19:23:20  gouriano
  193. * PRODUCTION: UPGRADED [GCC34_MSVC7] Dev-tree R1.21
  194. *
  195. * Revision 1.21  2004/05/21 21:42:12  gorelenk
  196. * Added PCH ncbi_pch.hpp
  197. *
  198. * Revision 1.20  2004/02/19 17:17:23  vasilche
  199. * Removed unused include.
  200. *
  201. * Revision 1.19  2003/07/17 20:07:56  vasilche
  202. * Reduced memory usage by feature indexes.
  203. * SNP data is loaded separately through PUBSEQ_OS.
  204. * String compression for SNP data.
  205. *
  206. * Revision 1.18  2003/06/02 16:06:38  dicuccio
  207. * Rearranged src/objects/ subtree.  This includes the following shifts:
  208. *     - src/objects/asn2asn --> arc/app/asn2asn
  209. *     - src/objects/testmedline --> src/objects/ncbimime/test
  210. *     - src/objects/objmgr --> src/objmgr
  211. *     - src/objects/util --> src/objmgr/util
  212. *     - src/objects/alnmgr --> src/objtools/alnmgr
  213. *     - src/objects/flat --> src/objtools/flat
  214. *     - src/objects/validator --> src/objtools/validator
  215. *     - src/objects/cddalignview --> src/objtools/cddalignview
  216. * In addition, libseq now includes six of the objects/seq... libs, and libmmdb
  217. * replaces the three libmmdb? libs.
  218. *
  219. * Revision 1.17  2003/04/24 16:12:38  vasilche
  220. * Object manager internal structures are splitted more straightforward.
  221. * Removed excessive header dependencies.
  222. *
  223. * Revision 1.16  2003/03/14 19:10:41  grichenk
  224. * + SAnnotSelector::EIdResolving; fixed operator=() for several classes
  225. *
  226. * Revision 1.15  2003/03/11 15:51:06  kuznets
  227. * iterate -> ITERATE
  228. *
  229. * Revision 1.14  2003/02/24 18:57:22  vasilche
  230. * Make feature gathering in one linear pass using CSeqMap iterator.
  231. * Do not use feture index by sub locations.
  232. * Sort features at the end of gathering in one vector.
  233. * Extracted some internal structures and classes in separate header.
  234. * Delay creation of mapped features.
  235. *
  236. * Revision 1.13  2003/02/05 17:59:17  dicuccio
  237. * Moved formerly private headers into include/objects/objmgr/impl
  238. *
  239. * Revision 1.12  2003/01/23 18:26:02  ucko
  240. * Explicitly #include <algorithm>
  241. *
  242. * Revision 1.11  2003/01/22 20:11:54  vasilche
  243. * Merged functionality of CSeqMapResolved_CI to CSeqMap_CI.
  244. * CSeqMap_CI now supports resolution and iteration over sequence range.
  245. * Added several caches to CScope.
  246. * Optimized CSeqVector().
  247. * Added serveral variants of CBioseqHandle::GetSeqVector().
  248. * Tried to optimize annotations iterator (not much success).
  249. * Rewritten CHandleRange and CHandleRangeMap classes to avoid sorting of list.
  250. *
  251. * Revision 1.10  2002/12/19 20:18:01  grichenk
  252. * Fixed test case for minus strand location
  253. *
  254. * Revision 1.9  2002/07/08 20:51:01  grichenk
  255. * Moved log to the end of file
  256. * Replaced static mutex (in CScope, CDataSource) with the mutex
  257. * pool. Redesigned CDataSource data locking.
  258. *
  259. * Revision 1.8  2002/06/12 14:40:47  grichenk
  260. * Made some methods inline
  261. *
  262. * Revision 1.7  2002/05/24 14:58:55  grichenk
  263. * Fixed Empty() for unsigned intervals
  264. * SerialAssign<>() -> CSerialObject::Assign()
  265. * Improved performance for eResolve_None case
  266. *
  267. * Revision 1.6  2002/05/09 14:18:55  grichenk
  268. * Fixed "unused variable" warnings
  269. *
  270. * Revision 1.5  2002/04/22 20:05:35  grichenk
  271. * +MergeRange()
  272. *
  273. * Revision 1.4  2002/02/21 19:27:05  grichenk
  274. * Rearranged includes. Added scope history. Added searching for the
  275. * best seq-id match in data sources and scopes. Updated tests.
  276. *
  277. * Revision 1.3  2002/02/15 20:35:38  gouriano
  278. * changed implementation of HandleRangeMap
  279. *
  280. * Revision 1.2  2002/01/23 21:59:31  grichenk
  281. * Redesigned seq-id handles and mapper
  282. *
  283. * Revision 1.1  2002/01/11 19:06:19  gouriano
  284. * restructured objmgr
  285. *
  286. *
  287. * ===========================================================================
  288. */