contrib/llvm/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   /// A proxy object for computing a reference via indirecting a copy of an
  50   /// iterator. This is used in APIs which need to produce a reference via
  51   /// indirection but for which the iterator object might be a temporary. The
  52   /// proxy preserves the iterator internally and exposes the indirected
  53   /// reference via a conversion operator.
  54   class ReferenceProxy {
  55     friend iterator_facade_base;
  56
  57     DerivedT I;
  58
  59     ReferenceProxy(DerivedT I) : I(std::move(I)) {}
  60
  61   public:
  62     operator ReferenceT() const { return *I; }
  63   };
  64
  65 public:
  66   DerivedT operator+(DifferenceTypeT n) const {
  67     static_assert(
  68         IsRandomAccess,
  69         "The '+' operator is only defined for random access iterators.");
  70     DerivedT tmp = *static_cast<const DerivedT *>(this);
  71     tmp += n;
  72     return tmp;
  73   }
  74   friend DerivedT operator+(DifferenceTypeT n, const DerivedT &i) {
  75     static_assert(
  76         IsRandomAccess,
  77         "The '+' operator is only defined for random access iterators.");
  78     return i + n;
  79   }
  80   DerivedT operator-(DifferenceTypeT n) const {
  81     static_assert(
  82         IsRandomAccess,
  83         "The '-' operator is only defined for random access iterators.");
  84     DerivedT tmp = *static_cast<const DerivedT *>(this);
  85     tmp -= n;
  86     return tmp;
  87   }
  88
  89   DerivedT &operator++() {
  90     return static_cast<DerivedT *>(this)->operator+=(1);
  91   }
  92   DerivedT operator++(int) {
  93     DerivedT tmp = *static_cast<DerivedT *>(this);
  94     ++*static_cast<DerivedT *>(this);
  95     return tmp;
  96   }
  97   DerivedT &operator--() {
  98     static_assert(
  99         IsBidirectional,
 100         "The decrement operator is only defined for bidirectional iterators.");
 101     return static_cast<DerivedT *>(this)->operator-=(1);
 102   }
 103   DerivedT operator--(int) {
 104     static_assert(
 105         IsBidirectional,
 106         "The decrement operator is only defined for bidirectional iterators.");
 107     DerivedT tmp = *static_cast<DerivedT *>(this);
 108     --*static_cast<DerivedT *>(this);
 109     return tmp;
 110   }
 111
 112   bool operator!=(const DerivedT &RHS) const {
 113     return !static_cast<const DerivedT *>(this)->operator==(RHS);
 114   }
 115
 116   bool operator>(const DerivedT &RHS) const {
 117     static_assert(
 118         IsRandomAccess,
 119         "Relational operators are only defined for random access iterators.");
 120     return !static_cast<const DerivedT *>(this)->operator<(RHS) &&
 121            !static_cast<const DerivedT *>(this)->operator==(RHS);
 122   }
 123   bool operator<=(const DerivedT &RHS) const {
 124     static_assert(
 125         IsRandomAccess,
 126         "Relational operators are only defined for random access iterators.");
 127     return !static_cast<const DerivedT *>(this)->operator>(RHS);
 128   }
 129   bool operator>=(const DerivedT &RHS) const {
 130     static_assert(
 131         IsRandomAccess,
 132         "Relational operators are only defined for random access iterators.");
 133     return !static_cast<const DerivedT *>(this)->operator<(RHS);
 134   }
 135
 136   PointerT operator->() const {
 137     return &static_cast<const DerivedT *>(this)->operator*();
 138   }
 139   ReferenceProxy operator[](DifferenceTypeT n) const {
 140     static_assert(IsRandomAccess,
 141                   "Subscripting is only defined for random access iterators.");
 142     return ReferenceProxy(static_cast<const DerivedT *>(this)->operator+(n));
 143   }
 144 };
 145
 146 /// \brief CRTP base class for adapting an iterator to a different type.
 147 ///
 148 /// This class can be used through CRTP to adapt one iterator into another.
 149 /// Typically this is done through providing in the derived class a custom \c
 150 /// operator* implementation. Other methods can be overridden as well.
 151 template <
 152     typename DerivedT, typename WrappedIteratorT,
 153     typename IteratorCategoryT =
 154         typename std::iterator_traits<WrappedIteratorT>::iterator_category,
 155     typename T = typename std::iterator_traits<WrappedIteratorT>::value_type,
 156     typename DifferenceTypeT =
 157         typename std::iterator_traits<WrappedIteratorT>::difference_type,
 158     typename PointerT = typename std::conditional<
 159         std::is_same<T, typename std::iterator_traits<
 160                             WrappedIteratorT>::value_type>::value,
 161         typename std::iterator_traits<WrappedIteratorT>::pointer, T *>::type,
 162     typename ReferenceT = typename std::conditional<
 163         std::is_same<T, typename std::iterator_traits<
 164                             WrappedIteratorT>::value_type>::value,
 165         typename std::iterator_traits<WrappedIteratorT>::reference, T &>::type,
 166     // Don't provide these, they are mostly to act as aliases below.
 167     typename WrappedTraitsT = std::iterator_traits<WrappedIteratorT>>
 168 class iterator_adaptor_base
 169     : public iterator_facade_base<DerivedT, IteratorCategoryT, T,
 170                                   DifferenceTypeT, PointerT, ReferenceT> {
 171   typedef typename iterator_adaptor_base::iterator_facade_base BaseT;
 172
 173 protected:
 174   WrappedIteratorT I;
 175
 176   iterator_adaptor_base() = default;
 177
 178   explicit iterator_adaptor_base(WrappedIteratorT u) : I(std::move(u)) {}
 179
 180   const WrappedIteratorT &wrapped() const { return I; }
 181
 182 public:
 183   typedef DifferenceTypeT difference_type;
 184
 185   DerivedT &operator+=(difference_type n) {
 186     static_assert(
 187         BaseT::IsRandomAccess,
 188         "The '+=' operator is only defined for random access iterators.");
 189     I += n;
 190     return *static_cast<DerivedT *>(this);
 191   }
 192   DerivedT &operator-=(difference_type n) {
 193     static_assert(
 194         BaseT::IsRandomAccess,
 195         "The '-=' operator is only defined for random access iterators.");
 196     I -= n;
 197     return *static_cast<DerivedT *>(this);
 198   }
 199   using BaseT::operator-;
 200   difference_type operator-(const DerivedT &RHS) const {
 201     static_assert(
 202         BaseT::IsRandomAccess,
 203         "The '-' operator is only defined for random access iterators.");
 204     return I - RHS.I;
 205   }
 206
 207   // We have to explicitly provide ++ and -- rather than letting the facade
 208   // forward to += because WrappedIteratorT might not support +=.
 209   using BaseT::operator++;
 210   DerivedT &operator++() {
 211     ++I;
 212     return *static_cast<DerivedT *>(this);
 213   }
 214   using BaseT::operator--;
 215   DerivedT &operator--() {
 216     static_assert(
 217         BaseT::IsBidirectional,
 218         "The decrement operator is only defined for bidirectional iterators.");
 219     --I;
 220     return *static_cast<DerivedT *>(this);
 221   }
 222
 223   bool operator==(const DerivedT &RHS) const { return I == RHS.I; }
 224   bool operator<(const DerivedT &RHS) const {
 225     static_assert(
 226         BaseT::IsRandomAccess,
 227         "Relational operators are only defined for random access iterators.");
 228     return I < RHS.I;
 229   }
 230
 231   ReferenceT operator*() const { return *I; }
 232 };
 233
 234 /// \brief An iterator type that allows iterating over the pointees via some
 235 /// other iterator.
 236 ///
 237 /// The typical usage of this is to expose a type that iterates over Ts, but
 238 /// which is implemented with some iterator over T*s:
 239 ///
 240 /// \code
 241 ///   typedef pointee_iterator<SmallVectorImpl<T *>::iterator> iterator;
 242 /// \endcode
 243 template <typename WrappedIteratorT,
 244           typename T = typename std::remove_reference<
 245               decltype(**std::declval<WrappedIteratorT>())>::type>
 246 struct pointee_iterator
 247     : iterator_adaptor_base<
 248           pointee_iterator<WrappedIteratorT>, WrappedIteratorT,
 249           typename std::iterator_traits<WrappedIteratorT>::iterator_category,
 250           T> {
 251   pointee_iterator() = default;
 252   template <typename U>
 253   pointee_iterator(U &&u)
 254       : pointee_iterator::iterator_adaptor_base(std::forward<U &&>(u)) {}
 255
 256   T &operator*() const { return **this->I; }
 257 };
 258
 259 }
 260
 261 #endif