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, 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 protected:
 108   WrappedIteratorT I;
 109
 110   iterator_adaptor_base() {}
 111
 112   template <
 113       typename U,
 114       typename = typename std::enable_if<
 115           !std::is_base_of<typename std::remove_cv<
 116                                typename std::remove_reference<U>::type>::type,
 117                            DerivedT>::value>::type>
 118   explicit iterator_adaptor_base(U &&u)
 119       : I(std::forward<U &&>(u)) {}
 120
 121 public:
 122   typedef typename WrappedTraitsT::difference_type difference_type;
 123
 124   DerivedT &operator+=(difference_type n) {
 125     I += n;
 126     return *static_cast<DerivedT *>(this);
 127   }
 128   DerivedT &operator-=(difference_type n) {
 129     I -= n;
 130     return *static_cast<DerivedT *>(this);
 131   }
 132   using iterator_adaptor_base::iterator_facade_base::operator-;
 133   difference_type operator-(const DerivedT &RHS) const { return I - RHS.I; }
 134
 135   // We have to explicitly provide ++ and -- rather than letting the facade
 136   // forward to += because WrappedIteratorT might not support +=.
 137   using iterator_adaptor_base::iterator_facade_base::operator++;
 138   DerivedT &operator++() {
 139     ++I;
 140     return *static_cast<DerivedT *>(this);
 141   }
 142   using iterator_adaptor_base::iterator_facade_base::operator--;
 143   DerivedT &operator--() {
 144     --I;
 145     return *static_cast<DerivedT *>(this);
 146   }
 147
 148   bool operator==(const DerivedT &RHS) const { return I == RHS.I; }
 149   bool operator<(const DerivedT &RHS) const { return I < RHS.I; }
 150
 151   ReferenceT operator*() const { return *I; }
 152 };
 153
 154 /// \brief An iterator type that allows iterating over the pointees via some
 155 /// other iterator.
 156 ///
 157 /// The typical usage of this is to expose a type that iterates over Ts, but
 158 /// which is implemented with some iterator over T*s:
 159 ///
 160 /// \code
 161 ///   typedef pointee_iterator<SmallVectorImpl<T *>::iterator> iterator;
 162 /// \endcode
 163 template <
 164     typename WrappedIteratorT,
 165     typename T = typename std::remove_pointer<
 166         typename std::iterator_traits<WrappedIteratorT>::value_type>::type>
 167 struct pointee_iterator
 168     : iterator_adaptor_base<pointee_iterator<WrappedIteratorT>,
 169                             WrappedIteratorT, T> {
 170   pointee_iterator() {}
 171   template <typename U>
 172   pointee_iterator(U &&u)
 173       : pointee_iterator::iterator_adaptor_base(std::forward<U &&>(u)) {}
 174
 175   T &operator*() const { return **this->I; }
 176 };
 177
 178 }
 179
 180 #endif