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
42#include <StormByte/safe/exception.hxx>
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;
60 NodeType* parent = m_node->Parent;
61 while (m_node == parent->Right) {
63 parent = parent->Parent;
65 if (m_node->Right != parent)
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;
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;
87 if (m_node->Left != nullptr) {
88 m_node = m_node->Left;
89 while (m_node->Right != nullptr)
90 m_node = m_node->Right;
93 NodeType* parent = m_node->Parent;
94 while (m_node == parent->Left) {
96 parent = parent->Parent;
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;
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) {
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) {
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) {
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;
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) {
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() {
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 {
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) {
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 {
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);
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);
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);
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);
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);
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 {
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 {
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;
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 {
236 swap(m_compare, other.m_compare);
237 swap(m_header, other.m_header);
238 swap(m_size, other.m_size);
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 {
245 return empty() || m_compare(m_header->Right->Entry.first, key);
246 if (m_compare(key, hint->first)) {
247 if (hint == cbegin())
249 const_iterator previous = hint;
251 return m_compare(previous->first, key);
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);
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));
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);
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));
280 template<Type::SafeValue K, Type::SafeValue V, class Compare>
281 requires std::strict_weak_order<Compare, const K&, const K&>
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)));
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());
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);
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);
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;
323 if (HintMatches(hint, key)) {
324 if (hint == cend()) {
325 parent = empty() ? m_header : m_header->Right;
328 parent = const_cast<Node*>(hint.m_node);
332 Node* current = m_header->Parent;
333 while (current != nullptr) {
335 left = m_compare(key, current->Entry.first);
336 current = left ? current->Left : current->Right;
339 Node* created = nullptr;
340 if constexpr (sizeof...(Args) == 0)
341 created = MakeNode(key, V{});
343 created = MakeNode(key, std::forward<Args>(args)...);
344 InsertNode(created, parent, left);
345 return iterator(created);
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;
358 if (HintMatches(hint, lookup)) {
359 if (hint == cend()) {
360 parent = empty() ? m_header : m_header->Right;
363 parent = const_cast<Node*>(hint.m_node);
367 Node* current = m_header->Parent;
368 while (current != nullptr) {
370 left = m_compare(lookup, current->Entry.first);
371 current = left ? current->Left : current->Right;
374 Node* created = nullptr;
375 if constexpr (sizeof...(Args) == 0)
376 created = MakeNode(std::move(key), V{});
378 created = MakeNode(std::move(key), std::forward<Args>(args)...);
379 InsertNode(created, parent, left);
380 return iterator(created);
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)...));
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)...));
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);
405 return insert_result(try_emplace(cend(), key, value), true);
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);
416 return insert_result(try_emplace(cend(), key, std::move(value)), true);
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);
427 return insert_result(try_emplace(cend(), std::move(key), value), true);
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);
438 return insert_result(try_emplace(cend(), std::move(key), std::move(value)), true);
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);
449 return try_emplace(hint, key, value);
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);
460 return try_emplace(hint, key, std::move(value));
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);
471 return try_emplace(hint, std::move(key), value);
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);
482 return try_emplace(hint, std::move(key), std::move(value));
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) {
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;
498 const K& key = node->Entry.first;
499 Node* parent = m_header;
500 Node* current = m_header->Parent;
502 while (current != nullptr) {
504 left = m_compare(key, current->Entry.first);
505 current = left ? current->Left : current->Right;
507 InsertNode(node, parent, left);
508 return insert_return_type{iterator(node), true, node_type{}};
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) {
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;
526 Node* parent = m_header;
528 if (hint == cend()) {
529 parent = empty() ? m_header : m_header->Right;
532 parent = const_cast<Node*>(hint.m_node);
535 InsertNode(node, parent, left);
536 return iterator(node);
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())
544 Node* node = const_cast<Node*>(position.m_node);
546 node->Parent = nullptr;
547 node->Left = nullptr;
548 node->Right = nullptr;
549 return node_type(node);
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);
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()) {
567 if (FindNode(cursor->first) == nullptr) {
568 node_type handle = source.extract(cursor);
569 insert(std::move(handle));
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;
580 Unlink(position.m_node);
581 DestroyNode(position.m_node);
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)));
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));
599 return iterator(const_cast<Node*>(last.m_node));
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);
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);
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);
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;
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;
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)) {
647 current = current->Left;
649 current = current->Right;
652 return iterator(bound);
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)) {
663 current = current->Left;
665 current = current->Right;
668 return const_iterator(bound);
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)) {
679 current = current->Left;
681 current = current->Right;
684 return iterator(bound);
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)) {
695 current = current->Left;
697 current = current->Right;
700 return const_iterator(bound);
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));
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));
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;
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;
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);
732 throw OutOfBoundsError();
733 return node->Entry.second;
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);
741 throw OutOfBoundsError();
742 return node->Entry.second;
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)
751 auto right = other.begin();
752 while (left != end()) {
753 if (!(left->first == right->first) || !(left->second == right->second))
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)
767 return left.second <=> right.second;
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);
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);
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;
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);
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;
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);
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));
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;
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();
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;
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);
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;
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;
893 node->Parent->Right = next;
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;
911 node->Parent->Left = next;
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;
926 if (parent == m_header->Left)
927 m_header->Left = node;
929 parent->Right = node;
930 if (parent == m_header->Right)
931 m_header->Right = node;
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;
944 if (node == node->Parent->Right) {
948 node->Parent->Red = false;
953 Node* uncle = upper->Left;
954 if (uncle != nullptr && uncle->Red) {
955 node->Parent->Red = false;
960 if (node == node->Parent->Left) {
964 node->Parent->Red = false;
970 m_header->Parent->Red = false;
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;
979 while (node->Left != nullptr)
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 {
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;
1001 successor = successor->Right;
1002 while (successor->Left != nullptr)
1003 successor = successor->Left;
1004 child = successor->Right;
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;
1017 childParent = successor;
1019 if (m_header->Parent == node)
1020 m_header->Parent = successor;
1021 else if (node->Parent->Left == node)
1022 node->Parent->Left = successor;
1024 node->Parent->Right = successor;
1025 successor->Parent = node->Parent;
1026 std::swap(successor->Red, node->Red);
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;
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;
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;
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;
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;
1071 sibling->Red = childParent->Red;
1072 childParent->Red = false;
1073 if (sibling->Right != nullptr)
1074 sibling->Right->Red = false;
1075 RotateLeft(childParent);
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;
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;
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;
1099 sibling->Red = childParent->Red;
1100 childParent->Red = false;
1101 if (sibling->Left != nullptr)
1102 sibling->Left->Red = false;
1103 RotateRight(childParent);
1108 if (child != nullptr)
1113 m_header->Parent = nullptr;
1114 m_header->Left = m_header;
1115 m_header->Right = m_header;