1 #include "intervalset.h"
2 #include <stdio.h>
3 #include <assert.h>
4 #include <limits>
5 #include <algorithm>
6
7 const IntervalSet::key_t IntervalSet::npos=std::numeric_limits<IntervalSet::key_t>::max();
8
clear()9 void IntervalSet::clear() // {{{
10 {
11 data.clear();
12 }
13 // }}}
14
add(key_t start,key_t end)15 void IntervalSet::add(key_t start,key_t end) // {{{
16 {
17 if (start<end) {
18 data.push_back(std::make_pair(start,end));
19 }
20 }
21 // }}}
22
finish()23 void IntervalSet::finish() // {{{
24 {
25 data_t::iterator it=data.begin(),end=data.end(),pos=it;
26 if (it==end) {
27 return;
28 }
29
30 std::sort(it,end);
31
32 while (1) {
33 ++it;
34 if (it==end) {
35 ++pos;
36 break;
37 }
38 if (pos->second>=it->first) {
39 pos->second=it->second;
40 } else {
41 ++pos;
42 if (pos!=it) {
43 *pos=*it;
44 }
45 }
46 }
47
48 data.erase(pos,data.end());
49 }
50 // }}}
51
contains(key_t val) const52 bool IntervalSet::contains(key_t val) const // {{{
53 {
54 data_t::const_iterator it=std::upper_bound(data.begin(),data.end(),std::make_pair(val,npos));
55 if (it==data.begin()) {
56 return false;
57 }
58 --it;
59 return (val<it->second);
60 }
61 // }}}
62
next(key_t val) const63 IntervalSet::key_t IntervalSet::next(key_t val) const // {{{
64 {
65 val++;
66 data_t::const_iterator it=std::upper_bound(data.begin(),data.end(),std::make_pair(val,npos));
67 if (it==data.begin()) {
68 if (it==data.end()) { // empty
69 return npos;
70 }
71 return it->first;
72 }
73 --it;
74 if (val<it->second) {
75 return val;
76 }
77 ++it;
78 if (it==data.end()) {
79 return npos;
80 }
81 return it->first;
82 }
83 // }}}
84
intersect(const value_t & a,const value_t & b) const85 bool IntervalSet::intersect(const value_t &a,const value_t &b) const // {{{
86 {
87 return ((a.first>=b.first) && (a.first<b.second)) ||
88 ((b.first>=a.first) && (b.first<a.second));
89 }
90 // }}}
91
unite(value_t & aret,const value_t & b) const92 void IntervalSet::unite(value_t &aret,const value_t &b) const // {{{
93 {
94 assert(intersect(aret,b));
95 if (b.first<aret.first) {
96 aret.first=b.first;
97 }
98 if (b.second>aret.second) {
99 aret.second=b.second;
100 }
101 }
102 // }}}
103
dump() const104 void IntervalSet::dump() const // {{{
105 {
106 int len=data.size();
107 if (len==0) {
108 fprintf(stderr,"(empty)\n");
109 return;
110 }
111 len--;
112 for (int iA=0;iA<len;iA++) {
113 fprintf(stderr,"[%d,%d),",data[iA].first,data[iA].second);
114 }
115 if (data[len].second==npos) {
116 fprintf(stderr,"[%d,inf)\n",data[len].first);
117 } else {
118 fprintf(stderr,"[%d,%d)\n",data[len].first,data[len].second);
119 }
120 }
121 // }}}
122