matrixfurry.com
The open source OpenXR runtime
1// Copyright 2021-2022, Collabora, Ltd.
2//
3// SPDX-License-Identifier: BSL-1.0
4/*!
5 * @file
6 *
7 * @brief A template class to serve as the base of iterator and const_iterator
8 * types for things with "random access".
9 * @author Rylie Pavlik <rylie.pavlik@collabora.com>
10 * @ingroup aux_util
11 */
12
13#pragma once
14
15#include <stdexcept>
16#include <limits>
17#include <iterator>
18
19namespace xrt::auxiliary::util {
20/*!
21 * @brief Template for base class used by "random-access" iterators and const_iterators, providing all the functionality
22 * that is independent of element type and const-ness of the iterator.
23 *
24 * Using inheritance instead of composition here to more easily satisfy the C++ standard's requirements for
25 * iterators (e.g. that const iterators and iterators are comparable, etc.)
26 *
27 * All invalid instances will compare as equal, as required by the spec, but they are not all equivalent. You can freely
28 * go "past the end" (they will be invalid, so cannot dereference, but you can get them back to valid), but you can't go
29 * "past the beginning". That is, you can do `*(buf.end() - 1)` successfully if your buffer has at least one element,
30 * even though `buf.end()` is invalid.
31 *
32 * @tparam ContainerOrHelper Your container or some member thereof that provides a size() method. If it's a helper
33 * instead of the actual container, make it const.
34 *
35 */
36template <typename ContainerOrHelper> class RandomAccessIteratorBase
37{
38public:
39 using iterator_category = std::random_access_iterator_tag;
40 using difference_type = std::ptrdiff_t;
41
42
43 //! Is this iterator valid?
44 bool
45 valid() const noexcept;
46
47 //! Is this iterator valid?
48 explicit operator bool() const noexcept
49 {
50 return valid();
51 }
52
53 //! What is the index stored by this iterator?
54 size_t
55 index() const noexcept
56 {
57 return index_;
58 }
59
60 //! Is this iterator pointing "past the end" of the container?
61 bool
62 is_past_the_end() const noexcept
63 {
64 return container_ != nullptr && index_ >= container_->size();
65 }
66
67 /*!
68 * @brief True if this iterator is "irrecoverably" invalid (that is, cleared or default constructed).
69 *
70 * Implies !valid() but is stronger. `buf.end().is_cleared()` is false.
71 */
72 bool
73 is_cleared() const noexcept
74 {
75 return container_ == nullptr;
76 }
77
78 /*!
79 * @brief Compute the difference between two iterators.
80 *
81 * - If both are cleared, the result is 0.
82 * - Otherwise the result is the difference in index.
83 *
84 * @throws std::logic_error if exactly one of the iterators is cleared
85 * @throws std::out_of_range if at least one of the iterators has an index larger than the maximum value of
86 * std::ptrdiff_t.
87 */
88 std::ptrdiff_t
89 operator-(const RandomAccessIteratorBase<ContainerOrHelper> &other) const;
90
91 /*!
92 * @brief Increment by an arbitrary value.
93 */
94 RandomAccessIteratorBase &
95 operator+=(std::ptrdiff_t n);
96
97 /*!
98 * @brief Decrement by an arbitrary value.
99 */
100 RandomAccessIteratorBase &
101 operator-=(std::ptrdiff_t n);
102
103 /*!
104 * @brief Add some arbitrary amount to a copy of this iterator.
105 */
106 RandomAccessIteratorBase
107 operator+(std::ptrdiff_t n) const;
108
109 /*!
110 * @brief Subtract some arbitrary amount from a copy of this iterator.
111 */
112 RandomAccessIteratorBase
113 operator-(std::ptrdiff_t n) const;
114
115 //! Factory function: construct the "begin" iterator
116 static RandomAccessIteratorBase
117 begin(ContainerOrHelper &container)
118 {
119 return RandomAccessIteratorBase(container, 0);
120 }
121
122 //! Factory function: construct the "past the end" iterator that can be decremented safely
123 static RandomAccessIteratorBase
124 end(ContainerOrHelper &container)
125 {
126 return RandomAccessIteratorBase(container, container.size());
127 }
128
129
130 /**
131 * @brief Default constructor - initializes to "cleared" (that is, irrecoverably invalid - because we have no
132 * reference to a container)
133 */
134 RandomAccessIteratorBase() = default;
135
136 /**
137 * @brief Constructor from a helper/container and index
138 *
139 * @param container The helper or container we will iterate through.
140 * @param index An index - may be out of range.
141 */
142 explicit RandomAccessIteratorBase(ContainerOrHelper &container, size_t index);
143
144
145 using const_iterator_base = std::conditional_t<std::is_const<ContainerOrHelper>::value,
146 RandomAccessIteratorBase,
147 RandomAccessIteratorBase<std::add_const_t<ContainerOrHelper>>>;
148
149 /**
150 * @brief Get a const iterator base pointing to the same element as this element.
151 *
152 * @return const_iterator_base
153 */
154 const_iterator_base
155 as_const() const
156 {
157 if (is_cleared()) {
158 return {};
159 }
160
161 return const_iterator_base{*container_, index_};
162 }
163
164protected:
165 //! for internal use
166 RandomAccessIteratorBase(ContainerOrHelper *container, size_t index) : container_(container), index_(index) {}
167
168 //! Increment an arbitrary amount
169 void
170 increment_n(std::size_t n);
171
172 //! Decrement an arbitrary amount
173 void
174 decrement_n(std::size_t n);
175
176 //! Get the associated container or helper
177 ContainerOrHelper *
178 container() const noexcept
179 {
180 return container_;
181 }
182
183private:
184 /**
185 * @brief The container or helper we're associated with.
186 *
187 * If we were created knowing a container, this pointer is non-null.
188 * Used to determine if an index is in bounds.
189 * If this is null, the iterator is irrecoverably invalid.
190 */
191 ContainerOrHelper *container_{nullptr};
192
193 //! This is the index in the container. May be out-of-range.
194 size_t index_{0};
195};
196
197/*!
198 * @brief Equality comparison operator for @ref RandomAccessIteratorBase
199 *
200 * @relates RandomAccessIteratorBase
201 */
202template <typename ContainerOrHelper>
203static inline bool
204operator==(RandomAccessIteratorBase<ContainerOrHelper> const &lhs,
205 RandomAccessIteratorBase<ContainerOrHelper> const &rhs) noexcept
206{
207 const bool lhs_valid = lhs.valid();
208 const bool rhs_valid = rhs.valid();
209 if (!lhs_valid && !rhs_valid) {
210 // all invalid iterators compare equal.
211 return true;
212 }
213 if (lhs_valid != rhs_valid) {
214 // valid is never equal to invalid.
215 return false;
216 }
217 // OK, so both are valid. Now, we look at the index
218 return lhs.index() == rhs.index();
219}
220
221/*!
222 * @overload
223 */
224template <typename ContainerOrHelper>
225static inline bool
226operator==(RandomAccessIteratorBase<const ContainerOrHelper> const &lhs,
227 RandomAccessIteratorBase<ContainerOrHelper> const &rhs) noexcept
228{
229 return lhs == rhs.as_const();
230}
231/*!
232 * @overload
233 */
234template <typename ContainerOrHelper>
235static inline bool
236operator==(RandomAccessIteratorBase<ContainerOrHelper> const &lhs,
237 RandomAccessIteratorBase<const ContainerOrHelper> const &rhs) noexcept
238{
239 return lhs.as_const() == rhs;
240}
241
242/*!
243 * @brief Inequality comparison operator for @ref RandomAccessIteratorBase
244 *
245 * @relates RandomAccessIteratorBase
246 */
247template <typename ContainerOrHelper>
248static inline bool
249operator!=(RandomAccessIteratorBase<ContainerOrHelper> const &lhs,
250 RandomAccessIteratorBase<ContainerOrHelper> const &rhs) noexcept
251{
252 return !(lhs == rhs);
253}
254
255/*!
256 * @overload
257 */
258template <typename ContainerOrHelper>
259static inline bool
260operator!=(RandomAccessIteratorBase<const ContainerOrHelper> const &lhs,
261 RandomAccessIteratorBase<ContainerOrHelper> const &rhs) noexcept
262{
263 return !(lhs == rhs.as_const());
264}
265
266/*!
267 * @overload
268 */
269template <typename ContainerOrHelper>
270static inline bool
271operator!=(RandomAccessIteratorBase<ContainerOrHelper> const &lhs,
272 RandomAccessIteratorBase<const ContainerOrHelper> const &rhs) noexcept
273{
274 return !(lhs.as_const() == rhs);
275}
276
277template <typename ContainerOrHelper>
278inline bool
279RandomAccessIteratorBase<ContainerOrHelper>::valid() const noexcept
280{
281 return container_ != nullptr && index_ < container_->size();
282}
283
284template <typename ContainerOrHelper>
285inline RandomAccessIteratorBase<ContainerOrHelper> &
286RandomAccessIteratorBase<ContainerOrHelper>::operator+=(std::ptrdiff_t n)
287{
288 if (n < 0) {
289 decrement_n(static_cast<size_t>(-1 * n));
290 } else {
291 increment_n(static_cast<size_t>(n));
292 }
293 return *this;
294}
295
296template <typename ContainerOrHelper>
297inline RandomAccessIteratorBase<ContainerOrHelper> &
298RandomAccessIteratorBase<ContainerOrHelper>::operator-=(std::ptrdiff_t n)
299{
300 if (n < 0) {
301 increment_n(static_cast<size_t>(-1 * n));
302 } else {
303 decrement_n(static_cast<size_t>(n));
304 }
305 return *this;
306}
307
308template <typename ContainerOrHelper>
309inline void
310RandomAccessIteratorBase<ContainerOrHelper>::increment_n(std::size_t n)
311{
312 // being cleared is permanent
313 if (is_cleared())
314 return;
315 index_ += n;
316}
317
318template <typename ContainerOrHelper>
319inline void
320RandomAccessIteratorBase<ContainerOrHelper>::decrement_n(std::size_t n)
321{
322 // being cleared is permanent
323 if (is_cleared())
324 return;
325 if (n > index_) {
326 // would move backward past the beginning which you can't recover from. So, clear it.
327 *this = {};
328 return;
329 }
330 index_ -= n;
331}
332
333template <typename ContainerOrHelper>
334inline std::ptrdiff_t
335RandomAccessIteratorBase<ContainerOrHelper>::operator-(const RandomAccessIteratorBase<ContainerOrHelper> &other) const
336{
337 const bool self_cleared = is_cleared();
338 const bool other_cleared = other.is_cleared();
339 if (self_cleared && other_cleared) {
340 // If both cleared, they're at the same place.
341 return 0;
342 }
343 if (self_cleared || other_cleared) {
344 // If only one is cleared, we can't do this.
345 throw std::logic_error(
346 "Tried to find the difference between a cleared iterator and a non-cleared iterator.");
347 }
348 constexpr size_t max_ptrdiff = static_cast<size_t>(std::numeric_limits<std::ptrdiff_t>::max());
349 if (index_ > max_ptrdiff || other.index_ > max_ptrdiff) {
350 throw std::out_of_range("An index exceeded the maximum value of the signed version of the index type.");
351 }
352 // Otherwise subtract the index values.
353 return static_cast<std::ptrdiff_t>(index_) - static_cast<std::ptrdiff_t>(other.index_);
354}
355
356template <typename ContainerOrHelper>
357inline RandomAccessIteratorBase<ContainerOrHelper>::RandomAccessIteratorBase(ContainerOrHelper &container, size_t index)
358 : container_(&container), index_(index)
359{}
360
361} // namespace xrt::auxiliary::util