retdec
range.h
Go to the documentation of this file.
1 
7 #ifndef RETDEC_COMMON_RANGE_H
8 #define RETDEC_COMMON_RANGE_H
9 
10 #include <algorithm>
11 #include <cassert>
12 #include <cstdint>
13 #include <sstream>
14 #include <type_traits>
15 #include <utility>
16 #include <vector>
17 
18 namespace retdec {
19 namespace common {
20 
21 class InvalidRangeException : public std::exception
22 {
23 public:
24  InvalidRangeException() noexcept {}
25  InvalidRangeException(const InvalidRangeException&) noexcept = default;
26  virtual ~InvalidRangeException() = default;
27 
28  virtual const char* what() const noexcept override
29  {
30  return "Invalid Range: end is greater than start";
31  }
32 };
33 
44 template <typename T> class Range
45 {
46 public:
47  using RangeType = T;
48 
52  Range() :
53  _start(),
54  _end()
55  {}
56 
63  Range(const RangeType& start, const RangeType& end) :
64  _start(start),
65  _end(end)
66  {
67  if (end < start)
68  throw InvalidRangeException();
69  }
70 
76  Range(const Range<RangeType>& range) :
77  _start(range._start),
78  _end(range._end)
79  {}
80 
87  noexcept(std::is_nothrow_move_constructible<RangeType>::value) :
88  _start(std::move(range._start)),
89  _end(std::move(range._end)) {}
90 
94  virtual ~Range() = default;
95 
103  Range& operator =(const Range<RangeType>& rhs) = default;
104 
112  Range& operator =(Range<RangeType>&& rhs) = default;
113 
119  const RangeType& getStart() const
120  {
121  return _start;
122  }
123 
129  const RangeType& getEnd() const
130  {
131  return _end;
132  }
133 
139  void setStart(const RangeType& start)
140  {
141  if (_end < start)
142  {
143  throw InvalidRangeException();
144  }
145  _start = start;
146  }
147 
153  void setEnd(const RangeType& end)
154  {
155  if (end < _start)
156  {
157  throw InvalidRangeException();
158  }
159  _end = end;
160  }
161 
168  void setStartEnd(const RangeType& start, const RangeType& end)
169  {
170  if (end < start)
171  {
172  throw InvalidRangeException();
173  }
174  _start = start;
175  _end = end;
176  }
177 
184  {
185  return _end - _start;
186  }
187 
196  bool contains(const RangeType& value) const
197  {
198  return _start <= value && value < _end;
199  }
200 
209  bool contains(const Range<RangeType>& o) const
210  {
211  return contains(o.getStart()) && o.getEnd() <= getEnd();
212  }
213 
218  bool overlaps(const Range<RangeType>& o) const
219  {
220  return _start < o._end && o._start < _end;
221  }
222 
229  bool operator ==(const Range<RangeType>& rhs) const
230  {
231  return _start == rhs._start && _end == rhs._end;
232  }
233 
240  bool operator <(const Range<RangeType>& rhs) const
241  {
242  return _start < rhs._start;
243  }
244 
251  bool operator !=(const Range<RangeType>& rhs) const
252  {
253  return !(*this == rhs);
254  }
255 
256  friend std::ostream& operator<<(
257  std::ostream& out,
258  const Range<RangeType>& r)
259  {
260  return out << std::hex << std::showbase
261  << "<" << r.getStart() << ", " << r.getEnd() << ")";
262  }
263 
264 protected:
267 };
268 
278 // template <typename T, typename = std::enable_if_t<std::is_integral<T>::value, void>>
279 template <typename T>
281 {
282 public:
284  using RangeElementType = T;
285 
286  using iterator = typename std::vector<RangeType>::iterator;
287  using const_iterator = typename std::vector<RangeType>::const_iterator;
288 
290 
291  RangeContainer() = default;
292  RangeContainer(const RangeContainer&) = default;
294 
297  bool operator==(const RangeContainer& o) const { return _ranges == o._ranges; }
298  bool operator!=(const RangeContainer& o) const { return !(*this == o); }
299 
300  auto begin() { return _ranges.begin(); }
301  auto end() { return _ranges.end(); }
302  auto begin() const { return _ranges.begin(); }
303  auto end() const { return _ranges.end(); }
304  std::size_t size() const { return _ranges.size(); }
305  bool empty() const { return _ranges.empty(); }
306  void clear() { _ranges.clear(); }
307  auto front() { return _ranges.front(); }
308  auto front() const { return _ranges.front(); }
309  auto back() { return _ranges.back(); }
310  auto back() const { return _ranges.back(); }
311 
312  decltype(auto) operator[](std::size_t index) { return _ranges[index]; }
313  decltype(auto) operator[](std::size_t index) const { return _ranges[index]; }
314 
327  template <typename RangeT>
328  std::pair<iterator,bool> insert(RangeT&& range)
329  {
330  // Find the range which ends right before the inserted range.
331  auto startItr = std::lower_bound(
332  _ranges.begin(),
333  _ranges.end(),
334  range.getStart(),
335  [](const auto& range, const auto& start) {
336  return range.getEnd() < start;
337  });
338  // Find the range which starts right after the inserted range.
339  auto endItr = std::upper_bound(
340  _ranges.begin(),
341  _ranges.end(),
342  range.getEnd(),
343  [](const auto& end, const auto& range) {
344  return end < range.getStart();
345  });
346 
347  // If the lower and upper bound are the same, that means we have unique
348  // range which does not overlap any other range.
349  // Just insert it into the right position.
350  if (startItr == endItr)
351  {
352  auto it = _ranges.insert(startItr, std::forward<RangeT>(range));
353  // return {it, true};
354  return std::make_pair(it, true);
355  }
356  else
357  {
358  // Rewrite the lower bound and remove the rest which overlaps our
359  // inserted range.
360  auto newStart = std::min(range.getStart(), startItr->getStart());
361  auto newEnd = std::max(range.getEnd(), (endItr - 1)->getEnd());
362  bool startChanged = startItr->getStart() != newStart;
363  bool endChanged = startItr->getEnd() != newEnd;
364  *startItr = RangeType{newStart, newEnd};
365  if (startItr + 1 != endItr)
366  {
367  _ranges.erase(startItr + 1, endItr);
368  }
369 
370  // return {startItr, startChanged || endChanged};
371  return std::make_pair(startItr, startChanged || endChanged);
372  }
373  }
374  template <typename RangeT>
375  std::pair<iterator,bool> insert(const_iterator, RangeT&& range)
376  {
377  return insert(range);
378  }
379 
380  std::pair<iterator,bool> insert(
381  const RangeElementType& s,
382  const RangeElementType& e)
383  {
384  return insert(RangeType(s, e));
385  }
386 
387  const RangeType* getRange(const RangeElementType& e) const
388  {
389  if (_ranges.empty())
390  {
391  return nullptr;
392  }
393 
394  auto pos = std::lower_bound(
395  _ranges.begin(),
396  _ranges.end(),
397  RangeType(e, e));
398 
399  if (pos == _ranges.end())
400  {
401  auto last = _ranges.rbegin();
402  return (last->contains(e)) ? (&(*last)) : (nullptr);
403  }
404 
405  if (pos != _ranges.begin() && pos->getStart() != e)
406  {
407  pos--;
408  }
409 
410  return pos->contains(e) ? &(*pos) : nullptr;
411  }
412 
413  bool contains(const RangeElementType& e) const
414  {
415  return getRange(e) != nullptr;
416  }
417 
418  bool containsExact(const RangeType& r) const
419  {
420  auto* rr = getRange(r.getStart());
421  return rr ? *rr == r : false;
422  }
423 
424  void remove(const RangeType& r)
425  {
426  auto pos = std::lower_bound(_ranges.begin(), _ranges.end(), r);
427  if (pos != _ranges.begin())
428  {
429  --pos; // Move to previous no matter what.
430  }
431  while (pos != _ranges.end() && pos->getStart() <= r.getEnd())
432  {
433  if (pos->contains(r.getStart())
434  || pos->contains(r.getEnd())
435  || r.contains(pos->getStart())
436  || r.contains(pos->getEnd()))
437  {
438  RangeType old = *pos;
439 
440  pos = _ranges.erase(pos);
441  if (old.getStart() < r.getStart())
442  {
443  pos = _ranges.emplace(
444  pos,
445  RangeType(old.getStart(), r.getStart()));
446  ++pos;
447  }
448  if (old.getEnd() > r.getEnd())
449  {
450  pos = _ranges.emplace(
451  pos,
452  RangeType(r.getEnd(), old.getEnd()));
453  ++pos;
454  }
455  }
456  else
457  {
458  ++pos;
459  }
460  }
461  }
462 
463  void remove(const RangeElementType& s, const RangeElementType& e)
464  {
465  return remove(RangeType(s, e));
466  }
467 
468  friend std::ostream& operator<<(
469  std::ostream& out,
471  {
472  for (auto& rr : r)
473  {
474  out << rr << "\n";
475  }
476  return out;
477  }
478 
479 private:
480  std::vector<RangeType> _ranges;
481 };
482 
483 } // namespace common
484 } // namespace retdec
485 
486 #endif
virtual const char * what() const noexcept override
Definition: range.h:28
InvalidRangeException() noexcept
Definition: range.h:24
InvalidRangeException(const InvalidRangeException &) noexcept=default
Definition: range.h:281
typename std::vector< RangeType >::const_iterator const_iterator
Definition: range.h:287
auto back() const
Definition: range.h:310
auto front()
Definition: range.h:307
bool operator==(const RangeContainer &o) const
Definition: range.h:297
Range< T > RangeType
Definition: range.h:283
auto begin() const
Definition: range.h:302
std::vector< RangeType > _ranges
Definition: range.h:480
bool containsExact(const RangeType &r) const
Definition: range.h:418
std::size_t size() const
Definition: range.h:304
RangeContainer & operator=(const RangeContainer &)=default
void remove(const RangeElementType &s, const RangeElementType &e)
Definition: range.h:463
void clear()
Definition: range.h:306
bool empty() const
Definition: range.h:305
RangeContainer(RangeContainer &&)=default
std::pair< iterator, bool > insert(const RangeElementType &s, const RangeElementType &e)
Definition: range.h:380
RangeType value_type
Definition: range.h:289
bool contains(const RangeElementType &e) const
Definition: range.h:413
std::pair< iterator, bool > insert(const_iterator, RangeT &&range)
Definition: range.h:375
auto back()
Definition: range.h:309
std::pair< iterator, bool > insert(RangeT &&range)
Definition: range.h:328
auto front() const
Definition: range.h:308
typename std::vector< RangeType >::iterator iterator
Definition: range.h:286
void remove(const RangeType &r)
Definition: range.h:424
RangeContainer(const RangeContainer &)=default
T RangeElementType
Definition: range.h:284
bool operator!=(const RangeContainer &o) const
Definition: range.h:298
auto end() const
Definition: range.h:303
RangeContainer & operator=(RangeContainer &&)=default
auto end()
Definition: range.h:301
const RangeType * getRange(const RangeElementType &e) const
Definition: range.h:387
auto begin()
Definition: range.h:300
friend std::ostream & operator<<(std::ostream &out, const RangeContainer< RangeElementType > &r)
Definition: range.h:468
Definition: range.h:45
Range(const RangeType &start, const RangeType &end)
Definition: range.h:63
RangeType _end
Definition: range.h:266
RangeType getSize() const
Definition: range.h:183
bool contains(const Range< RangeType > &o) const
Definition: range.h:209
void setEnd(const RangeType &end)
Definition: range.h:153
Range()
Definition: range.h:52
const RangeType & getEnd() const
Definition: range.h:129
bool contains(const RangeType &value) const
Definition: range.h:196
void setStart(const RangeType &start)
Definition: range.h:139
bool operator!=(const Range< RangeType > &rhs) const
Definition: range.h:251
bool overlaps(const Range< RangeType > &o) const
Definition: range.h:218
Range(const Range< RangeType > &range)
Definition: range.h:76
void setStartEnd(const RangeType &start, const RangeType &end)
Definition: range.h:168
RangeType _start
Definition: range.h:265
virtual ~Range()=default
friend std::ostream & operator<<(std::ostream &out, const Range< RangeType > &r)
Definition: range.h:256
Range(Range< RangeType > &&range) noexcept(std::is_nothrow_move_constructible< RangeType >::value)
Definition: range.h:86
const RangeType & getStart() const
Definition: range.h:119
Range & operator=(const Range< RangeType > &rhs)=default
bool operator<(const Range< RangeType > &rhs) const
Definition: range.h:240
T RangeType
Definition: range.h:47
bool operator==(const Range< RangeType > &rhs) const
Definition: range.h:229
Definition: archive_wrapper.h:19