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