mfbt/IntegerRange.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 /* Iterator over ranges of integers */
   8
   9 #ifndef mozilla_IntegerRange_h
  10 #define mozilla_IntegerRange_h
  11
  12 #include "mozilla/Assertions.h"
  13 #include "mozilla/ReverseIterator.h"
  14
  15 #include <iterator>
  16 #include <type_traits>
  17
  18 namespace mozilla {
  19
  20 namespace detail {
  21
  22 template <typename IntTypeT>
  23 class IntegerIterator {
  24  public:
  25   // It is disputable whether these type definitions are correct, since
  26   // operator* doesn't return a reference at all. Also, the iterator_category
  27   // can be at most std::input_iterator_tag (rather than
  28   // std::bidrectional_iterator_tag, as it might seem), because it is a stashing
  29   // iterator. See also, e.g.,
  30   // https://stackoverflow.com/questions/50909701/what-should-be-iterator-category-for-a-stashing-iterator
  31   using value_type = const IntTypeT;
  32   using pointer = const value_type*;
  33   using reference = const value_type&;
  34   using difference_type = std::make_signed_t<IntTypeT>;
  35   using iterator_category = std::input_iterator_tag;
  36
  37   template <typename IntType>
  38   explicit IntegerIterator(IntType aCurrent) : mCurrent(aCurrent) {}
  39
  40   template <typename IntType>
  41   explicit IntegerIterator(const IntegerIterator<IntType>& aOther)
  42       : mCurrent(aOther.mCurrent) {}
  43
  44   // This intentionally returns a value rather than a reference, to make
  45   // mozilla::ReverseIterator work with it. Still, std::reverse_iterator cannot
  46   // be used with IntegerIterator because it still is a "stashing iterator". See
  47   // Bug 1175485.
  48   IntTypeT operator*() const { return mCurrent; }
  49
  50   /* Increment and decrement operators */
  51
  52   IntegerIterator& operator++() {
  53     ++mCurrent;
  54     return *this;
  55   }
  56   IntegerIterator& operator--() {
  57     --mCurrent;
  58     return *this;
  59   }
  60   IntegerIterator operator++(int) {
  61     auto ret = *this;
  62     ++mCurrent;
  63     return ret;
  64   }
  65   IntegerIterator operator--(int) {
  66     auto ret = *this;
  67     --mCurrent;
  68     return ret;
  69   }
  70
  71   /* Comparison operators */
  72
  73   template <typename IntType1, typename IntType2>
  74   friend bool operator==(const IntegerIterator<IntType1>& aIter1,
  75                          const IntegerIterator<IntType2>& aIter2);
  76   template <typename IntType1, typename IntType2>
  77   friend bool operator!=(const IntegerIterator<IntType1>& aIter1,
  78                          const IntegerIterator<IntType2>& aIter2);
  79   template <typename IntType1, typename IntType2>
  80   friend bool operator<(const IntegerIterator<IntType1>& aIter1,
  81                         const IntegerIterator<IntType2>& aIter2);
  82   template <typename IntType1, typename IntType2>
  83   friend bool operator<=(const IntegerIterator<IntType1>& aIter1,
  84                          const IntegerIterator<IntType2>& aIter2);
  85   template <typename IntType1, typename IntType2>
  86   friend bool operator>(const IntegerIterator<IntType1>& aIter1,
  87                         const IntegerIterator<IntType2>& aIter2);
  88   template <typename IntType1, typename IntType2>
  89   friend bool operator>=(const IntegerIterator<IntType1>& aIter1,
  90                          const IntegerIterator<IntType2>& aIter2);
  91
  92  private:
  93   IntTypeT mCurrent;
  94 };
  95
  96 template <typename IntType1, typename IntType2>
  97 bool operator==(const IntegerIterator<IntType1>& aIter1,
  98                 const IntegerIterator<IntType2>& aIter2) {
  99   return aIter1.mCurrent == aIter2.mCurrent;
 100 }
 101
 102 template <typename IntType1, typename IntType2>
 103 bool operator!=(const IntegerIterator<IntType1>& aIter1,
 104                 const IntegerIterator<IntType2>& aIter2) {
 105   return aIter1.mCurrent != aIter2.mCurrent;
 106 }
 107
 108 template <typename IntType1, typename IntType2>
 109 bool operator<(const IntegerIterator<IntType1>& aIter1,
 110                const IntegerIterator<IntType2>& aIter2) {
 111   return aIter1.mCurrent < aIter2.mCurrent;
 112 }
 113
 114 template <typename IntType1, typename IntType2>
 115 bool operator<=(const IntegerIterator<IntType1>& aIter1,
 116                 const IntegerIterator<IntType2>& aIter2) {
 117   return aIter1.mCurrent <= aIter2.mCurrent;
 118 }
 119
 120 template <typename IntType1, typename IntType2>
 121 bool operator>(const IntegerIterator<IntType1>& aIter1,
 122                const IntegerIterator<IntType2>& aIter2) {
 123   return aIter1.mCurrent > aIter2.mCurrent;
 124 }
 125
 126 template <typename IntType1, typename IntType2>
 127 bool operator>=(const IntegerIterator<IntType1>& aIter1,
 128                 const IntegerIterator<IntType2>& aIter2) {
 129   return aIter1.mCurrent >= aIter2.mCurrent;
 130 }
 131
 132 template <typename IntTypeT>
 133 class IntegerRange {
 134  public:
 135   typedef IntegerIterator<IntTypeT> iterator;
 136   typedef IntegerIterator<IntTypeT> const_iterator;
 137   typedef ReverseIterator<IntegerIterator<IntTypeT>> reverse_iterator;
 138   typedef ReverseIterator<IntegerIterator<IntTypeT>> const_reverse_iterator;
 139
 140   template <typename IntType>
 141   explicit IntegerRange(IntType aEnd) : mBegin(0), mEnd(aEnd) {}
 142
 143   template <typename IntType1, typename IntType2>
 144   IntegerRange(IntType1 aBegin, IntType2 aEnd) : mBegin(aBegin), mEnd(aEnd) {}
 145
 146   iterator begin() const { return iterator(mBegin); }
 147   const_iterator cbegin() const { return begin(); }
 148   iterator end() const { return iterator(mEnd); }
 149   const_iterator cend() const { return end(); }
 150   reverse_iterator rbegin() const { return reverse_iterator(iterator(mEnd)); }
 151   const_reverse_iterator crbegin() const { return rbegin(); }
 152   reverse_iterator rend() const { return reverse_iterator(iterator(mBegin)); }
 153   const_reverse_iterator crend() const { return rend(); }
 154
 155  private:
 156   IntTypeT mBegin;
 157   IntTypeT mEnd;
 158 };
 159
 160 template <typename T, bool = std::is_unsigned_v<T>>
 161 struct GeqZero {
 162   static bool isNonNegative(T t) { return t >= 0; }
 163 };
 164
 165 template <typename T>
 166 struct GeqZero<T, true> {
 167   static bool isNonNegative(T t) { return true; }
 168 };
 169
 170 }  // namespace detail
 171
 172 template <typename IntType>
 173 detail::IntegerRange<IntType> IntegerRange(IntType aEnd) {
 174   static_assert(std::is_integral_v<IntType>, "value must be integral");
 175   MOZ_ASSERT(detail::GeqZero<IntType>::isNonNegative(aEnd),
 176              "Should never have negative value here");
 177   return detail::IntegerRange<IntType>(aEnd);
 178 }
 179
 180 template <typename IntType1, typename IntType2>
 181 detail::IntegerRange<IntType2> IntegerRange(IntType1 aBegin, IntType2 aEnd) {
 182   static_assert(std::is_integral_v<IntType1> && std::is_integral_v<IntType2>,
 183                 "values must both be integral");
 184   static_assert(std::is_signed_v<IntType1> == std::is_signed_v<IntType2>,
 185                 "signed/unsigned mismatch");
 186   MOZ_ASSERT(aEnd >= aBegin, "End value should be larger than begin value");
 187   return detail::IntegerRange<IntType2>(aBegin, aEnd);
 188 }
 189
 190 }  // namespace mozilla
 191
 192 #endif  // mozilla_IntegerRange_h