NCBI C++ ToolKit
range_coll.hpp
Go to the documentation of this file.

Go to the SVN repository for this file.

1 #ifndef UTIL___RANGE_COLL__HPP
2 #define UTIL___RANGE_COLL__HPP
3 
4 /* $Id: range_coll.hpp 100378 2023-07-26 18:59:30Z whlavina $
5  * ===========================================================================
6  *
7  * PUBLIC DOMAIN NOTICE
8  * National Center for Biotechnology Information
9  *
10  * This software/database is a "United States Government Work" under the
11  * terms of the United States Copyright Act. It was written as part of
12  * the author's official duties as a United States Government employee and
13  * thus cannot be copyrighted. This software/database is freely available
14  * to the public for use. The National Library of Medicine and the U.S.
15  * Government have not placed any restriction on its use or reproduction.
16  *
17  * Although all reasonable efforts have been taken to ensure the accuracy
18  * and reliability of the software and data, the NLM and the U.S.
19  * Government do not and cannot warrant the performance or results that
20  * may be obtained by using this software or data. The NLM and the U.S.
21  * Government disclaim all warranties, express or implied, including
22  * warranties of performance, merchantability or fitness for any particular
23  * purpose.
24  *
25  * Please cite the author in any work or product based on this material.
26  *
27  * ===========================================================================
28  *
29  * Authors: Andrey Yazhuk
30  *
31  * File Description:
32  * class CRangeCollection - sorted collection of non-overlapping CRange-s
33  */
34 
35 #include <corelib/ncbistd.hpp>
36 #include <corelib/ncbistl.hpp>
37 
38 #include <util/range.hpp>
39 
40 #include <algorithm>
41 
43 
44 template<class Range, class Position>
46 {
47  using is_transparent = void;
48  bool operator()(const Range &R, Position Pos) { return R.GetToOpen() <= Pos; }
49  //bool operator()(Position Pos, const Range &R) { return Pos < R.GetToOpen(); }
50  bool operator()(const Range &R1, const Range &R2) { return R1.GetToOpen() < R2.GetToOpen(); }
51 };
52 
53 ///////////////////////////////////////////////////////////////////////////////
54 // class CRangeCollection<Position> represent a sorted collection of
55 // CRange<Position>. It is guaranteed that ranges in collection do not overlap.
56 // Unless DivideAt() was explicitly called, it is also guarantees that they
57 // aren't adjacent so that there is no gap beween them.
58 // Adding an interval to the collection leads to possible merging it with
59 // existing intervals.
60 
61 template<class Position>
63 {
64 public:
65  typedef Position position_type;
67 
69  typedef vector<TRange> TRangeVector;
70  typedef typename TRangeVector::const_iterator const_iterator;
71  typedef typename TRangeVector::const_reverse_iterator const_reverse_iterator;
72  typedef typename TRangeVector::size_type size_type;
73 
75  explicit CRangeCollection(const TRange& r)
76  {
77  m_vRanges.push_back(r);
78  }
79  CRangeCollection(const CRangeCollection &c) = default;
80 
81  // immitating vector, but providing only "const" access to elements
83  {
84  return m_vRanges.begin();
85  }
87  {
88  return m_vRanges.end();
89  }
91  {
92  return m_vRanges.rbegin();
93  }
95  {
96  return m_vRanges.rend();
97  }
98  size_type size() const
99  {
100  return m_vRanges.size();
101  }
102  bool empty() const
103  {
104  return m_vRanges.empty();
105  }
106  const TRange& operator[](size_type pos) const
107  {
108  return m_vRanges[pos];
109  }
110  void clear()
111  {
112  m_vRanges.clear();
113  }
114  // returns iterator pointing to the TRange that has ToOpen > pos
116  {
118  return lower_bound(begin(), end(), pos, p);
119  }
121  {
122  if(! m_vRanges.empty())
123  return begin()->GetFrom();
124  else return TRange::GetEmptyFrom();
125  }
127  {
128  if(! m_vRanges.empty())
129  return rbegin()->GetToOpen();
130  else return TRange::GetEmptyToOpen();
131  }
133  {
134  if(! m_vRanges.empty())
135  return rbegin()->GetTo();
136  else return TRange::GetEmptyTo();
137  }
138  bool Empty() const
139  {
140  return empty();
141  }
142  bool NotEmpty() const
143  {
144  return ! empty();
145  }
147  {
148  if(! m_vRanges.empty()) {
149  position_type From = begin()->GetFrom();
150  return rbegin()->GetToOpen() - From;
151  } else return 0;
152  }
153  ///
154  /// Returns total length covered by ranges in this collection, i.e.
155  /// sum of lengths of ranges
156  ///
158  {
159  position_type length = 0;
160  ITERATE(typename TThisType, it, m_vRanges) {
161  length += it->GetLength();
162  }
163  return length;
164  }
166  {
167  if(! m_vRanges.empty()) {
168  position_type From = begin()->GetFrom();
169  position_type To = rbegin()->GetTo();
170  return TRange(From, To);
171  } else return TRange::GetEmpty();
172  }
174  {
176  return *this;
177  }
179  {
181  return *this;
182  }
183  bool operator == (const TThisType& c) const
184  {
185  return x_Equals(c);
186  }
187  bool IntersectingWith (const TRange& r) const
188  {
189  return x_Intersects(r).second;
190  }
191  bool Contains (const TRange& r) const
192  {
193  return x_Contains(r).second;
194  }
196  {
197  x_CombineWith(r);
198  return *this;
199  }
201  {
202  x_CombineWith(r);
203  return *this;
204  }
206  {
207  x_Subtract(r);
208  return *this;
209  }
211  {
212  x_Subtract(r);
213  return *this;
214  }
216  {
217  x_IntersectWith(c);
218  return *this;
219  }
221  {
222  x_IntersectWith(c);
223  return *this;
224  }
226  {
227  x_CombineWith(c);
228  return *this;
229  }
231  {
232  x_CombineWith(c);
233  return *this;
234  }
236  {
237  x_Subtract(c);
238  return *this;
239  }
241  {
242  x_Subtract(c);
243  return *this;
244  }
245 
246  /// If position is in middle of range, divide into two consecutive ranges
247  /// after this position
249  {
250  x_Divide(p);
251  return *this;
252  }
253 
254 protected:
255  typedef typename TRangeVector::iterator iterator;
256  typedef typename TRangeVector::reverse_iterator reverse_iterator;
257 
259  {
260  return m_vRanges.begin();
261  }
263  {
264  return m_vRanges.end();
265  }
268  return lower_bound(begin_nc(), end_nc(), pos, p);
269  }
270  pair<const_iterator, bool> x_Find(position_type pos) const
271  {
273  const_iterator it = lower_bound(begin(), end(), pos, p);
274  bool b_contains = it != end() && it->GetFrom() >= pos;
275  return make_pair(it, b_contains);
276  }
277  pair<const_iterator, bool> x_Intersects(const TRange& r) const
278  {
280  const_iterator it = lower_bound(begin(), end(), r.GetFrom(), p);
281  bool b_intersects = it != end() && it->GetFrom() < r.GetToOpen();
282  return make_pair(it, b_intersects);
283  }
284  pair<const_iterator, bool> x_Contains(const TRange& r) const
285  {
287  const_iterator it = lower_bound(begin(), end(), r.GetFrom(), p);
288  bool contains = false;
289  if (it != end()) {
290  contains = (it->GetFrom() <= r.GetFrom() &&
291  it->GetTo() >= r.GetTo());
292  }
293  return make_pair(it, contains);
294  }
295 
296  void x_IntersectWith(const TRange& r)
297  {
299 
300  position_type pos_to = r.GetTo();
301  iterator it_right = lower_bound(begin_nc(), end_nc(), pos_to, p);
302  if(it_right != end_nc()) {
303  if(it_right->GetFrom() <= pos_to) { //intersects
304  it_right->SetTo(pos_to);
305  ++it_right; // exclude from removal
306  }
307  m_vRanges.erase(it_right, end_nc()); // erase ranges to the right
308  }
309 
310  position_type pos_from = r.GetFrom();
311  iterator it_left =
312  lower_bound(begin_nc(), end_nc(), pos_from, p);
313  if(it_left != end_nc()) {
314  if(it_left->GetFrom() < pos_from)
315  it_left->SetFrom(pos_from);
316  }
317  m_vRanges.erase(begin_nc(), it_left); //erase ranges to the left
318  }
319 
320  // returns iterator to the range representing result of combination
322  {
324 
325  position_type pos_from = r.GetFrom();
326  position_type pos_to_open = r.GetToOpen();
327 
328  if (pos_from == TRange::GetWholeFrom()) {
329  pos_from++; // Prevent overflow
330  }
331  iterator it_begin_m =
332  lower_bound(begin_nc(), end_nc(), pos_from - 1, p); /* NCBI_FAKE_WARNING: WorkShop */
333  if(it_begin_m != end_nc() && it_begin_m->GetFrom() <= pos_to_open) { // intersection
334  iterator it_end_m = lower_bound(it_begin_m, end_nc(), pos_to_open, p);
335  it_begin_m->CombineWith(r);
336 
337  if(it_end_m != end_nc() && it_end_m->GetFrom() <= pos_to_open) {// subject to merge
338  it_begin_m->SetToOpen(it_end_m->GetToOpen());
339  ++it_end_m; // including it into erased set
340  }
341  m_vRanges.erase(it_begin_m + 1, it_end_m);
342  } else {
343  m_vRanges.insert(it_begin_m, r);
344  }
345  return it_begin_m;
346  }
347 
348  void x_Subtract(const TRange& r)
349  {
351 
352  position_type pos_from = r.GetFrom();
353  position_type pos_to_open = r.GetToOpen();
354 
355  iterator it_begin_e = lower_bound(begin_nc(), end_nc(), pos_from, P);
356  if(it_begin_e != end_nc()) { // possible intersection
357 
358  if(it_begin_e->GetFrom() < pos_from && it_begin_e->GetToOpen() > pos_to_open) {
359  //it_begin_e contains R, split it in two
360  TRange it_r = *it_begin_e;
361  it_begin_e = m_vRanges.insert(it_begin_e, it_r);
362  it_begin_e->SetToOpen(pos_from);
363  (++it_begin_e)->SetFrom(pos_to_open);
364  } else {
365  if(it_begin_e->GetFrom() < pos_from) { // cut this segement , but don't erase
366  it_begin_e->SetToOpen(pos_from);
367  ++it_begin_e;
368  }
369  iterator it_end_e = lower_bound(it_begin_e, end_nc(), pos_to_open, P);
370  if(it_end_e != end_nc() && it_end_e->GetFrom() < pos_to_open) {
371  it_end_e->SetFrom(pos_to_open); // truncate
372  }
373  // erase ranges fully covered by R
374  m_vRanges.erase(it_begin_e, it_end_e);
375  }
376  }
377  }
378  void x_IntersectWith(const TThisType &c)
379  {
380  TRangeVector intersection_ranges;
381  const_iterator my_iterator = begin(),
382  c_iterator = c.begin();
383  while(my_iterator != end() && c_iterator != c.end())
384  {
385  TRange intersection = my_iterator->IntersectionWith(*c_iterator);
386  if(intersection.NotEmpty())
387  intersection_ranges.push_back(intersection);
388  if(my_iterator->GetTo() < c_iterator->GetTo())
389  ++my_iterator;
390  else
391  ++c_iterator;
392  }
393  m_vRanges = intersection_ranges;
394  }
395 
396  void x_Divide(const position_type& p)
397  {
399  iterator it = lower_bound(begin_nc(), end_nc(), p, P);
400  if (it != end_nc() && it->GetFrom() <= p && it->GetTo() > p) {
401  position_type end_pos = it->GetTo();
402  it->SetTo(p);
403  m_vRanges.insert(++it, TRange(p+1, end_pos));
404  }
405  }
406 
407  void x_CombineWith(const TThisType &c)
408  {
409  ITERATE(typename TThisType, it, c) {
410  x_CombineWith(*it);
411  }
412  }
413  void x_Subtract(const TThisType &c)
414  {
415  ITERATE(typename TThisType, it, c) {
416  x_Subtract(*it);
417  }
418  }
419  bool x_Equals(const TThisType &c) const
420  {
421  if(&c == this) {
422  return true;
423  } else {
424  return m_vRanges == c.m_vRanges;
425  }
426  }
427 
428 protected:
430 };
431 
433 
434 #endif // UTIL___RANGE_COLL__HPP
void x_Subtract(const TThisType &c)
Definition: range_coll.hpp:413
bool NotEmpty() const
Definition: range_coll.hpp:142
iterator end_nc()
Definition: range_coll.hpp:262
TThisType & IntersectWith(const TThisType &c)
Definition: range_coll.hpp:215
void x_IntersectWith(const TRange &r)
Definition: range_coll.hpp:296
position_type GetTo() const
Definition: range_coll.hpp:132
pair< const_iterator, bool > x_Find(position_type pos) const
Definition: range_coll.hpp:270
TThisType & DivideAfter(const position_type &p)
If position is in middle of range, divide into two consecutive ranges after this position.
Definition: range_coll.hpp:248
pair< const_iterator, bool > x_Contains(const TRange &r) const
Definition: range_coll.hpp:284
TRangeVector::const_reverse_iterator const_reverse_iterator
Definition: range_coll.hpp:71
Position position_type
Definition: range_coll.hpp:65
void x_IntersectWith(const TThisType &c)
Definition: range_coll.hpp:378
TRangeVector::const_iterator const_iterator
Definition: range_coll.hpp:70
const_reverse_iterator rend() const
Definition: range_coll.hpp:94
size_type size() const
Definition: range_coll.hpp:98
TRangeVector::reverse_iterator reverse_iterator
Definition: range_coll.hpp:256
const_iterator end() const
Definition: range_coll.hpp:86
TThisType & CombineWith(const TRange &r)
Definition: range_coll.hpp:195
iterator x_CombineWith(const TRange &r)
Definition: range_coll.hpp:321
position_type GetLength(void) const
Definition: range_coll.hpp:146
TThisType & operator+=(const TRange &r)
Definition: range_coll.hpp:200
TRange GetLimits() const
Definition: range_coll.hpp:165
CRange< position_type > TRange
Definition: range_coll.hpp:68
TThisType & Subtract(const TThisType &c)
Definition: range_coll.hpp:235
TThisType & IntersectWith(const TRange &r)
Definition: range_coll.hpp:173
void x_Subtract(const TRange &r)
Definition: range_coll.hpp:348
TThisType & operator-=(const TRange &r)
Definition: range_coll.hpp:210
bool empty() const
Definition: range_coll.hpp:102
iterator begin_nc()
Definition: range_coll.hpp:258
CRangeCollection(const TRange &r)
Definition: range_coll.hpp:75
bool operator==(const TThisType &c) const
Definition: range_coll.hpp:183
position_type GetToOpen() const
Definition: range_coll.hpp:126
TThisType & operator&=(const TRange &r)
Definition: range_coll.hpp:178
const_iterator begin() const
Definition: range_coll.hpp:82
bool IntersectingWith(const TRange &r) const
Definition: range_coll.hpp:187
pair< const_iterator, bool > x_Intersects(const TRange &r) const
Definition: range_coll.hpp:277
void x_CombineWith(const TThisType &c)
Definition: range_coll.hpp:407
bool Contains(const TRange &r) const
Definition: range_coll.hpp:191
position_type GetFrom() const
Definition: range_coll.hpp:120
TThisType & Subtract(const TRange &r)
Definition: range_coll.hpp:205
const TRange & operator[](size_type pos) const
Definition: range_coll.hpp:106
iterator find_nc(position_type pos)
Definition: range_coll.hpp:266
bool x_Equals(const TThisType &c) const
Definition: range_coll.hpp:419
position_type GetCoveredLength(void) const
Returns total length covered by ranges in this collection, i.e.
Definition: range_coll.hpp:157
const_reverse_iterator rbegin() const
Definition: range_coll.hpp:90
const_iterator find(position_type pos) const
Definition: range_coll.hpp:115
CRangeCollection(const CRangeCollection &c)=default
vector< TRange > TRangeVector
Definition: range_coll.hpp:69
TThisType & CombineWith(const TThisType &c)
Definition: range_coll.hpp:225
bool Empty() const
Definition: range_coll.hpp:138
CRangeCollection< position_type > TThisType
Definition: range_coll.hpp:66
void x_Divide(const position_type &p)
Definition: range_coll.hpp:396
TRangeVector m_vRanges
Definition: range_coll.hpp:429
TRangeVector::size_type size_type
Definition: range_coll.hpp:72
TRangeVector::iterator iterator
Definition: range_coll.hpp:255
CRange –.
Definition: Range.hpp:68
Include a standard set of the NCBI C++ Toolkit most basic headers.
unsigned short Pos
#define ITERATE(Type, Var, Cont)
ITERATE macro to sequence through container elements.
Definition: ncbimisc.hpp:815
bool NotEmpty(void) const
Definition: range.hpp:152
TThisType IntersectionWith(const TThisType &r) const
Definition: range.hpp:312
static TThisType GetEmpty(void)
Definition: range.hpp:306
static position_type GetEmptyFrom(void)
Definition: range.hpp:290
static position_type GetEmptyTo(void)
Definition: range.hpp:298
static position_type GetWholeFrom(void)
Definition: range.hpp:256
static position_type GetEmptyToOpen(void)
Definition: range.hpp:294
#define END_NCBI_SCOPE
End previously defined NCBI scope.
Definition: ncbistl.hpp:103
#define BEGIN_NCBI_SCOPE
Define ncbi namespace.
Definition: ncbistl.hpp:100
#define P(a, b, c, d, k, s, t)
The NCBI C++/STL use hints.
double r(size_t dimension_, const Int4 *score_, const double *prob_, double theta_)
void is_transparent
Definition: range_coll.hpp:47
bool operator()(const Range &R1, const Range &R2)
Definition: range_coll.hpp:50
bool operator()(const Range &R, Position Pos)
Definition: range_coll.hpp:48
Modified on Fri Feb 23 11:50:32 2024 by modify_doxy.py rev. 669887