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 <iterator>
  14
  15 namespace llvm {
  16
  17 /// \brief CRTP base class which implements the entire standard iterator facade
  18 /// in terms of a minimal subset of the interface.
  19 ///
  20 /// Use this when it is reasonable to implement most of the iterator
  21 /// functionality in terms of a core subset. If you need special behavior or
  22 /// there are performance implications for this, you may want to override the
  23 /// relevant members instead.
  24 ///
  25 /// Note, one abstraction that this does *not* provide is implementing
  26 /// subtraction in terms of addition by negating the difference. Negation isn't
  27 /// always information preserving, and I can see very reasonable iterator
  28 /// designs where this doesn't work well. It doesn't really force much added
  29 /// boilerplate anyways.
  30 ///
  31 /// Another abstraction that this doesn't provide is implementing increment in
  32 /// terms of addition of one. These aren't equivalent for all iterator
  33 /// categories, and respecting that adds a lot of complexity for little gain.
  34 template <typename DerivedT, typename IteratorCategoryT, typename T,
  35           typename DifferenceTypeT = ptrdiff_t, typename PointerT = T *,
  36           typename ReferenceT = T &>
  37 struct iterator_facade_base
  38     : std::iterator<IteratorCategoryT, T, DifferenceTypeT, PointerT,
  39                     ReferenceT> {
  40   DerivedT operator+(DifferenceTypeT n) const {
  41     DerivedT tmp = *static_cast<const DerivedT *>(this);
  42     tmp += n;
  43     return tmp;
  44   }
  45   friend DerivedT operator+(DifferenceTypeT n, const DerivedT &i) {
  46     return i + n;
  47   }
  48   DerivedT operator-(DifferenceTypeT n) const {
  49     DerivedT tmp = *static_cast<const DerivedT *>(this);
  50     tmp -= n;
  51     return tmp;
  52   }
  53
  54   DerivedT &operator++() {
  55     return static_cast<DerivedT *>(this)->operator+=(1);
  56   }
  57   DerivedT operator++(int) {
  58     DerivedT tmp = *static_cast<DerivedT *>(this);
  59     ++*static_cast<DerivedT *>(this);
  60     return tmp;
  61   }
  62   DerivedT &operator--() {
  63     return static_cast<DerivedT *>(this)->operator-=(1);
  64   }
  65   DerivedT operator--(int) {
  66     DerivedT tmp = *static_cast<DerivedT *>(this);
  67     --*static_cast<DerivedT *>(this);
  68     return tmp;
  69   }
  70
  71   bool operator!=(const DerivedT &RHS) const {
  72     return !static_cast<const DerivedT *>(this)->operator==(RHS);
  73   }
  74
  75   bool operator>(const DerivedT &RHS) const {
  76     return !static_cast<const DerivedT *>(this)->operator<(RHS) &&
  77            !static_cast<const DerivedT *>(this)->operator==(RHS);
  78   }
  79   bool operator<=(const DerivedT &RHS) const {
  80     return !static_cast<const DerivedT *>(this)->operator>(RHS);
  81   }
  82   bool operator>=(const DerivedT &RHS) const {
  83     return !static_cast<const DerivedT *>(this)->operator<(RHS);
  84   }
  85
  86   PointerT operator->() const {
  87     return &static_cast<const DerivedT *>(this)->operator*();
  88   }
  89   ReferenceT operator[](DifferenceTypeT n) const {
  90     return *static_cast<const DerivedT *>(this)->operator+(n);
  91   }
  92 };
  93
  94 /// \brief CRTP base class for adapting an iterator to a different type.
  95 ///
  96 /// This class can be used through CRTP to adapt one iterator into another.
  97 /// Typically this is done through providing in the derived class a custom \c
  98 /// operator* implementation. Other methods can be overridden as well.
  99 template <typename DerivedT, typename WrappedIteratorT, typename T,
 100           typename PointerT = T *, typename ReferenceT = T &,
 101           // Don't provide these, they are mostly to act as aliases below.
 102           typename WrappedTraitsT = std::iterator_traits<WrappedIteratorT>>
 103 class iterator_adaptor_base
 104     : public iterator_facade_base<
 105           DerivedT, typename WrappedTraitsT::iterator_category, T,
 106           typename WrappedTraitsT::difference_type, PointerT, ReferenceT> {
 107   typedef typename iterator_adaptor_base::iterator_facade_base BaseT;
 108
 109 protected:
 110   WrappedIteratorT I;
 111
 112   iterator_adaptor_base() {}
 113
 114   template <typename U>
 115   explicit iterator_adaptor_base(
 116       U &&u,
 117       typename std::enable_if<
 118           !std::is_base_of<typename std::remove_cv<
 119                                typename std::remove_reference<U>::type>::type,
 120                            DerivedT>::value,
 121           int>::type = 0)
 122       : I(std::forward<U &&>(u)) {}
 123
 124 public:
 125   typedef typename WrappedTraitsT::difference_type difference_type;
 126
 127   DerivedT &operator+=(difference_type n) {
 128     I += n;
 129     return *static_cast<DerivedT *>(this);
 130   }
 131   DerivedT &operator-=(difference_type n) {
 132     I -= n;
 133     return *static_cast<DerivedT *>(this);
 134   }
 135   using BaseT::operator-;
 136   difference_type operator-(const DerivedT &RHS) const { return I - RHS.I; }
 137
 138   // We have to explicitly provide ++ and -- rather than letting the facade
 139   // forward to += because WrappedIteratorT might not support +=.
 140   using BaseT::operator++;
 141   DerivedT &operator++() {
 142     ++I;
 143     return *static_cast<DerivedT *>(this);
 144   }
 145   using BaseT::operator--;
 146   DerivedT &operator--() {
 147     --I;
 148     return *static_cast<DerivedT *>(this);
 149   }
 150
 151   bool operator==(const DerivedT &RHS) const { return I == RHS.I; }
 152   bool operator<(const DerivedT &RHS) const { return I < RHS.I; }
 153
 154   ReferenceT operator*() const { return *I; }
 155 };
 156
 157 /// \brief An iterator type that allows iterating over the pointees via some
 158 /// other iterator.
 159 ///
 160 /// The typical usage of this is to expose a type that iterates over Ts, but
 161 /// which is implemented with some iterator over T*s:
 162 ///
 163 /// \code
 164 ///   typedef pointee_iterator<SmallVectorImpl<T *>::iterator> iterator;
 165 /// \endcode
 166 template <typename WrappedIteratorT,
 167           typename T = typename std::remove_reference<
 168               decltype(**std::declval<WrappedIteratorT>())>::type>
 169 struct pointee_iterator
 170     : iterator_adaptor_base<pointee_iterator<WrappedIteratorT>,
 171                             WrappedIteratorT, T> {
 172   pointee_iterator() {}
 173   template <typename U>
 174   pointee_iterator(U &&u)
 175       : pointee_iterator::iterator_adaptor_base(std::forward<U &&>(u)) {}
 176
 177   T &operator*() const { return **this->I; }
 178 };
 179
 180 }
 181
 182 #endif