Fabcoin Core  0.16.2
P2P Digital Currency
RangeMask.h
Go to the documentation of this file.
1 /*
2  This file is part of cpp-ethereum.
3 
4  cpp-ethereum is free software: you can redistribute it and/or modify
5  it under the terms of the GNU General Public License as published by
6  the Free Software Foundation, either version 3 of the License, or
7  (at your option) any later version.
8 
9  cpp-ethereum is distributed in the hope that it will be useful,
10  but WITHOUT ANY WARRANTY; without even the implied warranty of
11  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12  GNU General Public License for more details.
13 
14  You should have received a copy of the GNU General Public License
15  along with cpp-ethereum. If not, see <http://www.gnu.org/licenses/>.
16 */
22 #pragma once
23 
24 #include <map>
25 #include <utility>
26 #include <vector>
27 #include <iterator>
28 #include <iostream>
29 #include <assert.h>
30 
31 namespace dev
32 {
33 
34 class RLPStream;
35 
36 using UnsignedRange = std::pair<unsigned, unsigned>;
37 using UnsignedRanges = std::vector<UnsignedRange>;
38 
45 template <class T>
46 class RangeMask
47 {
48  template <class U> friend std::ostream& operator<<(std::ostream& _out, RangeMask<U> const& _r);
49 
50 public:
51  using Range = std::pair<T, T>;
52  using Ranges = std::vector<Range>;
53 
55  RangeMask(): m_all(0, 0) {}
57  RangeMask(T _begin, T _end): m_all(_begin, _end) {}
59  RangeMask(Range const& _c): m_all(_c) {}
60 
62  RangeMask unionedWith(RangeMask const& _m) const { return operator+(_m); }
63  RangeMask operator+(RangeMask const& _m) const { return RangeMask(*this) += _m; }
64 
66  RangeMask lowest(decltype(T{} - T{}) _items) const
67  {
68  RangeMask ret(m_all);
69  for (auto i = m_ranges.begin(); i != m_ranges.end() && _items; ++i)
70  _items -= (ret.m_ranges[i->first] = std::min(i->first + _items, i->second)) - i->first;
71  return ret;
72  }
73 
75  RangeMask operator~() const { return inverted(); }
76 
79  {
80  RangeMask ret(m_all);
81  T last = m_all.first;
82  for (auto i: m_ranges)
83  {
84  if (i.first != last)
85  ret.m_ranges[last] = i.first;
86  last = i.second;
87  }
88  if (last != m_all.second)
89  ret.m_ranges[last] = m_all.second;
90  return ret;
91  }
92 
95  RangeMask& invert() { return *this = inverted(); }
96 
97  template <class S> RangeMask operator-(S const& _m) const { auto ret = *this; return ret -= _m; }
98  template <class S> RangeMask& operator-=(S const& _m) { return invert().unionWith(_m).invert(); }
99 
100  RangeMask& operator+=(RangeMask const& _m) { return unionWith(_m); }
101 
103  {
104  m_all.first = std::min(_m.m_all.first, m_all.first);
105  m_all.second = std::max(_m.m_all.second, m_all.second);
106  for (auto const& i: _m.m_ranges)
107  unionWith(i);
108  return *this;
109  }
110  RangeMask& operator+=(Range const& _m) { return unionWith(_m); }
113  RangeMask& unionWith(Range const& _m);
114 
116  RangeMask& operator+=(T _m) { return unionWith(_m); }
119  {
120  return operator+=(Range(_i, _i + 1));
121  }
122 
123  bool contains(T _i) const
124  {
125  auto it = m_ranges.upper_bound(_i);
126  if (it == m_ranges.begin())
127  return false;
128  return (--it)->second > _i;
129  }
130 
131  bool empty() const
132  {
133  return m_ranges.empty();
134  }
135 
136  bool full() const
137  {
138  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);
139  }
140 
141  void clear()
142  {
143  m_ranges.clear();
144  }
145 
146  void reset()
147  {
148  m_ranges.clear();
149  m_all = std::make_pair(0, 0);
150  }
151 
153  std::pair<T, T> const& all() const { return m_all; }
155  void extendAll(T _i) { m_all = std::make_pair(std::min(m_all.first, _i), std::max(m_all.second, _i + 1)); }
156 
157  class const_iterator: public std::iterator<std::forward_iterator_tag, T>
158  {
159  friend class RangeMask;
160 
161  public:
163 
164  T operator*() const { return m_value; }
165  const_iterator& operator++() { if (m_owner) m_value = m_owner->next(m_value); return *this; }
166  const_iterator operator++(int) { auto ret = *this; if (m_owner) m_value = m_owner->next(m_value); return ret; }
167 
168  bool operator==(const_iterator const& _i) const { return m_owner == _i.m_owner && m_value == _i.m_value; }
169  bool operator!=(const_iterator const& _i) const { return !operator==(_i); }
170  bool operator<(const_iterator const& _i) const { return m_value < _i.m_value; }
171 
172  private:
173  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) {}
174 
175  RangeMask const* m_owner = nullptr;
176  T m_value = 0;
177  };
178 
179  const_iterator begin() const { return const_iterator(*this, false); }
180  const_iterator end() const { return const_iterator(*this, true); }
183  T next(T _t) const
184  {
185  _t++;
186  // find next item in range at least _t
187  auto uit = m_ranges.upper_bound(_t); // > _t
188  auto it = uit == m_ranges.begin() ? m_ranges.end() : std::prev(uit);
189  if (it != m_ranges.end() && it->first <= _t && it->second > _t)
190  return _t;
191  return uit == m_ranges.end() ? m_all.second : uit->first;
192  }
193 
195  size_t size() const
196  {
197  size_t c = 0;
198  for (auto const& r: this->m_ranges)
199  c += r.second - r.first;
200  return c;
201  }
202 
203  size_t firstOut() const
204  {
205  if (m_ranges.empty() || !m_ranges.count(m_all.first))
206  return m_all.first;
207  return m_ranges.at(m_all.first);
208  }
209 
210  size_t lastIn() const
211  {
212  if (m_ranges.empty())
213  return m_all.first;
214  return m_ranges.rbegin()->second - 1;
215  }
216 
217 private:
221  std::map<T, T> m_ranges;
222 };
223 
224 template <class T> inline std::ostream& operator<<(std::ostream& _out, RangeMask<T> const& _r)
225 {
226  _out << _r.m_all.first << "{ ";
227  for (auto const& i: _r.m_ranges)
228  _out << "[" << i.first << ", " << i.second << ") ";
229  _out << "}" << _r.m_all.second;
230  return _out;
231 }
232 
233 template <class T>
235 {
236  for (auto i = _m.first; i < _m.second;)
237  {
238  assert(i >= m_all.first);
239  assert(i < m_all.second);
240  // For each number, we find the element equal or next lower. this, if any, must contain the value.
241  // First range that starts after i.
242  auto rangeAfter = m_ranges.upper_bound(i);
243  // Range before rangeAfter or "end" if the rangeAfter is the first ever...
244  auto it = rangeAfter == m_ranges.begin() ? m_ranges.end() : std::prev(rangeAfter);
245  if (it == m_ranges.end() || it->second < i)
246  {
247  // i is either before the first range or between two ranges (with some distance
248  // so that we cannot merge it onto "it").
249  // lower range is too low to merge.
250  // if the next higher range is too high.
251  if (rangeAfter == m_ranges.end() || rangeAfter->first > _m.second)
252  {
253  // just create a new range
254  m_ranges[i] = _m.second;
255  break;
256  }
257  else
258  {
259  if (rangeAfter->first == i)
260  // move i to end of range
261  i = rangeAfter->second;
262  else
263  {
264  // merge with the next higher range
265  // move i to end of range
266  i = m_ranges[i] = rangeAfter->second;
267  m_ranges.erase(rangeAfter);
268  }
269  }
270  }
271  else if (it->second == i)
272  {
273  // The range before i ends with i.
274  // if the next higher range is too high.
275  if (rangeAfter == m_ranges.end() || rangeAfter->first > _m.second)
276  {
277  // merge with the next lower range
278  m_ranges[it->first] = _m.second;
279  break;
280  }
281  else
282  {
283  // merge with both next lower & next higher.
284  i = m_ranges[it->first] = rangeAfter->second;
285  m_ranges.erase(rangeAfter);
286  }
287  }
288  else
289  i = it->second;
290  }
291  return *this;
292 }
293 
294 }
Adapted from code found on http://stackoverflow.com/questions/180947/base64-decode-snippet-in-c Origi...
Definition: Arith256.cpp:15
RangeMask(Range const &_c)
Constructs an empty range mask with ground range _c.
Definition: RangeMask.h:59
std::vector< Range > Ranges
Definition: RangeMask.h:52
RangeMask & operator+=(Range const &_m)
Definition: RangeMask.h:110
RangeMask unionedWith(RangeMask const &_m) const
Definition: RangeMask.h:62
RangeMask()
Constructs an empty range mask with empty ground range.
Definition: RangeMask.h:55
#define T(i, x)
void extendAll(T _i)
Extends the ground range to include _i.
Definition: RangeMask.h:155
RangeMask & unionWith(T _i)
Adds the single element _i to the range mask.
Definition: RangeMask.h:118
#define c(i)
assert(len-trim+(2 *lenIndices)<=WIDTH)
const_iterator & operator++()
Definition: RangeMask.h:165
ExecStats::duration min
Definition: ExecStats.cpp:35
UnsignedRange m_all
The ground range.
Definition: RangeMask.h:219
std::pair< unsigned, unsigned > UnsignedRange
Definition: RangeMask.h:36
RangeMask const * m_owner
Definition: RangeMask.h:175
size_t size() const
Definition: RangeMask.h:195
void reset()
Definition: RangeMask.h:146
RangeMask & unionWith(RangeMask const &_m)
Definition: RangeMask.h:102
bool full() const
Definition: RangeMask.h:136
RangeMask & invert()
Changes the range mask to its complement relative to the ground range and returns a reference to itse...
Definition: RangeMask.h:95
bool operator!=(const_iterator const &_i) const
Definition: RangeMask.h:169
std::pair< T, T > Range
Definition: RangeMask.h:51
std::vector< UnsignedRange > UnsignedRanges
Definition: RangeMask.h:37
const_iterator begin() const
Definition: RangeMask.h:179
T next(T _t) const
Definition: RangeMask.h:183
const_iterator end() const
Definition: RangeMask.h:180
RangeMask inverted() const
Definition: RangeMask.h:78
RangeMask lowest(decltype(T{}-T{}) _items) const
Definition: RangeMask.h:66
size_t firstOut() const
Definition: RangeMask.h:203
const_iterator operator++(int)
Definition: RangeMask.h:166
bool contains(T _i) const
Definition: RangeMask.h:123
RangeMask & operator+=(T _m)
Adds the single element _i to the range mask.
Definition: RangeMask.h:116
RangeMask operator-(S const &_m) const
Definition: RangeMask.h:97
RangeMask operator~() const
Definition: RangeMask.h:75
RangeMask operator+(RangeMask const &_m) const
Definition: RangeMask.h:63
bool operator==(const_iterator const &_i) const
Definition: RangeMask.h:168
std::map< T, T > m_ranges
Mapping begin -> end containing the ranges.
Definition: RangeMask.h:221
std::pair< T, T > const & all() const
Definition: RangeMask.h:153
dev::WithExisting max(dev::WithExisting _a, dev::WithExisting _b)
Definition: Common.h:326
#define S(a)
Definition: mars.cpp:50
Set of elements of a certain "ground range" representable by unions of ranges inside this ground rang...
Definition: RangeMask.h:46
RangeMask & operator-=(S const &_m)
Definition: RangeMask.h:98
void clear()
Definition: RangeMask.h:141
bool operator<(const_iterator const &_i) const
Definition: RangeMask.h:170
bool empty() const
Definition: RangeMask.h:131
const_iterator(RangeMask const &_m, bool _end)
Definition: RangeMask.h:173
size_t lastIn() const
Definition: RangeMask.h:210
RangeMask & operator+=(RangeMask const &_m)
Definition: RangeMask.h:100
RangeMask(T _begin, T _end)
Constructs an empty range mask with ground range [_begin, _end).
Definition: RangeMask.h:57