StormByte 3.0.0
C++26 foundation of the StormByte suite
Loading...
Searching...
No Matches
list.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#pragma once
41
42namespace StormByte::Safe {
43 template<Type::SafeValue T>
44 List<T>::List() noexcept { ResetSentinel(); }
45
46 template<Type::SafeValue T>
47 List<T>::List(size_type count): List() {
48 for (size_type index = 0; index < count; ++index)
49 emplace_back();
50 }
51
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)
55 push_back(value);
56 }
57
58 template<Type::SafeValue T>
59 List<T>::List(const List& other): List() {
60 for (const T& value : other)
61 push_back(value);
62 }
63
64 template<Type::SafeValue T>
65 List<T>::List(List&& other) noexcept: m_size(other.m_size) {
66 if (other.empty()) {
67 ResetSentinel();
68 return;
69 }
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();
75 other.m_size = 0;
76 }
77
78 template<Type::SafeValue T>
79 List<T>::List(std::initializer_list<T> values): List() {
80 for (const T& value : values)
81 push_back(value);
82 }
83
84 template<Type::SafeValue T>
85 List<T>::~List() noexcept { Destroy(); }
86
87 template<Type::SafeValue T>
88 List<T>& List<T>::operator=(const List& other) {
89 if (this != &other) {
90 List replacement(other);
91 swap(replacement);
92 }
93 return *this;
94 }
95
96 template<Type::SafeValue T>
97 List<T>& List<T>::operator=(List&& other) noexcept {
98 if (this != &other) {
99 Destroy();
100 if (other.empty()) {
101 ResetSentinel();
102 m_size = 0;
103 } else {
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();
110 other.m_size = 0;
111 }
112 }
113 return *this;
114 }
115
116 template<Type::SafeValue T>
117 List<T>& List<T>::operator=(std::initializer_list<T> values) {
118 List replacement(values);
119 swap(replacement);
120 return *this;
121 }
122
123 template<Type::SafeValue T>
124 void List<T>::assign(size_type count, const T& value) {
125 List replacement(count, value);
126 swap(replacement);
127 }
128
129 template<Type::SafeValue T>
130 void List<T>::assign(std::initializer_list<T> values) {
131 *this = values;
132 }
133
134 template<Type::SafeValue T>
135 void List<T>::clear() noexcept { Destroy(); }
136
137 template<Type::SafeValue T>
138 List<T>::iterator List<T>::insert(const_iterator position, const T& value) {
139 return emplace(position, value);
140 }
141
142 template<Type::SafeValue T>
143 List<T>::iterator List<T>::insert(const_iterator position, T&& value) {
144 return emplace(position, std::move(value));
145 }
146
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);
152 if (index == 0)
153 first = inserted;
154 }
155 return first;
156 }
157
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);
161 }
162
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);
168 ++m_size;
169 return iterator(node);
170 }
171
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;
176 Unlink(node);
177 node->Value.~T();
178 Heap::Free(node);
179 --m_size;
180 return iterator(next);
181 }
182
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));
188 }
189
190 template<Type::SafeValue T>
191 void List<T>::push_front(const T& value) { emplace(begin(), value); }
192
193 template<Type::SafeValue T>
194 void List<T>::push_front(T&& value) { emplace(begin(), std::move(value)); }
195
196 template<Type::SafeValue T>
197 template<class... Args>
198 T& List<T>::emplace_front(Args&&... args) { return *emplace(begin(), std::forward<Args>(args)...); }
199
200 template<Type::SafeValue T>
201 void List<T>::pop_front() noexcept { assert(!empty()); erase(begin()); }
202
203 template<Type::SafeValue T>
204 void List<T>::push_back(const T& value) { emplace(end(), value); }
205
206 template<Type::SafeValue T>
207 void List<T>::push_back(T&& value) { emplace(end(), std::move(value)); }
208
209 template<Type::SafeValue T>
210 template<class... Args>
211 T& List<T>::emplace_back(Args&&... args) { return *emplace(end(), std::forward<Args>(args)...); }
212
213 template<Type::SafeValue T>
214 void List<T>::pop_back() noexcept { assert(!empty()); erase(std::prev(end())); }
215
216 template<Type::SafeValue T>
217 void List<T>::resize(size_type count) {
218 while (m_size > count)
219 pop_back();
220 while (m_size < count)
221 emplace_back();
222 }
223
224 template<Type::SafeValue T>
225 void List<T>::resize(size_type count, const T& value) {
226 while (m_size > count)
227 pop_back();
228 while (m_size < count)
229 push_back(value);
230 }
231
232 template<Type::SafeValue T>
233 void List<T>::swap(List& other) noexcept {
234 if (this == &other)
235 return;
236 List temporary(std::move(*this));
237 *this = std::move(other);
238 other = std::move(temporary);
239 }
240
241 template<Type::SafeValue T>
242 void List<T>::splice(const_iterator position, List& other) noexcept {
243 splice(position, other, other.begin(), other.end());
244 }
245
246 template<Type::SafeValue T>
247 void List<T>::splice(const_iterator position, List& other, const_iterator source) noexcept {
248 const_iterator next = source;
249 ++next;
250 splice(position, other, source, next);
251 }
252
253 template<Type::SafeValue T>
254 void List<T>::splice(const_iterator position, List& other, const_iterator first, const_iterator last) noexcept {
255 if (first == last)
256 return;
257 size_type count = 0;
258 for (const_iterator cursor = first; cursor != last; ++cursor)
259 ++count;
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;
267 after->Next = at;
268 at->Prev->Next = before;
269 at->Prev = after;
270 m_size += count;
271 }
272
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));
276 Unlink(node);
277 --m_size;
278 return node_type(node);
279 }
280
281 template<Type::SafeValue T>
282 List<T>::iterator List<T>::insert(const_iterator position, node_type&& node) {
283 if (node.empty())
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);
288 ++m_size;
289 return iterator(taken);
290 }
291
292 template<Type::SafeValue T>
293 void List<T>::merge(List& other) { merge(other, std::less<T>{}); }
294
295 template<Type::SafeValue T>
296 template<class Compare>
297 void List<T>::merge(List& other, Compare compare) {
298 if (this == &other)
299 return;
300 iterator mine = begin();
301 while (!other.empty()) {
302 if (mine == end() || compare(other.front(), *mine))
303 splice(mine, other, other.begin());
304 else
305 ++mine;
306 }
307 }
308
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; });
313 }
314
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);
323 ++erased;
324 } else
325 ++cursor;
326 }
327 return erased;
328 }
329
330 template<Type::SafeValue T>
331 void List<T>::reverse() noexcept {
332 Link* cursor = &m_sentinel;
333 do {
334 std::swap(cursor->Next, cursor->Prev);
335 cursor = cursor->Prev;
336 } while (cursor != &m_sentinel);
337 }
338
339 template<Type::SafeValue T>
340 List<T>::size_type List<T>::unique() {
341 return unique(std::equal_to<T>{});
342 }
343
344 template<Type::SafeValue T>
345 template<class Predicate>
346 List<T>::size_type List<T>::unique(Predicate predicate) {
347 if (size() < 2)
348 return 0;
349 size_type erased = 0;
350 iterator cursor = begin();
351 iterator next = std::next(cursor);
352 while (next != end()) {
353 if (predicate(*cursor, *next)) {
354 next = erase(next);
355 ++erased;
356 } else {
357 cursor = next;
358 ++next;
359 }
360 }
361 return erased;
362 }
363
364 template<Type::SafeValue T>
365 void List<T>::sort() { sort(std::less<T>{}); }
366
367 template<Type::SafeValue T>
368 template<class Compare>
369 void List<T>::sort(Compare compare) {
370 if (size() < 2)
371 return;
372 List left;
373 List right;
374 size_type half = m_size / 2;
375 const_iterator middle = begin();
376 for (size_type index = 0; index < half; ++index)
377 ++middle;
378 right.splice(right.end(), *this, middle, end());
379 left.splice(left.end(), *this);
380 left.sort(compare);
381 right.sort(compare);
382 left.merge(right, compare);
383 splice(end(), left);
384 }
385
386 template<Type::SafeValue T>
387 bool List<T>::operator==(const List& other) const {
388 return operator<=>(other) == 0;
389 }
390
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()) {
396 if (*left < *right)
397 return std::strong_ordering::less;
398 if (*right < *left)
399 return std::strong_ordering::greater;
400 ++left;
401 ++right;
402 }
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;
406 }
407
408 template<Type::SafeValue T>
409 void List<T>::ResetSentinel() noexcept {
410 m_sentinel.Next = &m_sentinel;
411 m_sentinel.Prev = &m_sentinel;
412 }
413
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();
420 try {
421 return new (storage) Node(std::forward<Args>(args)...);
422 } catch (...) {
423 Heap::Free(storage);
424 throw;
425 }
426 }
427
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;
434 }
435
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;
440 }
441
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;
448 node->Value.~T();
449 Heap::Free(node);
450 }
451 ResetSentinel();
452 m_size = 0;
453 }
454}