1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
|
#include <stdexcept>
#include "RangeUtils.hpp"
using namespace std;
Range::Range(UInt pStart) {
start = end = pStart;
}
Range::Range(UInt pStart, UInt pEnd) {
start = pStart;
end = pEnd;
if (start > end) {
cout << "ERROR: start of a range should be less than the end."
<< endl;
exit(1);
}
}
bool Range::contains(const UInt & query) {
return (start <= query && query <= end);
}
bool Range::operator < (const Range & pRange) const {
if (start == pRange.start) {
return (end > pRange.end);
}
return (start < pRange.start);
}
//
// Input is a comma-delimited string of ranges.
// e.g. 1,2,3,10-20
bool ParseRanges(string & rangesStr, vector<Range> & ranges) {
ranges.clear();
bool parseSucceed = true;
vector<string> strList;
ParseSeparatedList(rangesStr, strList, ',');
for(int i=0; i<int(strList.size()); i++) {
string & str = strList[i];
if(str.find('-') == string::npos) {
ranges.push_back(Range(atoi(str.c_str())));
} else {
vector<string> start_end;
ParseSeparatedList(str, start_end, '-');
if (start_end.size() != 2) {
parseSucceed = false;
break;
}
ranges.push_back(Range(atoi(start_end[0].c_str()),
atoi(start_end[1].c_str())));
}
}
if (parseSucceed) {
sort(ranges.begin(), ranges.end());
} else {
ranges.clear();
}
return parseSucceed;
}
Ranges::Ranges(string rangesStr) {
if (!ParseRanges(rangesStr, ranges))
throw std::invalid_argument("bad range");
}
bool Ranges::setRanges(string rangesStr) {
return ParseRanges(rangesStr, ranges);
}
int Ranges::size() {
return ranges.size();
}
UInt Ranges::max() {
if (size() == 0) {
cout << "ERROR, could not determine the maximum value "
<< "of an empty Ranges object." << endl;
exit(1);
}
return ranges.back().end;
}
bool Ranges::contains(const UInt & query) {
if (ranges.size() == 0) return false;
vector<Range> searchRanges;
searchRanges.push_back(Range(0, ranges.size()-1));
while (searchRanges.size() > 0) {
Range searchRange = searchRanges.back();
searchRanges.pop_back();
UInt mid = (searchRange.start + searchRange.end) / 2;
if (ranges[mid].contains(query)) {
return true;
}
if (mid > 0 && searchRange.start <= mid - 1) {
searchRanges.push_back(Range(searchRange.start,
mid - 1));
}
if (ranges[mid].start <= query and
searchRange.end >= mid + 1) {
searchRanges.push_back(Range(mid + 1,
searchRange.end));
}
}
return false;
}
|
