1 // Copyright 2010-2021 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
setcharvdc(ushort CharMem)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
22 namespace 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)) { ... }
37 template <typename Iterator>
38 class BeginEndWrapper {
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.
57 template <typename Iterator>
58 inline BeginEndWrapper<Iterator> BeginEndRange(Iterator begin, Iterator end) {
59 return BeginEndWrapper<Iterator>(begin, end);
60 }
61 template <typename Iterator>
62 inline BeginEndWrapper<Iterator> BeginEndRange(
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.
70 template <typename MultiMap>
71 inline BeginEndWrapper<typename MultiMap::iterator> EqualRange(
72 MultiMap& multi_map, const typename MultiMap::key_type& key) {
73 return BeginEndRange(multi_map.equal_range(key));
74 }
75 template <typename MultiMap>
76 inline BeginEndWrapper<typename MultiMap::const_iterator> EqualRange(
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)) { ... }
85 template <typename Container>
86 class BeginEndReverseIteratorWrapper {
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 };
97 template <typename Container>
98 BeginEndReverseIteratorWrapper<Container> Reverse(const Container& c) {
99 return BeginEndReverseIteratorWrapper<Container>(c);
100 }
101
102 // Simple iterator on an integer range, see IntegerRange below.
103 template <typename IntegerType>
104 class IntegerRangeIterator
105 : public std::iterator<std::input_iterator_tag, IntegerType> {
106 public:
107 explicit IntegerRangeIterator(IntegerType value) : index_(value) {}
108 IntegerRangeIterator(const IntegerRangeIterator& other)
109 : index_(other.index_) {}
110 IntegerRangeIterator& operator=(const IntegerRangeIterator& other) {
111 index_ = other.index_;
112 }
113 bool operator!=(const IntegerRangeIterator& other) const {
114 // This may seems weird, but using < instead of != avoid almost-infinite
115 // loop if one use IntegerRange<int>(1, 0) below for instance.
116 return index_ < other.index_;
117 }
118 bool operator==(const IntegerRangeIterator& other) const {
119 return index_ == other.index_;
120 }
121 IntegerType operator*() const { return index_; }
122 IntegerRangeIterator& operator++() {
123 ++index_;
124 return *this;
125 }
126 IntegerRangeIterator operator++(int) {
127 IntegerRangeIterator previous_position(*this);
128 ++index_;
129 return previous_position;
130 }
131
132 private:
133 IntegerType index_;
134 };
135
136 // Allows to easily construct nice functions for range-based for loop.
137 // This can be used like this:
138 //
139 // for (const int i : IntegerRange<int>(0, 10)) { ... }
140 //
141 // But it main purpose is to be used as return value for more complex classes:
142 //
143 // for (const ArcIndex arc : graph.AllOutgoingArcs());
144 // for (const NodeIndex node : graph.AllNodes());
145 template <typename IntegerType>
146 class IntegerRange : public BeginEndWrapper<IntegerRangeIterator<IntegerType>> {
147 public:
148 IntegerRange(IntegerType begin, IntegerType end)
149 : BeginEndWrapper<IntegerRangeIterator<IntegerType>>(
150 IntegerRangeIterator<IntegerType>(begin),
151 IntegerRangeIterator<IntegerType>(end)) {}
152 };
153
154 // Allow iterating over a vector<T> as a mutable vector<T*>.
155 template <class T>
156 struct MutableVectorIteration {
157 explicit MutableVectorIteration(std::vector<T>* v) : v_(v) {}
158 struct Iterator {
159 explicit Iterator(typename std::vector<T>::iterator it) : it_(it) {}
160 T* operator*() { return &*it_; }
161 Iterator& operator++() {
162 it_++;
163 return *this;
164 }
165 bool operator!=(const Iterator& other) const { return other.it_ != it_; }
166
167 private:
168 typename std::vector<T>::iterator it_;
169 };
170 Iterator begin() { return Iterator(v_->begin()); }
171 Iterator end() { return Iterator(v_->end()); }
172
173 private:
174 std::vector<T>* const v_;
175 };
176 } // namespace util
177
178 #endif // UTIL_GRAPH_ITERATORS_H_
179