mfbt/ReverseIterator.h

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
   3 /* This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 /* An iterator that acts like another iterator, but iterating in
   8  * the negative direction. (Note that not all iterators can iterate
   9  * in the negative direction.) */
  10
  11 #ifndef mozilla_ReverseIterator_h
  12 #define mozilla_ReverseIterator_h
  13
  14 #include <utility>
  15
  16 #include "mozilla/Attributes.h"
  17
  18 namespace mozilla {
  19
  20 // This should only be used in cases where std::reverse_iterator cannot be used,
  21 // because the underlying iterator is not a proper bidirectional iterator, but
  22 // rather, e.g., a stashing iterator such as IntegerIterator. It is less
  23 // efficient than std::reverse_iterator for proper bidirectional iterators.
  24 template <typename IteratorT>
  25 class ReverseIterator {
  26  public:
  27   using value_type = typename IteratorT::value_type;
  28   using pointer = typename IteratorT::pointer;
  29   using reference = typename IteratorT::reference;
  30   using difference_type = typename IteratorT::difference_type;
  31   using iterator_category = typename IteratorT::iterator_category;
  32
  33   explicit ReverseIterator(IteratorT aIter) : mCurrent(std::move(aIter)) {}
  34
  35   // The return type is not reference, but rather the return type of
  36   // Iterator::operator*(), which might be value_type, to allow this to work
  37   // with stashing iterators such as IntegerIterator, see also Bug 1175485.
  38   decltype(*std::declval<IteratorT>()) operator*() const {
  39     IteratorT tmp = mCurrent;
  40     return *--tmp;
  41   }
  42
  43   /* Difference operator */
  44   difference_type operator-(const ReverseIterator& aOther) const {
  45     return aOther.mCurrent - mCurrent;
  46   }
  47
  48   /* Increments and decrements operators */
  49
  50   ReverseIterator& operator++() {
  51     --mCurrent;
  52     return *this;
  53   }
  54   ReverseIterator& operator--() {
  55     ++mCurrent;
  56     return *this;
  57   }
  58   ReverseIterator operator++(int) {
  59     auto ret = *this;
  60     mCurrent--;
  61     return ret;
  62   }
  63   ReverseIterator operator--(int) {
  64     auto ret = *this;
  65     mCurrent++;
  66     return ret;
  67   }
  68
  69   /* Comparison operators */
  70
  71   template <typename Iterator1, typename Iterator2>
  72   friend bool operator==(const ReverseIterator<Iterator1>& aIter1,
  73                          const ReverseIterator<Iterator2>& aIter2);
  74   template <typename Iterator1, typename Iterator2>
  75   friend bool operator!=(const ReverseIterator<Iterator1>& aIter1,
  76                          const ReverseIterator<Iterator2>& aIter2);
  77   template <typename Iterator1, typename Iterator2>
  78   friend bool operator<(const ReverseIterator<Iterator1>& aIter1,
  79                         const ReverseIterator<Iterator2>& aIter2);
  80   template <typename Iterator1, typename Iterator2>
  81   friend bool operator<=(const ReverseIterator<Iterator1>& aIter1,
  82                          const ReverseIterator<Iterator2>& aIter2);
  83   template <typename Iterator1, typename Iterator2>
  84   friend bool operator>(const ReverseIterator<Iterator1>& aIter1,
  85                         const ReverseIterator<Iterator2>& aIter2);
  86   template <typename Iterator1, typename Iterator2>
  87   friend bool operator>=(const ReverseIterator<Iterator1>& aIter1,
  88                          const ReverseIterator<Iterator2>& aIter2);
  89
  90  private:
  91   IteratorT mCurrent;
  92 };
  93
  94 template <typename Iterator1, typename Iterator2>
  95 bool operator==(const ReverseIterator<Iterator1>& aIter1,
  96                 const ReverseIterator<Iterator2>& aIter2) {
  97   return aIter1.mCurrent == aIter2.mCurrent;
  98 }
  99
 100 template <typename Iterator1, typename Iterator2>
 101 bool operator!=(const ReverseIterator<Iterator1>& aIter1,
 102                 const ReverseIterator<Iterator2>& aIter2) {
 103   return aIter1.mCurrent != aIter2.mCurrent;
 104 }
 105
 106 template <typename Iterator1, typename Iterator2>
 107 bool operator<(const ReverseIterator<Iterator1>& aIter1,
 108                const ReverseIterator<Iterator2>& aIter2) {
 109   return aIter1.mCurrent > aIter2.mCurrent;
 110 }
 111
 112 template <typename Iterator1, typename Iterator2>
 113 bool operator<=(const ReverseIterator<Iterator1>& aIter1,
 114                 const ReverseIterator<Iterator2>& aIter2) {
 115   return aIter1.mCurrent >= aIter2.mCurrent;
 116 }
 117
 118 template <typename Iterator1, typename Iterator2>
 119 bool operator>(const ReverseIterator<Iterator1>& aIter1,
 120                const ReverseIterator<Iterator2>& aIter2) {
 121   return aIter1.mCurrent < aIter2.mCurrent;
 122 }
 123
 124 template <typename Iterator1, typename Iterator2>
 125 bool operator>=(const ReverseIterator<Iterator1>& aIter1,
 126                 const ReverseIterator<Iterator2>& aIter2) {
 127   return aIter1.mCurrent <= aIter2.mCurrent;
 128 }
 129
 130 namespace detail {
 131
 132 template <typename IteratorT,
 133           typename ReverseIteratorT = ReverseIterator<IteratorT>>
 134 class IteratorRange {
 135  public:
 136   typedef IteratorT iterator;
 137   typedef IteratorT const_iterator;
 138   typedef ReverseIteratorT reverse_iterator;
 139   typedef ReverseIteratorT const_reverse_iterator;
 140
 141   IteratorRange(IteratorT aIterBegin, IteratorT aIterEnd)
 142       : mIterBegin(std::move(aIterBegin)), mIterEnd(std::move(aIterEnd)) {}
 143
 144   iterator begin() const { return mIterBegin; }
 145   const_iterator cbegin() const { return begin(); }
 146   iterator end() const { return mIterEnd; }
 147   const_iterator cend() const { return end(); }
 148   reverse_iterator rbegin() const { return reverse_iterator(mIterEnd); }
 149   const_reverse_iterator crbegin() const { return rbegin(); }
 150   reverse_iterator rend() const { return reverse_iterator(mIterBegin); }
 151   const_reverse_iterator crend() const { return rend(); }
 152
 153   IteratorT mIterBegin;
 154   IteratorT mIterEnd;
 155 };
 156
 157 }  // namespace detail
 158
 159 template <typename Range>
 160 detail::IteratorRange<typename Range::reverse_iterator> Reversed(
 161     Range& aRange) {
 162   return {aRange.rbegin(), aRange.rend()};
 163 }
 164
 165 template <typename Range>
 166 detail::IteratorRange<typename Range::const_reverse_iterator> Reversed(
 167     const Range& aRange) {
 168   return {aRange.rbegin(), aRange.rend()};
 169 }
 170
 171 }  // namespace mozilla
 172
 173 #endif  // mozilla_ReverseIterator_h