cprover
range.h
Go to the documentation of this file.
1/*******************************************************************\
2
3Module: Range
4
5Author: 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
25template <typename iteratort, typename outputt>
27{
28public:
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)),
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
96private:
97 iteratort underlying;
98 iteratort underlying_end;
99 std::shared_ptr<
100 std::function<value_type(const typename iteratort::value_type &)>>
102
105 std::shared_ptr<outputt> current = nullptr;
106};
107
110template <typename iteratort>
112{
113public:
114 using difference_type = typename iteratort::difference_type;
115 using value_type = typename iteratort::value_type;
116 using pointer = typename iteratort::pointer;
117 using reference = typename iteratort::reference;
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
164 std::shared_ptr<std::function<bool(const value_type &)>> f,
165 iteratort underlying,
166 iteratort end)
167 : underlying(std::move(underlying)),
168 underlying_end(std::move(end)),
169 f(std::move(f))
170 {
172 }
173
174private:
175 iteratort underlying;
176 const iteratort underlying_end;
177 std::shared_ptr<std::function<bool(const value_type &)>> f;
178
185 {
186 while(underlying != underlying_end && !(*f)(*underlying))
187 ++underlying;
188 }
189};
190
195template <typename first_iteratort, typename second_iteratort>
197{
198public:
199 using difference_type = typename first_iteratort::difference_type;
200 using value_type = typename first_iteratort::value_type;
201 using pointer = typename first_iteratort::pointer;
202 using reference = typename first_iteratort::reference;
203 using iterator_category = std::forward_iterator_tag;
204
205 static_assert(
206 std::is_same<value_type, typename first_iteratort::value_type>::value,
207 "Concatenated iterators should have the same value type");
208
209 bool operator==(const concat_iteratort &other) const
210 {
211 return first_begin == other.first_begin && first_end == other.first_end &&
212 second_begin == other.second_begin;
213 }
214
215 bool operator!=(const concat_iteratort &other) const
216 {
217 return !(*this == other);
218 }
219
222 {
224 ++second_begin;
225 else
226 ++first_begin;
227 return *this;
228 }
229
232 {
234 this->operator++();
235 return tmp;
236 }
237
239 {
241 return *second_begin;
242 return *first_begin;
243 }
244
246 {
248 return &(*second_begin);
249 return &(*first_begin);
250 }
251
253 first_iteratort first_begin,
254 first_iteratort first_end,
255 second_iteratort second_begin)
256 : first_begin(std::move(first_begin)),
257 first_end(std::move(first_end)),
259 {
260 }
261
262private:
263 first_iteratort first_begin;
264 first_iteratort first_end;
265 second_iteratort second_begin;
266};
267
274template <
275 typename first_iteratort,
276 typename second_iteratort,
277 bool same_size = true>
279{
280public:
281 using difference_type = typename first_iteratort::difference_type;
282 using value_type = std::pair<
283 typename first_iteratort::value_type,
284 typename second_iteratort::value_type>;
287 using iterator_category = std::forward_iterator_tag;
288
289 bool operator==(const zip_iteratort &other) const
290 {
291 if(!same_size && end_reached() && other.end_reached())
292 return true;
293
294 return first_begin == other.first_begin && first_end == other.first_end &&
295 second_begin == other.second_begin && second_end == other.second_end;
296 }
297
298 bool operator!=(const zip_iteratort &other) const
299 {
300 return !(*this == other);
301 }
302
305 {
307 ++first_begin;
308 ++second_begin;
309 INVARIANT(
310 !same_size ||
312 "Zipped ranges should have the same size");
314 ? std::make_shared<value_type>(*first_begin, *second_begin)
315 : nullptr;
316 return *this;
317 }
318
321 {
323 this->operator++();
324 return tmp;
325 }
326
328 {
329 PRECONDITION(current != nullptr);
330 return *current;
331 }
332
334 {
335 return current.get();
336 }
337
339 first_iteratort _first_begin,
340 first_iteratort _first_end,
341 second_iteratort _second_begin,
342 second_iteratort _second_end)
343 : first_begin(std::move(_first_begin)),
344 first_end(std::move(_first_end)),
345 second_begin(std::move(_second_begin)),
346 second_end(std::move(_second_end))
347 {
349 !same_size ||
352 current = util_make_unique<value_type>(*first_begin, *second_begin);
353 }
354
355private:
356 first_iteratort first_begin;
357 first_iteratort first_end;
358 second_iteratort second_begin;
359 second_iteratort second_end;
360 std::shared_ptr<value_type> current = nullptr;
361
362 bool end_reached() const
363 {
364 if(same_size)
365 {
366 INVARIANT(
368 "Zip ranges should have same size");
369 return first_begin == first_end;
370 }
371 else
373 }
374};
375
394template <typename iteratort>
395struct ranget final
396{
397public:
398 using value_type = typename iteratort::value_type;
399
400 ranget(iteratort begin, iteratort end)
401 : begin_value(std::move(begin)), end_value(std::move(end))
402 {
403 }
404
406 filter(std::function<bool(const value_type &)> f)
407 {
408 auto shared_f = std::make_shared<decltype(f)>(std::move(f));
409 filter_iteratort<iteratort> filter_begin(shared_f, begin(), end());
410 filter_iteratort<iteratort> filter_end(shared_f, end(), end());
411 return ranget<filter_iteratort<iteratort>>(filter_begin, filter_end);
412 }
413
420 template <typename functiont>
421 auto map(functiont &&f) -> ranget<map_iteratort<
422 iteratort,
423 typename std::result_of<functiont(value_type)>::type>>
424 {
425 using outputt = typename std::result_of<functiont(value_type)>::type;
426 auto shared_f = std::make_shared<
427 std::function<outputt(const typename iteratort::value_type &)>>(
428 std::forward<functiont>(f));
429 auto map_begin =
431 auto map_end = map_iteratort<iteratort, outputt>(end(), end(), shared_f);
433 std::move(map_begin), std::move(map_end));
434 }
435
436 template <typename other_iteratort>
439 {
441 begin(), end(), other.begin());
442 auto concat_end =
445 concat_begin, concat_end);
446 }
447
451 template <bool same_size = true, typename other_iteratort>
454 {
456 begin(), end(), other.begin(), other.end());
458 end(), end(), other.end(), other.end());
460 zip_begin, zip_end);
461 }
462
463 template <bool same_size = true, typename containert>
464 auto zip(containert &container)
465 -> ranget<zip_iteratort<iteratort, decltype(container.begin()), same_size>>
466 {
467 return zip<same_size>(
468 ranget<decltype(container.begin())>{container.begin(), container.end()});
469 }
470
471 bool empty() const
472 {
473 return begin_value == end_value;
474 }
475
479 ranget<iteratort> drop(std::size_t count) &&
480 {
481 for(; count > 0 && begin_value != end_value; --count)
482 ++begin_value;
483 return ranget<iteratort>{std::move(begin_value), std::move(end_value)};
484 }
485
489 ranget<iteratort> drop(std::size_t count) const &
490 {
491 return ranget<iteratort>{begin(), end()}.drop(count);
492 }
493
494 iteratort begin() const
495 {
496 return begin_value;
497 }
498
499 const iteratort &end() const
500 {
501 return end_value;
502 }
503
506 template <typename containert>
507 containert collect() const
508 {
509 return containert(begin(), end());
510 }
511
512 template <typename containert>
513 operator containert() const
514 {
515 return collect<containert>();
516 }
517
518private:
519 iteratort begin_value;
520 iteratort end_value;
521};
522
523template <typename iteratort>
524ranget<iteratort> make_range(iteratort begin, iteratort end)
525{
526 return ranget<iteratort>(begin, end);
527}
528
529template <typename containert>
530auto make_range(containert &container) -> ranget<decltype(container.begin())>
531{
532 return ranget<decltype(container.begin())>(
533 container.begin(), container.end());
534}
535
539template <typename multimapt>
541equal_range(const multimapt &multimap, const typename multimapt::key_type &key)
542{
543 auto iterator_pair = multimap.equal_range(key);
544 return make_range(iterator_pair.first, iterator_pair.second);
545}
546
547#endif // CPROVER_UTIL_RANGE_H
Iterator which only stops at elements for which some given function f is true.
Definition: range.h:112
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:184
reference operator*() const
Definition: range.h:146
iteratort underlying
Definition: range.h:175
typename iteratort::difference_type difference_type
Definition: range.h:114
typename iteratort::value_type value_type
Definition: range.h:115
typename iteratort::reference reference
Definition: range.h:117
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:163
typename iteratort::pointer pointer
Definition: range.h:116
std::shared_ptr< std::function< bool(const value_type &)> > f
Definition: range.h:177
bool operator==(const filter_iteratort &other) const
Definition: range.h:120
bool operator!=(const filter_iteratort &other) const
Definition: range.h:125
pointer operator->() const
Definition: range.h:151
filter_iteratort operator++(int)
Postincrement operator.
Definition: range.h:139
filter_iteratort & operator++()
Preincrement operator.
Definition: range.h:131
const iteratort underlying_end
Definition: range.h:176
std::forward_iterator_tag iterator_category
Definition: range.h:118
Iterator which applies some given function f after each increment and returns its result on dereferen...
Definition: range.h:27
value_type * operator->()
Definition: range.h:68
const value_type & operator*() const
Definition: range.h:73
const outputt * pointer
Definition: range.h:31
std::shared_ptr< outputt > current
Stores the result of f at the current position of the iterator.
Definition: range.h:105
iteratort underlying
Definition: range.h:97
typename iteratort::difference_type difference_type
Definition: range.h:29
outputt value_type
Definition: range.h:30
bool operator==(const map_iteratort &other) const
Definition: range.h:35
std::shared_ptr< std::function< value_type(const typename iteratort::value_type &)> > f
Definition: range.h:101
bool operator!=(const map_iteratort &other) const
Definition: range.h:40
map_iteratort operator++(int)
Postincrement operator.
Definition: range.h:56
const value_type * operator->() const
Definition: range.h:78
map_iteratort(iteratort underlying, iteratort underlying_end, std::shared_ptr< std::function< value_type(const typename iteratort::value_type &)> > f)
Definition: range.h:83
iteratort underlying_end
Definition: range.h:98
value_type & operator*()
Definition: range.h:63
map_iteratort & operator++()
Preincrement operator.
Definition: range.h:46
std::forward_iterator_tag iterator_category
Definition: range.h:33
const outputt & reference
Definition: range.h:32
STL namespace.
ranget< iteratort > make_range(iteratort begin, iteratort end)
Definition: range.h:524
ranget< typename multimapt::const_iterator > equal_range(const multimapt &multimap, const typename multimapt::key_type &key)
Utility function to make equal_range method of multimap easier to use by returning a ranget object.
Definition: range.h:541
#define PRECONDITION(CONDITION)
Definition: invariant.h:463
On increment, increments a first iterator and when the corresponding end iterator is reached,...
Definition: range.h:197
typename first_iteratort::difference_type difference_type
Definition: range.h:199
bool operator!=(const concat_iteratort &other) const
Definition: range.h:215
reference operator*() const
Definition: range.h:238
concat_iteratort operator++(int)
Postincrement operator.
Definition: range.h:231
typename first_iteratort::reference reference
Definition: range.h:202
typename first_iteratort::value_type value_type
Definition: range.h:200
typename first_iteratort::pointer pointer
Definition: range.h:201
concat_iteratort(first_iteratort first_begin, first_iteratort first_end, second_iteratort second_begin)
Definition: range.h:252
first_iteratort first_end
Definition: range.h:264
std::forward_iterator_tag iterator_category
Definition: range.h:203
pointer operator->() const
Definition: range.h:245
first_iteratort first_begin
Definition: range.h:263
second_iteratort second_begin
Definition: range.h:265
concat_iteratort & operator++()
Preincrement operator.
Definition: range.h:221
bool operator==(const concat_iteratort &other) const
Definition: range.h:209
A range is a pair of a begin and an end iterators.
Definition: range.h:396
iteratort begin() const
Definition: range.h:494
iteratort end_value
Definition: range.h:520
ranget< zip_iteratort< iteratort, other_iteratort, same_size > > zip(ranget< other_iteratort > other)
Combine two ranges to make a range over pairs.
Definition: range.h:453
auto zip(containert &container) -> ranget< zip_iteratort< iteratort, decltype(container.begin()), same_size > >
Definition: range.h:464
ranget< iteratort > drop(std::size_t count) &&
Return an new range containing the same elements except for the first count elements.
Definition: range.h:479
ranget< iteratort > drop(std::size_t count) const &
Return an new range containing the same elements except for the first count elements.
Definition: range.h:489
ranget(iteratort begin, iteratort end)
Definition: range.h:400
ranget< filter_iteratort< iteratort > > filter(std::function< bool(const value_type &)> f)
Definition: range.h:406
iteratort begin_value
Definition: range.h:519
const iteratort & end() const
Definition: range.h:499
bool empty() const
Definition: range.h:471
auto map(functiont &&f) -> ranget< map_iteratort< iteratort, typename std::result_of< functiont(value_type)>::type > >
The type of elements contained in the resulting range is deduced from the return type of f.
Definition: range.h:421
typename iteratort::value_type value_type
Definition: range.h:398
containert collect() const
Constructs a collection containing the values, which this range iterates over.
Definition: range.h:507
ranget< concat_iteratort< iteratort, other_iteratort > > concat(ranget< other_iteratort > other)
Definition: range.h:438
Zip two ranges to make a range of pairs.
Definition: range.h:279
typename first_iteratort::difference_type difference_type
Definition: range.h:281
zip_iteratort(first_iteratort _first_begin, first_iteratort _first_end, second_iteratort _second_begin, second_iteratort _second_end)
Definition: range.h:338
second_iteratort second_begin
Definition: range.h:358
first_iteratort first_begin
Definition: range.h:356
second_iteratort second_end
Definition: range.h:359
bool operator!=(const zip_iteratort &other) const
Definition: range.h:298
zip_iteratort operator++(int)
Postincrement operator.
Definition: range.h:320
reference operator*() const
Definition: range.h:327
first_iteratort first_end
Definition: range.h:357
std::shared_ptr< value_type > current
Definition: range.h:360
value_type * pointer
Definition: range.h:285
pointer operator->() const
Definition: range.h:333
std::forward_iterator_tag iterator_category
Definition: range.h:287
value_type & reference
Definition: range.h:286
zip_iteratort & operator++()
Preincrement operator.
Definition: range.h:304
std::pair< typename first_iteratort::value_type, typename second_iteratort::value_type > value_type
Definition: range.h:284
bool operator==(const zip_iteratort &other) const
Definition: range.h:289
bool end_reached() const
Definition: range.h:362