• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
13 #include <cstddef>
14 #include <iterator>
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() = default;
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)
I(std::forward<U &&> (u))163       : I(std::forward<U &&>(u)) {}
164 
wrapped()165   const WrappedIteratorT &wrapped() const { return I; }
166 
167 public:
168   typedef DifferenceTypeT difference_type;
169 
170   DerivedT &operator+=(difference_type n) {
171     static_assert(
172         BaseT::IsRandomAccess,
173         "The '+=' operator is only defined for random access iterators.");
174     I += n;
175     return *static_cast<DerivedT *>(this);
176   }
177   DerivedT &operator-=(difference_type n) {
178     static_assert(
179         BaseT::IsRandomAccess,
180         "The '-=' operator is only defined for random access iterators.");
181     I -= n;
182     return *static_cast<DerivedT *>(this);
183   }
184   using BaseT::operator-;
185   difference_type operator-(const DerivedT &RHS) const {
186     static_assert(
187         BaseT::IsRandomAccess,
188         "The '-' operator is only defined for random access iterators.");
189     return I - RHS.I;
190   }
191 
192   // We have to explicitly provide ++ and -- rather than letting the facade
193   // forward to += because WrappedIteratorT might not support +=.
194   using BaseT::operator++;
195   DerivedT &operator++() {
196     ++I;
197     return *static_cast<DerivedT *>(this);
198   }
199   using BaseT::operator--;
200   DerivedT &operator--() {
201     static_assert(
202         BaseT::IsBidirectional,
203         "The decrement operator is only defined for bidirectional iterators.");
204     --I;
205     return *static_cast<DerivedT *>(this);
206   }
207 
208   bool operator==(const DerivedT &RHS) const { return I == RHS.I; }
209   bool operator<(const DerivedT &RHS) const {
210     static_assert(
211         BaseT::IsRandomAccess,
212         "Relational operators are only defined for random access iterators.");
213     return I < RHS.I;
214   }
215 
216   ReferenceT operator*() const { return *I; }
217 };
218 
219 /// \brief An iterator type that allows iterating over the pointees via some
220 /// other iterator.
221 ///
222 /// The typical usage of this is to expose a type that iterates over Ts, but
223 /// which is implemented with some iterator over T*s:
224 ///
225 /// \code
226 ///   typedef pointee_iterator<SmallVectorImpl<T *>::iterator> iterator;
227 /// \endcode
228 template <typename WrappedIteratorT,
229           typename T = typename std::remove_reference<
230               decltype(**std::declval<WrappedIteratorT>())>::type>
231 struct pointee_iterator
232     : iterator_adaptor_base<
233           pointee_iterator<WrappedIteratorT>, WrappedIteratorT,
234           typename std::iterator_traits<WrappedIteratorT>::iterator_category,
235           T> {
236   pointee_iterator() = default;
237   template <typename U>
pointee_iteratorpointee_iterator238   pointee_iterator(U &&u)
239       : pointee_iterator::iterator_adaptor_base(std::forward<U &&>(u)) {}
240 
241   T &operator*() const { return **this->I; }
242 };
243 
244 }
245 
246 #endif
247