Line data Source code
1 : /* ✔ */
2 :
3 : #pragma once
4 :
5 : #include <AH/Settings/Warnings.hpp>
6 :
7 : AH_DIAGNOSTIC_WERROR() // Enable errors on warnings
8 :
9 : #include <AH/Error/Error.hpp>
10 : #include <AH/STL/iterator>
11 : #include <AH/STL/type_traits> // conditional
12 : #include <stddef.h> // size_t
13 :
14 : BEGIN_AH_NAMESPACE
15 :
16 : template <class T>
17 : constexpr T abs_diff(const T &a, const T &b) {
18 : return a < b ? b - a : a - b;
19 : }
20 :
21 : /// @addtogroup AH_Containers
22 : /// @{
23 :
24 : template <class T, size_t N, bool Reverse, bool Const>
25 : class ArraySlice;
26 :
27 : /**
28 : * @brief An array wrapper for easy copying, comparing, and iterating.
29 : *
30 : * @tparam T
31 : * The type of the elements in the array.
32 : * @tparam N
33 : * The number of elements in the array.
34 : */
35 : template <class T, size_t N>
36 : struct Array {
37 : T data[N];
38 : using type = T;
39 : constexpr static size_t length = N;
40 :
41 : /**
42 : * @brief Get the element at the given index.
43 : *
44 : * @note Bounds checking is performed. If fatal errors are disabled, the
45 : * last element is returned if the index is out of bounds.
46 : *
47 : * @param index
48 : * The (zero-based) index of the element to return.
49 : */
50 1116 : T &operator[](size_t index) {
51 1116 : if (index >= N) { // TODO
52 1 : ERROR(F("Index out of bounds: ") << index << F(" ≥ ") << N, 0xEDED);
53 : index = N - 1; // LCOV_EXCL_LINE
54 : } // LCOV_EXCL_LINE
55 1115 : return data[index];
56 : }
57 :
58 : /**
59 : * @brief Get the element at the given index.
60 : *
61 : * @note Bounds checking is performed. If fatal errors are disabled, the
62 : * last element is returned if the index is out of bounds.
63 : *
64 : * @param index
65 : * The (zero-based) index of the element to return.
66 : */
67 1597 : const T &operator[](size_t index) const {
68 1597 : if (index >= N) { // TODO
69 1 : ERROR(F("Index out of bounds: ") << index << F(" ≥ ") << N, 0xEDED);
70 : index = N - 1; // LCOV_EXCL_LINE
71 : } // LCOV_EXCL_LINE
72 1596 : return data[index];
73 : }
74 :
75 : /**
76 : * @brief Get a pointer to the first element.
77 : */
78 54 : T *begin() { return &data[0]; }
79 :
80 : /**
81 : * @brief Get a pointer to the first element.
82 : */
83 42 : const T *begin() const { return &data[0]; }
84 :
85 : /**
86 : * @brief Get a pointer to the memory beyond the array.
87 : */
88 48 : T *end() { return &data[N]; }
89 :
90 : /**
91 : * @brief Get a pointer to the memory beyond the array.
92 : */
93 42 : const T *end() const { return &data[N]; }
94 :
95 : /**
96 : * @brief Check the equality of all elements in two arrays.
97 : *
98 : * @param rhs
99 : * The array to compare this array to.
100 : */
101 43 : bool operator==(const Array<T, N> &rhs) const {
102 43 : if (this == &rhs)
103 3 : return true;
104 219 : for (size_t i = 0; i < N; i++)
105 182 : if ((*this)[i] != rhs[i])
106 3 : return false;
107 37 : return true;
108 : }
109 :
110 : /**
111 : * @brief Check the inequality of all elements in two arrays.
112 : *
113 : * @param rhs
114 : * The array to compare this array to.
115 : */
116 4 : bool operator!=(const Array<T, N> &rhs) const { return !(*this == rhs); }
117 :
118 : public:
119 : /**
120 : * @brief Get a view on a slice of the Array.
121 : *
122 : * Doesn't copy the contents of the array, it's just a reference to the
123 : * original array.
124 : *
125 : * @tparam Start
126 : * The start index of the slice.
127 : * @tparam End
128 : * The end index of the slice.
129 : */
130 : template <size_t Start = 0, size_t End = N - 1>
131 : ArraySlice<T, abs_diff(Start, End) + 1, (End < Start), false> slice();
132 :
133 : /**
134 : * @brief Get a read-only view on a slice of the Array.
135 : * @copydetails slice()
136 : */
137 : template <size_t Start = 0, size_t End = N - 1>
138 : ArraySlice<T, abs_diff(Start, End) + 1, (End < Start), true> slice() const;
139 :
140 : /**
141 : * @brief Get a read-only view on a slice of the Array.
142 : * @copydetails slice()
143 : */
144 : template <size_t Start = 0, size_t End = N - 1>
145 : ArraySlice<T, abs_diff(Start, End) + 1, (End < Start), true>
146 : cslice() const {
147 : const Array<T, N> *This = this;
148 : return This->slice();
149 : }
150 : };
151 :
152 : /**
153 : * @brief Class for a view on a slice of an array.
154 : *
155 : * Doesn't copy the contents of the array, it's just a reference to the original
156 : * array.
157 : *
158 : * @tparam T
159 : * The type of elements of the Array.
160 : * @tparam N
161 : * The size of the slice.
162 : * @tparam Reverse
163 : * Whether the slice is reversed or not.
164 : * @tparam Const
165 : * Whether to save a read-only or mutable reference to the Array.
166 : */
167 : template <class T, size_t N, bool Reverse = false, bool Const = true>
168 : class ArraySlice {
169 : using ElementRefType =
170 : typename std::conditional<Const, const T &, T &>::type;
171 : using ElementPtrType =
172 : typename std::conditional<Const, const T *, T *>::type;
173 :
174 : public:
175 : /// Constructor
176 56 : ArraySlice(ElementPtrType array) : array{array} {}
177 :
178 : /// Implicit conversion from slice to new array (creates a copy).
179 1 : operator Array<T, N>() const { return asArray(); }
180 :
181 2 : Array<T, N> asArray() const {
182 2 : Array<T, N> slice = {{}};
183 10 : for (size_t i = 0; i < N; ++i)
184 8 : slice[i] = (*this)[i];
185 2 : return slice;
186 : }
187 :
188 : class Iterator {
189 : public:
190 18 : Iterator(ElementPtrType ptr) : ptr(ptr) {}
191 :
192 : using difference_type = std::ptrdiff_t;
193 : using value_type = T;
194 : using pointer = ElementPtrType;
195 : using reference = ElementRefType;
196 : using iterator_category = std::random_access_iterator_tag;
197 :
198 3 : bool operator==(Iterator rhs) const { return ptr == rhs.ptr; }
199 12 : bool operator!=(Iterator rhs) const { return ptr != rhs.ptr; }
200 :
201 62 : reference operator*() const { return *ptr; }
202 : pointer operator->() const { return ptr; }
203 :
204 : reference operator[](difference_type n) const { return ptr[n]; }
205 :
206 10 : Iterator &operator++() {
207 10 : Reverse ? --ptr : ++ptr;
208 10 : return *this;
209 : }
210 :
211 25 : Iterator &operator--() {
212 25 : Reverse ? ++ptr : --ptr;
213 25 : return *this;
214 : }
215 :
216 : Iterator operator++(int) {
217 : Iterator ret = *this;
218 : ++(*this);
219 : return ret;
220 : }
221 :
222 : Iterator operator--(int) {
223 : Iterator ret = *this;
224 : --(*this);
225 : return ret;
226 : }
227 :
228 : Iterator &operator+=(difference_type n) {
229 : Reverse ? (ptr -= n) : (ptr += n);
230 : return *this;
231 : }
232 :
233 : Iterator &operator-=(difference_type n) {
234 : Reverse ? (ptr += n) : (ptr -= n);
235 : return *this;
236 : }
237 :
238 8 : difference_type operator-(Iterator rhs) const {
239 8 : return Reverse ? rhs.ptr - ptr : ptr - rhs.ptr;
240 : }
241 :
242 4 : Iterator operator+(difference_type rhs) const {
243 4 : return Reverse ? ptr - rhs : ptr + rhs;
244 : }
245 :
246 4 : Iterator operator-(difference_type rhs) const {
247 4 : return Reverse ? ptr + rhs : ptr - rhs;
248 : }
249 :
250 3 : bool operator<(Iterator rhs) const {
251 3 : return Reverse ? rhs.ptr < ptr : ptr < rhs.ptr;
252 : }
253 :
254 : bool operator>(Iterator rhs) const { return rhs < *this; }
255 :
256 : bool operator<=(Iterator rhs) const { return !(*this > rhs); }
257 :
258 : bool operator>=(Iterator rhs) const { return !(*this < rhs); }
259 :
260 : private:
261 : ElementPtrType ptr;
262 : };
263 :
264 : /**
265 : * @brief Get the element at the given index.
266 : *
267 : * @note Bounds checking is performed. If fatal errors are disabled, the
268 : * last element is returned if the index is out of bounds.
269 : *
270 : * @param index
271 : * The (zero-based) index of the element to return.
272 : */
273 366 : ElementRefType operator[](size_t index) const {
274 366 : if (index >= N) { // TODO
275 2 : ERROR(F("Index out of bounds: ") << index << F(" ≥ ") << N, 0xEDEF);
276 : index = N - 1; // LCOV_EXCL_LINE
277 : } // LCOV_EXCL_LINE
278 : if (Reverse)
279 17 : return *(array - index);
280 : else
281 347 : return *(array + index);
282 : }
283 :
284 3 : Iterator begin() const {
285 : if (Reverse)
286 2 : return array;
287 : else
288 1 : return array;
289 : }
290 :
291 7 : Iterator end() const {
292 : if (Reverse)
293 4 : return array - N;
294 : else
295 3 : return array + N;
296 : }
297 :
298 : template <size_t Start, size_t End>
299 : ArraySlice<T, abs_diff(End, Start) + 1, Reverse ^ (End < Start), Const>
300 : slice() const;
301 :
302 : private:
303 : ElementPtrType array;
304 : };
305 :
306 : template <class T, size_t N>
307 : template <size_t Start, size_t End>
308 : inline ArraySlice<T, abs_diff(Start, End) + 1, (End < Start), false>
309 35 : Array<T, N>::slice() {
310 : static_assert(Start < N, "");
311 : static_assert(End < N, "");
312 35 : return &(*this)[Start];
313 : }
314 :
315 : template <class T, size_t N>
316 : template <size_t Start, size_t End>
317 : inline ArraySlice<T, abs_diff(Start, End) + 1, (End < Start), true>
318 19 : Array<T, N>::slice() const {
319 : static_assert(Start < N, "");
320 : static_assert(End < N, "");
321 19 : return &(*this)[Start];
322 : }
323 :
324 : template <class T, size_t N, bool Reverse, bool Const>
325 : template <size_t Start, size_t End>
326 : ArraySlice<T, abs_diff(End, Start) + 1, Reverse ^ (End < Start), Const>
327 2 : ArraySlice<T, N, Reverse, Const>::slice() const {
328 : static_assert(Start < N, "");
329 : static_assert(End < N, "");
330 2 : return &(*this)[Start];
331 : }
332 :
333 : /// @related ArraySlice::Iterator
334 : template <class T, size_t N, bool Reverse, bool Const>
335 : typename ArraySlice<T, N, Reverse, Const>::Iterator operator+(
336 : typename ArraySlice<T, N, Reverse, Const>::Iterator::difference_type n,
337 : typename ArraySlice<T, N, Reverse, Const>::Iterator a) {
338 : return a + n;
339 : }
340 :
341 : // Equality ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
342 :
343 : /// Slice == Slice
344 : /// @related ArraySlice
345 : template <class T1, class T2, size_t N1, size_t N2, bool Reverse1,
346 : bool Reverse2, bool Const1, bool Const2>
347 16 : bool operator==(ArraySlice<T1, N1, Reverse1, Const1> a,
348 : ArraySlice<T2, N2, Reverse2, Const2> b) {
349 : static_assert(N1 == N2, "Error: sizes do not match");
350 85 : for (size_t i = 0; i < N1; ++i)
351 72 : if (a[i] != b[i])
352 3 : return false;
353 13 : return true;
354 : }
355 :
356 : /// Array == Slice
357 : /// @related ArraySlice
358 : template <class T1, class T2, size_t N1, size_t N2, bool Reverse2, bool Const2>
359 : bool operator==(const Array<T1, N1> &a,
360 : ArraySlice<T2, N2, Reverse2, Const2> b) {
361 : return a.slice() == b;
362 : }
363 :
364 : /// Slice == Array
365 : /// @related ArraySlice
366 : template <class T1, class T2, size_t N1, size_t N2, bool Reverse1, bool Const1>
367 3 : bool operator==(ArraySlice<T1, N1, Reverse1, Const1> a,
368 : const Array<T2, N2> &b) {
369 3 : return a == b.slice();
370 : }
371 :
372 : // Inequality ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
373 :
374 : /// Slice != Slice
375 : /// @related ArraySlice
376 : template <class T1, class T2, size_t N1, size_t N2, bool Reverse1,
377 : bool Reverse2, bool Const1, bool Const2>
378 4 : bool operator!=(ArraySlice<T1, N1, Reverse1, Const1> a,
379 : ArraySlice<T2, N2, Reverse2, Const2> b) {
380 4 : return !(a == b);
381 : }
382 :
383 : /// Array != Slice
384 : /// @related ArraySlice
385 : template <class T1, class T2, size_t N1, size_t N2, bool Reverse2, bool Const2>
386 : bool operator!=(const Array<T1, N1> &a,
387 : ArraySlice<T2, N2, Reverse2, Const2> b) {
388 : return a.slice() != b;
389 : }
390 :
391 : /// Slice != Array
392 : /// @related ArraySlice
393 : template <class T1, class T2, size_t N1, size_t N2, bool Reverse1, bool Const1>
394 : bool operator!=(ArraySlice<T1, N1, Reverse1, Const1> a,
395 : const Array<T2, N2> &b) {
396 : return a != b.slice();
397 : }
398 :
399 : // Addition ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
400 :
401 : /// Slice + Slice
402 : /// @related ArraySlice
403 : template <class T1, class T2, size_t N1, size_t N2, bool Reverse1,
404 : bool Reverse2, bool Const1, bool Const2>
405 : Array<decltype(T1{} + T2{}), N1>
406 2 : operator+(ArraySlice<T1, N1, Reverse1, Const1> a,
407 : ArraySlice<T2, N2, Reverse2, Const2> b) {
408 : static_assert(N1 == N2, "Error: sizes do not match");
409 2 : Array<decltype(T1{} + T2{}), N1> result = {{}};
410 8 : for (size_t i = 0; i < N1; ++i)
411 6 : result[i] = a[i] + b[i];
412 2 : return result;
413 : }
414 :
415 : /// Array + Array
416 : /// @related Array
417 : template <class T1, class T2, size_t N1, size_t N2>
418 1 : Array<decltype(T1{} + T2{}), N1> operator+(const Array<T1, N1> &a,
419 : const Array<T2, N2> &b) {
420 1 : return a.slice() + b.slice();
421 : }
422 :
423 : /// Slice += Slice
424 : /// @related ArraySlice
425 : template <class T1, class T2, size_t N1, size_t N2, bool Reverse1,
426 : bool Reverse2, bool Const1, bool Const2>
427 : const ArraySlice<T1, N1, Reverse1, Const1> &
428 2 : operator+=(const ArraySlice<T1, N1, Reverse1, Const1> &a,
429 : const ArraySlice<T2, N2, Reverse2, Const2> &b) {
430 : static_assert(N1 == N2, "Error: sizes do not match");
431 8 : for (size_t i = 0; i < N1; ++i)
432 6 : a[i] += b[i];
433 2 : return a;
434 : }
435 :
436 : /// Array += Array
437 : /// @related Array
438 : template <class T1, class T2, size_t N1, size_t N2>
439 1 : Array<T1, N1> &operator+=(Array<T1, N1> &a, const Array<T2, N2> &b) {
440 1 : a.slice() += b.slice();
441 1 : return a;
442 : }
443 :
444 : // Subtraction :::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
445 :
446 : /// Slice - Slice
447 : /// @related ArraySlice
448 : template <class T1, class T2, size_t N1, size_t N2, bool Reverse1,
449 : bool Reverse2, bool Const1, bool Const2>
450 : Array<decltype(T1{} - T2{}), N1>
451 2 : operator-(ArraySlice<T1, N1, Reverse1, Const1> a,
452 : ArraySlice<T2, N2, Reverse2, Const2> b) {
453 : static_assert(N1 == N2, "Error: sizes do not match");
454 2 : Array<decltype(T1{} - T2{}), N1> result = {{}};
455 8 : for (size_t i = 0; i < N1; ++i)
456 6 : result[i] = a[i] - b[i];
457 2 : return result;
458 : }
459 :
460 : /// Array - Array
461 : /// @related Array
462 : template <class T1, class T2, size_t N1, size_t N2>
463 1 : Array<decltype(T1{} - T2{}), N1> operator-(const Array<T1, N1> &a,
464 : const Array<T2, N2> &b) {
465 1 : return a.slice() - b.slice();
466 : }
467 :
468 : /// Slice -= Slice
469 : /// @related ArraySlice
470 : template <class T1, class T2, size_t N1, size_t N2, bool Reverse1,
471 : bool Reverse2, bool Const1, bool Const2>
472 : const ArraySlice<T1, N1, Reverse1, Const1> &
473 : operator-=(const ArraySlice<T1, N1, Reverse1, Const1> &a,
474 : const ArraySlice<T2, N2, Reverse2, Const2> &b) {
475 : static_assert(N1 == N2, "Error: sizes do not match");
476 : for (size_t i = 0; i < N1; ++i)
477 : a[i] -= b[i];
478 : return a;
479 : }
480 :
481 : /// Array -= Array
482 : /// @related Array
483 : template <class T1, class T2, size_t N1, size_t N2>
484 : Array<T1, N1> &operator-=(Array<T1, N1> &a, const Array<T2, N2> &b) {
485 : a.slice() -= b.slice();
486 : return a;
487 : }
488 :
489 : // Scalar Multiplication :::::::::::::::::::::::::::::::::::::::::::::::::::::::
490 :
491 : /// Slice * Scalar
492 : /// @related ArraySlice
493 : template <class T1, class T2, size_t N1, bool Reverse1, bool Const1>
494 : Array<decltype(T1{} * T2{}), N1>
495 2 : operator*(ArraySlice<T1, N1, Reverse1, Const1> a, T2 b) {
496 2 : Array<decltype(T1{} * T2{}), N1> result = {{}};
497 10 : for (size_t i = 0; i < N1; ++i)
498 8 : result[i] = a[i] * b;
499 2 : return result;
500 : }
501 :
502 : /// Array * Scalar
503 : /// @related Array
504 : template <class T1, class T2, size_t N1>
505 1 : Array<decltype(T1{} * T2{}), N1> operator*(const Array<T1, N1> &a, T2 b) {
506 1 : return a.slice() * b;
507 : }
508 :
509 : /// Scalar * Slice
510 : /// @related ArraySlice
511 : template <class T1, class T2, size_t N2, bool Reverse2, bool Const2>
512 : Array<decltype(T1{} * T2{}), N2>
513 2 : operator*(T1 a, ArraySlice<T2, N2, Reverse2, Const2> b) {
514 2 : Array<decltype(T1{} * T2{}), N2> result = {{}};
515 10 : for (size_t i = 0; i < N2; ++i)
516 8 : result[i] = a * b[i];
517 2 : return result;
518 : }
519 :
520 : /// Scalar * Array
521 : /// @related Array
522 : template <class T1, class T2, size_t N2>
523 1 : Array<decltype(T1{} * T2{}), N2> operator*(T1 a, const Array<T2, N2> &b) {
524 1 : return a * b.slice();
525 : }
526 :
527 : /// Slice *= Scalar
528 : /// @related ArraySlice
529 : template <class T1, class T2, size_t N1, bool Reverse1, bool Const1>
530 : const ArraySlice<T1, N1, Reverse1, Const1> &
531 2 : operator*=(const ArraySlice<T1, N1, Reverse1, Const1> &a, T2 b) {
532 10 : for (size_t i = 0; i < N1; ++i)
533 8 : a[i] *= b;
534 2 : return a;
535 : }
536 :
537 : /// Array *= Scalar
538 : /// @related Array
539 : template <class T1, class T2, size_t N1>
540 1 : Array<T1, N1> &operator*=(Array<T1, N1> &a, T2 b) {
541 1 : a.slice() *= b;
542 1 : return a;
543 : }
544 :
545 : // Scalar Division :::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
546 :
547 : /// Slice / Scalar
548 : /// @related ArraySlice
549 : template <class T1, class T2, size_t N1, bool Reverse1, bool Const1>
550 : Array<decltype(T1{} / T2{}), N1>
551 2 : operator/(ArraySlice<T1, N1, Reverse1, Const1> a, T2 b) {
552 2 : Array<decltype(T1{} / T2{}), N1> result = {{}};
553 10 : for (size_t i = 0; i < N1; ++i)
554 8 : result[i] = a[i] / b;
555 2 : return result;
556 : }
557 :
558 : /// Array / Scalar
559 : /// @related Array
560 : template <class T1, class T2, size_t N1>
561 1 : Array<decltype(T1{} / T2{}), N1> operator/(const Array<T1, N1> &a, T2 b) {
562 1 : return a.slice() / b;
563 : }
564 :
565 : /// Slice /= Scalar
566 : /// @related ArraySlice
567 : template <class T1, class T2, size_t N1, bool Reverse1, bool Const1>
568 : const ArraySlice<T1, N1, Reverse1, Const1> &
569 2 : operator/=(const ArraySlice<T1, N1, Reverse1, Const1> &a, T2 b) {
570 10 : for (size_t i = 0; i < N1; ++i)
571 8 : a[i] /= b;
572 2 : return a;
573 : }
574 :
575 : /// Array /= Scalar
576 : /// @related Array
577 : template <class T1, class T2, size_t N1>
578 1 : Array<T1, N1> &operator/=(Array<T1, N1> &a, T2 b) {
579 1 : a.slice() /= b;
580 1 : return a;
581 : }
582 :
583 : // Negation ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
584 :
585 : /// -Slice
586 : /// @related ArraySlice
587 : template <class T, size_t N, bool Reverse, bool Const>
588 2 : Array<decltype(-T{}), N> operator-(ArraySlice<T, N, Reverse, Const> a) {
589 2 : Array<decltype(-T{}), N> result = {{}};
590 11 : for (size_t i = 0; i < N; ++i)
591 9 : result[i] = -a[i];
592 2 : return result;
593 : }
594 :
595 : /// -Array
596 : /// @related Array
597 : template <class T, size_t N>
598 1 : Array<decltype(-T{}), N> operator-(const Array<T, N> &a) {
599 1 : return -a.slice();
600 : }
601 :
602 : // Type aliases ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
603 :
604 : /// An easy alias for two-dimensional Arrays.
605 : template <class T, size_t NumRows, size_t NumCols>
606 : using Array2D = Array<Array<T, NumCols>, NumRows>;
607 :
608 : /// @}
609 :
610 : END_AH_NAMESPACE
611 :
612 : AH_DIAGNOSTIC_POP()
|
