openMSX
xrange.hh
Go to the documentation of this file.
1 #ifndef XRANGE_HH
2 #define XRANGE_HH
3 
4 // Utility to iterate over a range of numbers,
5 // modeled after python's xrange() function.
6 //
7 // Typically used as a more compact notation for some for-loop patterns:
8 //
9 // a) loop over [0, N)
10 //
11 // auto num = expensiveFunctionCall();
12 // for (decltype(num) i = 0; i < num; ++i) { ... }
13 //
14 // for (auto i : xrange(expensiveFunctionCall()) { ... }
15 //
16 // b) loop over [B, E)
17 //
18 // auto i = func1();
19 // auto end = func2();
20 // for (/**/; i < end; ++i) { ... }
21 //
22 // for (auto i : xrange(func1(), func2()) { ... }
23 //
24 // Note that when using the xrange utility you also don't need to worry about
25 // the correct type of the induction variable.
26 //
27 // Gcc is able to optimize the xrange() based loops to the same code as the
28 // equivalent 'old-style' for loop.
29 //
30 // In an earlier version of this utility I also implemented the possibility to
31 // specify a step size (currently the step size is always +1). Although I
32 // believe that code was correct I still removed it because it was quite tricky
33 // (getting the stop condition correct is not trivial) and we don't need it
34 // currently.
35 
36 #include <cstddef>
37 #include <iterator>
38 #include <type_traits>
39 
40 template<typename T> struct XRange
41 {
42  struct Iter
43  {
44  using difference_type = ptrdiff_t;
45  using value_type = T;
46  using pointer = T*;
47  using reference = T&;
48  using iterator_category = std::random_access_iterator_tag;
49 
50  // ForwardIterator
51  [[nodiscard]] constexpr T operator*() const
52  {
53  return x;
54  }
55 
56  constexpr Iter& operator++()
57  {
58  ++x;
59  return *this;
60  }
61  constexpr Iter operator++(int)
62  {
63  auto copy = *this;
64  ++x;
65  return copy;
66  }
67 
68  [[nodiscard]] constexpr bool operator==(const Iter& other) const
69  {
70  return x == other.x;
71  }
72  [[nodiscard]] constexpr bool operator!=(const Iter& other) const
73  {
74  return x != other.x;
75  }
76 
77  // BidirectionalIterator
78  constexpr Iter& operator--()
79  {
80  --x;
81  return *this;
82  }
83  constexpr Iter operator--(int)
84  {
85  auto copy = *this;
86  --x;
87  return copy;
88  }
89 
90  // RandomAccessIterator
92  {
93  x += n;
94  return *this;
95  }
97  {
98  x -= n;
99  return *this;
100  }
101 
102  [[nodiscard]] constexpr friend Iter operator+(Iter i, difference_type n)
103  {
104  i += n;
105  return i;
106  }
107  [[nodiscard]] constexpr friend Iter operator+(difference_type n, Iter i)
108  {
109  i += n;
110  return i;
111  }
112  [[nodiscard]] constexpr friend Iter operator-(Iter i, difference_type n)
113  {
114  i -= n;
115  return i;
116  }
117 
118  [[nodiscard]] constexpr friend difference_type operator-(const Iter& i, const Iter& j)
119  {
120  return i.x - j.x;
121  }
122 
123  [[nodiscard]] constexpr T operator[](difference_type n)
124  {
125  return *(*this + n);
126  }
127 
128  [[nodiscard]] constexpr friend bool operator<(const Iter& i, const Iter& j)
129  {
130  return i.x < j.x;
131  }
132  [[nodiscard]] constexpr friend bool operator<=(const Iter& i, const Iter& j)
133  {
134  return i.x <= j.x;
135  }
136  [[nodiscard]] constexpr friend bool operator>(const Iter& i, const Iter& j)
137  {
138  return i.x > j.x;
139  }
140  [[nodiscard]] constexpr friend bool operator>=(const Iter& i, const Iter& j)
141  {
142  return i.x >= j.x;
143  }
144 
145  T x;
146  };
147 
148  [[nodiscard]] constexpr auto begin() const { return Iter{b}; }
149  [[nodiscard]] constexpr auto end() const { return Iter{e}; }
150 
151  /*const*/ T b; // non-const to workaround msvc bug(?)
152  /*const*/ T e;
153 };
154 
155 template<typename T> [[nodiscard]] constexpr auto xrange(T e)
156 {
157  return XRange<T>{T(0), e < T(0) ? T(0) : e};
158 }
159 template<typename T1, typename T2> [[nodiscard]] constexpr auto xrange(T1 b, T2 e)
160 {
161  static_assert(std::is_signed_v<T1> == std::is_signed_v<T2>);
162  using T = std::common_type_t<T1, T2>;
163  return XRange<T>{b, e < b ? b : e};
164 }
165 
166 
169 template<typename T, typename Op>
170 constexpr void repeat(T n, Op op)
171 {
172  for (auto i : xrange(n)) {
173  (void)i;
174  op();
175  }
176 }
177 
178 #endif
auto copy(InputRange &&range, OutputIter out)
Definition: ranges.hh:149
constexpr friend Iter operator+(Iter i, difference_type n)
Definition: xrange.hh:102
ptrdiff_t difference_type
Definition: xrange.hh:44
constexpr friend bool operator>=(const Iter &i, const Iter &j)
Definition: xrange.hh:140
constexpr friend bool operator<(const Iter &i, const Iter &j)
Definition: xrange.hh:128
constexpr friend bool operator<=(const Iter &i, const Iter &j)
Definition: xrange.hh:132
constexpr T operator[](difference_type n)
Definition: xrange.hh:123
std::random_access_iterator_tag iterator_category
Definition: xrange.hh:48
constexpr bool operator==(const Iter &other) const
Definition: xrange.hh:68
constexpr Iter & operator+=(difference_type n)
Definition: xrange.hh:91
constexpr friend difference_type operator-(const Iter &i, const Iter &j)
Definition: xrange.hh:118
constexpr friend Iter operator+(difference_type n, Iter i)
Definition: xrange.hh:107
constexpr friend bool operator>(const Iter &i, const Iter &j)
Definition: xrange.hh:136
T * pointer
Definition: xrange.hh:46
constexpr friend Iter operator-(Iter i, difference_type n)
Definition: xrange.hh:112
constexpr Iter & operator++()
Definition: xrange.hh:56
constexpr Iter operator++(int)
Definition: xrange.hh:61
constexpr T operator*() const
Definition: xrange.hh:51
constexpr bool operator!=(const Iter &other) const
Definition: xrange.hh:72
T & reference
Definition: xrange.hh:47
constexpr Iter & operator-=(difference_type n)
Definition: xrange.hh:96
constexpr Iter & operator--()
Definition: xrange.hh:78
T value_type
Definition: xrange.hh:45
constexpr Iter operator--(int)
Definition: xrange.hh:83
Definition: xrange.hh:41
T e
Definition: xrange.hh:152
constexpr auto end() const
Definition: xrange.hh:149
constexpr auto begin() const
Definition: xrange.hh:148
T b
Definition: xrange.hh:151
constexpr void repeat(T n, Op op)
Repeat the given operation 'op' 'n' times.
Definition: xrange.hh:170
constexpr auto xrange(T e)
Definition: xrange.hh:155