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 for adapting an iterator to a different type.
  18 ///
  19 /// This class can be used through CRTP to adapt one iterator into another.
  20 /// Typically this is done through providing in the derived class a custom \c
  21 /// operator* implementation. Other methods can be overridden as well.
  22 ///
  23 /// FIXME: Factor out the iterator-facade-like aspects into a base class that
  24 /// can be used for defining completely custom iterators.
  25 template <typename DerivedT, typename WrappedIteratorT, typename T,
  26           typename PointerT = T *, typename ReferenceT = T &,
  27           // Don't provide these, they are mostly to act as aliases below.
  28           typename WrappedTraitsT = std::iterator_traits<WrappedIteratorT>>
  29 class iterator_adaptor_base
  30     : public std::iterator<typename WrappedTraitsT::iterator_category, T,
  31                            typename WrappedTraitsT::difference_type, PointerT,
  32                            ReferenceT> {
  33 protected:
  34   WrappedIteratorT I;
  35
  36   iterator_adaptor_base() {}
  37
  38   template <
  39       typename U,
  40       typename = typename std::enable_if<
  41           !std::is_same<typename std::remove_cv<
  42                             typename std::remove_reference<U>::type>::type,
  43                         DerivedT>::value>::type>
  44   explicit iterator_adaptor_base(U &&u)
  45       : I(std::forward<U &&>(u)) {}
  46
  47 public:
  48   typedef typename iterator_adaptor_base::iterator::difference_type
  49   difference_type;
  50
  51   DerivedT &operator+=(difference_type n) {
  52     I += n;
  53     return *static_cast<DerivedT *>(this);
  54   }
  55   DerivedT &operator-=(difference_type n) {
  56     I -= n;
  57     return *static_cast<DerivedT *>(this);
  58   }
  59   DerivedT operator+(difference_type n) const {
  60     DerivedT tmp = *this;
  61     tmp += n;
  62     return tmp;
  63   }
  64   friend DerivedT operator+(difference_type n, const DerivedT &i) {
  65     return i + n;
  66   }
  67   DerivedT operator-(difference_type n) const {
  68     DerivedT tmp = *this;
  69     tmp -= n;
  70     return tmp;
  71   }
  72   difference_type operator-(const DerivedT &RHS) const { return I - RHS.I; }
  73
  74   DerivedT &operator++() {
  75     ++I;
  76     return *static_cast<DerivedT *>(this);
  77   }
  78   DerivedT &operator--() {
  79     --I;
  80     return *static_cast<DerivedT *>(this);
  81   }
  82   DerivedT operator++(int) {
  83     DerivedT tmp = *static_cast<DerivedT *>(this);
  84     ++*this;
  85     return tmp;
  86   }
  87   DerivedT operator--(int) {
  88     DerivedT tmp = *static_cast<DerivedT *>(this);
  89     --*this;
  90     return tmp;
  91   }
  92
  93   bool operator==(const DerivedT &RHS) const { return I == RHS.I; }
  94   bool operator!=(const DerivedT &RHS) const {
  95     return !static_cast<const DerivedT *>(this)->operator==(RHS);
  96   }
  97
  98   bool operator<(const DerivedT &RHS) const { return I < RHS.I; }
  99   bool operator>(const DerivedT &RHS) const {
 100     return !static_cast<const DerivedT *>(this)->operator<(RHS) &&
 101            !static_cast<const DerivedT *>(this)->operator==(RHS);
 102   }
 103   bool operator<=(const DerivedT &RHS) const {
 104     return !static_cast<const DerivedT *>(this)->operator>(RHS);
 105   }
 106   bool operator>=(const DerivedT &RHS) const {
 107     return !static_cast<const DerivedT *>(this)->operator<(RHS);
 108   }
 109
 110   ReferenceT operator*() const { return *I; }
 111   PointerT operator->() const {
 112     return static_cast<const DerivedT *>(this)->operator*();
 113   }
 114   ReferenceT operator[](difference_type n) const {
 115     return *static_cast<const DerivedT *>(this)->operator+(n);
 116   }
 117 };
 118
 119 /// \brief An iterator type that allows iterating over the pointees via some
 120 /// other iterator.
 121 ///
 122 /// The typical usage of this is to expose a type that iterates over Ts, but
 123 /// which is implemented with some iterator over T*s:
 124 ///
 125 /// \code
 126 ///   typedef pointee_iterator<SmallVectorImpl<T *>::iterator> iterator;
 127 /// \endcode
 128 template <
 129     typename WrappedIteratorT,
 130     typename T = typename std::remove_pointer<
 131         typename std::iterator_traits<WrappedIteratorT>::value_type>::type>
 132 struct pointee_iterator
 133     : iterator_adaptor_base<pointee_iterator<WrappedIteratorT>,
 134                             WrappedIteratorT, T> {
 135   pointee_iterator() {}
 136   template <typename U>
 137   pointee_iterator(U &&u)
 138       : pointee_iterator::iterator_adaptor_base(std::forward<U &&>(u)) {}
 139
 140   T &operator*() const { return **this->I; }
 141 };
 142
 143 }
 144
 145 #endif