This repository was archived by the owner on Oct 28, 2021. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 2.2k
Expand file tree
/
Copy pathRangeMask.h
More file actions
293 lines (253 loc) · 8.67 KB
/
RangeMask.h
File metadata and controls
293 lines (253 loc) · 8.67 KB
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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
/*
This file is part of cpp-ethereum.
cpp-ethereum is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
cpp-ethereum is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with cpp-ethereum. If not, see <http://www.gnu.org/licenses/>.
*/
/** @file RangeMask.h
* @author Gav Wood <i@gavwood.com>
* @date 2014
*/
#pragma once
#include <map>
#include <utility>
#include <vector>
#include <iterator>
#include <ostream>
#include <assert.h>
#include <algorithm>
namespace dev
{
class RLPStream;
using UnsignedRange = std::pair<unsigned, unsigned>;
using UnsignedRanges = std::vector<UnsignedRange>;
/**
* Set of elements of a certain "ground range" representable by unions of ranges inside this
* ground range.
* Ranges are given as pairs (begin, end), denoting the interval [begin, end), i.e. end is excluded.
* Supports set-theoretic operators, size and iteration.
*/
class RangeMask
{
friend std::ostream& operator<<(std::ostream& _out, RangeMask const& _r);
public:
using Range = std::pair<unsigned, unsigned>;
using Ranges = std::vector<Range>;
/// Constructs an empty range mask with empty ground range.
RangeMask(): m_all(0, 0) {}
/// Constructs an empty range mask with ground range [_begin, _end).
RangeMask(unsigned _begin, unsigned _end): m_all(_begin, _end) {}
/// Constructs an empty range mask with ground range _c.
RangeMask(Range const& _c): m_all(_c) {}
/// @returns the union with the range mask _m, taking also the union of the ground ranges.
RangeMask unionedWith(RangeMask const& _m) const { return operator+(_m); }
RangeMask operator+(RangeMask const& _m) const { return RangeMask(*this) += _m; }
/// @returns a new range mask containing the smallest _items elements (not ranges).
RangeMask lowest(unsigned _items) const
{
RangeMask ret(m_all);
for (auto i = m_ranges.begin(); i != m_ranges.end() && _items; ++i)
_items -= (ret.m_ranges[i->first] = std::min(i->first + _items, i->second)) - i->first;
return ret;
}
/// @returns the complement of the range mask relative to the ground range.
RangeMask operator~() const { return inverted(); }
/// @returns a copy of this range mask representing the complement relative to the ground range.
RangeMask inverted() const
{
RangeMask ret(m_all);
unsigned last = m_all.first;
for (auto i: m_ranges)
{
if (i.first != last)
ret.m_ranges[last] = i.first;
last = i.second;
}
if (last != m_all.second)
ret.m_ranges[last] = m_all.second;
return ret;
}
/// Changes the range mask to its complement relative to the ground range and returns a
/// reference to itself.
RangeMask& invert() { return *this = inverted(); }
template <class S> RangeMask operator-(S const& _m) const { auto ret = *this; return ret -= _m; }
template <class S> RangeMask& operator-=(S const& _m) { return invert().unionWith(_m).invert(); }
RangeMask& operator+=(RangeMask const& _m) { return unionWith(_m); }
RangeMask& unionWith(RangeMask const& _m)
{
m_all.first = std::min(_m.m_all.first, m_all.first);
m_all.second = std::max(_m.m_all.second, m_all.second);
for (auto const& i: _m.m_ranges)
unionWith(i);
return *this;
}
RangeMask& operator+=(Range const& _m) { return unionWith(_m); }
/// Modifies this range mask to also include the range _m, which has to be a subset of
/// the ground range.
RangeMask& unionWith(Range const& _m);
/// Adds the single element _i to the range mask.
RangeMask& operator+=(unsigned _m) { return unionWith(_m); }
/// Adds the single element _i to the range mask.
RangeMask& unionWith(unsigned _i)
{
return operator+=(Range(_i, _i + 1));
}
bool contains(unsigned _i) const
{
auto it = m_ranges.upper_bound(_i);
if (it == m_ranges.begin())
return false;
return (--it)->second > _i;
}
bool empty() const
{
return m_ranges.empty();
}
bool full() const
{
return m_all.first == m_all.second || (m_ranges.size() == 1 && m_ranges.begin()->first == m_all.first && m_ranges.begin()->second == m_all.second);
}
void clear()
{
m_ranges.clear();
}
void reset()
{
m_ranges.clear();
m_all = std::make_pair(0, 0);
}
/// @returns the ground range.
std::pair<unsigned, unsigned> const& all() const { return m_all; }
/// Extends the ground range to include _i.
void extendAll(unsigned _i) { m_all = std::make_pair(std::min(m_all.first, _i), std::max(m_all.second, _i + 1)); }
class const_iterator: public std::iterator<std::forward_iterator_tag, unsigned>
{
friend class RangeMask;
public:
const_iterator() {}
unsigned operator*() const { return m_value; }
const_iterator& operator++() { if (m_owner) m_value = m_owner->next(m_value); return *this; }
const_iterator operator++(int) { auto ret = *this; if (m_owner) m_value = m_owner->next(m_value); return ret; }
bool operator==(const_iterator const& _i) const { return m_owner == _i.m_owner && m_value == _i.m_value; }
bool operator!=(const_iterator const& _i) const { return !operator==(_i); }
bool operator<(const_iterator const& _i) const { return m_value < _i.m_value; }
private:
const_iterator(RangeMask const& _m, bool _end): m_owner(&_m), m_value(_m.m_ranges.empty() || _end ? _m.m_all.second : _m.m_ranges.begin()->first) {}
RangeMask const* m_owner = nullptr;
unsigned m_value = 0;
};
const_iterator begin() const { return const_iterator(*this, false); }
const_iterator end() const { return const_iterator(*this, true); }
/// @returns the smallest element in the range mask that is larger than _t or the end of the
/// base range if such an element does not exist.
unsigned next(unsigned _t) const
{
_t++;
// find next item in range at least _t
auto uit = m_ranges.upper_bound(_t); // > _t
auto it = uit == m_ranges.begin() ? m_ranges.end() : std::prev(uit);
if (it != m_ranges.end() && it->first <= _t && it->second > _t)
return _t;
return uit == m_ranges.end() ? m_all.second : uit->first;
}
/// @returns the number of elements (not ranges) in the range mask.
size_t size() const
{
size_t c = 0;
for (auto const& r: this->m_ranges)
c += r.second - r.first;
return c;
}
size_t firstOut() const
{
if (m_ranges.empty() || !m_ranges.count(m_all.first))
return m_all.first;
return m_ranges.at(m_all.first);
}
size_t lastIn() const
{
if (m_ranges.empty())
return m_all.first;
return m_ranges.rbegin()->second - 1;
}
private:
/// The ground range.
UnsignedRange m_all;
/// Mapping begin -> end containing the ranges.
std::map<unsigned, unsigned> m_ranges;
};
inline std::ostream& operator<<(std::ostream& _out, RangeMask const& _r)
{
_out << _r.m_all.first << "{ ";
for (auto const& i: _r.m_ranges)
_out << "[" << i.first << ", " << i.second << ") ";
_out << "}" << _r.m_all.second;
return _out;
}
RangeMask& RangeMask::unionWith(RangeMask::Range const& _m)
{
for (auto i = _m.first; i < _m.second;)
{
assert(i >= m_all.first);
assert(i < m_all.second);
// For each number, we find the element equal or next lower. this, if any, must contain the value.
// First range that starts after i.
auto rangeAfter = m_ranges.upper_bound(i);
// Range before rangeAfter or "end" if the rangeAfter is the first ever...
auto it = rangeAfter == m_ranges.begin() ? m_ranges.end() : std::prev(rangeAfter);
if (it == m_ranges.end() || it->second < i)
{
// i is either before the first range or between two ranges (with some distance
// so that we cannot merge it onto "it").
// lower range is too low to merge.
// if the next higher range is too high.
if (rangeAfter == m_ranges.end() || rangeAfter->first > _m.second)
{
// just create a new range
m_ranges[i] = _m.second;
break;
}
else
{
if (rangeAfter->first == i)
// move i to end of range
i = rangeAfter->second;
else
{
// merge with the next higher range
// move i to end of range
i = m_ranges[i] = rangeAfter->second;
m_ranges.erase(rangeAfter);
}
}
}
else if (it->second == i)
{
// The range before i ends with i.
// if the next higher range is too high.
if (rangeAfter == m_ranges.end() || rangeAfter->first > _m.second)
{
// merge with the next lower range
m_ranges[it->first] = _m.second;
break;
}
else
{
// merge with both next lower & next higher.
i = m_ranges[it->first] = rangeAfter->second;
m_ranges.erase(rangeAfter);
}
}
else
i = it->second;
}
return *this;
}
}