cprover
range.h
Go to the documentation of this file.
1 /*******************************************************************\
2 
3 Module: Range
4 
5 Author: Romain Brenguier, romain.brenguier@diffblue.com
6 
7 \*******************************************************************/
8 
13 
14 #ifndef CPROVER_UTIL_RANGE_H
15 #define CPROVER_UTIL_RANGE_H
16 
17 #include <functional>
18 #include <type_traits>
19 
20 #include <util/invariant.h>
21 #include <util/make_unique.h>
22 
25 template <typename iteratort, typename outputt>
27 {
28 public:
29  using difference_type = typename iteratort::difference_type;
30  using value_type = outputt;
31  using pointer = const outputt *;
32  using reference = const outputt &;
33  using iterator_category = std::forward_iterator_tag;
34 
35  bool operator==(const map_iteratort &other) const
36  {
37  return underlying == other.underlying;
38  }
39 
40  bool operator!=(const map_iteratort &other) const
41  {
42  return !(this->underlying == other.underlying);
43  }
44 
47  {
49  ++underlying;
51  current = std::make_shared<outputt>((*f)(*underlying));
52  return *this;
53  }
54 
57  {
58  map_iteratort tmp(*this);
59  this->operator++();
60  return tmp;
61  }
62 
64  {
65  return *current.get();
66  }
67 
69  {
70  return &(*current.get());
71  }
72 
73  const value_type &operator*() const
74  {
75  return *current.get();
76  }
77 
78  const value_type *operator->() const
79  {
80  return &(*current.get());
81  }
82 
83  explicit map_iteratort(
84  iteratort underlying,
85  iteratort underlying_end,
86  std::shared_ptr<
87  std::function<value_type(const typename iteratort::value_type &)>> f)
88  : underlying(std::move(underlying)),
89  underlying_end(std::move(underlying_end)),
90  f(std::move(f))
91  {
92  if(this->underlying != this->underlying_end)
93  current = std::make_shared<outputt>((*this->f)(*this->underlying));
94  }
95 
96 private:
97  iteratort underlying;
98  iteratort underlying_end;
99  std::shared_ptr<
100  std::function<value_type(const typename iteratort::value_type &)>>
101  f;
102 
105  std::shared_ptr<outputt> current = nullptr;
106 };
107 
110 template <typename iteratort>
112 {
113 public:
114  using difference_type = typename iteratort::difference_type;
115  using value_type = typename iteratort::value_type;
116  using pointer = const value_type *;
117  using reference = const value_type &;
118  using iterator_category = std::forward_iterator_tag;
119 
120  bool operator==(const filter_iteratort &other) const
121  {
122  return underlying == other.underlying;
123  }
124 
125  bool operator!=(const filter_iteratort &other) const
126  {
127  return !(this->underlying == other.underlying);
128  }
129 
132  {
133  ++underlying;
135  return *this;
136  }
137 
140  {
141  filter_iteratort tmp(*this);
142  this->operator++();
143  return tmp;
144  }
145 
147  {
148  return *underlying;
149  }
150 
152  {
153  return &(*underlying);
154  }
155 
156  const value_type &operator*() const
157  {
158  return *underlying;
159  }
160 
161  const value_type *operator->() const
162  {
163  return &(*underlying);
164  }
165 
174  std::shared_ptr<std::function<bool(const value_type &)>> f,
175  iteratort underlying,
176  iteratort end)
177  : underlying(std::move(underlying)),
178  underlying_end(std::move(end)),
179  f(std::move(f))
180  {
182  }
183 
184 private:
185  iteratort underlying;
186  const iteratort underlying_end;
187  std::shared_ptr<std::function<bool(const value_type &)>> f;
188 
195  {
196  while(underlying != underlying_end && !(*f)(*underlying))
197  ++underlying;
198  }
199 };
200 
205 template <typename first_iteratort, typename second_iteratort>
207 {
208 public:
209  using difference_type = typename first_iteratort::difference_type;
210  using value_type = typename first_iteratort::value_type;
211  using pointer = const value_type *;
212  using reference = const value_type &;
213  using iterator_category = std::forward_iterator_tag;
214 
215  static_assert(
216  std::is_same<value_type, typename first_iteratort::value_type>::value,
217  "Concatenated iterators should have the same value type");
218 
219  bool operator==(const concat_iteratort &other) const
220  {
221  return first_begin == other.first_begin && first_end == other.first_end &&
222  second_begin == other.second_begin;
223  }
224 
225  bool operator!=(const concat_iteratort &other) const
226  {
227  return !(*this == other);
228  }
229 
232  {
233  if(first_begin == first_end)
234  ++second_begin;
235  else
236  ++first_begin;
237  return *this;
238  }
239 
242  {
244  this->operator++();
245  return tmp;
246  }
247 
249  {
250  if(first_begin == first_end)
251  return *second_begin;
252  return *first_begin;
253  }
254 
256  {
257  if(first_begin == first_end)
258  return &(*second_begin);
259  return &(*first_begin);
260  }
261 
262  const value_type &operator*() const
263  {
264  if(first_begin == first_end)
265  return *second_begin;
266  return *first_begin;
267  }
268 
269  const value_type *operator->() const
270  {
271  if(first_begin == first_end)
272  return &(*second_begin);
273  return &(*first_begin);
274  }
275 
277  first_iteratort first_begin,
278  first_iteratort first_end,
279  second_iteratort second_begin)
280  : first_begin(std::move(first_begin)),
281  first_end(std::move(first_end)),
282  second_begin(std::move(second_begin))
283  {
284  }
285 
286 private:
287  first_iteratort first_begin;
288  first_iteratort first_end;
289  second_iteratort second_begin;
290 };
291 
310 template <typename iteratort>
311 struct ranget final
312 {
313 public:
314  using value_typet = typename iteratort::value_type;
315 
316  ranget(iteratort begin, iteratort end) : begin_value(begin), end_value(end)
317  {
318  }
319 
321  filter(std::function<bool(const value_typet &)> f)
322  {
323  auto shared_f = std::make_shared<decltype(f)>(std::move(f));
324  filter_iteratort<iteratort> filter_begin(shared_f, begin(), end());
325  filter_iteratort<iteratort> filter_end(shared_f, end(), end());
326  return ranget<filter_iteratort<iteratort>>(filter_begin, filter_end);
327  }
328 
335  template <typename functiont>
336  auto map(functiont &&f) -> ranget<map_iteratort<
337  iteratort,
338  typename std::result_of<functiont(value_typet)>::type>>
339  {
340  using outputt = typename std::result_of<functiont(value_typet)>::type;
341  auto shared_f = std::make_shared<
342  std::function<outputt(const typename iteratort::value_type &)>>(
343  std::forward<functiont>(f));
344  auto map_begin =
346  auto map_end = map_iteratort<iteratort, outputt>(end(), end(), shared_f);
348  std::move(map_begin), std::move(map_end));
349  }
350 
351  template <typename other_iteratort>
354  {
356  begin(), end(), other.begin());
357  auto concat_end =
360  concat_begin, concat_end);
361  }
362 
363  bool empty() const
364  {
365  return begin_value == end_value;
366  }
367 
368  iteratort begin()
369  {
370  return begin_value;
371  }
372 
373  const iteratort &end() const
374  {
375  return end_value;
376  }
377 
378 private:
379  iteratort begin_value;
380  iteratort end_value;
381 };
382 
383 template <typename iteratort>
384 ranget<iteratort> make_range(iteratort begin, iteratort end)
385 {
386  return ranget<iteratort>(begin, end);
387 }
388 
389 template <typename containert>
390 auto make_range(containert &container) -> ranget<decltype(container.begin())>
391 {
392  return ranget<decltype(container.begin())>(
393  container.begin(), container.end());
394 }
395 
396 #endif // CPROVER_UTIL_RANGE_H
concat_iteratort::value_type
typename first_iteratort::value_type value_type
Definition: range.h:210
filter_iteratort::underlying_end
const iteratort underlying_end
Definition: range.h:186
map_iteratort::operator==
bool operator==(const map_iteratort &other) const
Definition: range.h:35
PRECONDITION
#define PRECONDITION(CONDITION)
Definition: invariant.h:438
concat_iteratort::operator->
value_type * operator->()
Definition: range.h:255
map_iteratort::operator*
value_type & operator*()
Definition: range.h:63
concat_iteratort::operator++
concat_iteratort & operator++()
Preincrement operator.
Definition: range.h:231
filter_iteratort::point_to_first_to_peek
void point_to_first_to_peek()
Ensure that the underlying iterator is always positioned on an element for which f is true.
Definition: range.h:194
map_iteratort::operator++
map_iteratort & operator++()
Preincrement operator.
Definition: range.h:46
concat_iteratort::operator->
const value_type * operator->() const
Definition: range.h:269
concat_iteratort::first_end
first_iteratort first_end
Definition: range.h:288
ranget::end
const iteratort & end() const
Definition: range.h:373
ranget::begin_value
iteratort begin_value
Definition: range.h:379
concat_iteratort::operator==
bool operator==(const concat_iteratort &other) const
Definition: range.h:219
map_iteratort::iterator_category
std::forward_iterator_tag iterator_category
Definition: range.h:33
ranget::value_typet
typename iteratort::value_type value_typet
Definition: range.h:314
invariant.h
ranget::begin
iteratort begin()
Definition: range.h:368
concat_iteratort::operator*
const value_type & operator*() const
Definition: range.h:262
filter_iteratort::operator->
value_type * operator->()
Definition: range.h:151
map_iteratort
Iterator which applies some given function f after each increment and returns its result on dereferen...
Definition: range.h:26
ranget::map
auto map(functiont &&f) -> ranget< map_iteratort< iteratort, typename std::result_of< functiont(value_typet)>::type >>
The type of elements contained in the resulting range is deduced from the return type of f.
Definition: range.h:336
map_iteratort::pointer
const outputt * pointer
Definition: range.h:31
filter_iteratort::pointer
const value_type * pointer
Definition: range.h:116
filter_iteratort::underlying
iteratort underlying
Definition: range.h:185
concat_iteratort
On increment, increments a first iterator and when the corresponding end iterator is reached,...
Definition: range.h:206
ranget::end_value
iteratort end_value
Definition: range.h:380
filter_iteratort::operator*
value_type & operator*()
Definition: range.h:146
concat_iteratort::iterator_category
std::forward_iterator_tag iterator_category
Definition: range.h:213
make_unique.h
concat_iteratort::operator*
value_type & operator*()
Definition: range.h:248
map_iteratort::operator->
const value_type * operator->() const
Definition: range.h:78
map_iteratort::difference_type
typename iteratort::difference_type difference_type
Definition: range.h:29
map_iteratort::underlying
iteratort underlying
Definition: range.h:97
ranget
A range is a pair of a begin and an end iterators.
Definition: range.h:311
concat_iteratort::second_begin
second_iteratort second_begin
Definition: range.h:289
filter_iteratort::filter_iteratort
filter_iteratort(std::shared_ptr< std::function< bool(const value_type &)>> f, iteratort underlying, iteratort end)
Filter between underlying and end using f.
Definition: range.h:173
map_iteratort::current
std::shared_ptr< outputt > current
Stores the result of f at the current position of the iterator.
Definition: range.h:105
filter_iteratort::difference_type
typename iteratort::difference_type difference_type
Definition: range.h:114
filter_iteratort
Iterator which only stops at elements for which some given function f is true.
Definition: range.h:111
map_iteratort::operator!=
bool operator!=(const map_iteratort &other) const
Definition: range.h:40
concat_iteratort::pointer
const value_type * pointer
Definition: range.h:211
ranget::empty
bool empty() const
Definition: range.h:363
filter_iteratort::value_type
typename iteratort::value_type value_type
Definition: range.h:115
ranget::filter
ranget< filter_iteratort< iteratort > > filter(std::function< bool(const value_typet &)> f)
Definition: range.h:321
ranget::ranget
ranget(iteratort begin, iteratort end)
Definition: range.h:316
filter_iteratort::reference
const value_type & reference
Definition: range.h:117
map_iteratort::map_iteratort
map_iteratort(iteratort underlying, iteratort underlying_end, std::shared_ptr< std::function< value_type(const typename iteratort::value_type &)>> f)
Definition: range.h:83
concat_iteratort::operator!=
bool operator!=(const concat_iteratort &other) const
Definition: range.h:225
map_iteratort::reference
const outputt & reference
Definition: range.h:32
filter_iteratort::operator++
const filter_iteratort operator++(int)
Postincrement operator.
Definition: range.h:139
filter_iteratort::iterator_category
std::forward_iterator_tag iterator_category
Definition: range.h:118
concat_iteratort::first_begin
first_iteratort first_begin
Definition: range.h:287
map_iteratort::operator*
const value_type & operator*() const
Definition: range.h:73
concat_iteratort::concat_iteratort
concat_iteratort(first_iteratort first_begin, first_iteratort first_end, second_iteratort second_begin)
Definition: range.h:276
filter_iteratort::operator==
bool operator==(const filter_iteratort &other) const
Definition: range.h:120
map_iteratort::f
std::shared_ptr< std::function< value_type(const typename iteratort::value_type &)> > f
Definition: range.h:101
concat_iteratort::operator++
const concat_iteratort operator++(int)
Postincrement operator.
Definition: range.h:241
filter_iteratort::operator++
filter_iteratort & operator++()
Preincrement operator.
Definition: range.h:131
map_iteratort::operator->
value_type * operator->()
Definition: range.h:68
map_iteratort::operator++
const map_iteratort operator++(int)
Postincrement operator.
Definition: range.h:56
map_iteratort::underlying_end
iteratort underlying_end
Definition: range.h:98
filter_iteratort::operator->
const value_type * operator->() const
Definition: range.h:161
concat_iteratort::difference_type
typename first_iteratort::difference_type difference_type
Definition: range.h:209
filter_iteratort::operator*
const value_type & operator*() const
Definition: range.h:156
map_iteratort::value_type
outputt value_type
Definition: range.h:30
filter_iteratort::operator!=
bool operator!=(const filter_iteratort &other) const
Definition: range.h:125
concat_iteratort::reference
const value_type & reference
Definition: range.h:212
make_range
ranget< iteratort > make_range(iteratort begin, iteratort end)
Definition: range.h:384
filter_iteratort::f
std::shared_ptr< std::function< bool(const value_type &)> > f
Definition: range.h:187
ranget::concat
ranget< concat_iteratort< iteratort, other_iteratort > > concat(ranget< other_iteratort > other)
Definition: range.h:353