range_coll.hpp
上传用户:yhdzpy8989
上传日期:2007-06-13
资源大小:13604k
文件大小:12k
- /*
- * ===========================================================================
- * PRODUCTION $Log: range_coll.hpp,v $
- * PRODUCTION Revision 1000.2 2004/06/01 19:38:30 gouriano
- * PRODUCTION PRODUCTION: UPGRADED [GCC34_MSVC7] Dev-tree R1.4
- * PRODUCTION
- * ===========================================================================
- */
- #ifndef UTIL___RANGE_COLL__HPP
- #define UTIL___RANGE_COLL__HPP
- /* $Id: range_coll.hpp,v 1000.2 2004/06/01 19:38:30 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.
- *
- * ===========================================================================
- *
- * Authors: Andrey Yazhuk
- *
- * File Description:
- * class CRangeCollection - sorted collection of non-overlapping CRange-s
- */
- #include <corelib/ncbistd.hpp>
- #include <corelib/ncbistl.hpp>
- #include <util/range.hpp>
- #include <algorithm>
- BEGIN_NCBI_SCOPE
- template<class Range, class Position>
- struct PRangeLessPos
- {
- bool operator()(const Range &R, Position Pos) { return R.GetToOpen() <= Pos; }
- };
-
- ///////////////////////////////////////////////////////////////////////////////
- // class CRangeCollection<Position> represent a sorted collection of
- // CRange<Position>. It is guaranteed that ranges in collection do not overlap
- // and aren't adjacent so that there is no gap beween them.
- // Adding an interval to the collection leads to possible merging it with
- // existing intervals.
- template<class Position>
- class CRangeCollection
- {
- public:
- typedef Position position_type;
- typedef CRangeCollection<position_type> TThisType;
- typedef CRange<position_type> TRange;
- typedef vector<TRange> TRangeVector;
- typedef typename TRangeVector::const_iterator const_iterator;
- typedef typename TRangeVector::const_reverse_iterator const_reverse_iterator;
- typedef typename TRangeVector::size_type size_type;
-
- CRangeCollection() { }
- explicit CRangeCollection(const TRange& r)
- {
- m_vRanges.push_back(r);
- }
- CRangeCollection(const CRangeCollection &c)
- {
- m_vRanges = c.m_vRanges;
- }
-
- // immitating vector, but providing only "const" access to elements
- const_iterator begin() const
- {
- return m_vRanges.begin();
- }
- const_iterator end() const
- {
- return m_vRanges.end();
- }
- const_reverse_iterator rbegin() const
- {
- return m_vRanges.rbegin();
- }
- const_reverse_iterator rend() const
- {
- return m_vRanges.rend();
- }
- size_type size() const
- {
- return m_vRanges.size();
- }
- bool empty() const
- {
- return m_vRanges.empty();
- }
- const TRange& operator[](size_type pos) const
- {
- return m_vRanges[pos];
- }
- void clear()
- {
- m_vRanges.clear();
- }
- // returns iterator pointing to the TRange that has ToOpen > pos
- const_iterator find(position_type pos) const
- {
- return x_Find(pos);
- }
- position_type GetFrom() const
- {
- if(! m_vRanges.empty())
- return begin()->GetFrom();
- else return -1;
- }
- position_type GetToOpen() const
- {
- if(! m_vRanges.empty())
- return rbegin()->GetToOpen();
- else return -1;
- }
- position_type GetTo() const
- {
- if(! m_vRanges.empty())
- return rbegin()->GetToOpen();
- else return -1;
- }
- bool Empty() const
- {
- return empty();
- }
- bool NotEmpty() const
- {
- return ! empty();
- }
- position_type GetLength (void) const
- {
- if(! m_vRanges.empty()) {
- position_type From = begin()->GetFrom();
- return rbegin()->GetToOpen() - From;
- } else return 0;
- }
- TRange GetLimits() const
- {
- if(! m_vRanges.empty()) {
- position_type From = begin()->GetFrom();
- position_type To = rbegin()->GetTo();
- return TRange(From, To);
- } else return TRange(0, -1);
- }
- TThisType& IntersectWith (const TRange& r)
- {
- x_IntersectWith(r);
- return *this;
- }
- TThisType & operator &= (const TRange& r)
- {
- x_IntersectWith(r);
- return *this;
- }
- bool IntersectingWith (const TRange& r) const
- {
- return x_Intersects(r).second;
- }
- TThisType& CombineWith (const TRange& r)
- {
- x_CombineWith(r);
- return *this;
- }
- TThisType & operator+= (const TRange& r)
- {
- x_CombineWith(r);
- return *this;
- }
- TThisType& Subtract(const TRange& r)
- {
- x_Subtract(r);
- return *this;
- }
- TThisType & operator-= (const TRange& r)
- {
- x_Subtract(r);
- return *this;
- }
- TThisType& IntersectWith (const TThisType &c)
- {
- x_IntersectWith(c);
- return *this;
- }
- TThisType & operator&= (const TThisType &c)
- {
- x_IntersectWith(c);
- return *this;
- }
- TThisType& CombineWith (const TThisType &c)
- {
- x_CombineWith(c);
- return *this;
- }
- TThisType & operator+= (const TThisType &c)
- {
- x_CombineWith(c);
- return *this;
- }
- TThisType& Subtract(const TThisType &c)
- {
- x_Subtract(c);
- return *this;
- }
- TThisType & operator-= (const TThisType &c)
- {
- x_Subtract(c);
- return *this;
- }
- protected:
- typedef typename TRangeVector::iterator iterator;
- typedef typename TRangeVector::reverse_iterator reverse_iterator;
- iterator begin()
- {
- return m_vRanges.begin();
- }
- iterator end()
- {
- return m_vRanges.end();
- }
- pair<iterator, bool> x_Find(position_type pos)
- {
- PRangeLessPos<TRange, position_type> p;
- iterator it = lower_bound(begin(), end(), pos, p);
- bool b_contains = it != end() && it->GetFrom() >= pos;
- return make_pair(it, b_contains);
- }
- pair<iterator, bool> x_Intersects(const TRange& r)
- {
- PRangeLessPos<TRange, position_type> p;
- iterator it = lower_bound(begin(), end(), r.GetFrom(), p);
- bool b_intersects = it != end() && it->GetFrom() < r.GetToOpen();
- return make_pair(it, b_intersects);
- }
-
- void x_IntersectWith(const TRange& r)
- {
- PRangeLessPos<TRange, position_type> p;
- position_type pos_to = r.GetTo();
- iterator it_right = lower_bound(begin(), end(), pos_to, p);
- if(it_right != end()) {
- if(it_right->GetFrom() <= pos_to) { //intersects
- it_right->SetTo(pos_to);
- ++it_right; // exclude from removal
- }
- m_vRanges.erase(it_right, end()); // erase ranges to the right
- }
- position_type pos_from = this->R.GetFrom();
- iterator it_left = lower_bound(begin(), end(), pos_from, this->P);
- if(it_left != end()) {
- if(it_left->GetFrom() < pos_from)
- it_left->SetFrom(pos_from);
- m_vRanges.erase(begin(), it_left); //erase ranges to the left
- }
- }
- // returns iterator to the range representing result of combination
- iterator x_CombineWith(const TRange& r)
- {
- PRangeLessPos<TRange, position_type> p;
- position_type pos_from = r.GetFrom();
- position_type pos_to_open = r.GetToOpen();
- iterator it_begin_m = lower_bound(begin(), end(), pos_from - 1, p);
- if(it_begin_m != end() && it_begin_m->GetFrom() <= pos_to_open) { // intersection
- it_begin_m->CombineWith(r);
-
- iterator it_end_m = lower_bound(it_begin_m, end(), pos_to_open, p);
- if(it_end_m != end() && it_end_m->GetFrom() <= pos_to_open) {// subject to merge
- it_begin_m->SetToOpen(it_end_m->GetToOpen());
- ++it_end_m; // including it into erased set
- }
- m_vRanges.erase(it_begin_m + 1, it_end_m);
- } else {
- m_vRanges.insert(it_begin_m, r);
- }
- return it_begin_m;
- }
- void x_Subtract(const TRange& r)
- {
- PRangeLessPos<TRange, position_type> P;
- position_type pos_from = r.GetFrom();
- position_type pos_to_open = r.GetToOpen();
- iterator it_begin_e = lower_bound(begin(), end(), pos_from, P);
- if(it_begin_e != end()) { // possible intersection
-
- if(it_begin_e->GetFrom() < pos_from && it_begin_e->GetToOpen() > pos_to_open) {
- //it_begin_e contains R, split it in two
- it_begin_e = m_vRanges.insert(it_begin_e, *it_begin_e);
- it_begin_e->SetToOpen(pos_from);
- (++it_begin_e)->SetFrom(pos_to_open);
- } else {
- if(it_begin_e->GetFrom() < pos_from) { // cut this segement , but don't erase
- it_begin_e->SetToOpen(pos_from);
- ++it_begin_e;
- }
- iterator it_end_e = lower_bound(it_begin_e, end(), pos_to_open, P);
- if(it_end_e != end() && it_end_e->GetFrom() < pos_to_open) {
- it_end_e->SetFrom(pos_to_open); // truncate
- }
- // erase ranges fully covered by R
- m_vRanges.erase(it_begin_e, it_end_e);
- }
- }
- }
- void x_IntersectWith(const TThisType &c)
- {
- ITERATE(typename TThisType, it, c) {
- x_IntersectWith(*it);
- }
- }
- void x_CombineWith(const TThisType &c)
- {
- ITERATE(typename TThisType, it, c) {
- x_CombineWith(*it);
- }
- }
- void x_Subtract(const TThisType &c)
- {
- ITERATE(typename TThisType, it, c) {
- x_Subtract(*it);
- }
- }
- protected:
- TRangeVector m_vRanges;
- };
- END_NCBI_SCOPE
- /*
- * ===========================================================================
- * $Log: range_coll.hpp,v $
- * Revision 1000.2 2004/06/01 19:38:30 gouriano
- * PRODUCTION: UPGRADED [GCC34_MSVC7] Dev-tree R1.4
- *
- * Revision 1.4 2004/04/26 14:51:43 ucko
- * Add "typename" and "this->" to accommodate GCC 3.4's stricter
- * treatment of templates.
- *
- * Revision 1.3 2004/02/12 20:51:52 yazhuk
- * Fixed GetFrom()
- *
- * Revision 1.2 2003/12/22 19:17:49 dicuccio
- * Use correct #include guard
- *
- * Revision 1.1 2003/12/01 16:29:45 yazhuk
- * Moved from gui/widgets/aln_multiple
- *
- * Revision 1.7 2003/10/10 18:56:12 yazhuk
- * Added GetFrom(), fixed find()
- *
- * Revision 1.6 2003/10/08 14:12:58 dicuccio
- * Moved CGlPane into opengl
- *
- * Revision 1.5 2003/09/29 13:38:48 yazhuk
- * Enforced coding policy
- *
- * Revision 1.4 2003/09/23 20:45:47 yazhuk
- * Added comments
- *
- * Revision 1.3 2003/09/08 20:47:50 yazhuk
- * Bugfixes
- *
- * Revision 1.2 2003/09/08 17:04:12 yazhuk
- * GCC compilation fixes
- *
- * Revision 1.1 2003/09/08 16:34:38 yazhuk
- * Initial revision
- *
- * ===========================================================================
- */
- #endif // UTIL___RANGE_COLL__HPP