Line data Source code
1 0 : // Distributed under the MIT License.
2 : // See LICENSE.txt for details.
3 :
4 : #pragma once
5 :
6 : #include <algorithm>
7 : #include <cstddef>
8 : #include <iterator>
9 : #include <limits>
10 : #include <stdexcept>
11 : #include <type_traits>
12 :
13 : #include "Utilities/ErrorHandling/Assert.hpp"
14 : #include "Utilities/Gsl.hpp"
15 : #include "Utilities/MakeString.hpp"
16 :
17 : /// Classes to generate repetitive code needed for STL compatibility.
18 1 : namespace stl_boilerplate {
19 : /// Base class to generate methods for a random-access iterator. This
20 : /// class takes the derived class and the (optionally `const`)
21 : /// `value_type` of the iterator. The exposed `value_type` alias will
22 : /// always be non-const, as required by the standard, but the template
23 : /// parameter's constness will affect the `reference` and `pointer`
24 : /// aliases.
25 : ///
26 : /// The derived class must implement `operator*`, `operator+=`,
27 : /// `operator-` (of two iterators), and `operator==`.
28 : ///
29 : /// \snippet Test_StlBoilerplate.cpp RandomAccessIterator
30 : ///
31 : /// This class is inspired by Boost's `iterator_facade`, except that
32 : /// that has a lot of special cases, some of which work poorly because
33 : /// they predate C++11.
34 : template <typename Iter, typename ValueType>
35 1 : class RandomAccessIterator {
36 : protected:
37 0 : RandomAccessIterator() = default;
38 0 : RandomAccessIterator(const RandomAccessIterator&) = default;
39 0 : RandomAccessIterator(RandomAccessIterator&&) = default;
40 0 : RandomAccessIterator& operator=(const RandomAccessIterator&) = default;
41 0 : RandomAccessIterator& operator=(RandomAccessIterator&&) = default;
42 0 : ~RandomAccessIterator() = default;
43 :
44 : public:
45 0 : using iterator_category = std::random_access_iterator_tag;
46 0 : using value_type = std::remove_const_t<ValueType>;
47 0 : using reference = ValueType&;
48 0 : using pointer = ValueType*;
49 0 : using difference_type = std::ptrdiff_t;
50 :
51 0 : pointer operator->() const { return &**dthis(); }
52 :
53 0 : Iter& operator++() { return *dthis() += 1; }
54 0 : Iter operator++(int) {
55 : const auto ret = *dthis();
56 : ++*dthis();
57 : return ret;
58 : }
59 0 : Iter& operator--() { return *dthis() += -1; }
60 0 : Iter operator--(int) {
61 : const auto ret = *dthis();
62 : --*dthis();
63 : return ret;
64 : }
65 :
66 0 : Iter& operator-=(const difference_type n) { return *dthis() += -n; }
67 :
68 0 : reference operator[](const difference_type n) const {
69 : auto temp = *dthis();
70 : temp += n;
71 : return *temp;
72 : }
73 :
74 : private:
75 : // derived this
76 0 : Iter* dthis() { return static_cast<Iter*>(this); }
77 0 : const Iter* dthis() const { return static_cast<const Iter*>(this); }
78 : };
79 :
80 : template <typename Iter, typename ValueType>
81 0 : bool operator!=(const RandomAccessIterator<Iter, ValueType>& a,
82 : const RandomAccessIterator<Iter, ValueType>& b) {
83 : return not(static_cast<const Iter&>(a) == static_cast<const Iter&>(b));
84 : }
85 :
86 : template <typename Iter, typename ValueType>
87 0 : bool operator<(const RandomAccessIterator<Iter, ValueType>& a,
88 : const RandomAccessIterator<Iter, ValueType>& b) {
89 : return static_cast<const Iter&>(b) - static_cast<const Iter&>(a) > 0;
90 : }
91 :
92 : template <typename Iter, typename ValueType>
93 0 : bool operator>(const RandomAccessIterator<Iter, ValueType>& a,
94 : const RandomAccessIterator<Iter, ValueType>& b) {
95 : return b < a;
96 : }
97 :
98 : template <typename Iter, typename ValueType>
99 0 : bool operator<=(const RandomAccessIterator<Iter, ValueType>& a,
100 : const RandomAccessIterator<Iter, ValueType>& b) {
101 : return not(a > b);
102 : }
103 :
104 : template <typename Iter, typename ValueType>
105 0 : bool operator>=(const RandomAccessIterator<Iter, ValueType>& a,
106 : const RandomAccessIterator<Iter, ValueType>& b) {
107 : return not(a < b);
108 : }
109 :
110 : template <typename Iter, typename ValueType>
111 0 : Iter operator+(
112 : const RandomAccessIterator<Iter, ValueType>& a,
113 : const typename RandomAccessIterator<Iter, ValueType>::difference_type& n) {
114 : auto result = static_cast<const Iter&>(a);
115 : result += n;
116 : return result;
117 : }
118 :
119 : template <typename Iter, typename ValueType>
120 0 : Iter operator+(
121 : const typename RandomAccessIterator<Iter, ValueType>::difference_type& n,
122 : const RandomAccessIterator<Iter, ValueType>& a) {
123 : return a + n;
124 : }
125 :
126 : template <typename Iter, typename ValueType>
127 0 : Iter operator-(
128 : const RandomAccessIterator<Iter, ValueType>& a,
129 : const typename RandomAccessIterator<Iter, ValueType>::difference_type& n) {
130 : auto result = static_cast<const Iter&>(a);
131 : result -= n;
132 : return result;
133 : }
134 :
135 : /// Base class to generate methods for a random-access sequence,
136 : /// similar to a `std::array`.
137 : ///
138 : /// This class takes the derived class and the `value_type` of the
139 : /// sequence as template parameters. The third template parameter
140 : /// specifies whether to define comparison operators. Comparisons are
141 : /// required by the standard, but for derived classes with additional
142 : /// functionality the autogenerated ones can give incorrect results.
143 : ///
144 : /// The derived class must implement `size` and `operator[]`.
145 : ///
146 : /// \snippet Test_StlBoilerplate.cpp RandomAccessSequence
147 : ///
148 : /// This class provides methods for accessing and modifying elements
149 : /// of the sequence, such as `front` and `begin`, as well as iterators
150 : /// and reverse iterators. Methods modifying the sequence itself,
151 : /// such as `insert`, require explicit implementations.
152 : template <typename Sequence, typename ValueType, bool DefineComparisons>
153 1 : class RandomAccessSequence {
154 : protected:
155 0 : RandomAccessSequence() = default;
156 0 : RandomAccessSequence(const RandomAccessSequence&) = default;
157 0 : RandomAccessSequence(RandomAccessSequence&&) = default;
158 0 : RandomAccessSequence& operator=(const RandomAccessSequence&) = default;
159 0 : RandomAccessSequence& operator=(RandomAccessSequence&&) = default;
160 0 : ~RandomAccessSequence() = default;
161 :
162 : public:
163 0 : using value_type = ValueType;
164 0 : using reference = value_type&;
165 0 : using const_reference = const value_type&;
166 0 : using pointer = ValueType*;
167 0 : using const_pointer = const ValueType*;
168 :
169 0 : class const_iterator
170 : : public RandomAccessIterator<const_iterator, const value_type> {
171 : public:
172 0 : const_iterator() = default;
173 :
174 0 : const value_type& operator*() const { return (*container_)[offset_]; }
175 0 : const_iterator& operator+=(const std::ptrdiff_t n) {
176 : offset_ += static_cast<size_t>(n);
177 : return *this;
178 : }
179 :
180 : private:
181 0 : friend bool operator==(const const_iterator& a, const const_iterator& b) {
182 : return a.container_ == b.container_ and a.offset_ == b.offset_;
183 : }
184 :
185 0 : friend std::ptrdiff_t operator-(const const_iterator& a,
186 : const const_iterator& b) {
187 : ASSERT(a.container_ == b.container_, "Subtracting unrelated iterators");
188 : return static_cast<std::ptrdiff_t>(a.offset_) -
189 : static_cast<std::ptrdiff_t>(b.offset_);
190 : }
191 :
192 0 : friend RandomAccessSequence;
193 0 : const_iterator(const gsl::not_null<const Sequence*> container,
194 : const size_t offset)
195 : : container_(container), offset_(offset) {}
196 :
197 0 : const Sequence* container_{nullptr};
198 0 : size_t offset_{0};
199 : };
200 :
201 0 : class iterator : public RandomAccessIterator<iterator, value_type> {
202 : public:
203 0 : iterator() = default;
204 :
205 0 : value_type& operator*() const { return (*container_)[offset_]; }
206 0 : iterator& operator+=(const std::ptrdiff_t n) {
207 : offset_ += static_cast<size_t>(n);
208 : return *this;
209 : }
210 :
211 0 : operator const_iterator() const {
212 : return container_->cbegin() + static_cast<std::ptrdiff_t>(offset_);
213 : }
214 :
215 : private:
216 0 : friend bool operator==(const iterator& a, const iterator& b) {
217 : return a.container_ == b.container_ and a.offset_ == b.offset_;
218 : }
219 :
220 0 : friend std::ptrdiff_t operator-(const iterator& a, const iterator& b) {
221 : ASSERT(a.container_ == b.container_, "Subtracting unrelated iterators");
222 : return static_cast<std::ptrdiff_t>(a.offset_) -
223 : static_cast<std::ptrdiff_t>(b.offset_);
224 : }
225 :
226 0 : friend RandomAccessSequence;
227 0 : iterator(const gsl::not_null<Sequence*> container, const size_t offset)
228 : : container_(container), offset_(offset) {}
229 :
230 0 : Sequence* container_{nullptr};
231 0 : size_t offset_{0};
232 : };
233 :
234 0 : using reverse_iterator = std::reverse_iterator<iterator>;
235 0 : using const_reverse_iterator = std::reverse_iterator<const_iterator>;
236 0 : using difference_type =
237 : typename std::iterator_traits<const_iterator>::difference_type;
238 0 : using size_type = size_t;
239 :
240 0 : iterator begin() & { return {dthis(), 0}; }
241 0 : const_iterator begin() const& { return {dthis(), 0}; }
242 0 : const_iterator cbegin() const& { return begin(); }
243 0 : iterator end() & { return {dthis(), dthis()->size()}; }
244 0 : const_iterator end() const& { return {dthis(), dthis()->size()}; }
245 0 : const_iterator cend() const& { return end(); }
246 :
247 0 : reverse_iterator rbegin() & { return reverse_iterator(end()); }
248 0 : const_reverse_iterator rbegin() const& {
249 : return const_reverse_iterator(end());
250 : }
251 0 : const_reverse_iterator crbegin() const& { return rbegin(); }
252 0 : reverse_iterator rend() & { return reverse_iterator(begin()); }
253 0 : const_reverse_iterator rend() const& {
254 : return const_reverse_iterator(begin());
255 : }
256 0 : const_reverse_iterator crend() const& { return rend(); }
257 :
258 : /// Not part of the standard, but any attempt to store the results
259 : /// of a call that would match one of these would be undefined
260 : /// behavior. Valid uses would be: use as temporaries, but that can
261 : /// usually be better done through the normal container access; and
262 : /// use in unevaluated contexts, but those should really be
263 : /// explicitly requesting lvalue references if that's what they're
264 : /// checking. Either of these can be easily worked around. If
265 : /// these things happen in code outside our control we may have to
266 : /// reconsider.
267 : /// @{
268 1 : void begin() && = delete;
269 1 : void begin() const&& = delete;
270 1 : void cbegin() && = delete;
271 1 : void cbegin() const&& = delete;
272 1 : void end() && = delete;
273 1 : void end() const&& = delete;
274 1 : void cend() && = delete;
275 1 : void cend() const&& = delete;
276 1 : void rbegin() && = delete;
277 1 : void rbegin() const&& = delete;
278 1 : void crbegin() && = delete;
279 1 : void crbegin() const&& = delete;
280 1 : void rend() && = delete;
281 1 : void rend() const&& = delete;
282 1 : void crend() && = delete;
283 1 : void crend() const&& = delete;
284 : /// @}
285 :
286 0 : size_type max_size() const { return std::numeric_limits<size_type>::max(); }
287 0 : bool empty() const { return begin() == end(); }
288 :
289 0 : reference front() { return *begin(); }
290 0 : const_reference front() const { return *begin(); }
291 0 : reference back() { return *(end() - 1); }
292 0 : const_reference back() const { return *(end() - 1); }
293 :
294 0 : reference at(const size_type n) {
295 : if (n >= dthis()->size()) {
296 : throw std::out_of_range(MakeString{} << "RandomAccessSequence::at " << n
297 : << " >= " << dthis()->size());
298 : }
299 : return (*dthis())[n];
300 : }
301 0 : const_reference at(const size_type n) const {
302 : if (n >= dthis()->size()) {
303 : throw std::out_of_range(MakeString{} << "RandomAccessSequence::at " << n
304 : << " >= " << dthis()->size());
305 : }
306 : return (*dthis())[n];
307 : }
308 :
309 : private:
310 : // derived this
311 0 : Sequence* dthis() { return static_cast<Sequence*>(this); }
312 0 : const Sequence* dthis() const { return static_cast<const Sequence*>(this); }
313 : };
314 :
315 : template <typename Sequence, typename ValueType>
316 0 : bool operator==(const RandomAccessSequence<Sequence, ValueType, true>& a,
317 : const RandomAccessSequence<Sequence, ValueType, true>& b) {
318 : return static_cast<const Sequence&>(a).size() ==
319 : static_cast<const Sequence&>(b).size() and
320 : std::equal(a.begin(), a.end(), b.begin());
321 : }
322 :
323 : template <typename Sequence, typename ValueType>
324 0 : bool operator!=(const RandomAccessSequence<Sequence, ValueType, true>& a,
325 : const RandomAccessSequence<Sequence, ValueType, true>& b) {
326 : return not(a == b);
327 : }
328 :
329 : template <typename Sequence, typename ValueType>
330 0 : bool operator<(const RandomAccessSequence<Sequence, ValueType, true>& a,
331 : const RandomAccessSequence<Sequence, ValueType, true>& b) {
332 : return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());
333 : }
334 :
335 : template <typename Sequence, typename ValueType>
336 0 : bool operator>(const RandomAccessSequence<Sequence, ValueType, true>& a,
337 : const RandomAccessSequence<Sequence, ValueType, true>& b) {
338 : return b < a;
339 : }
340 :
341 : template <typename Sequence, typename ValueType>
342 0 : bool operator<=(const RandomAccessSequence<Sequence, ValueType, true>& a,
343 : const RandomAccessSequence<Sequence, ValueType, true>& b) {
344 : return not(a > b);
345 : }
346 :
347 : template <typename Sequence, typename ValueType>
348 0 : bool operator>=(const RandomAccessSequence<Sequence, ValueType, true>& a,
349 : const RandomAccessSequence<Sequence, ValueType, true>& b) {
350 : return not(a < b);
351 : }
352 : } // namespace stl_boilerplate
|
