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() {}
 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