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 public:
    166   typedef DifferenceTypeT difference_type;
    167 
    168   DerivedT &operator+=(difference_type n) {
    169     static_assert(
    170         BaseT::IsRandomAccess,
    171         "The '+=' operator is only defined for random access iterators.");
    172     I += n;
    173     return *static_cast<DerivedT *>(this);
    174   }
    175   DerivedT &operator-=(difference_type n) {
    176     static_assert(
    177         BaseT::IsRandomAccess,
    178         "The '-=' operator is only defined for random access iterators.");
    179     I -= n;
    180     return *static_cast<DerivedT *>(this);
    181   }
    182   using BaseT::operator-;
    183   difference_type operator-(const DerivedT &RHS) const {
    184     static_assert(
    185         BaseT::IsRandomAccess,
    186         "The '-' operator is only defined for random access iterators.");
    187     return I - RHS.I;
    188   }
    189 
    190   // We have to explicitly provide ++ and -- rather than letting the facade
    191   // forward to += because WrappedIteratorT might not support +=.
    192   using BaseT::operator++;
    193   DerivedT &operator++() {
    194     ++I;
    195     return *static_cast<DerivedT *>(this);
    196   }
    197   using BaseT::operator--;
    198   DerivedT &operator--() {
    199     static_assert(
    200         BaseT::IsBidirectional,
    201         "The decrement operator is only defined for bidirectional iterators.");
    202     --I;
    203     return *static_cast<DerivedT *>(this);
    204   }
    205 
    206   bool operator==(const DerivedT &RHS) const { return I == RHS.I; }
    207   bool operator<(const DerivedT &RHS) const {
    208     static_assert(
    209         BaseT::IsRandomAccess,
    210         "Relational operators are only defined for random access iterators.");
    211     return I < RHS.I;
    212   }
    213 
    214   ReferenceT operator*() const { return *I; }
    215 };
    216 
    217 /// \brief An iterator type that allows iterating over the pointees via some
    218 /// other iterator.
    219 ///
    220 /// The typical usage of this is to expose a type that iterates over Ts, but
    221 /// which is implemented with some iterator over T*s:
    222 ///
    223 /// \code
    224 ///   typedef pointee_iterator<SmallVectorImpl<T *>::iterator> iterator;
    225 /// \endcode
    226 template <typename WrappedIteratorT,
    227           typename T = typename std::remove_reference<
    228               decltype(**std::declval<WrappedIteratorT>())>::type>
    229 struct pointee_iterator
    230     : iterator_adaptor_base<
    231           pointee_iterator<WrappedIteratorT>, WrappedIteratorT,
    232           typename std::iterator_traits<WrappedIteratorT>::iterator_category,
    233           T> {
    234   pointee_iterator() = default;
    235   template <typename U>
    236   pointee_iterator(U &&u)
    237       : pointee_iterator::iterator_adaptor_base(std::forward<U &&>(u)) {}
    238 
    239   T &operator*() const { return **this->I; }
    240 };
    241 
    242 }
    243 
    244 #endif
    245