OR-Tools  8.2
iterators.h
Go to the documentation of this file.
1// Copyright 2010-2018 Google LLC
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6// http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
14// Helper classes to make it easy to implement range-based for loops.
15
16#ifndef UTIL_GRAPH_ITERATORS_H_
17#define UTIL_GRAPH_ITERATORS_H_
18
19#include <iterator>
20#include <vector>
21
22namespace util {
23
24// This is useful for wrapping iterators of a class that support many different
25// iterations. For instance, on a Graph class, one can write:
26//
27// BeginEndWrapper<OutgoingArcIterator> Graph::OutgoingArcs(NodeInde node)
28// const {
29// return BeginEndRange(
30// OutgoingArcIterator(*this, node, /*at_end=*/false),
31// OutgoingArcIterator(*this, node, /*at_end=*/true));
32// }
33//
34// And a client will use it like this:
35//
36// for (const ArcIndex arc : graph.OutgoingArcs(node)) { ... }
37template <typename Iterator>
39 public:
40 using const_iterator = Iterator;
41 using value_type = typename std::iterator_traits<Iterator>::value_type;
42
43 BeginEndWrapper(Iterator begin, Iterator end) : begin_(begin), end_(end) {}
44 Iterator begin() const { return begin_; }
45 Iterator end() const { return end_; }
46
47 bool empty() const { return begin() == end(); }
48
49 private:
50 const Iterator begin_;
51 const Iterator end_;
52};
53
54// Inline wrapper methods, to make the client code even simpler.
55// The harm of overloading is probably less than the benefit of the nice,
56// compact name, in this special case.
57template <typename Iterator>
58inline BeginEndWrapper<Iterator> BeginEndRange(Iterator begin, Iterator end) {
59 return BeginEndWrapper<Iterator>(begin, end);
60}
61template <typename Iterator>
63 std::pair<Iterator, Iterator> begin_end) {
64 return BeginEndWrapper<Iterator>(begin_end.first, begin_end.second);
65}
66
67// Shortcut for BeginEndRange(multimap::equal_range(key)).
68// TODO(user): go further and expose only the values, not the pairs (key,
69// values) since the caller already knows the key.
70template <typename MultiMap>
72 MultiMap& multi_map, const typename MultiMap::key_type& key) {
73 return BeginEndRange(multi_map.equal_range(key));
74}
75template <typename MultiMap>
77 const MultiMap& multi_map, const typename MultiMap::key_type& key) {
78 return BeginEndRange(multi_map.equal_range(key));
79}
80
81// The Reverse() function allows to reverse the iteration order of a range-based
82// for loop over a container that support STL reverse iterators.
83// The syntax is:
84// for (const type& t : Reverse(container_of_t)) { ... }
85template <typename Container>
87 public:
88 explicit BeginEndReverseIteratorWrapper(const Container& c) : c_(c) {}
89 typename Container::const_reverse_iterator begin() const {
90 return c_.rbegin();
91 }
92 typename Container::const_reverse_iterator end() const { return c_.rend(); }
93
94 private:
95 const Container& c_;
96};
97template <typename Container>
100}
101
102// Simple iterator on an integer range, see IntegerRange below.
103template <typename IntegerType>
105{
106 public:
107 using iterator_category = std::input_iterator_tag;
108 using value_type = IntegerType;
109 using difference_type = std::ptrdiff_t;
110 using pointer = IntegerType*;
111 using reference = IntegerType&;
112 explicit IntegerRangeIterator(IntegerType value) : index_(value) {}
114 : index_(other.index_) {}
116 index_ = other.index_;
117 }
118 bool operator!=(const IntegerRangeIterator& other) const {
119 // This may seems weird, but using < instead of != avoid almost-infinite
120 // loop if one use IntegerRange<int>(1, 0) below for instance.
121 return index_ < other.index_;
122 }
123 bool operator==(const IntegerRangeIterator& other) const {
124 return index_ == other.index_;
125 }
126 IntegerType operator*() const { return index_; }
128 ++index_;
129 return *this;
130 }
132 IntegerRangeIterator previous_position(*this);
133 ++index_;
134 return previous_position;
135 }
136
137 private:
138 IntegerType index_;
139};
140
141// Allows to easily construct nice functions for range-based for loop.
142// This can be used like this:
143//
144// for (const int i : IntegerRange<int>(0, 10)) { ... }
145//
146// But it main purpose is to be used as return value for more complex classes:
147//
148// for (const ArcIndex arc : graph.AllOutgoingArcs());
149// for (const NodeIndex node : graph.AllNodes());
150template <typename IntegerType>
151class IntegerRange : public BeginEndWrapper<IntegerRangeIterator<IntegerType>> {
152 public:
153 IntegerRange(IntegerType begin, IntegerType end)
155 IntegerRangeIterator<IntegerType>(begin),
156 IntegerRangeIterator<IntegerType>(end)) {}
157};
158
159// Allow iterating over a vector<T> as a mutable vector<T*>.
160template <class T>
162 explicit MutableVectorIteration(std::vector<T>* v) : v_(v) {}
163 struct Iterator {
164 explicit Iterator(typename std::vector<T>::iterator it) : it_(it) {}
165 T* operator*() { return &*it_; }
167 it_++;
168 return *this;
169 }
170 bool operator!=(const Iterator& other) const { return other.it_ != it_; }
171
172 private:
173 typename std::vector<T>::iterator it_;
174 };
175 Iterator begin() { return Iterator(v_->begin()); }
176 Iterator end() { return Iterator(v_->end()); }
177
178 private:
179 std::vector<T>* const v_;
180};
181} // namespace util
182
183#endif // UTIL_GRAPH_ITERATORS_H_
Container::const_reverse_iterator begin() const
Definition: iterators.h:89
BeginEndReverseIteratorWrapper(const Container &c)
Definition: iterators.h:88
Container::const_reverse_iterator end() const
Definition: iterators.h:92
Iterator begin() const
Definition: iterators.h:44
Iterator end() const
Definition: iterators.h:45
bool empty() const
Definition: iterators.h:47
Iterator const_iterator
Definition: iterators.h:40
typename std::iterator_traits< Iterator >::value_type value_type
Definition: iterators.h:41
BeginEndWrapper(Iterator begin, Iterator end)
Definition: iterators.h:43
IntegerRange(IntegerType begin, IntegerType end)
Definition: iterators.h:153
IntegerType operator*() const
Definition: iterators.h:126
IntegerRangeIterator(IntegerType value)
Definition: iterators.h:112
IntegerRangeIterator(const IntegerRangeIterator &other)
Definition: iterators.h:113
IntegerType & reference
Definition: iterators.h:111
IntegerRangeIterator operator++(int)
Definition: iterators.h:131
IntegerRangeIterator & operator=(const IntegerRangeIterator &other)
Definition: iterators.h:115
bool operator!=(const IntegerRangeIterator &other) const
Definition: iterators.h:118
bool operator==(const IntegerRangeIterator &other) const
Definition: iterators.h:123
std::input_iterator_tag iterator_category
Definition: iterators.h:107
std::ptrdiff_t difference_type
Definition: iterators.h:109
IntegerRangeIterator & operator++()
Definition: iterators.h:127
int64 value
BeginEndWrapper< typename MultiMap::iterator > EqualRange(MultiMap &multi_map, const typename MultiMap::key_type &key)
Definition: iterators.h:71
BeginEndReverseIteratorWrapper< Container > Reverse(const Container &c)
Definition: iterators.h:98
BeginEndWrapper< Iterator > BeginEndRange(Iterator begin, Iterator end)
Definition: iterators.h:58
bool operator!=(const Iterator &other) const
Definition: iterators.h:170
Iterator(typename std::vector< T >::iterator it)
Definition: iterators.h:164
MutableVectorIteration(std::vector< T > *v)
Definition: iterators.h:162