StormByte 3.0.0
C++26 foundation of the StormByte suite
Loading...
Searching...
No Matches
map.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
42#include <StormByte/safe/exception.hxx>
43
44#include <algorithm>
45#include <new>
46#include <utility>
47
48namespace StormByte {
49 namespace Safe {
50 template<Type::SafeValue K, Type::SafeValue V, class Compare>
51 requires std::strict_weak_order<Compare, const K&, const K&>
52 template<bool IsConst>
53 Map<K, V, Compare>::BasicIterator<IsConst>& Map<K, V, Compare>::BasicIterator<IsConst>::operator++() noexcept {
54 if (m_node->Right != nullptr) {
55 m_node = m_node->Right;
56 while (m_node->Left != nullptr)
57 m_node = m_node->Left;
58 return *this;
59 }
60 NodeType* parent = m_node->Parent;
61 while (m_node == parent->Right) {
62 m_node = parent;
63 parent = parent->Parent;
64 }
65 if (m_node->Right != parent)
66 m_node = parent;
67 return *this;
68 }
69
70 template<Type::SafeValue K, Type::SafeValue V, class Compare>
71 requires std::strict_weak_order<Compare, const K&, const K&>
72 template<bool IsConst>
73 Map<K, V, Compare>::BasicIterator<IsConst> Map<K, V, Compare>::BasicIterator<IsConst>::operator++(int) noexcept {
74 BasicIterator previous = *this;
75 ++*this;
76 return previous;
77 }
78
79 template<Type::SafeValue K, Type::SafeValue V, class Compare>
80 requires std::strict_weak_order<Compare, const K&, const K&>
81 template<bool IsConst>
82 Map<K, V, Compare>::BasicIterator<IsConst>& Map<K, V, Compare>::BasicIterator<IsConst>::operator--() noexcept {
83 if (m_node->Red && m_node->Parent->Parent == m_node) {
84 m_node = m_node->Right;
85 return *this;
86 }
87 if (m_node->Left != nullptr) {
88 m_node = m_node->Left;
89 while (m_node->Right != nullptr)
90 m_node = m_node->Right;
91 return *this;
92 }
93 NodeType* parent = m_node->Parent;
94 while (m_node == parent->Left) {
95 m_node = parent;
96 parent = parent->Parent;
97 }
98 m_node = parent;
99 return *this;
100 }
101
102 template<Type::SafeValue K, Type::SafeValue V, class Compare>
103 requires std::strict_weak_order<Compare, const K&, const K&>
104 template<bool IsConst>
105 Map<K, V, Compare>::BasicIterator<IsConst> Map<K, V, Compare>::BasicIterator<IsConst>::operator--(int) noexcept {
106 BasicIterator previous = *this;
107 --*this;
108 return previous;
109 }
110
111 template<Type::SafeValue K, Type::SafeValue V, class Compare>
112 requires std::strict_weak_order<Compare, const K&, const K&>
113 Map<K, V, Compare>::Map(): m_compare(), m_header(nullptr), m_size(0) {
114 CreateHeader();
115 }
116
117 template<Type::SafeValue K, Type::SafeValue V, class Compare>
118 requires std::strict_weak_order<Compare, const K&, const K&>
119 Map<K, V, Compare>::Map(const Compare& compare): m_compare(compare), m_header(nullptr), m_size(0) {
120 CreateHeader();
121 }
122
123 template<Type::SafeValue K, Type::SafeValue V, class Compare>
124 requires std::strict_weak_order<Compare, const K&, const K&>
125 Map<K, V, Compare>::Map(const Map& other): m_compare(other.m_compare), m_header(nullptr), m_size(0) {
126 CreateHeader();
127 if (other.m_header->Parent != nullptr) {
128 m_header->Parent = Clone(other.m_header->Parent, m_header);
129 m_header->Left = Leftmost();
130 Node* right = m_header->Parent;
131 while (right->Right != nullptr)
132 right = right->Right;
133 m_header->Right = right;
134 m_size = other.m_size;
135 }
136 }
137
138 template<Type::SafeValue K, Type::SafeValue V, class Compare>
139 requires std::strict_weak_order<Compare, const K&, const K&>
140 Map<K, V, Compare>::Map(Map&& other): Map(other.m_compare) {
141 swap(other);
142 }
143
144 template<Type::SafeValue K, Type::SafeValue V, class Compare>
145 requires std::strict_weak_order<Compare, const K&, const K&>
146 Map<K, V, Compare>::Map(std::initializer_list<value_type> values): Map() {
147 insert(values);
148 }
149
150 template<Type::SafeValue K, Type::SafeValue V, class Compare>
151 requires std::strict_weak_order<Compare, const K&, const K&>
152 Map<K, V, Compare>::~Map() noexcept {
153 clear();
154 DestroyHeader();
155 }
156
157 template<Type::SafeValue K, Type::SafeValue V, class Compare>
158 requires std::strict_weak_order<Compare, const K&, const K&>
159 Map<K, V, Compare>& Map<K, V, Compare>::operator=(const Map& other) {
160 if (this == &other)
161 return *this;
162 Map copy(other);
163 swap(copy);
164 return *this;
165 }
166
167 template<Type::SafeValue K, Type::SafeValue V, class Compare>
168 requires std::strict_weak_order<Compare, const K&, const K&>
169 Map<K, V, Compare>& Map<K, V, Compare>::operator=(Map&& other) noexcept {
170 if (this == &other)
171 return *this;
172 clear();
173 swap(other);
174 return *this;
175 }
176
177 template<Type::SafeValue K, Type::SafeValue V, class Compare>
178 requires std::strict_weak_order<Compare, const K&, const K&>
179 Map<K, V, Compare>& Map<K, V, Compare>::operator=(std::initializer_list<value_type> values) {
180 Map replacement(m_compare);
181 replacement.insert(values);
182 swap(replacement);
183 return *this;
184 }
185
186 template<Type::SafeValue K, Type::SafeValue V, class Compare>
187 requires std::strict_weak_order<Compare, const K&, const K&>
188 Map<K, V, Compare>::iterator Map<K, V, Compare>::begin() noexcept {
189 return iterator(m_header->Left);
190 }
191
192 template<Type::SafeValue K, Type::SafeValue V, class Compare>
193 requires std::strict_weak_order<Compare, const K&, const K&>
194 Map<K, V, Compare>::iterator Map<K, V, Compare>::end() noexcept {
195 return iterator(m_header);
196 }
197
198 template<Type::SafeValue K, Type::SafeValue V, class Compare>
199 requires std::strict_weak_order<Compare, const K&, const K&>
200 Map<K, V, Compare>::const_iterator Map<K, V, Compare>::begin() const noexcept {
201 return const_iterator(m_header->Left);
202 }
203
204 template<Type::SafeValue K, Type::SafeValue V, class Compare>
205 requires std::strict_weak_order<Compare, const K&, const K&>
206 Map<K, V, Compare>::const_iterator Map<K, V, Compare>::end() const noexcept {
207 return const_iterator(m_header);
208 }
209
210 template<Type::SafeValue K, Type::SafeValue V, class Compare>
211 requires std::strict_weak_order<Compare, const K&, const K&>
212 Map<K, V, Compare>::const_iterator Map<K, V, Compare>::cbegin() const noexcept {
213 return begin();
214 }
215
216 template<Type::SafeValue K, Type::SafeValue V, class Compare>
217 requires std::strict_weak_order<Compare, const K&, const K&>
218 Map<K, V, Compare>::const_iterator Map<K, V, Compare>::cend() const noexcept {
219 return end();
220 }
221
222 template<Type::SafeValue K, Type::SafeValue V, class Compare>
223 requires std::strict_weak_order<Compare, const K&, const K&>
224 void Map<K, V, Compare>::clear() noexcept {
225 DestroyTree(m_header->Parent);
226 m_header->Parent = nullptr;
227 m_header->Left = m_header;
228 m_header->Right = m_header;
229 m_size = 0;
230 }
231
232 template<Type::SafeValue K, Type::SafeValue V, class Compare>
233 requires std::strict_weak_order<Compare, const K&, const K&>
234 void Map<K, V, Compare>::swap(Map& other) noexcept {
235 using std::swap;
236 swap(m_compare, other.m_compare);
237 swap(m_header, other.m_header);
238 swap(m_size, other.m_size);
239 }
240
241 template<Type::SafeValue K, Type::SafeValue V, class Compare>
242 requires std::strict_weak_order<Compare, const K&, const K&>
243 bool Map<K, V, Compare>::HintMatches(const_iterator hint, const K& key) const noexcept {
244 if (hint == cend())
245 return empty() || m_compare(m_header->Right->Entry.first, key);
246 if (m_compare(key, hint->first)) {
247 if (hint == cbegin())
248 return true;
249 const_iterator previous = hint;
250 --previous;
251 return m_compare(previous->first, key);
252 }
253 return false;
254 }
255
256 template<Type::SafeValue K, Type::SafeValue V, class Compare>
257 requires std::strict_weak_order<Compare, const K&, const K&>
258 Map<K, V, Compare>::insert_result Map<K, V, Compare>::insert(const value_type& entry) {
259 return try_emplace(entry.first, entry.second);
260 }
261
262 template<Type::SafeValue K, Type::SafeValue V, class Compare>
263 requires std::strict_weak_order<Compare, const K&, const K&>
264 Map<K, V, Compare>::insert_result Map<K, V, Compare>::insert(value_type&& entry) {
265 return try_emplace(entry.first, std::move(entry.second));
266 }
267
268 template<Type::SafeValue K, Type::SafeValue V, class Compare>
269 requires std::strict_weak_order<Compare, const K&, const K&>
270 Map<K, V, Compare>::iterator Map<K, V, Compare>::insert(const_iterator hint, const value_type& entry) {
271 return try_emplace(hint, entry.first, entry.second);
272 }
273
274 template<Type::SafeValue K, Type::SafeValue V, class Compare>
275 requires std::strict_weak_order<Compare, const K&, const K&>
276 Map<K, V, Compare>::iterator Map<K, V, Compare>::insert(const_iterator hint, value_type&& entry) {
277 return try_emplace(hint, entry.first, std::move(entry.second));
278 }
279
280 template<Type::SafeValue K, Type::SafeValue V, class Compare>
281 requires std::strict_weak_order<Compare, const K&, const K&>
282 template<class P>
283 requires Type::ConstructibleFrom<typename Map<K, V, Compare>::value_type, P> && (!Type::SameAs<std::remove_cvref_t<P>, typename Map<K, V, Compare>::value_type>)
284 Map<K, V, Compare>::insert_result Map<K, V, Compare>::insert(P&& entry) {
285 return insert(value_type(std::forward<P>(entry)));
286 }
287
288 template<Type::SafeValue K, Type::SafeValue V, class Compare>
289 requires std::strict_weak_order<Compare, const K&, const K&>
290 void Map<K, V, Compare>::insert(std::initializer_list<value_type> values) {
291 insert(values.begin(), values.end());
292 }
293
294 template<Type::SafeValue K, Type::SafeValue V, class Compare>
295 requires std::strict_weak_order<Compare, const K&, const K&>
296 template<class... Args>
297 Map<K, V, Compare>::insert_result Map<K, V, Compare>::try_emplace(const K& key, Args&&... args) {
298 Node* existing = FindNode(key);
299 if (existing != nullptr)
300 return insert_result(iterator(existing), false);
301 return insert_result(try_emplace(cend(), key, std::forward<Args>(args)...), true);
302 }
303
304 template<Type::SafeValue K, Type::SafeValue V, class Compare>
305 requires std::strict_weak_order<Compare, const K&, const K&>
306 template<class... Args>
307 Map<K, V, Compare>::insert_result Map<K, V, Compare>::try_emplace(K&& key, Args&&... args) {
308 Node* existing = FindNode(key);
309 if (existing != nullptr)
310 return insert_result(iterator(existing), false);
311 return insert_result(try_emplace(cend(), std::move(key), std::forward<Args>(args)...), true);
312 }
313
314 template<Type::SafeValue K, Type::SafeValue V, class Compare>
315 requires std::strict_weak_order<Compare, const K&, const K&>
316 template<class... Args>
317 Map<K, V, Compare>::iterator Map<K, V, Compare>::try_emplace(const_iterator hint, const K& key, Args&&... args) {
318 Node* existing = FindNode(key);
319 if (existing != nullptr)
320 return iterator(existing);
321 Node* parent = m_header;
322 bool left = true;
323 if (HintMatches(hint, key)) {
324 if (hint == cend()) {
325 parent = empty() ? m_header : m_header->Right;
326 left = empty();
327 } else {
328 parent = const_cast<Node*>(hint.m_node);
329 left = true;
330 }
331 } else {
332 Node* current = m_header->Parent;
333 while (current != nullptr) {
334 parent = current;
335 left = m_compare(key, current->Entry.first);
336 current = left ? current->Left : current->Right;
337 }
338 }
339 Node* created = nullptr;
340 if constexpr (sizeof...(Args) == 0)
341 created = MakeNode(key, V{});
342 else
343 created = MakeNode(key, std::forward<Args>(args)...);
344 InsertNode(created, parent, left);
345 return iterator(created);
346 }
347
348 template<Type::SafeValue K, Type::SafeValue V, class Compare>
349 requires std::strict_weak_order<Compare, const K&, const K&>
350 template<class... Args>
351 Map<K, V, Compare>::iterator Map<K, V, Compare>::try_emplace(const_iterator hint, K&& key, Args&&... args) {
352 const K& lookup = key;
353 Node* existing = FindNode(lookup);
354 if (existing != nullptr)
355 return iterator(existing);
356 Node* parent = m_header;
357 bool left = true;
358 if (HintMatches(hint, lookup)) {
359 if (hint == cend()) {
360 parent = empty() ? m_header : m_header->Right;
361 left = empty();
362 } else {
363 parent = const_cast<Node*>(hint.m_node);
364 left = true;
365 }
366 } else {
367 Node* current = m_header->Parent;
368 while (current != nullptr) {
369 parent = current;
370 left = m_compare(lookup, current->Entry.first);
371 current = left ? current->Left : current->Right;
372 }
373 }
374 Node* created = nullptr;
375 if constexpr (sizeof...(Args) == 0)
376 created = MakeNode(std::move(key), V{});
377 else
378 created = MakeNode(std::move(key), std::forward<Args>(args)...);
379 InsertNode(created, parent, left);
380 return iterator(created);
381 }
382
383 template<Type::SafeValue K, Type::SafeValue V, class Compare>
384 requires std::strict_weak_order<Compare, const K&, const K&>
385 template<class... Args>
386 Map<K, V, Compare>::insert_result Map<K, V, Compare>::emplace(Args&&... args) {
387 return insert(value_type(std::forward<Args>(args)...));
388 }
389
390 template<Type::SafeValue K, Type::SafeValue V, class Compare>
391 requires std::strict_weak_order<Compare, const K&, const K&>
392 template<class... Args>
393 Map<K, V, Compare>::iterator Map<K, V, Compare>::emplace_hint(const_iterator hint, Args&&... args) {
394 return insert(hint, value_type(std::forward<Args>(args)...));
395 }
396
397 template<Type::SafeValue K, Type::SafeValue V, class Compare>
398 requires std::strict_weak_order<Compare, const K&, const K&>
399 Map<K, V, Compare>::insert_result Map<K, V, Compare>::insert_or_assign(const K& key, const V& value) {
400 Node* existing = FindNode(key);
401 if (existing != nullptr) {
402 existing->Entry.second = value;
403 return insert_result(iterator(existing), false);
404 }
405 return insert_result(try_emplace(cend(), key, value), true);
406 }
407
408 template<Type::SafeValue K, Type::SafeValue V, class Compare>
409 requires std::strict_weak_order<Compare, const K&, const K&>
410 Map<K, V, Compare>::insert_result Map<K, V, Compare>::insert_or_assign(const K& key, V&& value) {
411 Node* existing = FindNode(key);
412 if (existing != nullptr) {
413 existing->Entry.second = std::move(value);
414 return insert_result(iterator(existing), false);
415 }
416 return insert_result(try_emplace(cend(), key, std::move(value)), true);
417 }
418
419 template<Type::SafeValue K, Type::SafeValue V, class Compare>
420 requires std::strict_weak_order<Compare, const K&, const K&>
421 Map<K, V, Compare>::insert_result Map<K, V, Compare>::insert_or_assign(K&& key, const V& value) {
422 Node* existing = FindNode(key);
423 if (existing != nullptr) {
424 existing->Entry.second = value;
425 return insert_result(iterator(existing), false);
426 }
427 return insert_result(try_emplace(cend(), std::move(key), value), true);
428 }
429
430 template<Type::SafeValue K, Type::SafeValue V, class Compare>
431 requires std::strict_weak_order<Compare, const K&, const K&>
432 Map<K, V, Compare>::insert_result Map<K, V, Compare>::insert_or_assign(K&& key, V&& value) {
433 Node* existing = FindNode(key);
434 if (existing != nullptr) {
435 existing->Entry.second = std::move(value);
436 return insert_result(iterator(existing), false);
437 }
438 return insert_result(try_emplace(cend(), std::move(key), std::move(value)), true);
439 }
440
441 template<Type::SafeValue K, Type::SafeValue V, class Compare>
442 requires std::strict_weak_order<Compare, const K&, const K&>
443 Map<K, V, Compare>::iterator Map<K, V, Compare>::insert_or_assign(const_iterator hint, const K& key, const V& value) {
444 Node* existing = FindNode(key);
445 if (existing != nullptr) {
446 existing->Entry.second = value;
447 return iterator(existing);
448 }
449 return try_emplace(hint, key, value);
450 }
451
452 template<Type::SafeValue K, Type::SafeValue V, class Compare>
453 requires std::strict_weak_order<Compare, const K&, const K&>
454 Map<K, V, Compare>::iterator Map<K, V, Compare>::insert_or_assign(const_iterator hint, const K& key, V&& value) {
455 Node* existing = FindNode(key);
456 if (existing != nullptr) {
457 existing->Entry.second = std::move(value);
458 return iterator(existing);
459 }
460 return try_emplace(hint, key, std::move(value));
461 }
462
463 template<Type::SafeValue K, Type::SafeValue V, class Compare>
464 requires std::strict_weak_order<Compare, const K&, const K&>
465 Map<K, V, Compare>::iterator Map<K, V, Compare>::insert_or_assign(const_iterator hint, K&& key, const V& value) {
466 Node* existing = FindNode(key);
467 if (existing != nullptr) {
468 existing->Entry.second = value;
469 return iterator(existing);
470 }
471 return try_emplace(hint, std::move(key), value);
472 }
473
474 template<Type::SafeValue K, Type::SafeValue V, class Compare>
475 requires std::strict_weak_order<Compare, const K&, const K&>
476 Map<K, V, Compare>::iterator Map<K, V, Compare>::insert_or_assign(const_iterator hint, K&& key, V&& value) {
477 Node* existing = FindNode(key);
478 if (existing != nullptr) {
479 existing->Entry.second = std::move(value);
480 return iterator(existing);
481 }
482 return try_emplace(hint, std::move(key), std::move(value));
483 }
484
485 template<Type::SafeValue K, Type::SafeValue V, class Compare>
486 requires std::strict_weak_order<Compare, const K&, const K&>
487 Map<K, V, Compare>::insert_return_type Map<K, V, Compare>::insert(node_type&& handle) {
488 if (!handle)
489 return insert_return_type{end(), false, node_type{}};
490 Node* existing = FindNode(handle.key());
491 if (existing != nullptr)
492 return insert_return_type{iterator(existing), false, std::move(handle)};
493 Node* node = handle.m_node;
494 handle.m_node = nullptr;
495 node->Left = nullptr;
496 node->Right = nullptr;
497 node->Red = true;
498 const K& key = node->Entry.first;
499 Node* parent = m_header;
500 Node* current = m_header->Parent;
501 bool left = true;
502 while (current != nullptr) {
503 parent = current;
504 left = m_compare(key, current->Entry.first);
505 current = left ? current->Left : current->Right;
506 }
507 InsertNode(node, parent, left);
508 return insert_return_type{iterator(node), true, node_type{}};
509 }
510
511 template<Type::SafeValue K, Type::SafeValue V, class Compare>
512 requires std::strict_weak_order<Compare, const K&, const K&>
513 Map<K, V, Compare>::iterator Map<K, V, Compare>::insert(const_iterator hint, node_type&& handle) {
514 if (!handle)
515 return end();
516 Node* existing = FindNode(handle.key());
517 if (existing != nullptr)
518 return iterator(existing);
519 if (!HintMatches(hint, handle.key()))
520 return insert(std::move(handle)).position;
521 Node* node = handle.m_node;
522 handle.m_node = nullptr;
523 node->Left = nullptr;
524 node->Right = nullptr;
525 node->Red = true;
526 Node* parent = m_header;
527 bool left = true;
528 if (hint == cend()) {
529 parent = empty() ? m_header : m_header->Right;
530 left = empty();
531 } else {
532 parent = const_cast<Node*>(hint.m_node);
533 left = true;
534 }
535 InsertNode(node, parent, left);
536 return iterator(node);
537 }
538
539 template<Type::SafeValue K, Type::SafeValue V, class Compare>
540 requires std::strict_weak_order<Compare, const K&, const K&>
541 Map<K, V, Compare>::node_type Map<K, V, Compare>::extract(const_iterator position) {
542 if (position == cend())
543 return node_type{};
544 Node* node = const_cast<Node*>(position.m_node);
545 Unlink(node);
546 node->Parent = nullptr;
547 node->Left = nullptr;
548 node->Right = nullptr;
549 return node_type(node);
550 }
551
552 template<Type::SafeValue K, Type::SafeValue V, class Compare>
553 requires std::strict_weak_order<Compare, const K&, const K&>
554 Map<K, V, Compare>::node_type Map<K, V, Compare>::extract(const K& key) {
555 iterator found = find(key);
556 return found == end() ? node_type{} : extract(found);
557 }
558
559 template<Type::SafeValue K, Type::SafeValue V, class Compare>
560 requires std::strict_weak_order<Compare, const K&, const K&>
561 template<class OtherCompare>
562 void Map<K, V, Compare>::merge(Map<K, V, OtherCompare>& source) {
563 auto cursor = source.begin();
564 while (cursor != source.end()) {
565 auto next = cursor;
566 ++next;
567 if (FindNode(cursor->first) == nullptr) {
568 node_type handle = source.extract(cursor);
569 insert(std::move(handle));
570 }
571 cursor = next;
572 }
573 }
574
575 template<Type::SafeValue K, Type::SafeValue V, class Compare>
576 requires std::strict_weak_order<Compare, const K&, const K&>
577 Map<K, V, Compare>::iterator Map<K, V, Compare>::erase(iterator position) noexcept {
578 iterator following = position;
579 ++following;
580 Unlink(position.m_node);
581 DestroyNode(position.m_node);
582 return following;
583 }
584
585 template<Type::SafeValue K, Type::SafeValue V, class Compare>
586 requires std::strict_weak_order<Compare, const K&, const K&>
587 Map<K, V, Compare>::iterator Map<K, V, Compare>::erase(const_iterator position) noexcept {
588 return erase(iterator(const_cast<Node*>(position.m_node)));
589 }
590
591 template<Type::SafeValue K, Type::SafeValue V, class Compare>
592 requires std::strict_weak_order<Compare, const K&, const K&>
593 Map<K, V, Compare>::iterator Map<K, V, Compare>::erase(const_iterator first, const_iterator last) noexcept {
594 while (first != last) {
595 iterator current(const_cast<Node*>(first.m_node));
596 ++first;
597 erase(current);
598 }
599 return iterator(const_cast<Node*>(last.m_node));
600 }
601
602 template<Type::SafeValue K, Type::SafeValue V, class Compare>
603 requires std::strict_weak_order<Compare, const K&, const K&>
604 Map<K, V, Compare>::size_type Map<K, V, Compare>::erase(const K& key) noexcept {
605 Node* node = FindNode(key);
606 if (node == nullptr)
607 return 0;
608 Unlink(node);
609 DestroyNode(node);
610 return 1;
611 }
612
613 template<Type::SafeValue K, Type::SafeValue V, class Compare>
614 requires std::strict_weak_order<Compare, const K&, const K&>
615 Map<K, V, Compare>::iterator Map<K, V, Compare>::find(const K& key) noexcept {
616 Node* node = FindNode(key);
617 return node == nullptr ? end() : iterator(node);
618 }
619
620 template<Type::SafeValue K, Type::SafeValue V, class Compare>
621 requires std::strict_weak_order<Compare, const K&, const K&>
622 Map<K, V, Compare>::const_iterator Map<K, V, Compare>::find(const K& key) const noexcept {
623 Node* node = FindNode(key);
624 return node == nullptr ? end() : const_iterator(node);
625 }
626
627 template<Type::SafeValue K, Type::SafeValue V, class Compare>
628 requires std::strict_weak_order<Compare, const K&, const K&>
629 bool Map<K, V, Compare>::contains(const K& key) const noexcept {
630 return FindNode(key) != nullptr;
631 }
632
633 template<Type::SafeValue K, Type::SafeValue V, class Compare>
634 requires std::strict_weak_order<Compare, const K&, const K&>
635 Map<K, V, Compare>::size_type Map<K, V, Compare>::count(const K& key) const noexcept {
636 return contains(key) ? 1 : 0;
637 }
638
639 template<Type::SafeValue K, Type::SafeValue V, class Compare>
640 requires std::strict_weak_order<Compare, const K&, const K&>
641 Map<K, V, Compare>::iterator Map<K, V, Compare>::lower_bound(const K& key) noexcept {
642 Node* current = m_header->Parent;
643 Node* bound = m_header;
644 while (current != nullptr) {
645 if (!m_compare(current->Entry.first, key)) {
646 bound = current;
647 current = current->Left;
648 } else {
649 current = current->Right;
650 }
651 }
652 return iterator(bound);
653 }
654
655 template<Type::SafeValue K, Type::SafeValue V, class Compare>
656 requires std::strict_weak_order<Compare, const K&, const K&>
657 Map<K, V, Compare>::const_iterator Map<K, V, Compare>::lower_bound(const K& key) const noexcept {
658 Node* current = m_header->Parent;
659 Node* bound = m_header;
660 while (current != nullptr) {
661 if (!m_compare(current->Entry.first, key)) {
662 bound = current;
663 current = current->Left;
664 } else {
665 current = current->Right;
666 }
667 }
668 return const_iterator(bound);
669 }
670
671 template<Type::SafeValue K, Type::SafeValue V, class Compare>
672 requires std::strict_weak_order<Compare, const K&, const K&>
673 Map<K, V, Compare>::iterator Map<K, V, Compare>::upper_bound(const K& key) noexcept {
674 Node* current = m_header->Parent;
675 Node* bound = m_header;
676 while (current != nullptr) {
677 if (m_compare(key, current->Entry.first)) {
678 bound = current;
679 current = current->Left;
680 } else {
681 current = current->Right;
682 }
683 }
684 return iterator(bound);
685 }
686
687 template<Type::SafeValue K, Type::SafeValue V, class Compare>
688 requires std::strict_weak_order<Compare, const K&, const K&>
689 Map<K, V, Compare>::const_iterator Map<K, V, Compare>::upper_bound(const K& key) const noexcept {
690 Node* current = m_header->Parent;
691 Node* bound = m_header;
692 while (current != nullptr) {
693 if (m_compare(key, current->Entry.first)) {
694 bound = current;
695 current = current->Left;
696 } else {
697 current = current->Right;
698 }
699 }
700 return const_iterator(bound);
701 }
702
703 template<Type::SafeValue K, Type::SafeValue V, class Compare>
704 requires std::strict_weak_order<Compare, const K&, const K&>
705 Map<K, V, Compare>::equal_range_result Map<K, V, Compare>::equal_range(const K& key) noexcept {
706 return equal_range_result(lower_bound(key), upper_bound(key));
707 }
708
709 template<Type::SafeValue K, Type::SafeValue V, class Compare>
710 requires std::strict_weak_order<Compare, const K&, const K&>
711 Map<K, V, Compare>::const_equal_range_result Map<K, V, Compare>::equal_range(const K& key) const noexcept {
712 return const_equal_range_result(lower_bound(key), upper_bound(key));
713 }
714
715 template<Type::SafeValue K, Type::SafeValue V, class Compare>
716 requires std::strict_weak_order<Compare, const K&, const K&>
717 V& Map<K, V, Compare>::operator[](const K& key) {
718 return try_emplace(key).first->second;
719 }
720
721 template<Type::SafeValue K, Type::SafeValue V, class Compare>
722 requires std::strict_weak_order<Compare, const K&, const K&>
723 V& Map<K, V, Compare>::operator[](K&& key) {
724 return try_emplace(std::move(key)).first->second;
725 }
726
727 template<Type::SafeValue K, Type::SafeValue V, class Compare>
728 requires std::strict_weak_order<Compare, const K&, const K&>
729 V& Map<K, V, Compare>::at(const K& key) {
730 Node* node = FindNode(key);
731 if (node == nullptr)
732 throw OutOfBoundsError();
733 return node->Entry.second;
734 }
735
736 template<Type::SafeValue K, Type::SafeValue V, class Compare>
737 requires std::strict_weak_order<Compare, const K&, const K&>
738 const V& Map<K, V, Compare>::at(const K& key) const {
739 Node* node = FindNode(key);
740 if (node == nullptr)
741 throw OutOfBoundsError();
742 return node->Entry.second;
743 }
744
745 template<Type::SafeValue K, Type::SafeValue V, class Compare>
746 requires std::strict_weak_order<Compare, const K&, const K&>
747 bool Map<K, V, Compare>::operator==(const Map& other) const requires Type::EqualityComparable<K> && Type::EqualityComparable<V> {
748 if (m_size != other.m_size)
749 return false;
750 auto left = begin();
751 auto right = other.begin();
752 while (left != end()) {
753 if (!(left->first == right->first) || !(left->second == right->second))
754 return false;
755 ++left;
756 ++right;
757 }
758 return true;
759 }
760
761 template<Type::SafeValue K, Type::SafeValue V, class Compare>
762 requires std::strict_weak_order<Compare, const K&, const K&>
763 STORMBYTE_FORCE_INLINE std::strong_ordering Map<K, V, Compare>::operator<=>(const Map& other) const requires std::three_way_comparable<K> && std::three_way_comparable<V> {
764 return std::lexicographical_compare_three_way(begin(), end(), other.begin(), other.end(), [](const value_type& left, const value_type& right) {
765 if (auto key = left.first <=> right.first; key != 0)
766 return key;
767 return left.second <=> right.second;
768 });
769 }
770
771 template<Type::SafeValue K, Type::SafeValue V, class Compare>
772 requires std::strict_weak_order<Compare, const K&, const K&>
773 bool Map<K, V, Compare>::operator<(const Map& other) const requires requires(const K& a, const K& b, const V& c, const V& d) { a < b; c < d; } {
774 return std::lexicographical_compare(begin(), end(), other.begin(), other.end(), [](const value_type& left, const value_type& right) {
775 return left.first < right.first || (!(right.first < left.first) && left.second < right.second);
776 });
777 }
778
779 template<Type::SafeValue K, Type::SafeValue V, class Compare>
780 requires std::strict_weak_order<Compare, const K&, const K&>
781 bool Map<K, V, Compare>::operator<=(const Map& other) const requires requires(const K& a, const K& b, const V& c, const V& d) { a < b; c < d; } {
782 return !(other < *this);
783 }
784
785 template<Type::SafeValue K, Type::SafeValue V, class Compare>
786 requires std::strict_weak_order<Compare, const K&, const K&>
787 bool Map<K, V, Compare>::operator>(const Map& other) const requires requires(const K& a, const K& b, const V& c, const V& d) { a < b; c < d; } {
788 return other < *this;
789 }
790
791 template<Type::SafeValue K, Type::SafeValue V, class Compare>
792 requires std::strict_weak_order<Compare, const K&, const K&>
793 bool Map<K, V, Compare>::operator>=(const Map& other) const requires requires(const K& a, const K& b, const V& c, const V& d) { a < b; c < d; } {
794 return !(*this < other);
795 }
796
797 template<Type::SafeValue K, Type::SafeValue V, class Compare>
798 requires std::strict_weak_order<Compare, const K&, const K&>
799 void Map<K, V, Compare>::CreateHeader() {
800 void* block = Heap::Allocate(sizeof(Node));
801 m_header = static_cast<Node*>(block);
802 m_header->Parent = nullptr;
803 m_header->Left = m_header;
804 m_header->Right = m_header;
805 m_header->Red = true;
806 }
807
808 template<Type::SafeValue K, Type::SafeValue V, class Compare>
809 requires std::strict_weak_order<Compare, const K&, const K&>
810 void Map<K, V, Compare>::DestroyHeader() noexcept {
811 Heap::Free(m_header);
812 m_header = nullptr;
813 }
814
815 template<Type::SafeValue K, Type::SafeValue V, class Compare>
816 requires std::strict_weak_order<Compare, const K&, const K&>
817 template<class... Args>
818 Map<K, V, Compare>::Node* Map<K, V, Compare>::MakeNode(Args&&... args) {
819 void* block = Heap::Allocate(sizeof(Node));
820 try {
821 Node* node = static_cast<Node*>(block);
822 new (&node->Entry) value_type(std::forward<Args>(args)...);
823 node->Parent = nullptr;
824 node->Left = nullptr;
825 node->Right = nullptr;
826 node->Red = true;
827 return node;
828 } catch (...) {
829 Heap::Free(block);
830 throw;
831 }
832 }
833
834 template<Type::SafeValue K, Type::SafeValue V, class Compare>
835 requires std::strict_weak_order<Compare, const K&, const K&>
836 void Map<K, V, Compare>::DestroyNode(Node* node) noexcept {
837 node->Entry.~value_type();
838 Heap::Free(node);
839 }
840
841 template<Type::SafeValue K, Type::SafeValue V, class Compare>
842 requires std::strict_weak_order<Compare, const K&, const K&>
843 void Map<K, V, Compare>::DestroyTree(Node* node) noexcept {
844 while (node != nullptr) {
845 DestroyTree(node->Right);
846 Node* left = node->Left;
847 DestroyNode(node);
848 node = left;
849 }
850 }
851
852 template<Type::SafeValue K, Type::SafeValue V, class Compare>
853 requires std::strict_weak_order<Compare, const K&, const K&>
854 Map<K, V, Compare>::Node* Map<K, V, Compare>::Clone(const Node* source, Node* parent) {
855 Node* node = MakeNode(source->Entry.first, source->Entry.second);
856 node->Parent = parent;
857 node->Red = source->Red;
858 if (source->Left != nullptr)
859 node->Left = Clone(source->Left, node);
860 if (source->Right != nullptr)
861 node->Right = Clone(source->Right, node);
862 return node;
863 }
864
865 template<Type::SafeValue K, Type::SafeValue V, class Compare>
866 requires std::strict_weak_order<Compare, const K&, const K&>
867 Map<K, V, Compare>::Node* Map<K, V, Compare>::FindNode(const K& key) const noexcept {
868 Node* current = m_header->Parent;
869 while (current != nullptr) {
870 if (m_compare(key, current->Entry.first))
871 current = current->Left;
872 else if (m_compare(current->Entry.first, key))
873 current = current->Right;
874 else
875 return current;
876 }
877 return nullptr;
878 }
879
880 template<Type::SafeValue K, Type::SafeValue V, class Compare>
881 requires std::strict_weak_order<Compare, const K&, const K&>
882 void Map<K, V, Compare>::RotateLeft(Node* node) noexcept {
883 Node* next = node->Right;
884 node->Right = next->Left;
885 if (next->Left != nullptr)
886 next->Left->Parent = node;
887 next->Parent = node->Parent;
888 if (node == m_header->Parent)
889 m_header->Parent = next;
890 else if (node == node->Parent->Left)
891 node->Parent->Left = next;
892 else
893 node->Parent->Right = next;
894 next->Left = node;
895 node->Parent = next;
896 }
897
898 template<Type::SafeValue K, Type::SafeValue V, class Compare>
899 requires std::strict_weak_order<Compare, const K&, const K&>
900 void Map<K, V, Compare>::RotateRight(Node* node) noexcept {
901 Node* next = node->Left;
902 node->Left = next->Right;
903 if (next->Right != nullptr)
904 next->Right->Parent = node;
905 next->Parent = node->Parent;
906 if (node == m_header->Parent)
907 m_header->Parent = next;
908 else if (node == node->Parent->Right)
909 node->Parent->Right = next;
910 else
911 node->Parent->Left = next;
912 next->Right = node;
913 node->Parent = next;
914 }
915
916 template<Type::SafeValue K, Type::SafeValue V, class Compare>
917 requires std::strict_weak_order<Compare, const K&, const K&>
918 void Map<K, V, Compare>::InsertNode(Node* node, Node* parent, bool left) noexcept {
919 node->Parent = parent;
920 if (parent == m_header) {
921 m_header->Parent = node;
922 m_header->Left = node;
923 m_header->Right = node;
924 } else if (left) {
925 parent->Left = node;
926 if (parent == m_header->Left)
927 m_header->Left = node;
928 } else {
929 parent->Right = node;
930 if (parent == m_header->Right)
931 m_header->Right = node;
932 }
933 ++m_size;
934 while (node != m_header->Parent && node->Parent->Red) {
935 Node* upper = node->Parent->Parent;
936 if (node->Parent == upper->Left) {
937 Node* uncle = upper->Right;
938 if (uncle != nullptr && uncle->Red) {
939 node->Parent->Red = false;
940 uncle->Red = false;
941 upper->Red = true;
942 node = upper;
943 } else {
944 if (node == node->Parent->Right) {
945 node = node->Parent;
946 RotateLeft(node);
947 }
948 node->Parent->Red = false;
949 upper->Red = true;
950 RotateRight(upper);
951 }
952 } else {
953 Node* uncle = upper->Left;
954 if (uncle != nullptr && uncle->Red) {
955 node->Parent->Red = false;
956 uncle->Red = false;
957 upper->Red = true;
958 node = upper;
959 } else {
960 if (node == node->Parent->Left) {
961 node = node->Parent;
962 RotateRight(node);
963 }
964 node->Parent->Red = false;
965 upper->Red = true;
966 RotateLeft(upper);
967 }
968 }
969 }
970 m_header->Parent->Red = false;
971 }
972
973 template<Type::SafeValue K, Type::SafeValue V, class Compare>
974 requires std::strict_weak_order<Compare, const K&, const K&>
975 Map<K, V, Compare>::Node* Map<K, V, Compare>::Leftmost() const noexcept {
976 Node* node = m_header->Parent;
977 if (node == nullptr)
978 return m_header;
979 while (node->Left != nullptr)
980 node = node->Left;
981 return node;
982 }
983
984 template<Type::SafeValue K, Type::SafeValue V, class Compare>
985 requires std::strict_weak_order<Compare, const K&, const K&>
986 void Map<K, V, Compare>::Unlink(Node* node) noexcept {
987 EraseNode(node);
988 }
989
990 template<Type::SafeValue K, Type::SafeValue V, class Compare>
991 requires std::strict_weak_order<Compare, const K&, const K&>
992 void Map<K, V, Compare>::EraseNode(Node* node) noexcept {
993 Node* successor = node;
994 Node* child = nullptr;
995 Node* childParent = nullptr;
996 if (successor->Left == nullptr)
997 child = successor->Right;
998 else if (successor->Right == nullptr)
999 child = successor->Left;
1000 else {
1001 successor = successor->Right;
1002 while (successor->Left != nullptr)
1003 successor = successor->Left;
1004 child = successor->Right;
1005 }
1006 if (successor != node) {
1007 node->Left->Parent = successor;
1008 successor->Left = node->Left;
1009 if (successor != node->Right) {
1010 childParent = successor->Parent;
1011 if (child != nullptr)
1012 child->Parent = successor->Parent;
1013 successor->Parent->Left = child;
1014 successor->Right = node->Right;
1015 node->Right->Parent = successor;
1016 } else {
1017 childParent = successor;
1018 }
1019 if (m_header->Parent == node)
1020 m_header->Parent = successor;
1021 else if (node->Parent->Left == node)
1022 node->Parent->Left = successor;
1023 else
1024 node->Parent->Right = successor;
1025 successor->Parent = node->Parent;
1026 std::swap(successor->Red, node->Red);
1027 successor = node;
1028 } else {
1029 childParent = node->Parent;
1030 if (child != nullptr)
1031 child->Parent = node->Parent;
1032 if (m_header->Parent == node)
1033 m_header->Parent = child;
1034 else if (node->Parent->Left == node)
1035 node->Parent->Left = child;
1036 else
1037 node->Parent->Right = child;
1038 if (m_header->Left == node)
1039 m_header->Left = child == nullptr ? node->Parent : Leftmost();
1040 if (m_header->Right == node) {
1041 Node* right = child == nullptr ? node->Parent : child;
1042 if (child != nullptr)
1043 while (right->Right != nullptr)
1044 right = right->Right;
1045 m_header->Right = right;
1046 }
1047 }
1048 if (!successor->Red) {
1049 while (child != m_header->Parent && (child == nullptr || !child->Red)) {
1050 if (child == childParent->Left) {
1051 Node* sibling = childParent->Right;
1052 if (sibling != nullptr && sibling->Red) {
1053 sibling->Red = false;
1054 childParent->Red = true;
1055 RotateLeft(childParent);
1056 sibling = childParent->Right;
1057 }
1058 if (sibling == nullptr || ((sibling->Left == nullptr || !sibling->Left->Red) && (sibling->Right == nullptr || !sibling->Right->Red))) {
1059 if (sibling != nullptr)
1060 sibling->Red = true;
1061 child = childParent;
1062 childParent = childParent->Parent;
1063 } else {
1064 if (sibling->Right == nullptr || !sibling->Right->Red) {
1065 if (sibling->Left != nullptr)
1066 sibling->Left->Red = false;
1067 sibling->Red = true;
1068 RotateRight(sibling);
1069 sibling = childParent->Right;
1070 }
1071 sibling->Red = childParent->Red;
1072 childParent->Red = false;
1073 if (sibling->Right != nullptr)
1074 sibling->Right->Red = false;
1075 RotateLeft(childParent);
1076 break;
1077 }
1078 } else {
1079 Node* sibling = childParent->Left;
1080 if (sibling != nullptr && sibling->Red) {
1081 sibling->Red = false;
1082 childParent->Red = true;
1083 RotateRight(childParent);
1084 sibling = childParent->Left;
1085 }
1086 if (sibling == nullptr || ((sibling->Left == nullptr || !sibling->Left->Red) && (sibling->Right == nullptr || !sibling->Right->Red))) {
1087 if (sibling != nullptr)
1088 sibling->Red = true;
1089 child = childParent;
1090 childParent = childParent->Parent;
1091 } else {
1092 if (sibling->Left == nullptr || !sibling->Left->Red) {
1093 if (sibling->Right != nullptr)
1094 sibling->Right->Red = false;
1095 sibling->Red = true;
1096 RotateLeft(sibling);
1097 sibling = childParent->Left;
1098 }
1099 sibling->Red = childParent->Red;
1100 childParent->Red = false;
1101 if (sibling->Left != nullptr)
1102 sibling->Left->Red = false;
1103 RotateRight(childParent);
1104 break;
1105 }
1106 }
1107 }
1108 if (child != nullptr)
1109 child->Red = false;
1110 }
1111 --m_size;
1112 if (m_size == 0) {
1113 m_header->Parent = nullptr;
1114 m_header->Left = m_header;
1115 m_header->Right = m_header;
1116 }
1117 }
1118
1119 }
1120}