include/llvm/ADT/iterator.h

   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)
 163       : I(std::forward<U &&>(u)) {}
 164
 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>
 238   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