]>
Commit | Line | Data |
---|---|---|
1a4d82fc JJ |
1 | //===- iterator.h - Utilities for using and defining iterators --*- C++ -*-===// |
2 | // | |
3 | // The LLVM Compiler Infrastructure | |
4 | // | |
5 | // This file is distributed under the University of Illinois Open Source | |
6 | // License. See LICENSE.TXT for details. | |
7 | // | |
8 | //===----------------------------------------------------------------------===// | |
9 | ||
10 | #ifndef LLVM_ADT_ITERATOR_H | |
11 | #define LLVM_ADT_ITERATOR_H | |
12 | ||
1a4d82fc | 13 | #include <cstddef> |
85aaf69f | 14 | #include <iterator> |
1a4d82fc JJ |
15 | |
16 | namespace llvm { | |
17 | ||
18 | /// \brief CRTP base class which implements the entire standard iterator facade | |
19 | /// in terms of a minimal subset of the interface. | |
20 | /// | |
21 | /// Use this when it is reasonable to implement most of the iterator | |
22 | /// functionality in terms of a core subset. If you need special behavior or | |
23 | /// there are performance implications for this, you may want to override the | |
24 | /// relevant members instead. | |
25 | /// | |
26 | /// Note, one abstraction that this does *not* provide is implementing | |
27 | /// subtraction in terms of addition by negating the difference. Negation isn't | |
28 | /// always information preserving, and I can see very reasonable iterator | |
29 | /// designs where this doesn't work well. It doesn't really force much added | |
30 | /// boilerplate anyways. | |
31 | /// | |
32 | /// Another abstraction that this doesn't provide is implementing increment in | |
33 | /// terms of addition of one. These aren't equivalent for all iterator | |
34 | /// categories, and respecting that adds a lot of complexity for little gain. | |
35 | template <typename DerivedT, typename IteratorCategoryT, typename T, | |
36 | typename DifferenceTypeT = std::ptrdiff_t, typename PointerT = T *, | |
37 | typename ReferenceT = T &> | |
38 | class iterator_facade_base | |
39 | : public std::iterator<IteratorCategoryT, T, DifferenceTypeT, PointerT, | |
40 | ReferenceT> { | |
41 | protected: | |
42 | enum { | |
43 | IsRandomAccess = | |
44 | std::is_base_of<std::random_access_iterator_tag, IteratorCategoryT>::value, | |
45 | IsBidirectional = | |
46 | std::is_base_of<std::bidirectional_iterator_tag, IteratorCategoryT>::value, | |
47 | }; | |
48 | ||
49 | public: | |
50 | DerivedT operator+(DifferenceTypeT n) const { | |
51 | static_assert( | |
52 | IsRandomAccess, | |
53 | "The '+' operator is only defined for random access iterators."); | |
54 | DerivedT tmp = *static_cast<const DerivedT *>(this); | |
55 | tmp += n; | |
56 | return tmp; | |
57 | } | |
58 | friend DerivedT operator+(DifferenceTypeT n, const DerivedT &i) { | |
59 | static_assert( | |
60 | IsRandomAccess, | |
61 | "The '+' operator is only defined for random access iterators."); | |
62 | return i + n; | |
63 | } | |
64 | DerivedT operator-(DifferenceTypeT n) const { | |
65 | static_assert( | |
66 | IsRandomAccess, | |
67 | "The '-' operator is only defined for random access iterators."); | |
68 | DerivedT tmp = *static_cast<const DerivedT *>(this); | |
69 | tmp -= n; | |
70 | return tmp; | |
71 | } | |
72 | ||
73 | DerivedT &operator++() { | |
74 | return static_cast<DerivedT *>(this)->operator+=(1); | |
75 | } | |
76 | DerivedT operator++(int) { | |
77 | DerivedT tmp = *static_cast<DerivedT *>(this); | |
78 | ++*static_cast<DerivedT *>(this); | |
79 | return tmp; | |
80 | } | |
81 | DerivedT &operator--() { | |
82 | static_assert( | |
83 | IsBidirectional, | |
84 | "The decrement operator is only defined for bidirectional iterators."); | |
85 | return static_cast<DerivedT *>(this)->operator-=(1); | |
86 | } | |
87 | DerivedT operator--(int) { | |
88 | static_assert( | |
89 | IsBidirectional, | |
90 | "The decrement operator is only defined for bidirectional iterators."); | |
91 | DerivedT tmp = *static_cast<DerivedT *>(this); | |
92 | --*static_cast<DerivedT *>(this); | |
93 | return tmp; | |
94 | } | |
95 | ||
96 | bool operator!=(const DerivedT &RHS) const { | |
97 | return !static_cast<const DerivedT *>(this)->operator==(RHS); | |
98 | } | |
99 | ||
100 | bool operator>(const DerivedT &RHS) const { | |
101 | static_assert( | |
102 | IsRandomAccess, | |
103 | "Relational operators are only defined for random access iterators."); | |
104 | return !static_cast<const DerivedT *>(this)->operator<(RHS) && | |
105 | !static_cast<const DerivedT *>(this)->operator==(RHS); | |
106 | } | |
107 | bool operator<=(const DerivedT &RHS) const { | |
108 | static_assert( | |
109 | IsRandomAccess, | |
110 | "Relational operators are only defined for random access iterators."); | |
111 | return !static_cast<const DerivedT *>(this)->operator>(RHS); | |
112 | } | |
113 | bool operator>=(const DerivedT &RHS) const { | |
114 | static_assert( | |
115 | IsRandomAccess, | |
116 | "Relational operators are only defined for random access iterators."); | |
117 | return !static_cast<const DerivedT *>(this)->operator<(RHS); | |
118 | } | |
119 | ||
120 | PointerT operator->() const { | |
121 | return &static_cast<const DerivedT *>(this)->operator*(); | |
122 | } | |
123 | ReferenceT operator[](DifferenceTypeT n) const { | |
124 | static_assert(IsRandomAccess, | |
125 | "Subscripting is only defined for random access iterators."); | |
126 | return *static_cast<const DerivedT *>(this)->operator+(n); | |
127 | } | |
128 | }; | |
129 | ||
130 | /// \brief CRTP base class for adapting an iterator to a different type. | |
131 | /// | |
132 | /// This class can be used through CRTP to adapt one iterator into another. | |
133 | /// Typically this is done through providing in the derived class a custom \c | |
134 | /// operator* implementation. Other methods can be overridden as well. | |
135 | template < | |
136 | typename DerivedT, typename WrappedIteratorT, | |
137 | typename IteratorCategoryT = | |
138 | typename std::iterator_traits<WrappedIteratorT>::iterator_category, | |
139 | typename T = typename std::iterator_traits<WrappedIteratorT>::value_type, | |
140 | typename DifferenceTypeT = | |
141 | typename std::iterator_traits<WrappedIteratorT>::difference_type, | |
142 | typename PointerT = T *, typename ReferenceT = T &, | |
143 | // Don't provide these, they are mostly to act as aliases below. | |
144 | typename WrappedTraitsT = std::iterator_traits<WrappedIteratorT>> | |
145 | class iterator_adaptor_base | |
146 | : public iterator_facade_base<DerivedT, IteratorCategoryT, T, | |
147 | DifferenceTypeT, PointerT, ReferenceT> { | |
148 | typedef typename iterator_adaptor_base::iterator_facade_base BaseT; | |
149 | ||
150 | protected: | |
151 | WrappedIteratorT I; | |
152 | ||
153 | iterator_adaptor_base() {} | |
154 | ||
155 | template <typename U> | |
156 | explicit iterator_adaptor_base( | |
157 | U &&u, | |
158 | typename std::enable_if< | |
159 | !std::is_base_of<typename std::remove_cv< | |
160 | typename std::remove_reference<U>::type>::type, | |
161 | DerivedT>::value, | |
162 | int>::type = 0) | |
163 | : I(std::forward<U &&>(u)) {} | |
164 | ||
165 | public: | |
166 | typedef DifferenceTypeT difference_type; | |
167 | ||
168 | DerivedT &operator+=(difference_type n) { | |
169 | static_assert( | |
170 | BaseT::IsRandomAccess, | |
171 | "The '+=' operator is only defined for random access iterators."); | |
172 | I += n; | |
173 | return *static_cast<DerivedT *>(this); | |
174 | } | |
175 | DerivedT &operator-=(difference_type n) { | |
176 | static_assert( | |
177 | BaseT::IsRandomAccess, | |
178 | "The '-=' operator is only defined for random access iterators."); | |
179 | I -= n; | |
180 | return *static_cast<DerivedT *>(this); | |
181 | } | |
182 | using BaseT::operator-; | |
183 | difference_type operator-(const DerivedT &RHS) const { | |
184 | static_assert( | |
185 | BaseT::IsRandomAccess, | |
186 | "The '-' operator is only defined for random access iterators."); | |
187 | return I - RHS.I; | |
188 | } | |
189 | ||
190 | // We have to explicitly provide ++ and -- rather than letting the facade | |
191 | // forward to += because WrappedIteratorT might not support +=. | |
192 | using BaseT::operator++; | |
193 | DerivedT &operator++() { | |
194 | ++I; | |
195 | return *static_cast<DerivedT *>(this); | |
196 | } | |
197 | using BaseT::operator--; | |
198 | DerivedT &operator--() { | |
199 | static_assert( | |
200 | BaseT::IsBidirectional, | |
201 | "The decrement operator is only defined for bidirectional iterators."); | |
202 | --I; | |
203 | return *static_cast<DerivedT *>(this); | |
204 | } | |
205 | ||
206 | bool operator==(const DerivedT &RHS) const { return I == RHS.I; } | |
207 | bool operator<(const DerivedT &RHS) const { | |
208 | static_assert( | |
209 | BaseT::IsRandomAccess, | |
210 | "Relational operators are only defined for random access iterators."); | |
211 | return I < RHS.I; | |
212 | } | |
213 | ||
214 | ReferenceT operator*() const { return *I; } | |
215 | }; | |
216 | ||
217 | /// \brief An iterator type that allows iterating over the pointees via some | |
218 | /// other iterator. | |
219 | /// | |
220 | /// The typical usage of this is to expose a type that iterates over Ts, but | |
221 | /// which is implemented with some iterator over T*s: | |
222 | /// | |
223 | /// \code | |
224 | /// typedef pointee_iterator<SmallVectorImpl<T *>::iterator> iterator; | |
225 | /// \endcode | |
226 | template <typename WrappedIteratorT, | |
227 | typename T = typename std::remove_reference< | |
228 | decltype(**std::declval<WrappedIteratorT>())>::type> | |
229 | struct pointee_iterator | |
230 | : iterator_adaptor_base< | |
231 | pointee_iterator<WrappedIteratorT>, WrappedIteratorT, | |
232 | typename std::iterator_traits<WrappedIteratorT>::iterator_category, | |
233 | T> { | |
234 | pointee_iterator() {} | |
235 | template <typename U> | |
236 | pointee_iterator(U &&u) | |
237 | : pointee_iterator::iterator_adaptor_base(std::forward<U &&>(u)) {} | |
238 | ||
239 | T &operator*() const { return **this->I; } | |
240 | }; | |
241 | ||
242 | } | |
243 | ||
244 | #endif |