2 * Copyright (C) 2024-2026 David C. Manuelda (StormBytePP)
4 * This is the base for StormByte Suite libraries.
6 * StormByte original source is dual-licensed:
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)
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>).
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.
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.
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.
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>.
37 * SPDX-License-Identifier: LGPL-3.0-or-later OR LicenseRef-StormByte-Commercial
47namespace StormByte::Safe {
49 constexpr std::size_t BlockCount = 16;
53 return static_cast<T*>(Heap::Allocate(sizeof(T) * BlockCount));
57 template<Type::SafeValue T>
58 struct Deque<T>::Block {
62 template<Type::SafeValue T>
63 class Deque<T>::iterator {
65 using iterator_category = std::random_access_iterator_tag;
67 using difference_type = std::ptrdiff_t;
71 iterator() noexcept = default;
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; }
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;
96 template<Type::SafeValue T>
97 class Deque<T>::const_iterator {
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&;
105 const_iterator() noexcept = default;
106 const_iterator(iterator other) noexcept : m_deque{other.m_deque}, m_index{other.m_index} {}
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; }
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;
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];
136 template<Type::SafeValue T>
137 const T& Deque<T>::Slot(size_type index) const noexcept {
138 return const_cast<Deque*>(this)->Slot(index);
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)
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)
150 for (size_type i = m_capacity; i < capacity; ++i)
151 map[i].elements = nullptr;
154 m_capacity = capacity;
157 template<Type::SafeValue T>
158 void Deque<T>::EnsureFront() {
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];
168 m_capacity = capacity;
169 m_offset = BlockCount;
172 template<Type::SafeValue T>
173 Deque<T>::Deque() noexcept
174 : m_map{nullptr}, m_offset{0}, m_size{0}, m_capacity{0} {}
176 template<Type::SafeValue T>
177 Deque<T>::Deque(size_type count, const T& value)
179 for (size_type i = 0; i < count; ++i)
183 template<Type::SafeValue T>
184 Deque<T>::Deque(size_type count)
186 for (size_type i = 0; i < count; ++i)
190 template<Type::SafeValue T>
191 template<std::input_iterator InputIt>
192 Deque<T>::Deque(InputIt first, InputIt last)
194 for (; first != last; ++first)
198 template<Type::SafeValue T>
199 Deque<T>::Deque(std::initializer_list<T> values)
200 : Deque(values.begin(), values.end()) {}
202 template<Type::SafeValue T>
203 Deque<T>::Deque(const std::deque<T>& values)
204 : Deque(values.begin(), values.end()) {}
206 template<Type::SafeValue T>
207 Deque<T>::Deque(const Deque& other)
208 : Deque(other.begin(), other.end()) {}
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;
216 other.m_capacity = 0;
219 template<Type::SafeValue T>
220 Deque<T>::~Deque() noexcept {
222 if (m_map != nullptr) {
223 for (size_type i = 0; i < m_capacity; ++i)
224 Heap::Free(m_map[i].elements);
229 template<Type::SafeValue T>
230 Deque<T>& Deque<T>::operator=(const Deque& other) {
231 if (this != &other) {
238 template<Type::SafeValue T>
239 Deque<T>& Deque<T>::operator=(Deque&& other) noexcept {
240 if (this != &other) {
241 Deque taken(std::move(other));
247 template<Type::SafeValue T>
248 Deque<T>& Deque<T>::operator=(std::initializer_list<T> values) {
254 template<Type::SafeValue T>
255 Deque<T>& Deque<T>::operator=(const std::deque<T>& values) {
261 template<Type::SafeValue T>
262 void Deque<T>::assign(size_type count, const T& value) {
263 Deque copy(count, value);
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);
274 template<Type::SafeValue T>
275 void Deque<T>::assign(std::initializer_list<T> values) {
276 assign(values.begin(), values.end());
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));
285 template<Type::SafeValue T>
286 T& Deque<T>::at(size_type index) {
288 ThrowDequeOutOfBounds(index);
292 template<Type::SafeValue T>
293 const T& Deque<T>::at(size_type index) const {
294 return const_cast<Deque*>(this)->at(index);
297 template<Type::SafeValue T>
298 T& Deque<T>::operator[](size_type index) noexcept {
299 assert(index < m_size);
303 template<Type::SafeValue T>
304 const T& Deque<T>::operator[](size_type index) const noexcept {
305 return const_cast<Deque*>(this)->operator[](index);
308 template<Type::SafeValue T>
309 T& Deque<T>::front() { return at(0); }
311 template<Type::SafeValue T>
312 const T& Deque<T>::front() const { return at(0); }
314 template<Type::SafeValue T>
315 T& Deque<T>::back() {
317 ThrowDequeOutOfBounds();
318 return Slot(m_size - 1);
321 template<Type::SafeValue T>
322 const T& Deque<T>::back() const {
324 ThrowDequeOutOfBounds();
325 return Slot(m_size - 1);
328 template<Type::SafeValue T>
329 typename Deque<T>::iterator Deque<T>::begin() noexcept { return iterator(this, 0); }
331 template<Type::SafeValue T>
332 typename Deque<T>::iterator Deque<T>::end() noexcept { return iterator(this, static_cast<std::ptrdiff_t>(m_size)); }
334 template<Type::SafeValue T>
335 typename Deque<T>::const_iterator Deque<T>::begin() const noexcept { return const_iterator(this, 0); }
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)); }
340 template<Type::SafeValue T>
341 typename Deque<T>::const_iterator Deque<T>::cbegin() const noexcept { return begin(); }
343 template<Type::SafeValue T>
344 typename Deque<T>::const_iterator Deque<T>::cend() const noexcept { return end(); }
346 template<Type::SafeValue T>
347 bool Deque<T>::empty() const noexcept { return m_size == 0; }
349 template<Type::SafeValue T>
350 typename Deque<T>::size_type Deque<T>::size() const noexcept { return m_size; }
352 template<Type::SafeValue T>
353 void Deque<T>::shrink_to_fit() {}
355 template<Type::SafeValue T>
356 void Deque<T>::clear() noexcept {
361 template<Type::SafeValue T>
362 typename Deque<T>::iterator Deque<T>::insert(const_iterator position, const T& value) {
363 return emplace(position, value);
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));
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;
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);
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);
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());
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));
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)...);
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);
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));
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;
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)
430 return iterator(this, index);
433 template<Type::SafeValue T>
434 void Deque<T>::push_back(const T& value) { emplace_back(value); }
436 template<Type::SafeValue T>
437 void Deque<T>::push_back(T&& value) { emplace_back(std::move(value)); }
439 template<Type::SafeValue T>
440 template<typename... Args>
441 T& Deque<T>::emplace_back(Args&&... args) {
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)...);
453 template<Type::SafeValue T>
454 void Deque<T>::pop_back() {
456 Slot(m_size - 1).~T();
460 template<Type::SafeValue T>
461 void Deque<T>::push_front(const T& value) { emplace_front(value); }
463 template<Type::SafeValue T>
464 void Deque<T>::push_front(T&& value) { emplace_front(std::move(value)); }
466 template<Type::SafeValue T>
467 template<typename... Args>
468 T& Deque<T>::emplace_front(Args&&... args) {
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)...);
481 template<Type::SafeValue T>
482 void Deque<T>::pop_front() {
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));
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));
506 template<Type::SafeValue T>
507 void Deque<T>::resize(size_type count) {
508 while (m_size > count)
510 while (m_size < count)
514 template<Type::SafeValue T>
515 void Deque<T>::resize(size_type count, const T& value) {
516 while (m_size > count)
518 while (m_size < count)
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);
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());
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());
540 template<Type::SafeValue T>
541 void swap(Deque<T>& left, Deque<T>& right) noexcept {