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
42namespace StormByte::Safe {
43 template<Type::SafeValue T>
44 List<T>::List() noexcept { ResetSentinel(); }
46 template<Type::SafeValue T>
47 List<T>::List(size_type count): List() {
48 for (size_type index = 0; index < count; ++index)
52 template<Type::SafeValue T>
53 List<T>::List(size_type count, const T& value): List() {
54 for (size_type index = 0; index < count; ++index)
58 template<Type::SafeValue T>
59 List<T>::List(const List& other): List() {
60 for (const T& value : other)
64 template<Type::SafeValue T>
65 List<T>::List(List&& other) noexcept: m_size(other.m_size) {
70 m_sentinel.Next = other.m_sentinel.Next;
71 m_sentinel.Prev = other.m_sentinel.Prev;
72 m_sentinel.Next->Prev = &m_sentinel;
73 m_sentinel.Prev->Next = &m_sentinel;
74 other.ResetSentinel();
78 template<Type::SafeValue T>
79 List<T>::List(std::initializer_list<T> values): List() {
80 for (const T& value : values)
84 template<Type::SafeValue T>
85 List<T>::~List() noexcept { Destroy(); }
87 template<Type::SafeValue T>
88 List<T>& List<T>::operator=(const List& other) {
90 List replacement(other);
96 template<Type::SafeValue T>
97 List<T>& List<T>::operator=(List&& other) noexcept {
104 m_sentinel.Next = other.m_sentinel.Next;
105 m_sentinel.Prev = other.m_sentinel.Prev;
106 m_sentinel.Next->Prev = &m_sentinel;
107 m_sentinel.Prev->Next = &m_sentinel;
108 m_size = other.m_size;
109 other.ResetSentinel();
116 template<Type::SafeValue T>
117 List<T>& List<T>::operator=(std::initializer_list<T> values) {
118 List replacement(values);
123 template<Type::SafeValue T>
124 void List<T>::assign(size_type count, const T& value) {
125 List replacement(count, value);
129 template<Type::SafeValue T>
130 void List<T>::assign(std::initializer_list<T> values) {
134 template<Type::SafeValue T>
135 void List<T>::clear() noexcept { Destroy(); }
137 template<Type::SafeValue T>
138 List<T>::iterator List<T>::insert(const_iterator position, const T& value) {
139 return emplace(position, value);
142 template<Type::SafeValue T>
143 List<T>::iterator List<T>::insert(const_iterator position, T&& value) {
144 return emplace(position, std::move(value));
147 template<Type::SafeValue T>
148 List<T>::iterator List<T>::insert(const_iterator position, size_type count, const T& value) {
149 iterator first(const_cast<Link*>(position.m_link));
150 for (size_type index = 0; index < count; ++index) {
151 iterator inserted = insert(position, value);
158 template<Type::SafeValue T>
159 List<T>::iterator List<T>::insert(const_iterator position, std::initializer_list<T> values) {
160 return insert_range(position, values);
163 template<Type::SafeValue T>
164 template<class... Args>
165 List<T>::iterator List<T>::emplace(const_iterator position, Args&&... args) {
166 Node* node = MakeNode(std::forward<Args>(args)...);
167 LinkBefore(const_cast<Link*>(position.m_link), node);
169 return iterator(node);
172 template<Type::SafeValue T>
173 List<T>::iterator List<T>::erase(const_iterator position) {
174 Node* node = static_cast<Node*>(const_cast<Link*>(position.m_link));
175 Link* next = node->Next;
180 return iterator(next);
183 template<Type::SafeValue T>
184 List<T>::iterator List<T>::erase(const_iterator first, const_iterator last) {
185 while (first != last)
186 first = erase(first);
187 return iterator(const_cast<Link*>(last.m_link));
190 template<Type::SafeValue T>
191 void List<T>::push_front(const T& value) { emplace(begin(), value); }
193 template<Type::SafeValue T>
194 void List<T>::push_front(T&& value) { emplace(begin(), std::move(value)); }
196 template<Type::SafeValue T>
197 template<class... Args>
198 T& List<T>::emplace_front(Args&&... args) { return *emplace(begin(), std::forward<Args>(args)...); }
200 template<Type::SafeValue T>
201 void List<T>::pop_front() noexcept { assert(!empty()); erase(begin()); }
203 template<Type::SafeValue T>
204 void List<T>::push_back(const T& value) { emplace(end(), value); }
206 template<Type::SafeValue T>
207 void List<T>::push_back(T&& value) { emplace(end(), std::move(value)); }
209 template<Type::SafeValue T>
210 template<class... Args>
211 T& List<T>::emplace_back(Args&&... args) { return *emplace(end(), std::forward<Args>(args)...); }
213 template<Type::SafeValue T>
214 void List<T>::pop_back() noexcept { assert(!empty()); erase(std::prev(end())); }
216 template<Type::SafeValue T>
217 void List<T>::resize(size_type count) {
218 while (m_size > count)
220 while (m_size < count)
224 template<Type::SafeValue T>
225 void List<T>::resize(size_type count, const T& value) {
226 while (m_size > count)
228 while (m_size < count)
232 template<Type::SafeValue T>
233 void List<T>::swap(List& other) noexcept {
236 List temporary(std::move(*this));
237 *this = std::move(other);
238 other = std::move(temporary);
241 template<Type::SafeValue T>
242 void List<T>::splice(const_iterator position, List& other) noexcept {
243 splice(position, other, other.begin(), other.end());
246 template<Type::SafeValue T>
247 void List<T>::splice(const_iterator position, List& other, const_iterator source) noexcept {
248 const_iterator next = source;
250 splice(position, other, source, next);
253 template<Type::SafeValue T>
254 void List<T>::splice(const_iterator position, List& other, const_iterator first, const_iterator last) noexcept {
258 for (const_iterator cursor = first; cursor != last; ++cursor)
260 Link* before = const_cast<Link*>(first.m_link);
261 Link* after = const_cast<Link*>(last.m_link)->Prev;
262 before->Prev->Next = after->Next;
263 after->Next->Prev = before->Prev;
264 other.m_size -= count;
265 Link* at = const_cast<Link*>(position.m_link);
266 before->Prev = at->Prev;
268 at->Prev->Next = before;
273 template<Type::SafeValue T>
274 List<T>::node_type List<T>::extract(const_iterator position) {
275 Node* node = static_cast<Node*>(const_cast<Link*>(position.m_link));
278 return node_type(node);
281 template<Type::SafeValue T>
282 List<T>::iterator List<T>::insert(const_iterator position, node_type&& node) {
284 return iterator(const_cast<Link*>(position.m_link));
285 Node* taken = node.m_node;
286 node.m_node = nullptr;
287 LinkBefore(const_cast<Link*>(position.m_link), taken);
289 return iterator(taken);
292 template<Type::SafeValue T>
293 void List<T>::merge(List& other) { merge(other, std::less<T>{}); }
295 template<Type::SafeValue T>
296 template<class Compare>
297 void List<T>::merge(List& other, Compare compare) {
300 iterator mine = begin();
301 while (!other.empty()) {
302 if (mine == end() || compare(other.front(), *mine))
303 splice(mine, other, other.begin());
309 template<Type::SafeValue T>
310 List<T>::size_type List<T>::remove(const T& value) {
311 const T snapshot(value);
312 return remove_if([&snapshot](const T& current) { return current == snapshot; });
315 template<Type::SafeValue T>
316 template<class Predicate>
317 List<T>::size_type List<T>::remove_if(Predicate predicate) {
318 size_type erased = 0;
319 iterator cursor = begin();
320 while (cursor != end()) {
321 if (predicate(*cursor)) {
322 cursor = erase(cursor);
330 template<Type::SafeValue T>
331 void List<T>::reverse() noexcept {
332 Link* cursor = &m_sentinel;
334 std::swap(cursor->Next, cursor->Prev);
335 cursor = cursor->Prev;
336 } while (cursor != &m_sentinel);
339 template<Type::SafeValue T>
340 List<T>::size_type List<T>::unique() {
341 return unique(std::equal_to<T>{});
344 template<Type::SafeValue T>
345 template<class Predicate>
346 List<T>::size_type List<T>::unique(Predicate predicate) {
349 size_type erased = 0;
350 iterator cursor = begin();
351 iterator next = std::next(cursor);
352 while (next != end()) {
353 if (predicate(*cursor, *next)) {
364 template<Type::SafeValue T>
365 void List<T>::sort() { sort(std::less<T>{}); }
367 template<Type::SafeValue T>
368 template<class Compare>
369 void List<T>::sort(Compare compare) {
374 size_type half = m_size / 2;
375 const_iterator middle = begin();
376 for (size_type index = 0; index < half; ++index)
378 right.splice(right.end(), *this, middle, end());
379 left.splice(left.end(), *this);
382 left.merge(right, compare);
386 template<Type::SafeValue T>
387 bool List<T>::operator==(const List& other) const {
388 return operator<=>(other) == 0;
391 template<Type::SafeValue T>
392 STORMBYTE_FORCE_INLINE std::strong_ordering List<T>::operator<=>(const List& other) const {
393 const_iterator left = begin();
394 const_iterator right = other.begin();
395 while (left != end() && right != other.end()) {
397 return std::strong_ordering::less;
399 return std::strong_ordering::greater;
403 if (left == end() && right == other.end())
404 return std::strong_ordering::equal;
405 return left == end() ? std::strong_ordering::less : std::strong_ordering::greater;
408 template<Type::SafeValue T>
409 void List<T>::ResetSentinel() noexcept {
410 m_sentinel.Next = &m_sentinel;
411 m_sentinel.Prev = &m_sentinel;
414 template<Type::SafeValue T>
415 template<class... Args>
416 List<T>::Node* List<T>::MakeNode(Args&&... args) {
417 void* storage = Heap::Allocate(sizeof(Node));
418 if (storage == nullptr)
419 throw AllocationError();
421 return new (storage) Node(std::forward<Args>(args)...);
428 template<Type::SafeValue T>
429 void List<T>::LinkBefore(Link* position, Node* node) noexcept {
430 node->Next = position;
431 node->Prev = position->Prev;
432 position->Prev->Next = node;
433 position->Prev = node;
436 template<Type::SafeValue T>
437 void List<T>::Unlink(Node* node) noexcept {
438 node->Prev->Next = node->Next;
439 node->Next->Prev = node->Prev;
442 template<Type::SafeValue T>
443 void List<T>::Destroy() noexcept {
444 Link* cursor = m_sentinel.Next;
445 while (cursor != &m_sentinel) {
446 Node* node = static_cast<Node*>(cursor);
447 cursor = cursor->Next;