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