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 #include <cstddef>
  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 struct iterator_facade_base
  39     : std::iterator<IteratorCategoryT, T, DifferenceTypeT, PointerT,
  40                     ReferenceT> {
  41   DerivedT operator+(DifferenceTypeT n) const {
  42     DerivedT tmp = *static_cast<const DerivedT *>(this);
  43     tmp += n;
  44     return tmp;
  45   }
  46   friend DerivedT operator+(DifferenceTypeT n, const DerivedT &i) {
  47     return i + n;
  48   }
  49   DerivedT operator-(DifferenceTypeT n) const {
  50     DerivedT tmp = *static_cast<const DerivedT *>(this);
  51     tmp -= n;
  52     return tmp;
  53   }
  54
  55   DerivedT &operator++() {
  56     return static_cast<DerivedT *>(this)->operator+=(1);
  57   }
  58   DerivedT operator++(int) {
  59     DerivedT tmp = *static_cast<DerivedT *>(this);
  60     ++*static_cast<DerivedT *>(this);
  61     return tmp;
  62   }
  63   DerivedT &operator--() {
  64     return static_cast<DerivedT *>(this)->operator-=(1);
  65   }
  66   DerivedT operator--(int) {
  67     DerivedT tmp = *static_cast<DerivedT *>(this);
  68     --*static_cast<DerivedT *>(this);
  69     return tmp;
  70   }
  71
  72   bool operator!=(const DerivedT &RHS) const {
  73     return !static_cast<const DerivedT *>(this)->operator==(RHS);
  74   }
  75
  76   bool operator>(const DerivedT &RHS) const {
  77     return !static_cast<const DerivedT *>(this)->operator<(RHS) &&
  78            !static_cast<const DerivedT *>(this)->operator==(RHS);
  79   }
  80   bool operator<=(const DerivedT &RHS) const {
  81     return !static_cast<const DerivedT *>(this)->operator>(RHS);
  82   }
  83   bool operator>=(const DerivedT &RHS) const {
  84     return !static_cast<const DerivedT *>(this)->operator<(RHS);
  85   }
  86
  87   PointerT operator->() const {
  88     return &static_cast<const DerivedT *>(this)->operator*();
  89   }
  90   ReferenceT operator[](DifferenceTypeT n) const {
  91     return *static_cast<const DerivedT *>(this)->operator+(n);
  92   }
  93 };
  94
  95 /// \brief CRTP base class for adapting an iterator to a different type.
  96 ///
  97 /// This class can be used through CRTP to adapt one iterator into another.
  98 /// Typically this is done through providing in the derived class a custom \c
  99 /// operator* implementation. Other methods can be overridden as well.
 100 template <
 101     typename DerivedT, typename WrappedIteratorT,
 102     typename IteratorCategoryT =
 103         typename std::iterator_traits<WrappedIteratorT>::iterator_category,
 104     typename T = typename std::iterator_traits<WrappedIteratorT>::value_type,
 105     typename DifferenceTypeT =
 106         typename std::iterator_traits<WrappedIteratorT>::difference_type,
 107     typename PointerT = T *, typename ReferenceT = T &,
 108     // Don't provide these, they are mostly to act as aliases below.
 109     typename WrappedTraitsT = std::iterator_traits<WrappedIteratorT>>
 110 class iterator_adaptor_base
 111     : public iterator_facade_base<DerivedT, IteratorCategoryT, T,
 112                                   DifferenceTypeT, PointerT, ReferenceT> {
 113   typedef typename iterator_adaptor_base::iterator_facade_base BaseT;
 114
 115 protected:
 116   WrappedIteratorT I;
 117
 118   iterator_adaptor_base() {}
 119
 120   template <typename U>
 121   explicit iterator_adaptor_base(
 122       U &&u,
 123       typename std::enable_if<
 124           !std::is_base_of<typename std::remove_cv<
 125                                typename std::remove_reference<U>::type>::type,
 126                            DerivedT>::value,
 127           int>::type = 0)
 128       : I(std::forward<U &&>(u)) {}
 129
 130 public:
 131   typedef DifferenceTypeT difference_type;
 132
 133   DerivedT &operator+=(difference_type n) {
 134     I += n;
 135     return *static_cast<DerivedT *>(this);
 136   }
 137   DerivedT &operator-=(difference_type n) {
 138     I -= n;
 139     return *static_cast<DerivedT *>(this);
 140   }
 141   using BaseT::operator-;
 142   difference_type operator-(const DerivedT &RHS) const { return I - RHS.I; }
 143
 144   // We have to explicitly provide ++ and -- rather than letting the facade
 145   // forward to += because WrappedIteratorT might not support +=.
 146   using BaseT::operator++;
 147   DerivedT &operator++() {
 148     ++I;
 149     return *static_cast<DerivedT *>(this);
 150   }
 151   using BaseT::operator--;
 152   DerivedT &operator--() {
 153     --I;
 154     return *static_cast<DerivedT *>(this);
 155   }
 156
 157   bool operator==(const DerivedT &RHS) const { return I == RHS.I; }
 158   bool operator<(const DerivedT &RHS) const { return I < RHS.I; }
 159
 160   ReferenceT operator*() const { return *I; }
 161 };
 162
 163 /// \brief An iterator type that allows iterating over the pointees via some
 164 /// other iterator.
 165 ///
 166 /// The typical usage of this is to expose a type that iterates over Ts, but
 167 /// which is implemented with some iterator over T*s:
 168 ///
 169 /// \code
 170 ///   typedef pointee_iterator<SmallVectorImpl<T *>::iterator> iterator;
 171 /// \endcode
 172 template <typename WrappedIteratorT,
 173           typename T = typename std::remove_reference<
 174               decltype(**std::declval<WrappedIteratorT>())>::type>
 175 struct pointee_iterator
 176     : iterator_adaptor_base<
 177           pointee_iterator<WrappedIteratorT>, WrappedIteratorT,
 178           typename std::iterator_traits<WrappedIteratorT>::iterator_category,
 179           T> {
 180   pointee_iterator() {}
 181   template <typename U>
 182   pointee_iterator(U &&u)
 183       : pointee_iterator::iterator_adaptor_base(std::forward<U &&>(u)) {}
 184
 185   T &operator*() const { return **this->I; }
 186 };
 187
 188 }
 189
 190 #endif