StormByte 3.0.0
C++26 foundation of the StormByte suite
Loading...
Searching...
No Matches
deque.txx
Go to the documentation of this file.
1/*
2 * Copyright (C) 2024-2026 David C. Manuelda (StormBytePP)
3 *
4 * This is the base for StormByte Suite libraries.
5 *
6 * StormByte original source is dual-licensed:
7 *
8 * 1. GNU Lesser General Public License v3.0 (or later)
9 * You may redistribute and/or modify this file under the terms of the
10 * GNU Lesser General Public License as published by the Free Software
11 * Foundation, either version 3 of the License, or (at your option)
12 * any later version.
13 *
14 * 2. Commercial license
15 * Alternatively, this file may be used under the terms of a commercial
16 * license agreement with the copyright holder
17 * (David C. Manuelda <StormByte@gmail.com>).
18 *
19 * Both licenses apply only to original StormByte source in this repository.
20 * They do not cover other StormByte modules or any third-party material
21 * shipped with this repository (including everything under thirdparty/),
22 * which remains under its own license.
23 *
24 * Neither license grants any patent rights. Any patent licenses required
25 * to use this software or third-party components must be obtained separately
26 * from the patent holders.
27 *
28 * StormByte is distributed in the hope that it will be useful,
29 * but WITHOUT ANY WARRANTY; without even the implied warranty of
30 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
31 * GNU Lesser General Public License for more details.
32 *
33 * You should have received a copy of the GNU Lesser General Public License
34 * version 3 along with StormByte. If not, see
35 * <https://www.gnu.org/licenses/lgpl-3.0.html>.
36 *
37 * SPDX-License-Identifier: LGPL-3.0-or-later OR LicenseRef-StormByte-Commercial
38 */
39
40#include <algorithm>
41#include <cassert>
42#include <limits>
43#include <new>
44#include <ranges>
45#include <utility>
46
47namespace StormByte::Safe {
48 namespace {
49 constexpr std::size_t BlockCount = 16;
50
51 template<typename T>
52 T* AllocateBlock() {
53 return static_cast<T*>(Heap::Allocate(sizeof(T) * BlockCount));
54 }
55 }
56
57 template<Type::SafeValue T>
58 struct Deque<T>::Block {
59 T* elements;
60 };
61
62 template<Type::SafeValue T>
63 class Deque<T>::iterator {
64 public:
65 using iterator_category = std::random_access_iterator_tag;
66 using value_type = T;
67 using difference_type = std::ptrdiff_t;
68 using pointer = T*;
69 using reference = T&;
70
71 iterator() noexcept = default;
72
73 reference operator*() const { return (*m_deque)[static_cast<size_type>(m_index)]; }
74 pointer operator->() const { return &**this; }
75 iterator& operator++() noexcept { ++m_index; return *this; }
76 iterator operator++(int) noexcept { iterator previous = *this; ++*this; return previous; }
77 iterator& operator--() noexcept { --m_index; return *this; }
78 iterator operator--(int) noexcept { iterator previous = *this; --*this; return previous; }
79 iterator& operator+=(difference_type delta) noexcept { m_index += delta; return *this; }
80 iterator& operator-=(difference_type delta) noexcept { m_index -= delta; return *this; }
81 iterator operator+(difference_type delta) const noexcept { iterator copy = *this; copy += delta; return copy; }
82 iterator operator-(difference_type delta) const noexcept { iterator copy = *this; copy -= delta; return copy; }
83 difference_type operator-(const iterator& other) const noexcept { return m_index - other.m_index; }
84 reference operator[](difference_type delta) const { return *(*this + delta); }
85 bool operator==(const iterator& other) const noexcept { return m_index == other.m_index; }
86 STORMBYTE_FORCE_INLINE std::strong_ordering operator<=>(const iterator& other) const noexcept { return m_index <=> other.m_index; }
87
88 private:
89 friend class Deque;
90 friend class const_iterator;
91 iterator(Deque* deque, std::ptrdiff_t index) noexcept : m_deque{deque}, m_index{index} {}
92 Deque* m_deque = nullptr;
93 std::ptrdiff_t m_index = 0;
94 };
95
96 template<Type::SafeValue T>
97 class Deque<T>::const_iterator {
98 public:
99 using iterator_category = std::random_access_iterator_tag;
100 using value_type = T;
101 using difference_type = std::ptrdiff_t;
102 using pointer = const T*;
103 using reference = const T&;
104
105 const_iterator() noexcept = default;
106 const_iterator(iterator other) noexcept : m_deque{other.m_deque}, m_index{other.m_index} {}
107
108 reference operator*() const { return (*m_deque)[static_cast<size_type>(m_index)]; }
109 pointer operator->() const { return &**this; }
110 const_iterator& operator++() noexcept { ++m_index; return *this; }
111 const_iterator operator++(int) noexcept { const_iterator previous = *this; ++*this; return previous; }
112 const_iterator& operator--() noexcept { --m_index; return *this; }
113 const_iterator operator--(int) noexcept { const_iterator previous = *this; --*this; return previous; }
114 const_iterator& operator+=(difference_type delta) noexcept { m_index += delta; return *this; }
115 const_iterator& operator-=(difference_type delta) noexcept { m_index -= delta; return *this; }
116 const_iterator operator+(difference_type delta) const noexcept { const_iterator copy = *this; copy += delta; return copy; }
117 const_iterator operator-(difference_type delta) const noexcept { const_iterator copy = *this; copy -= delta; return copy; }
118 difference_type operator-(const const_iterator& other) const noexcept { return m_index - other.m_index; }
119 reference operator[](difference_type delta) const { return *(*this + delta); }
120 bool operator==(const const_iterator& other) const noexcept { return m_index == other.m_index; }
121 STORMBYTE_FORCE_INLINE std::strong_ordering operator<=>(const const_iterator& other) const noexcept { return m_index <=> other.m_index; }
122
123 private:
124 friend class Deque;
125 const_iterator(const Deque* deque, std::ptrdiff_t index) noexcept : m_deque{deque}, m_index{index} {}
126 const Deque* m_deque = nullptr;
127 std::ptrdiff_t m_index = 0;
128 };
129
130 template<Type::SafeValue T>
131 T& Deque<T>::Slot(size_type index) noexcept {
132 const size_type absolute = m_offset + index;
133 return m_map[absolute / BlockCount].elements[absolute % BlockCount];
134 }
135
136 template<Type::SafeValue T>
137 const T& Deque<T>::Slot(size_type index) const noexcept {
138 return const_cast<Deque*>(this)->Slot(index);
139 }
140
141 template<Type::SafeValue T>
142 void Deque<T>::EnsureBack() {
143 const size_type needed = (m_offset + m_size) / BlockCount + 1;
144 if (m_map != nullptr && needed <= m_capacity)
145 return;
146 const size_type capacity = m_capacity == 0 ? Size{1} : std::max(needed, m_capacity * 2);
147 Block* map = static_cast<Block*>(Heap::Allocate(sizeof(Block) * capacity));
148 for (size_type i = 0; i < m_capacity; ++i)
149 map[i] = m_map[i];
150 for (size_type i = m_capacity; i < capacity; ++i)
151 map[i].elements = nullptr;
152 Heap::Free(m_map);
153 m_map = map;
154 m_capacity = capacity;
155 }
156
157 template<Type::SafeValue T>
158 void Deque<T>::EnsureFront() {
159 if (m_offset > 0)
160 return;
161 const size_type capacity = m_capacity + 1;
162 Block* map = static_cast<Block*>(Heap::Allocate(sizeof(Block) * capacity));
163 map[0].elements = nullptr;
164 for (size_type i = 0; i < m_capacity; ++i)
165 map[i + 1] = m_map[i];
166 Heap::Free(m_map);
167 m_map = map;
168 m_capacity = capacity;
169 m_offset = BlockCount;
170 }
171
172 template<Type::SafeValue T>
173 Deque<T>::Deque() noexcept
174 : m_map{nullptr}, m_offset{0}, m_size{0}, m_capacity{0} {}
175
176 template<Type::SafeValue T>
177 Deque<T>::Deque(size_type count, const T& value)
178 : Deque() {
179 for (size_type i = 0; i < count; ++i)
180 push_back(value);
181 }
182
183 template<Type::SafeValue T>
184 Deque<T>::Deque(size_type count)
185 : Deque() {
186 for (size_type i = 0; i < count; ++i)
187 emplace_back();
188 }
189
190 template<Type::SafeValue T>
191 template<std::input_iterator InputIt>
192 Deque<T>::Deque(InputIt first, InputIt last)
193 : Deque() {
194 for (; first != last; ++first)
195 push_back(*first);
196 }
197
198 template<Type::SafeValue T>
199 Deque<T>::Deque(std::initializer_list<T> values)
200 : Deque(values.begin(), values.end()) {}
201
202 template<Type::SafeValue T>
203 Deque<T>::Deque(const std::deque<T>& values)
204 : Deque(values.begin(), values.end()) {}
205
206 template<Type::SafeValue T>
207 Deque<T>::Deque(const Deque& other)
208 : Deque(other.begin(), other.end()) {}
209
210 template<Type::SafeValue T>
211 Deque<T>::Deque(Deque&& other) noexcept
212 : m_map{other.m_map}, m_offset{other.m_offset}, m_size{other.m_size}, m_capacity{other.m_capacity} {
213 other.m_map = nullptr;
214 other.m_offset = 0;
215 other.m_size = 0;
216 other.m_capacity = 0;
217 }
218
219 template<Type::SafeValue T>
220 Deque<T>::~Deque() noexcept {
221 clear();
222 if (m_map != nullptr) {
223 for (size_type i = 0; i < m_capacity; ++i)
224 Heap::Free(m_map[i].elements);
225 Heap::Free(m_map);
226 }
227 }
228
229 template<Type::SafeValue T>
230 Deque<T>& Deque<T>::operator=(const Deque& other) {
231 if (this != &other) {
232 Deque copy(other);
233 swap(copy);
234 }
235 return *this;
236 }
237
238 template<Type::SafeValue T>
239 Deque<T>& Deque<T>::operator=(Deque&& other) noexcept {
240 if (this != &other) {
241 Deque taken(std::move(other));
242 swap(taken);
243 }
244 return *this;
245 }
246
247 template<Type::SafeValue T>
248 Deque<T>& Deque<T>::operator=(std::initializer_list<T> values) {
249 Deque copy(values);
250 swap(copy);
251 return *this;
252 }
253
254 template<Type::SafeValue T>
255 Deque<T>& Deque<T>::operator=(const std::deque<T>& values) {
256 Deque copy(values);
257 swap(copy);
258 return *this;
259 }
260
261 template<Type::SafeValue T>
262 void Deque<T>::assign(size_type count, const T& value) {
263 Deque copy(count, value);
264 swap(copy);
265 }
266
267 template<Type::SafeValue T>
268 template<std::input_iterator InputIt>
269 void Deque<T>::assign(InputIt first, InputIt last) {
270 Deque copy(first, last);
271 swap(copy);
272 }
273
274 template<Type::SafeValue T>
275 void Deque<T>::assign(std::initializer_list<T> values) {
276 assign(values.begin(), values.end());
277 }
278
279 template<Type::SafeValue T>
280 template<std::ranges::input_range R>
281 void Deque<T>::assign_range(R&& range) {
282 assign(std::ranges::begin(range), std::ranges::end(range));
283 }
284
285 template<Type::SafeValue T>
286 T& Deque<T>::at(size_type index) {
287 if (index >= m_size)
288 ThrowDequeOutOfBounds(index);
289 return Slot(index);
290 }
291
292 template<Type::SafeValue T>
293 const T& Deque<T>::at(size_type index) const {
294 return const_cast<Deque*>(this)->at(index);
295 }
296
297 template<Type::SafeValue T>
298 T& Deque<T>::operator[](size_type index) noexcept {
299 assert(index < m_size);
300 return Slot(index);
301 }
302
303 template<Type::SafeValue T>
304 const T& Deque<T>::operator[](size_type index) const noexcept {
305 return const_cast<Deque*>(this)->operator[](index);
306 }
307
308 template<Type::SafeValue T>
309 T& Deque<T>::front() { return at(0); }
310
311 template<Type::SafeValue T>
312 const T& Deque<T>::front() const { return at(0); }
313
314 template<Type::SafeValue T>
315 T& Deque<T>::back() {
316 if (m_size == 0)
317 ThrowDequeOutOfBounds();
318 return Slot(m_size - 1);
319 }
320
321 template<Type::SafeValue T>
322 const T& Deque<T>::back() const {
323 if (m_size == 0)
324 ThrowDequeOutOfBounds();
325 return Slot(m_size - 1);
326 }
327
328 template<Type::SafeValue T>
329 typename Deque<T>::iterator Deque<T>::begin() noexcept { return iterator(this, 0); }
330
331 template<Type::SafeValue T>
332 typename Deque<T>::iterator Deque<T>::end() noexcept { return iterator(this, static_cast<std::ptrdiff_t>(m_size)); }
333
334 template<Type::SafeValue T>
335 typename Deque<T>::const_iterator Deque<T>::begin() const noexcept { return const_iterator(this, 0); }
336
337 template<Type::SafeValue T>
338 typename Deque<T>::const_iterator Deque<T>::end() const noexcept { return const_iterator(this, static_cast<std::ptrdiff_t>(m_size)); }
339
340 template<Type::SafeValue T>
341 typename Deque<T>::const_iterator Deque<T>::cbegin() const noexcept { return begin(); }
342
343 template<Type::SafeValue T>
344 typename Deque<T>::const_iterator Deque<T>::cend() const noexcept { return end(); }
345
346 template<Type::SafeValue T>
347 bool Deque<T>::empty() const noexcept { return m_size == 0; }
348
349 template<Type::SafeValue T>
350 typename Deque<T>::size_type Deque<T>::size() const noexcept { return m_size; }
351
352 template<Type::SafeValue T>
353 void Deque<T>::shrink_to_fit() {}
354
355 template<Type::SafeValue T>
356 void Deque<T>::clear() noexcept {
357 while (!empty())
358 pop_back();
359 }
360
361 template<Type::SafeValue T>
362 typename Deque<T>::iterator Deque<T>::insert(const_iterator position, const T& value) {
363 return emplace(position, value);
364 }
365
366 template<Type::SafeValue T>
367 typename Deque<T>::iterator Deque<T>::insert(const_iterator position, T&& value) {
368 return emplace(position, std::move(value));
369 }
370
371 template<Type::SafeValue T>
372 typename Deque<T>::iterator Deque<T>::insert(const_iterator position, size_type count, const T& value) {
373 const std::ptrdiff_t index = position.m_index;
374 if (count == 0)
375 return iterator(this, index);
376 const T snapshot(value);
377 for (size_type i = 0; i < count; ++i)
378 insert(const_iterator(this, index + static_cast<std::ptrdiff_t>(i)), snapshot);
379 return iterator(this, index);
380 }
381
382 template<Type::SafeValue T>
383 template<std::input_iterator InputIt>
384 typename Deque<T>::iterator Deque<T>::insert(const_iterator position, InputIt first, InputIt last) {
385 const std::ptrdiff_t index = position.m_index;
386 std::ptrdiff_t written = 0;
387 for (; first != last; ++first, ++written)
388 insert(const_iterator(this, index + written), *first);
389 return iterator(this, index);
390 }
391
392 template<Type::SafeValue T>
393 typename Deque<T>::iterator Deque<T>::insert(const_iterator position, std::initializer_list<T> values) {
394 return insert(position, values.begin(), values.end());
395 }
396
397 template<Type::SafeValue T>
398 template<std::ranges::input_range R>
399 typename Deque<T>::iterator Deque<T>::insert_range(const_iterator position, R&& range) {
400 return insert(position, std::ranges::begin(range), std::ranges::end(range));
401 }
402
403 template<Type::SafeValue T>
404 template<typename... Args>
405 typename Deque<T>::iterator Deque<T>::emplace(const_iterator position, Args&&... args) {
406 const std::ptrdiff_t index = position.m_index;
407 T value(std::forward<Args>(args)...);
408 emplace_back();
409 for (std::ptrdiff_t i = static_cast<std::ptrdiff_t>(m_size) - 1; i > index; --i)
410 Slot(static_cast<size_type>(i)) = std::move(Slot(static_cast<size_type>(i - 1)));
411 Slot(static_cast<size_type>(index)) = std::move(value);
412 return iterator(this, index);
413 }
414
415 template<Type::SafeValue T>
416 typename Deque<T>::iterator Deque<T>::erase(const_iterator position) {
417 return erase(position, const_iterator(this, position.m_index + 1));
418 }
419
420 template<Type::SafeValue T>
421 typename Deque<T>::iterator Deque<T>::erase(const_iterator first, const_iterator last) {
422 const std::ptrdiff_t index = first.m_index;
423 const std::ptrdiff_t count = last.m_index - first.m_index;
424 if (count == 0)
425 return iterator(this, index);
426 for (std::ptrdiff_t i = index; i + count < static_cast<std::ptrdiff_t>(m_size); ++i)
427 Slot(static_cast<size_type>(i)) = std::move(Slot(static_cast<size_type>(i + count)));
428 for (std::ptrdiff_t i = 0; i < count; ++i)
429 pop_back();
430 return iterator(this, index);
431 }
432
433 template<Type::SafeValue T>
434 void Deque<T>::push_back(const T& value) { emplace_back(value); }
435
436 template<Type::SafeValue T>
437 void Deque<T>::push_back(T&& value) { emplace_back(std::move(value)); }
438
439 template<Type::SafeValue T>
440 template<typename... Args>
441 T& Deque<T>::emplace_back(Args&&... args) {
442 EnsureBack();
443 const size_type absolute = m_offset + m_size;
444 Block& block = m_map[absolute / BlockCount];
445 if (block.elements == nullptr)
446 block.elements = AllocateBlock<T>();
447 T* slot = block.elements + absolute % BlockCount;
448 new (slot) T(std::forward<Args>(args)...);
449 ++m_size;
450 return *slot;
451 }
452
453 template<Type::SafeValue T>
454 void Deque<T>::pop_back() {
455 assert(!empty());
456 Slot(m_size - 1).~T();
457 --m_size;
458 }
459
460 template<Type::SafeValue T>
461 void Deque<T>::push_front(const T& value) { emplace_front(value); }
462
463 template<Type::SafeValue T>
464 void Deque<T>::push_front(T&& value) { emplace_front(std::move(value)); }
465
466 template<Type::SafeValue T>
467 template<typename... Args>
468 T& Deque<T>::emplace_front(Args&&... args) {
469 EnsureFront();
470 --m_offset;
471 const size_type absolute = m_offset;
472 Block& block = m_map[absolute / BlockCount];
473 if (block.elements == nullptr)
474 block.elements = AllocateBlock<T>();
475 T* slot = block.elements + absolute % BlockCount;
476 new (slot) T(std::forward<Args>(args)...);
477 ++m_size;
478 return *slot;
479 }
480
481 template<Type::SafeValue T>
482 void Deque<T>::pop_front() {
483 assert(!empty());
484 Slot(0).~T();
485 ++m_offset;
486 --m_size;
487 }
488
489 template<Type::SafeValue T>
490 template<std::ranges::input_range R>
491 void Deque<T>::append_range(R&& range) {
492 for (auto&& value : range)
493 emplace_back(std::forward<decltype(value)>(value));
494 }
495
496 template<Type::SafeValue T>
497 template<std::ranges::input_range R>
498 void Deque<T>::prepend_range(R&& range) {
499 std::ptrdiff_t index = 0;
500 for (auto&& value : range) {
501 emplace(const_iterator(this, index), std::forward<decltype(value)>(value));
502 ++index;
503 }
504 }
505
506 template<Type::SafeValue T>
507 void Deque<T>::resize(size_type count) {
508 while (m_size > count)
509 pop_back();
510 while (m_size < count)
511 emplace_back();
512 }
513
514 template<Type::SafeValue T>
515 void Deque<T>::resize(size_type count, const T& value) {
516 while (m_size > count)
517 pop_back();
518 while (m_size < count)
519 push_back(value);
520 }
521
522 template<Type::SafeValue T>
523 void Deque<T>::swap(Deque& other) noexcept {
524 std::swap(m_map, other.m_map);
525 std::swap(m_offset, other.m_offset);
526 std::swap(m_size, other.m_size);
527 std::swap(m_capacity, other.m_capacity);
528 }
529
530 template<Type::SafeValue T>
531 bool operator==(const Deque<T>& left, const Deque<T>& right) {
532 return left.size() == right.size() && std::equal(left.begin(), left.end(), right.begin());
533 }
534
535 template<Type::SafeValue T>
536 STORMBYTE_FORCE_INLINE std::strong_ordering operator<=>(const Deque<T>& left, const Deque<T>& right) {
537 return std::lexicographical_compare_three_way(left.begin(), left.end(), right.begin(), right.end());
538 }
539
540 template<Type::SafeValue T>
541 void swap(Deque<T>& left, Deque<T>& right) noexcept {
542 left.swap(right);
543 }
544}