Embedded Template Library 1.0
Loading...
Searching...
No Matches
map.h
Go to the documentation of this file.
1
2
3/******************************************************************************
4The MIT License(MIT)
5
6Embedded Template Library.
7https://github.com/ETLCPP/etl
8https://www.etlcpp.com
9
10Copyright(c) 2021 John Wellbelove
11
12Permission is hereby granted, free of charge, to any person obtaining a copy
13of this software and associated documentation files(the "Software"), to deal
14in the Software without restriction, including without limitation the rights
15to use, copy, modify, merge, publish, distribute, sublicense, and / or sell
16copies of the Software, and to permit persons to whom the Software is
17furnished to do so, subject to the following conditions :
18
19The above copyright notice and this permission notice shall be included in all
20copies or substantial portions of the Software.
21
22THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
23IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
24FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE
25AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
26LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
27OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
28SOFTWARE.
29******************************************************************************/
30
31#ifndef ETL_MAP_INCLUDED
32#define ETL_MAP_INCLUDED
33
34#include "platform.h"
35#include "algorithm.h"
36#include "iterator.h"
37#include "functional.h"
38#include "pool.h"
39#include "exception.h"
40#include "error_handler.h"
41#include "debug_count.h"
42#include "nullptr.h"
43#include "type_traits.h"
44#include "nth_type.h"
45#include "parameter_type.h"
46#include "iterator.h"
47#include "utility.h"
48#include "placement_new.h"
49#include "initializer_list.h"
50
51#include <stddef.h>
52
53#include "private/minmax_push.h"
55
56//*****************************************************************************
60//*****************************************************************************
61
62namespace etl
63{
64 //***************************************************************************
67 //***************************************************************************
77
78 //***************************************************************************
81 //***************************************************************************
83 {
84 public:
85
87 : etl::map_exception(ETL_ERROR_TEXT("map:full", ETL_MAP_FILE_ID"A"), file_name_, line_number_)
88 {
89 }
90 };
91
92 //***************************************************************************
95 //***************************************************************************
97 {
98 public:
99
101 : etl::map_exception(ETL_ERROR_TEXT("map:bounds", ETL_MAP_FILE_ID"B"), file_name_, line_number_)
102 {
103 }
104 };
105
106 //***************************************************************************
109 //***************************************************************************
111 {
112 public:
113
115 : etl::map_exception(ETL_ERROR_TEXT("map:iterator", ETL_MAP_FILE_ID"C"), file_name_, line_number_)
116 {
117 }
118 };
119
120 //***************************************************************************
123 //***************************************************************************
125 {
126 public:
127
128 typedef size_t size_type;
129
130 //*************************************************************************
132 //*************************************************************************
134 {
135 return current_size;
136 }
137
138 //*************************************************************************
140 //*************************************************************************
142 {
143 return CAPACITY;
144 }
145
146 //*************************************************************************
148 //*************************************************************************
149 bool empty() const
150 {
151 return current_size == 0;
152 }
153
154 //*************************************************************************
156 //*************************************************************************
157 bool full() const
158 {
159 return current_size == CAPACITY;
160 }
161
162 //*************************************************************************
165 //*************************************************************************
167 {
168 return CAPACITY;
169 }
170
171 //*************************************************************************
174 //*************************************************************************
175 size_t available() const
176 {
177 return max_size() - size();
178 }
179
180 protected:
181
182 enum
183 {
184 kLeft = 0,
185 kRight = 1,
186 kNeither = 2
187 };
188
189 //*************************************************************************
191 //*************************************************************************
192 struct Node
193 {
194 //***********************************************************************
196 //***********************************************************************
198 weight(uint_least8_t(kNeither)),
199 dir(uint_least8_t(kNeither))
200 {
201 children[0] = ETL_NULLPTR;
202 children[1] = ETL_NULLPTR;
203 }
204
205 ~Node()
206 {
207
208 }
209
210 //***********************************************************************
212 //***********************************************************************
214 {
215 weight = uint_least8_t(kNeither);
216 dir = uint_least8_t(kNeither);
217 children[0] = ETL_NULLPTR;
218 children[1] = ETL_NULLPTR;
219 }
220
221 Node* children[2];
222 uint_least8_t weight;
223 uint_least8_t dir;
224 };
225
226 //*************************************************************************
228 //*************************************************************************
230 : current_size(0)
232 , root_node(ETL_NULLPTR)
233
234 {
235 }
236
237 //*************************************************************************
239 //*************************************************************************
241 {
242 }
243
244 //*************************************************************************
246 //*************************************************************************
248 {
249 // Step 1: Update weights for all children of the critical node up to the
250 // newly inserted node. This step is costly (in terms of traversing nodes
251 // multiple times during insertion) but doesn't require as much recursion
252 Node* weight_node = critical_node->children[critical_node->dir];
253 while (weight_node)
254 {
255 // Keep going until we reach a terminal node (dir == kNeither)
256 if (uint_least8_t(kNeither) != weight_node->dir)
257 {
258 // Does this insert balance the previous weight factor value?
259 if (weight_node->weight == 1 - weight_node->dir)
260 {
261 weight_node->weight = uint_least8_t(kNeither);
262 }
263 else
264 {
265 weight_node->weight = weight_node->dir;
266 }
267
268 // Update weight factor node to point to next node
269 weight_node = weight_node->children[weight_node->dir];
270 }
271 else
272 {
273 // Stop loop, terminal node found
274 break;
275 }
276 } // while(weight_node)
277
278 // Step 2: Update weight for critical_node or rotate tree to balance node
279 if (uint_least8_t(kNeither) == critical_node->weight)
280 {
281 critical_node->weight = critical_node->dir;
282 }
283 // If direction is different than weight, then it will now be balanced
284 else if (critical_node->dir != critical_node->weight)
285 {
286 critical_node->weight = uint_least8_t(kNeither);
287 }
288 // Rotate is required to balance the tree at the critical node
289 else
290 {
291 // If critical node matches child node direction then perform a two
292 // node rotate in the direction of the critical node
293 if (critical_node->weight == critical_node->children[critical_node->dir]->dir)
294 {
296 }
297 // Otherwise perform a three node rotation in the direction of the
298 // critical node
299 else
300 {
302 critical_node->children[critical_node->dir]->children[1 - critical_node->dir]->dir);
303 }
304 }
305 }
306
307 //*************************************************************************
309 //*************************************************************************
310 void rotate_2node(Node*& position, uint_least8_t dir)
311 {
312 // A C A B
313 // B C -> A E OR B C -> D A
314 // D E B D D E E C
315 // C (new position) becomes the root
316 // A (position) takes ownership of D as its children[kRight] child
317 // C (new position) takes ownership of A as its left child
318 // OR
319 // B (new position) becomes the root
320 // A (position) takes ownership of E as its left child
321 // B (new position) takes ownership of A as its right child
322
323 // Capture new root
324 Node* new_root = position->children[dir];
325 // Replace position's previous child with new root's other child
326 position->children[dir] = new_root->children[1 - dir];
327 // New root now becomes parent of current position
328 new_root->children[1 - dir] = position;
329 // Clear weight factor from current position
330 position->weight = uint_least8_t(kNeither);
331 // Newly detached right now becomes current position
332 position = new_root;
333 // Clear weight factor from new root
334 position->weight = uint_least8_t(kNeither);
335 }
336
337 //*************************************************************************
339 //*************************************************************************
341 {
342 // --A-- --E-- --A-- --D--
343 // _B_ C -> B A OR B _C_ -> A C
344 // D E D F G C D E B F G E
345 // F G F G
346 // E (new position) becomes the root
347 // B (position) takes ownership of F as its left child
348 // A takes ownership of G as its right child
349 // OR
350 // D (new position) becomes the root
351 // A (position) takes ownership of F as its right child
352 // C takes ownership of G as its left child
353
354 // Capture new root (either E or D depending on dir)
355 Node* new_root = position->children[dir]->children[1 - dir];
356 // Set weight factor for B or C based on F or G existing and being a different than dir
357 position->children[dir]->weight = third != uint_least8_t(kNeither) && third != dir ? dir : uint_least8_t(kNeither);
358
359 // Detach new root from its tree (replace with new roots child)
360 position->children[dir]->children[1 - dir] =
361 new_root->children[dir];
362 // Attach current left tree to new root
363 new_root->children[dir] = position->children[dir];
364 // Set weight factor for A based on F or G
365 position->weight = third != uint_least8_t(kNeither) && third == dir ? 1 - dir : uint_least8_t(kNeither);
366
367 // Move new root's right tree to current roots left tree
368 position->children[dir] = new_root->children[1 - dir];
369 // Attach current root to new roots right tree
370 new_root->children[1 - dir] = position;
371 // Replace current position with new root
372 position = new_root;
373 // Clear weight factor for new current position
374 position->weight = uint_least8_t(kNeither);
375 }
376
377 //*************************************************************************
380 //*************************************************************************
381 Node* find_limit_node(Node* position, const int8_t dir) const
382 {
383 // Something at this position and in the direction specified? keep going
384 Node* limit_node = position;
385 while (limit_node && limit_node->children[dir])
386 {
387 limit_node = limit_node->children[dir];
388 }
389
390 // Return the limit node position found
391 return limit_node;
392 }
393
394 //*************************************************************************
397 //*************************************************************************
398 const Node* find_limit_node(const Node* position, const int8_t dir) const
399 {
400 // Something at this position and in the direction specified? keep going
401 const Node* limit_node = position;
402 while (limit_node && limit_node->children[dir])
403 {
404 limit_node = limit_node->children[dir];
405 }
406
407 // Return the limit node position found
408 return limit_node;
409 }
410
411 //*************************************************************************
413 //*************************************************************************
414 void attach_node(Node*& position, Node& node)
415 {
416 // Mark new node as leaf on attach to tree at position provided
417 node.mark_as_leaf();
418
419 // Add the node here
420 position = &node;
421
422 // One more.
423 ++current_size;
424 }
425
426 //*************************************************************************
428 //*************************************************************************
429 void detach_node(Node*& position, Node*& replacement)
430 {
431 // Make temporary copy of actual nodes involved because we might lose
432 // their references in the process (e.g. position is the same as
433 // replacement or replacement is a child of position)
434 Node* detached = position;
436
437 // Update current position to point to swap (replacement) node first
438 position = swap;
439
440 // Update replacement node to point to child in opposite direction
441 // otherwise we might lose the other child of the swap node
442 replacement = swap->children[1 - swap->dir];
443
444 // Point swap node to detached node's children and weight
445 swap->children[kLeft] = detached->children[kLeft];
446 swap->children[kRight] = detached->children[kRight];
447 swap->weight = detached->weight;
448 }
449
453 ETL_DECLARE_DEBUG_COUNT;
454 };
455
456 //***************************************************************************
459 //***************************************************************************
460 template <typename TKey, typename TMapped, typename TKeyCompare = etl::less<TKey> >
461 class imap : public etl::map_base
462 {
463 public:
464
465 typedef TKey key_type;
466 typedef ETL_OR_STD::pair<const TKey, TMapped> value_type;
467 typedef TMapped mapped_type;
468 typedef TKeyCompare key_compare;
469 typedef value_type& reference;
470 typedef const value_type& const_reference;
471#if ETL_USING_CPP11
472 typedef value_type&& rvalue_reference;
473#endif
474 typedef value_type* pointer;
475 typedef const value_type* const_pointer;
476 typedef size_t size_type;
477
480#if ETL_USING_CPP11
482#endif
484 typedef const mapped_type& const_mapped_reference;
485
487 {
488 public:
489
490 bool operator()(const_reference lhs, const_reference rhs) const
491 {
492 return (kcompare(lhs.first, rhs.first));
493 }
494
495 private:
496
497 key_compare kcompare;
498 };
499
500 protected:
501
502 //*************************************************************************
504 //*************************************************************************
505 struct Data_Node : public Node
506 {
507 explicit Data_Node(value_type value_)
508 : value(value_)
509 {
510 }
511
512 ~Data_Node()
513 {
514
515 }
516
517 value_type value;
518 };
519
520 //*************************************************************************
522 //*************************************************************************
523 bool node_comp(const Data_Node& node1, const Data_Node& node2) const
524 {
525 return kcompare(node1.value.first, node2.value.first);
526 }
527
528 bool node_comp(const Data_Node& node, const_key_reference key) const
529 {
530 return kcompare(node.value.first, key);
531 }
532
533 bool node_comp(const_key_reference key, const Data_Node& node) const
534 {
535 return kcompare(key, node.value.first);
536 }
537
538#if ETL_USING_CPP11
539 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
540 bool node_comp(const Data_Node& node, const K& key) const
541 {
542 return kcompare(node.value.first, key);
543 }
544
545 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
546 bool node_comp(const K& key, const Data_Node& node) const
547 {
548 return kcompare(key, node.value.first);
549 }
550#endif
551
552 private:
553
555 ipool* p_node_pool;
556
557 key_compare kcompare;
558 value_compare vcompare;
559
560 //*************************************************************************
562 //*************************************************************************
563 static Data_Node* data_cast(Node* p_node)
564 {
565 return static_cast<Data_Node*>(p_node);
566 }
567
568 //*************************************************************************
570 //*************************************************************************
571 static Data_Node& data_cast(Node& node)
572 {
573 return static_cast<Data_Node&>(node);
574 }
575
576 //*************************************************************************
578 //*************************************************************************
579 static const Data_Node* data_cast(const Node* p_node)
580 {
581 return static_cast<const Data_Node*>(p_node);
582 }
583
584 //*************************************************************************
586 //*************************************************************************
587 static const Data_Node& data_cast(const Node& node)
588 {
589 return static_cast<const Data_Node&>(node);
590 }
591
592 public:
593
594 //*************************************************************************
596 //*************************************************************************
597 class iterator : public etl::iterator<ETL_OR_STD::bidirectional_iterator_tag, value_type>
598 {
599 public:
600
601 friend class imap;
602 friend class const_iterator;
603
604 iterator()
605 : p_map(ETL_NULLPTR)
606 , p_node(ETL_NULLPTR)
607 {
608 }
609
611 : p_map(&map)
612 , p_node(ETL_NULLPTR)
613 {
614 }
615
617 : p_map(&map)
618 , p_node(node)
619 {
620 }
621
622 iterator(const iterator& other)
623 : p_map(other.p_map)
624 , p_node(other.p_node)
625 {
626 }
627
628 ~iterator()
629 {
630 }
631
633 {
634 p_map->next_node(p_node);
635 return *this;
636 }
637
639 {
640 iterator temp(*this);
641 p_map->next_node(p_node);
642 return temp;
643 }
644
646 {
647 p_map->prev_node(p_node);
648 return *this;
649 }
650
652 {
653 iterator temp(*this);
654 p_map->prev_node(p_node);
655 return temp;
656 }
657
659 {
660 p_map = other.p_map;
661 p_node = other.p_node;
662 return *this;
663 }
664
665 reference operator *() const
666 {
667 return imap::data_cast(p_node)->value;
668 }
669
670 pointer operator &() const
671 {
672 return &(imap::data_cast(p_node)->value);
673 }
674
675 pointer operator ->() const
676 {
677 return &(imap::data_cast(p_node)->value);
678 }
679
680 friend bool operator == (const iterator& lhs, const iterator& rhs)
681 {
682 return lhs.p_map == rhs.p_map && lhs.p_node == rhs.p_node;
683 }
684
685 friend bool operator != (const iterator& lhs, const iterator& rhs)
686 {
687 return !(lhs == rhs);
688 }
689
690 private:
691
692 // Pointer to map associated with this iterator
693 imap* p_map;
694
695 // Pointer to the current node for this iterator
696 Node* p_node;
697 };
698
699 friend class iterator;
700
701 //*************************************************************************
703 //*************************************************************************
704 class const_iterator : public etl::iterator<ETL_OR_STD::bidirectional_iterator_tag, const value_type>
705 {
706 public:
707
708 friend class imap;
709
711 : p_map(ETL_NULLPTR)
712 , p_node(ETL_NULLPTR)
713 {
714 }
715
716 const_iterator(const imap& map)
717 : p_map(&map)
718 , p_node(ETL_NULLPTR)
719 {
720 }
721
722 const_iterator(const imap& map, const Node* node)
723 : p_map(&map)
724 , p_node(node)
725 {
726 }
727
728 const_iterator(const typename imap::iterator& other)
729 : p_map(other.p_map)
730 , p_node(other.p_node)
731 {
732 }
733
735 : p_map(other.p_map)
736 , p_node(other.p_node)
737 {
738 }
739
741 {
742 }
743
745 {
746 p_map->next_node(p_node);
747 return *this;
748 }
749
751 {
752 const_iterator temp(*this);
753 p_map->next_node(p_node);
754 return temp;
755 }
756
758 {
759 p_map->prev_node(p_node);
760 return *this;
761 }
762
764 {
765 const_iterator temp(*this);
766 p_map->prev_node(p_node);
767 return temp;
768 }
769
771 {
772 p_map = other.p_map;
773 p_node = other.p_node;
774 return *this;
775 }
776
777 const_reference operator *() const
778 {
779 return imap::data_cast(p_node)->value;
780 }
781
782 const_pointer operator &() const
783 {
784 return imap::data_cast(p_node)->value;
785 }
786
787 const_pointer operator ->() const
788 {
789 return &(imap::data_cast(p_node)->value);
790 }
791
792 friend bool operator == (const const_iterator& lhs, const const_iterator& rhs)
793 {
794 return lhs.p_map == rhs.p_map && lhs.p_node == rhs.p_node;
795 }
796
797 friend bool operator != (const const_iterator& lhs, const const_iterator& rhs)
798 {
799 return !(lhs == rhs);
800 }
801
802 private:
803
804 // Convert to an iterator.
805 imap::iterator to_iterator() const
806 {
807 return imap::iterator(const_cast<imap&>(*p_map), const_cast<Node*>(p_node));
808 }
809
810 // Pointer to map associated with this iterator
811 const imap* p_map;
812
813 // Pointer to the current node for this iterator
814 const Node* p_node;
815 };
816
817 friend class const_iterator;
818
819 typedef typename etl::iterator_traits<iterator>::difference_type difference_type;
820
821 typedef ETL_OR_STD::reverse_iterator<iterator> reverse_iterator;
822 typedef ETL_OR_STD::reverse_iterator<const_iterator> const_reverse_iterator;
823
824 //*************************************************************************
826 //*************************************************************************
828 {
829 return iterator(*this, find_limit_node(root_node, kLeft));
830 }
831
832 //*************************************************************************
834 //*************************************************************************
836 {
837 return const_iterator(*this, find_limit_node(root_node, kLeft));
838 }
839
840 //*************************************************************************
842 //*************************************************************************
844 {
845 return iterator(*this);
846 }
847
848 //*************************************************************************
850 //*************************************************************************
852 {
853 return const_iterator(*this);
854 }
855
856 //*************************************************************************
858 //*************************************************************************
860 {
861 return const_iterator(*this, find_limit_node(root_node, kLeft));
862 }
863
864 //*************************************************************************
866 //*************************************************************************
868 {
869 return const_iterator(*this);
870 }
871
872 //*************************************************************************
874 //*************************************************************************
875 reverse_iterator rbegin()
876 {
877 return reverse_iterator(iterator(*this));
878 }
879
880 //*************************************************************************
882 //*************************************************************************
883 const_reverse_iterator rbegin() const
884 {
885 return const_reverse_iterator(const_iterator(*this));
886 }
887
888 //*************************************************************************
890 //*************************************************************************
891 reverse_iterator rend()
892 {
893 return reverse_iterator(iterator(*this, find_limit_node(root_node, kLeft)));
894 }
895
896 //*************************************************************************
898 //*************************************************************************
899 const_reverse_iterator rend() const
900 {
901 return const_reverse_iterator(iterator(*this, find_limit_node(root_node, kLeft)));
902 }
903
904 //*************************************************************************
906 //*************************************************************************
907 const_reverse_iterator crbegin() const
908 {
909 return const_reverse_iterator(const_iterator(*this));
910 }
911
912 //*************************************************************************
914 //*************************************************************************
915 const_reverse_iterator crend() const
916 {
917 return const_reverse_iterator(const_iterator(*this, find_limit_node(root_node, kLeft)));
918 }
919
920#if ETL_USING_CPP11
921 //*********************************************************************
925 //*********************************************************************
926 mapped_reference operator [](rvalue_key_reference key)
927 {
928 iterator i_element = find(etl::move(key));
929
930 if (!i_element.p_node)
931 {
932 // Default to no inserted node
933 Node* inserted_node = ETL_NULLPTR;
934
935 ETL_ASSERT(!full(), ETL_ERROR(map_full));
936
937 // Get next available free node
938 Data_Node& node = allocate_data_node_with_key(etl::move(key));
939
940 // Obtain the inserted node (might be ETL_NULLPTR if node was a duplicate)
941 inserted_node = insert_node(root_node, node);
942
943 // Insert node into tree and return iterator to new node location in tree
945 }
946
947 return i_element->second;
948 }
949#endif
950
951 //*********************************************************************
955 //*********************************************************************
957 {
958 iterator i_element = find(key);
959
960 if (!i_element.p_node)
961 {
962 // Default to no inserted node
963 Node* inserted_node = ETL_NULLPTR;
964
965 ETL_ASSERT(!full(), ETL_ERROR(map_full));
966
967 // Get next available free node
968 Data_Node& node = allocate_data_node_with_key(key);
969
970 // Obtain the inserted node (might be ETL_NULLPTR if node was a duplicate)
971 inserted_node = insert_node(root_node, node);
972
973 // Insert node into tree and return iterator to new node location in tree
975 }
976
977 return i_element->second;
978 }
979
980 //*********************************************************************
985 //*********************************************************************
987 {
988 iterator i_element = find(key);
989
990 ETL_ASSERT(i_element.p_node != ETL_NULLPTR, ETL_ERROR(map_out_of_bounds));
991
992 return i_element->second;
993 }
994
995#if ETL_USING_CPP11
996 //*********************************************************************
998 mapped_reference at(const K& key)
999 {
1000 iterator i_element = find(key);
1001
1002 ETL_ASSERT(i_element.p_node != ETL_NULLPTR, ETL_ERROR(map_out_of_bounds));
1003
1004 return i_element->second;
1005 }
1006#endif
1007
1008 //*********************************************************************
1013 //*********************************************************************
1015 {
1017
1018 ETL_ASSERT(i_element.p_node != ETL_NULLPTR, ETL_ERROR(map_out_of_bounds));
1019
1020 return i_element->second;
1021 }
1022
1023#if ETL_USING_CPP11
1024 //*********************************************************************
1026 const_mapped_reference at(const K& key) const
1027 {
1028 const_iterator i_element = find(key);
1029
1030 ETL_ASSERT(i_element.p_node != ETL_NULLPTR, ETL_ERROR(map_out_of_bounds));
1031
1032 return i_element->second;
1033 }
1034#endif
1035
1036 //*********************************************************************
1042 //*********************************************************************
1043 template <typename TIterator>
1044 void assign(TIterator first, TIterator last)
1045 {
1046 initialise();
1047 insert(first, last);
1048 }
1049
1050 //*************************************************************************
1052 //*************************************************************************
1053 void clear()
1054 {
1055 initialise();
1056 }
1057
1058 //*********************************************************************
1062 //*********************************************************************
1064 {
1065 return find_node(root_node, key) ? 1 : 0;
1066 }
1067
1068#if ETL_USING_CPP11
1069 //*********************************************************************
1071 size_type count(const K& key) const
1072 {
1073 return find_node(root_node, key) ? 1 : 0;
1074 }
1075#endif
1076
1077 //*************************************************************************
1080 //*************************************************************************
1081 ETL_OR_STD::pair<iterator, iterator> equal_range(const_key_reference key)
1082 {
1083 return ETL_OR_STD::make_pair<iterator, iterator>(iterator(*this, find_lower_node(root_node, key)),
1084 iterator(*this, find_upper_node(root_node, key)));
1085 }
1086
1087#if ETL_USING_CPP11
1088 //*************************************************************************
1090 ETL_OR_STD::pair<iterator, iterator> equal_range(const K& key)
1091 {
1092 return ETL_OR_STD::make_pair<iterator, iterator>(iterator(*this, find_lower_node(root_node, key)),
1093 iterator(*this, find_upper_node(root_node, key)));
1094 }
1095#endif
1096
1097 //*************************************************************************
1100 //*************************************************************************
1101 ETL_OR_STD::pair<const_iterator, const_iterator> equal_range(const_key_reference key) const
1102 {
1103 return ETL_OR_STD::make_pair<const_iterator, const_iterator>(const_iterator(*this, find_lower_node(root_node, key)),
1104 const_iterator(*this, find_upper_node(root_node, key)));
1105 }
1106
1107#if ETL_USING_CPP11
1108 //*************************************************************************
1110 ETL_OR_STD::pair<const_iterator, const_iterator> equal_range(const K& key) const
1111 {
1112 return ETL_OR_STD::make_pair<const_iterator, const_iterator>(const_iterator(*this, find_lower_node(root_node, key)),
1113 const_iterator(*this, find_upper_node(root_node, key)));
1114 }
1115#endif
1116
1117 //*************************************************************************
1119 //*************************************************************************
1121 {
1122 // Find the parent node to be removed
1123 Node*& reference_node = find_node(root_node, position.p_node);
1124 iterator next(*this, reference_node);
1125 ++next;
1126
1127 remove_node(root_node, (*position).first);
1128
1129 return next;
1130 }
1131
1132 //*************************************************************************
1133 // Erase the key specified.
1134 //*************************************************************************
1135 size_type erase(const_key_reference key)
1136 {
1137 // Return 1 if key value was found and removed
1138 return remove_node(root_node, key) ? 1 : 0;
1139 }
1140
1141 //*********************************************************************
1142#if ETL_USING_CPP11
1143 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
1144 size_type erase(K&& key)
1145 {
1146 // Return 1 if key value was found and removed
1147 return remove_node(root_node, etl::forward<K>(key)) ? 1 : 0;
1148 }
1149#endif
1150
1151 //*************************************************************************
1153 //*************************************************************************
1155 {
1156 while (first != last)
1157 {
1158 first = erase(first);
1159 }
1160
1161 return last.to_iterator();
1162 }
1163
1164 //*********************************************************************
1168 //*********************************************************************
1170 {
1171 return iterator(*this, find_node(root_node, key));
1172 }
1173
1174#if ETL_USING_CPP11
1175 //*********************************************************************
1177 iterator find(const K& k)
1178 {
1179 return iterator(*this, find_node(root_node, k));
1180 }
1181#endif
1182
1183 //*********************************************************************
1187 //*********************************************************************
1189 {
1190 return const_iterator(*this, find_node(root_node, key));
1191 }
1192
1193#if ETL_USING_CPP11
1194 //*********************************************************************
1196 const_iterator find(const K& k) const
1197 {
1198 return const_iterator(*this, find_node(root_node, k));
1199 }
1200#endif
1201
1202 //*********************************************************************
1206 //*********************************************************************
1207 ETL_OR_STD::pair<iterator, bool> insert(const_reference value)
1208 {
1209 // Default to no inserted node
1210 Node* inserted_node = ETL_NULLPTR;
1211 bool inserted = false;
1212
1213 ETL_ASSERT(!full(), ETL_ERROR(map_full));
1214
1215 // Get next available free node
1216 Data_Node& node = allocate_data_node(value);
1217
1218 // Obtain the inserted node (might be ETL_NULLPTR if node was a duplicate)
1219 inserted_node = insert_node(root_node, node);
1221
1222 // Insert node into tree and return iterator to new node location in tree
1223 return ETL_OR_STD::make_pair(iterator(*this, inserted_node), inserted);
1224 }
1225
1226#if ETL_USING_CPP11
1227 //*********************************************************************
1231 //*********************************************************************
1232 ETL_OR_STD::pair<iterator, bool> insert(rvalue_reference value)
1233 {
1234 // Default to no inserted node
1235 Node* inserted_node = ETL_NULLPTR;
1236 bool inserted = false;
1237
1238 ETL_ASSERT(!full(), ETL_ERROR(map_full));
1239
1240 // Get next available free node
1241 Data_Node& node = allocate_data_node(etl::move(value));
1242
1243 // Obtain the inserted node (might be ETL_NULLPTR if node was a duplicate)
1244 inserted_node = insert_node(root_node, node);
1246
1247 // Insert node into tree and return iterator to new node location in tree
1248 return ETL_OR_STD::make_pair(iterator(*this, inserted_node), inserted);
1249 }
1250#endif
1251
1252 //*********************************************************************
1257 //*********************************************************************
1258 iterator insert(const_iterator /*position*/, const_reference value)
1259 {
1260 // Default to no inserted node
1261 Node* inserted_node = ETL_NULLPTR;
1262
1263 ETL_ASSERT(!full(), ETL_ERROR(map_full));
1264
1265 // Get next available free node
1266 Data_Node& node = allocate_data_node(value);
1267
1268 // Obtain the inserted node (might be ETL_NULLPTR if node was a duplicate)
1269 inserted_node = insert_node(root_node, node);
1270
1271 // Insert node into tree and return iterator to new node location in tree
1272 return iterator(*this, inserted_node);
1273 }
1274
1275#if ETL_USING_CPP11
1276 //*********************************************************************
1281 //*********************************************************************
1282 iterator insert(const_iterator /*position*/, rvalue_reference value)
1283 {
1284 // Default to no inserted node
1285 Node* inserted_node = ETL_NULLPTR;
1286
1287 ETL_ASSERT(!full(), ETL_ERROR(map_full));
1288
1289 // Get next available free node
1290 Data_Node& node = allocate_data_node(etl::move(value));
1291
1292 // Obtain the inserted node (might be ETL_NULLPTR if node was a duplicate)
1293 inserted_node = insert_node(root_node, node);
1294
1295 // Insert node into tree and return iterator to new node location in tree
1296 return iterator(*this, inserted_node);
1297 }
1298#endif
1299
1300 //*********************************************************************
1306 //*********************************************************************
1307 template <class TIterator>
1308 void insert(TIterator first, TIterator last)
1309 {
1310 while (first != last)
1311 {
1312 insert(*first);
1313 ++first;
1314 }
1315 }
1316
1317 //*********************************************************************
1322 //*********************************************************************
1324 {
1325 return iterator(*this, find_lower_node(root_node, key));
1326 }
1327
1328#if ETL_USING_CPP11
1329 //*********************************************************************
1331 iterator lower_bound(const K& key)
1332 {
1333 return iterator(*this, find_lower_node(root_node, key));
1334 }
1335#endif
1336
1337 //*********************************************************************
1342 //*********************************************************************
1344 {
1345 return const_iterator(*this, find_lower_node(root_node, key));
1346 }
1347
1348#if ETL_USING_CPP11
1349 //*********************************************************************
1351 const_iterator lower_bound(const K& key) const
1352 {
1353 return const_iterator(*this, find_lower_node(root_node, key));
1354 }
1355#endif
1356
1357 //*********************************************************************
1362 //*********************************************************************
1364 {
1365 return iterator(*this, find_upper_node(root_node, key));
1366 }
1367
1368#if ETL_USING_CPP11
1369 //*********************************************************************
1371 iterator upper_bound(const K& key)
1372 {
1373 return iterator(*this, find_upper_node(root_node, key));
1374 }
1375#endif
1376
1377 //*********************************************************************
1382 //*********************************************************************
1384 {
1385 return const_iterator(*this, find_upper_node(root_node, key));
1386 }
1387
1388#if ETL_USING_CPP11
1389 //*********************************************************************
1391 const_iterator upper_bound(const K& key) const
1392 {
1393 return const_iterator(*this, find_upper_node(root_node, key));
1394 }
1395#endif
1396
1397 //*************************************************************************
1399 //*************************************************************************
1401 {
1402 // Skip if doing self assignment
1403 if (this != &rhs)
1404 {
1405 assign(rhs.cbegin(), rhs.cend());
1406 }
1407
1408 return *this;
1409 }
1410
1411#if ETL_USING_CPP11
1412 //*************************************************************************
1414 //*************************************************************************
1416 {
1417 // Skip if doing self assignment
1418 if (this != &rhs)
1419 {
1420 this->clear();
1421
1423
1424 while (from != rhs.end())
1425 {
1426 this->insert(etl::move(*from));
1427 ++from;
1428 }
1429 }
1430
1431 return *this;
1432 }
1433#endif
1434
1435 //*************************************************************************
1437 //*************************************************************************
1439 {
1440 return kcompare;
1441 }
1442
1443 //*************************************************************************
1445 //*************************************************************************
1447 {
1448 return vcompare;
1449 }
1450
1451 //*************************************************************************
1453 //*************************************************************************
1454 bool contains(const TKey& key) const
1455 {
1456 return find(key) != end();
1457 }
1458
1459#if ETL_USING_CPP11
1460 //*************************************************************************
1462 bool contains(const K& k) const
1463 {
1464 return find(k) != end();
1465 }
1466#endif
1467
1468 protected:
1469
1470 //*************************************************************************
1472 //*************************************************************************
1473 imap(etl::ipool& node_pool, size_t max_size_)
1475 , p_node_pool(&node_pool)
1476 {
1477 }
1478
1479 //*************************************************************************
1481 //*************************************************************************
1483 {
1485
1486 while (item != end())
1487 {
1488 item = erase(item);
1489 }
1490 }
1491
1492 private:
1493
1494 //*************************************************************************
1496 //*************************************************************************
1497 Data_Node& allocate_data_node(const_reference value)
1498 {
1499 Data_Node* node = allocate_data_node();
1500 ::new (&node->value) value_type(value);
1501 ETL_INCREMENT_DEBUG_COUNT;
1502 return *node;
1503 }
1504
1505 //*************************************************************************
1507 //*************************************************************************
1508 Data_Node& allocate_data_node_with_key(const_key_reference key)
1509 {
1510 Data_Node* node = allocate_data_node();
1511
1512 ::new ((void*)etl::addressof(node->value.first)) key_type(key);
1513 ::new ((void*)etl::addressof(node->value.second)) mapped_type();
1514 ETL_INCREMENT_DEBUG_COUNT;
1515 return *node;
1516 }
1517
1518#if ETL_USING_CPP11
1519 //*************************************************************************
1521 //*************************************************************************
1522 Data_Node& allocate_data_node(rvalue_reference value)
1523 {
1524 Data_Node* node = allocate_data_node();
1525 ::new (&node->value) value_type(etl::move(value));
1526 ETL_INCREMENT_DEBUG_COUNT;
1527 return *node;
1528 }
1529
1530 //*************************************************************************
1532 //*************************************************************************
1533 Data_Node& allocate_data_node_with_key(rvalue_key_reference key)
1534 {
1535 Data_Node* node = allocate_data_node();
1536
1537 ::new ((void*)etl::addressof(node->value.first)) key_type(etl::move(key));
1538 ::new ((void*)etl::addressof(node->value.second)) mapped_type();
1539 ETL_INCREMENT_DEBUG_COUNT;
1540 return *node;
1541 }
1542
1543#endif
1544
1545 //*************************************************************************
1547 //*************************************************************************
1548 Data_Node* allocate_data_node()
1549 {
1550 Data_Node* (etl::ipool::*func)() = &etl::ipool::allocate<Data_Node>;
1551 return (p_node_pool->*func)();
1552 }
1553
1554 //*************************************************************************
1556 //*************************************************************************
1557 void destroy_data_node(Data_Node& node)
1558 {
1559 node.value.~value_type();
1560 p_node_pool->release(&node);
1561 ETL_DECREMENT_DEBUG_COUNT;
1562 }
1563
1564 //*************************************************************************
1566 //*************************************************************************
1567 Node* find_node(Node* position, const_key_reference key)
1568 {
1569 Node* found = position;
1570 while (found)
1571 {
1572 // Downcast found to Data_Node class for comparison and other operations
1573 Data_Node& found_data_node = imap::data_cast(*found);
1574
1575 // Compare the node value to the current position value
1576 if (node_comp(key, found_data_node))
1577 {
1578 // Keep searching for the node on the left
1579 found = found->children[kLeft];
1580 }
1581 else if (node_comp(found_data_node, key))
1582 {
1583 // Keep searching for the node on the right
1584 found = found->children[kRight];
1585 }
1586 else
1587 {
1588 // Node that matches the key provided was found, exit loop
1589 break;
1590 }
1591 }
1592
1593 // Return the node found (might be ETL_NULLPTR)
1594 return found;
1595 }
1596
1597#if ETL_USING_CPP11
1598 //*********************************************************************
1599 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
1600 Node* find_node(Node* position, const K& key)
1601 {
1602 Node* found = position;
1603 while (found)
1604 {
1605 // Downcast found to Data_Node class for comparison and other operations
1606 Data_Node& found_data_node = imap::data_cast(*found);
1607
1608 // Compare the node value to the current position value
1609 if (node_comp(key, found_data_node))
1610 {
1611 // Keep searching for the node on the left
1612 found = found->children[kLeft];
1613 }
1614 else if (node_comp(found_data_node, key))
1615 {
1616 // Keep searching for the node on the right
1617 found = found->children[kRight];
1618 }
1619 else
1620 {
1621 // Node that matches the key provided was found, exit loop
1622 break;
1623 }
1624 }
1625
1626 // Return the node found (might be ETL_NULLPTR)
1627 return found;
1628 }
1629#endif
1630
1631 //*************************************************************************
1633 //*************************************************************************
1634 const Node* find_node(const Node* position, const_key_reference key) const
1635 {
1636 const Node* found = position;
1637 while (found)
1638 {
1639 // Downcast found to Data_Node class for comparison and other operations
1640 const Data_Node& found_data_node = imap::data_cast(*found);
1641
1642 // Compare the node value to the current position value
1643 if (node_comp(key, found_data_node))
1644 {
1645 // Keep searching for the node on the left
1646 found = found->children[kLeft];
1647 }
1648 else if (node_comp(found_data_node, key))
1649 {
1650 // Keep searching for the node on the right
1651 found = found->children[kRight];
1652 }
1653 else
1654 {
1655 // Node that matches the key provided was found, exit loop
1656 break;
1657 }
1658 }
1659
1660 // Return the node found (might be ETL_NULLPTR)
1661 return found;
1662 }
1663
1664#if ETL_USING_CPP11
1665 //*********************************************************************
1666 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
1667 const Node* find_node(const Node* position, const K& key) const
1668 {
1669 const Node* found = position;
1670 while (found)
1671 {
1672 // Downcast found to Data_Node class for comparison and other operations
1673 const Data_Node& found_data_node = imap::data_cast(*found);
1674
1675 // Compare the node value to the current position value
1676 if (node_comp(key, found_data_node))
1677 {
1678 // Keep searching for the node on the left
1679 found = found->children[kLeft];
1680 }
1681 else if (node_comp(found_data_node, key))
1682 {
1683 // Keep searching for the node on the right
1684 found = found->children[kRight];
1685 }
1686 else
1687 {
1688 // Node that matches the key provided was found, exit loop
1689 break;
1690 }
1691 }
1692
1693 // Return the node found (might be ETL_NULLPTR)
1694 return found;
1695 }
1696#endif
1697
1698 //*************************************************************************
1700 //*************************************************************************
1701 Node*& find_node(Node*& position, const Node* node)
1702 {
1703 Node* found = position;
1704 while (found)
1705 {
1706 if (found->children[kLeft] == node)
1707 {
1708 return found->children[kLeft];
1709 }
1710 else if (found->children[kRight] == node)
1711 {
1712 return found->children[kRight];
1713 }
1714 else
1715 {
1716 // Downcast found to Data_Node class for comparison and other operations
1717 Data_Node& found_data_node = imap::data_cast(*found);
1718 const Data_Node& data_node = imap::data_cast(*node);
1719
1720 // Compare the node value to the current position value
1721 if (node_comp(data_node, found_data_node))
1722 {
1723 // Keep searching for the node on the left
1724 found = found->children[kLeft];
1725 }
1726 else if (node_comp(found_data_node, data_node))
1727 {
1728 // Keep searching for the node on the right
1729 found = found->children[kRight];
1730 }
1731 else
1732 {
1733 // Return position provided (it matches the node)
1734 return position;
1735 }
1736 }
1737 }
1738
1739 // Return root node if nothing was found
1740 return root_node;
1741 }
1742
1743 //*************************************************************************
1746 //*************************************************************************
1747 Node* find_parent_node(Node* position, const Node* node)
1748 {
1749 // Default to no parent node found
1750 Node* found = ETL_NULLPTR;
1751
1752 // If the position provided is the same as the node then there is no parent
1753 if (position && node && position != node)
1754 {
1755 while (position)
1756 {
1757 // Is this position not the parent of the node we are looking for?
1758 if (position->children[kLeft] != node &&
1759 position->children[kRight] != node)
1760 {
1761 // Downcast node and position to Data_Node references for key comparisons
1762 const Data_Node& node_data_node = imap::data_cast(*node);
1763 Data_Node& position_data_node = imap::data_cast(*position);
1764 // Compare the node value to the current position value
1765 if (node_comp(node_data_node, position_data_node))
1766 {
1767 // Keep looking for parent on the left
1768 position = position->children[kLeft];
1769 }
1770 else if (node_comp(position_data_node, node_data_node))
1771 {
1772 // Keep looking for parent on the right
1773 position = position->children[kRight];
1774 }
1775 }
1776 else
1777 {
1778 // Return the current position as the parent node found
1779 found = position;
1780
1781 // Parent node found, exit loop
1782 break;
1783 }
1784 }
1785 }
1786
1787 // Return the parent node found (might be ETL_NULLPTR)
1788 return found;
1789 }
1790
1791 //*************************************************************************
1794 //*************************************************************************
1795 const Node* find_parent_node(const Node* position, const Node* node) const
1796 {
1797 // Default to no parent node found
1798 const Node* found = ETL_NULLPTR;
1799
1800 // If the position provided is the same as the node then there is no parent
1801 if (position && node && position != node)
1802 {
1803 while (position)
1804 {
1805 // Is this position not the parent of the node we are looking for?
1806 if (position->children[kLeft] != node &&
1807 position->children[kRight] != node)
1808 {
1809 // Downcast node and position to Data_Node references for key comparisons
1810 const Data_Node& node_data_node = imap::data_cast(*node);
1811 const Data_Node& position_data_node = imap::data_cast(*position);
1812 // Compare the node value to the current position value
1813 if (node_comp(node_data_node, position_data_node))
1814 {
1815 // Keep looking for parent on the left
1816 position = position->children[kLeft];
1817 }
1818 else if (node_comp(position_data_node, node_data_node))
1819 {
1820 // Keep looking for parent on the right
1821 position = position->children[kRight];
1822 }
1823 }
1824 else
1825 {
1826 // Return the current position as the parent node found
1827 found = position;
1828
1829 // Parent node found, exit loop
1830 break;
1831 }
1832 }
1833 }
1834
1835 // Return the parent node found (might be ETL_NULLPTR)
1836 return found;
1837 }
1838
1839 //*************************************************************************
1841 //*************************************************************************
1842 Node* find_lower_node(Node* position, const_key_reference key) const
1843 {
1844 // Something at this position? keep going
1845 Node* lower_node = ETL_NULLPTR;
1846 while (position)
1847 {
1848 // Downcast lower node to Data_Node reference for key comparisons
1849 Data_Node& data_node = imap::data_cast(*position);
1850 // Compare the key value to the current lower node key value
1851 if (node_comp(key, data_node))
1852 {
1853 lower_node = position;
1854 if (position->children[kLeft])
1855 {
1856 position = position->children[kLeft];
1857 }
1858 else
1859 {
1860 // Found lowest node
1861 break;
1862 }
1863 }
1864 else if (node_comp(data_node, key))
1865 {
1866 position = position->children[kRight];
1867 }
1868 else
1869 {
1870 // Make note of current position, but keep looking to left for more
1871 lower_node = position;
1872 position = position->children[kLeft];
1873 }
1874 }
1875
1876 // Return the lower_node position found
1877 return lower_node;
1878 }
1879
1880#if ETL_USING_CPP11
1881 //*************************************************************************
1882 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
1883 Node* find_lower_node(Node* position, const K& key) const
1884 {
1885 // Something at this position? keep going
1886 Node* lower_node = ETL_NULLPTR;
1887 while (position)
1888 {
1889 // Downcast lower node to Data_Node reference for key comparisons
1890 Data_Node& data_node = imap::data_cast(*position);
1891 // Compare the key value to the current lower node key value
1892 if (node_comp(key, data_node))
1893 {
1894 lower_node = position;
1895 if (position->children[kLeft])
1896 {
1897 position = position->children[kLeft];
1898 }
1899 else
1900 {
1901 // Found lowest node
1902 break;
1903 }
1904 }
1905 else if (node_comp(data_node, key))
1906 {
1907 position = position->children[kRight];
1908 }
1909 else
1910 {
1911 // Make note of current position, but keep looking to left for more
1912 lower_node = position;
1913 position = position->children[kLeft];
1914 }
1915 }
1916
1917 // Return the lower_node position found
1918 return lower_node;
1919 }
1920#endif
1921
1922 //*************************************************************************
1924 //*************************************************************************
1925 Node* find_upper_node(Node* position, const_key_reference key) const
1926 {
1927 // Keep track of parent of last upper node
1928 Node* upper_node = ETL_NULLPTR;
1929 // Start with position provided
1930 Node* node = position;
1931 while (node)
1932 {
1933 // Downcast position to Data_Node reference for key comparisons
1934 Data_Node& data_node = imap::data_cast(*node);
1935 // Compare the key value to the current upper node key value
1936 if (node_comp(key, data_node))
1937 {
1938 upper_node = node;
1939 node = node->children[kLeft];
1940 }
1941 else if (node_comp(data_node, key))
1942 {
1943 node = node->children[kRight];
1944 }
1945 else if (node->children[kRight])
1946 {
1947 upper_node = find_limit_node(node->children[kRight], kLeft);
1948 break;
1949 }
1950 else
1951 {
1952 break;
1953 }
1954 }
1955
1956 // Return the upper node position found (might be ETL_NULLPTR)
1957 return upper_node;
1958 }
1959
1960#if ETL_USING_CPP11
1961 //*************************************************************************
1962 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
1963 Node* find_upper_node(Node* position, const K& key) const
1964 {
1965 // Keep track of parent of last upper node
1966 Node* upper_node = ETL_NULLPTR;
1967 // Start with position provided
1968 Node* node = position;
1969 while (node)
1970 {
1971 // Downcast position to Data_Node reference for key comparisons
1972 Data_Node& data_node = imap::data_cast(*node);
1973 // Compare the key value to the current upper node key value
1974 if (node_comp(key, data_node))
1975 {
1976 upper_node = node;
1977 node = node->children[kLeft];
1978 }
1979 else if (node_comp(data_node, key))
1980 {
1981 node = node->children[kRight];
1982 }
1983 else if (node->children[kRight])
1984 {
1985 upper_node = find_limit_node(node->children[kRight], kLeft);
1986 break;
1987 }
1988 else
1989 {
1990 break;
1991 }
1992 }
1993
1994 // Return the upper node position found (might be ETL_NULLPTR)
1995 return upper_node;
1996 }
1997#endif
1998
1999 //*************************************************************************
2001 //*************************************************************************
2002 Node* insert_node(Node*& position, Data_Node& node)
2003 {
2004 // Find the location where the node belongs
2005 Node* found = position;
2006
2007 // Was position provided not empty? then find where the node belongs
2008 if (position)
2009 {
2010 // Find the critical parent node (default to ETL_NULLPTR)
2011 Node* critical_parent_node = ETL_NULLPTR;
2012 Node* critical_node = root_node;
2013
2014 while (found)
2015 {
2016 // Search for critical weight node (all nodes whose weight factor
2017 // is set to kNeither (balanced)
2018 if (kNeither != found->weight)
2019 {
2020 critical_node = found;
2021 }
2022
2023 // Downcast found to Data_Node class for comparison and other operations
2024 Data_Node& found_data_node = imap::data_cast(*found);
2025
2026 // Is the node provided to the left of the current position?
2027 if (node_comp(node, found_data_node))
2028 {
2029 // Update direction taken to insert new node in parent node
2030 found->dir = kLeft;
2031 }
2032 // Is the node provided to the right of the current position?
2033 else if (node_comp(found_data_node, node))
2034 {
2035 // Update direction taken to insert new node in parent node
2036 found->dir = kRight;
2037 }
2038 else
2039 {
2040 // Update direction taken to insert new node in parent node
2041 found->dir = kNeither;
2042
2043 // Clear critical node value to skip weight step below
2044 critical_node = ETL_NULLPTR;
2045
2046 // Destroy the node provided (its a duplicate)
2047 destroy_data_node(node);
2048
2049 // Exit loop, duplicate node found
2050 break;
2051 }
2052
2053 // Is there a child of this parent node?
2054 if (found->children[found->dir])
2055 {
2056 // Will this node be the parent of the next critical node whose
2057 // weight factor is set to kNeither (balanced)?
2058 if (kNeither != found->children[found->dir]->weight)
2059 {
2060 critical_parent_node = found;
2061 }
2062
2063 // Keep looking for empty spot to insert new node
2064 found = found->children[found->dir];
2065 }
2066 else
2067 {
2068 // Attach node to right
2069 attach_node(found->children[found->dir], node);
2070
2071 // Return newly added node
2072 found = found->children[found->dir];
2073
2074 // Exit loop
2075 break;
2076 }
2077 }
2078
2079 // Was a critical node found that should be checked for balance?
2080 if (critical_node)
2081 {
2082 if (critical_parent_node == ETL_NULLPTR && critical_node == root_node)
2083 {
2085 }
2086 else if (critical_parent_node == ETL_NULLPTR && critical_node == position)
2087 {
2088 balance_node(position);
2089 }
2090 else
2091 {
2092 if (critical_parent_node != ETL_NULLPTR)
2093 {
2094 balance_node(critical_parent_node->children[critical_parent_node->dir]);
2095 }
2096 }
2097 }
2098 }
2099 else
2100 {
2101 // Attach node to current position
2102 attach_node(position, node);
2103
2104 // Return newly added node at current position
2105 found = position;
2106 }
2107
2108 // Return the node found (might be ETL_NULLPTR)
2109 return found;
2110 }
2111
2112 //*************************************************************************
2114 //*************************************************************************
2115 void next_node(Node*&position)
2116 {
2117 if (position)
2118 {
2119 // Is there a tree on the right? then find the minimum of that tree
2120 if (position->children[kRight])
2121 {
2122 // Return minimum node found
2123 position = find_limit_node(position->children[kRight], kLeft);
2124 }
2125 // Otherwise find the parent of this node
2126 else
2127 {
2128 // Start with current position as parent
2129 Node* parent = position;
2130 do {
2131 // Update current position as previous parent
2132 position = parent;
2133 // Find parent of current position
2134 parent = find_parent_node(root_node, position);
2135 // Repeat while previous position was on right side of parent tree
2136 } while (parent && parent->children[kRight] == position);
2137
2138 // Set parent node as the next position
2139 position = parent;
2140 }
2141 }
2142 }
2143
2144 //*************************************************************************
2146 //*************************************************************************
2147 void next_node(const Node*& position) const
2148 {
2149 if (position)
2150 {
2151 // Is there a tree on the right? then find the minimum of that tree
2152 if (position->children[kRight])
2153 {
2154 // Return minimum node found
2155 position = find_limit_node(position->children[kRight], kLeft);
2156 }
2157 // Otherwise find the parent of this node
2158 else
2159 {
2160 // Start with current position as parent
2161 const Node* parent = position;
2162 do {
2163 // Update current position as previous parent
2164 position = parent;
2165 // Find parent of current position
2166 parent = find_parent_node(root_node, position);
2167 // Repeat while previous position was on right side of parent tree
2168 } while (parent && parent->children[kRight] == position);
2169
2170 // Set parent node as the next position
2171 position = parent;
2172 }
2173 }
2174 }
2175
2176 //*************************************************************************
2178 //*************************************************************************
2179 void prev_node(Node*&position)
2180 {
2181 // If starting at the terminal end, the previous node is the maximum node
2182 // from the root
2183 if (!position)
2184 {
2185 position = find_limit_node(root_node, kRight);
2186 }
2187 else
2188 {
2189 // Is there a tree on the left? then find the maximum of that tree
2190 if (position->children[kLeft])
2191 {
2192 // Return maximum node found
2193 position = find_limit_node(position->children[kLeft], kRight);
2194 }
2195 // Otherwise find the parent of this node
2196 else
2197 {
2198 // Start with current position as parent
2199 Node* parent = position;
2200 do {
2201 // Update current position as previous parent
2202 position = parent;
2203 // Find parent of current position
2204 parent = find_parent_node(root_node, position);
2205 // Repeat while previous position was on left side of parent tree
2206 } while (parent && parent->children[kLeft] == position);
2207
2208 // Set parent node as the next position
2209 position = parent;
2210 }
2211 }
2212 }
2213
2214 //*************************************************************************
2216 //*************************************************************************
2217 void prev_node(const Node*& position) const
2218 {
2219 // If starting at the terminal end, the previous node is the maximum node
2220 // from the root
2221 if (!position)
2222 {
2223 position = find_limit_node(root_node, kRight);
2224 }
2225 else
2226 {
2227 // Is there a tree on the left? then find the maximum of that tree
2228 if (position->children[kLeft])
2229 {
2230 // Return maximum node found
2231 position = find_limit_node(position->children[kLeft], kRight);
2232 }
2233 // Otherwise find the parent of this node
2234 else
2235 {
2236 // Start with current position as parent
2237 const Node* parent = position;
2238 do {
2239 // Update current position as previous parent
2240 position = parent;
2241 // Find parent of current position
2242 parent = find_parent_node(root_node, position);
2243 // Repeat while previous position was on left side of parent tree
2244 } while (parent && parent->children[kLeft] == position);
2245
2246 // Set parent node as the next position
2247 position = parent;
2248 }
2249 }
2250 }
2251
2252 //*************************************************************************
2255 //*************************************************************************
2256 Node* remove_node(Node*& position, const_key_reference key)
2257 {
2258 // Step 1: Find the target node that matches the key provided, the
2259 // replacement node (might be the same as target node), and the critical
2260 // node to start rebalancing the tree from (up to the replacement node)
2261 Node* found_parent = ETL_NULLPTR;
2262 Node* found = ETL_NULLPTR;
2263 Node* replace_parent = ETL_NULLPTR;
2264 Node* replace = position;
2265 Node* balance_parent = ETL_NULLPTR;
2266 Node* balance = root_node;
2267 while (replace)
2268 {
2269 // Downcast found to Data_Node class for comparison and other operations
2270 Data_Node& replace_data_node = imap::data_cast(*replace);
2271
2272 // Compare the key provided to the replace data node key
2273 if (node_comp(key, replace_data_node))
2274 {
2275 // Update the direction to the target/replace node
2276 replace->dir = kLeft;
2277 }
2278 else if (node_comp(replace_data_node, key))
2279 {
2280 // Update the direction to the target/replace node
2281 replace->dir = kRight;
2282 }
2283 else
2284 {
2285 // Update the direction to the replace node (target node found here)
2286 replace->dir = replace->children[kLeft] ? kLeft : kRight;
2287
2288 // Note the target node was found (and its parent)
2289 found_parent = replace_parent;
2290 found = replace;
2291 }
2292 // Replacement node found if its missing a child in the replace->dir
2293 // value set above
2294 if (replace->children[replace->dir] == ETL_NULLPTR)
2295 {
2296 // Exit loop once replace node is found (target might not have been)
2297 break;
2298 }
2299
2300 // If replacement node weight is kNeither or we are taking the shorter
2301 // path of replacement node and our sibling (on longer path) is
2302 // balanced then we need to update the balance node to match this
2303 // replacement node but all our ancestors will not require rebalancing
2304 if ((replace->weight == kNeither) ||
2305 (replace->weight == (1 - replace->dir) &&
2306 replace->children[1 - replace->dir]->weight == kNeither))
2307 {
2308 // Update balance node (and its parent) to replacement node
2309 balance_parent = replace_parent;
2310 balance = replace;
2311 }
2312
2313 // Keep searching for the replacement node
2314 replace_parent = replace;
2315 replace = replace->children[replace->dir];
2316 }
2317
2318 // If target node was found, proceed with rebalancing and replacement
2319 if (found)
2320 {
2321 // Step 2: Update weights from critical node to replacement parent node
2322 while (balance)
2323 {
2324 if (balance->children[balance->dir] == ETL_NULLPTR)
2325 {
2326 break;
2327 }
2328
2329 if (balance->weight == kNeither)
2330 {
2331 balance->weight = 1 - balance->dir;
2332 }
2333 else if (balance->weight == balance->dir)
2334 {
2335 balance->weight = kNeither;
2336 }
2337 else
2338 {
2339 int weight = balance->children[1 - balance->dir]->weight;
2340 // Perform a 3 node rotation if weight is same as balance->dir
2341 if (weight == balance->dir)
2342 {
2343 // Is the root node being rebalanced (no parent)
2344 if (balance_parent == ETL_NULLPTR)
2345 {
2346 rotate_3node(root_node, 1 - balance->dir,
2347 balance->children[1 - balance->dir]->children[balance->dir]->weight);
2348 }
2349 else
2350 {
2351 rotate_3node(balance_parent->children[balance_parent->dir], 1 - balance->dir,
2352 balance->children[1 - balance->dir]->children[balance->dir]->weight);
2353 }
2354 }
2355 // Already balanced, rebalance and make it heavy in opposite
2356 // direction of the node being removed
2357 else if (weight == kNeither)
2358 {
2359 // Is the root node being rebalanced (no parent)
2360 if (balance_parent == ETL_NULLPTR)
2361 {
2362 rotate_2node(root_node, 1 - balance->dir);
2363 root_node->weight = balance->dir;
2364 }
2365 else
2366 {
2367 rotate_2node(balance_parent->children[balance_parent->dir], 1 - balance->dir);
2368 balance_parent->children[balance_parent->dir]->weight = balance->dir;
2369 }
2370 // Update balance node weight in opposite direction of node removed
2371 balance->weight = 1 - balance->dir;
2372 }
2373 // Rebalance and leave it balanced
2374 else
2375 {
2376 // Is the root node being rebalanced (no parent)
2377 if (balance_parent == ETL_NULLPTR)
2378 {
2379 rotate_2node(root_node, 1 - balance->dir);
2380 }
2381 else
2382 {
2383 rotate_2node(balance_parent->children[balance_parent->dir], 1 - balance->dir);
2384 }
2385 }
2386
2387 // Is balance node the same as the target node found? then update
2388 // its parent after the rotation performed above
2389 if (balance == found)
2390 {
2391 if (balance_parent)
2392 {
2393 found_parent = balance_parent->children[balance_parent->dir];
2394 // Update dir since it is likely stale
2395 found_parent->dir = found_parent->children[kLeft] == found ? kLeft : kRight;
2396 }
2397 else
2398 {
2399 found_parent = root_node;
2400 root_node->dir = root_node->children[kLeft] == found ? kLeft : kRight;
2401 }
2402 }
2403 }
2404
2405 // Next balance node to consider
2406 balance_parent = balance;
2407 balance = balance->children[balance->dir];
2408 } // while(balance)
2409
2410 // Step 3: Swap found node with replacement node
2411 if (found_parent)
2412 {
2413 // Handle traditional case
2414 detach_node(found_parent->children[found_parent->dir],
2415 replace_parent->children[replace_parent->dir]);
2416 }
2417 // Handle root node removal
2418 else
2419 {
2420 // Valid replacement node for root node being removed?
2421 if (replace_parent)
2422 {
2423 detach_node(root_node, replace_parent->children[replace_parent->dir]);
2424 }
2425 else
2426 {
2427 // Target node and replacement node are both root node
2429 }
2430 }
2431
2432 // Downcast found into data node
2433 Data_Node& found_data_node = imap::data_cast(*found);
2434
2435 // One less.
2436 --current_size;
2437
2438 // Destroy the node removed
2439 destroy_data_node(found_data_node);
2440 } // if(found)
2441
2442 // Return node found (might be ETL_NULLPTR)
2443 return found;
2444 }
2445
2446#if ETL_USING_CPP11
2447 //*************************************************************************
2450 //*************************************************************************
2451 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
2452 Node* remove_node(Node*& position, const K& key)
2453 {
2454 // Step 1: Find the target node that matches the key provided, the
2455 // replacement node (might be the same as target node), and the critical
2456 // node to start rebalancing the tree from (up to the replacement node)
2457 Node* found_parent = ETL_NULLPTR;
2458 Node* found = ETL_NULLPTR;
2459 Node* replace_parent = ETL_NULLPTR;
2460 Node* replace = position;
2461 Node* balance_parent = ETL_NULLPTR;
2462 Node* balance = root_node;
2463 while (replace)
2464 {
2465 // Downcast found to Data_Node class for comparison and other operations
2466 Data_Node& replace_data_node = imap::data_cast(*replace);
2467
2468 // Compare the key provided to the replace data node key
2469 if (node_comp(key, replace_data_node))
2470 {
2471 // Update the direction to the target/replace node
2472 replace->dir = kLeft;
2473 }
2474 else if (node_comp(replace_data_node, key))
2475 {
2476 // Update the direction to the target/replace node
2477 replace->dir = kRight;
2478 }
2479 else
2480 {
2481 // Update the direction to the replace node (target node found here)
2482 replace->dir = replace->children[kLeft] ? kLeft : kRight;
2483
2484 // Note the target node was found (and its parent)
2485 found_parent = replace_parent;
2486 found = replace;
2487 }
2488 // Replacement node found if its missing a child in the replace->dir
2489 // value set above
2490 if (replace->children[replace->dir] == ETL_NULLPTR)
2491 {
2492 // Exit loop once replace node is found (target might not have been)
2493 break;
2494 }
2495
2496 // If replacement node weight is kNeither or we are taking the shorter
2497 // path of replacement node and our sibling (on longer path) is
2498 // balanced then we need to update the balance node to match this
2499 // replacement node but all our ancestors will not require rebalancing
2500 if ((replace->weight == kNeither) ||
2501 (replace->weight == (1 - replace->dir) &&
2502 replace->children[1 - replace->dir]->weight == kNeither))
2503 {
2504 // Update balance node (and its parent) to replacement node
2505 balance_parent = replace_parent;
2506 balance = replace;
2507 }
2508
2509 // Keep searching for the replacement node
2510 replace_parent = replace;
2511 replace = replace->children[replace->dir];
2512 }
2513
2514 // If target node was found, proceed with rebalancing and replacement
2515 if (found)
2516 {
2517 // Step 2: Update weights from critical node to replacement parent node
2518 while (balance)
2519 {
2520 if (balance->children[balance->dir] == ETL_NULLPTR)
2521 {
2522 break;
2523 }
2524
2525 if (balance->weight == kNeither)
2526 {
2527 balance->weight = 1 - balance->dir;
2528 }
2529 else if (balance->weight == balance->dir)
2530 {
2531 balance->weight = kNeither;
2532 }
2533 else
2534 {
2535 int weight = balance->children[1 - balance->dir]->weight;
2536 // Perform a 3 node rotation if weight is same as balance->dir
2537 if (weight == balance->dir)
2538 {
2539 // Is the root node being rebalanced (no parent)
2540 if (balance_parent == ETL_NULLPTR)
2541 {
2542 rotate_3node(root_node, 1 - balance->dir,
2543 balance->children[1 - balance->dir]->children[balance->dir]->weight);
2544 }
2545 else
2546 {
2547 rotate_3node(balance_parent->children[balance_parent->dir], 1 - balance->dir,
2548 balance->children[1 - balance->dir]->children[balance->dir]->weight);
2549 }
2550 }
2551 // Already balanced, rebalance and make it heavy in opposite
2552 // direction of the node being removed
2553 else if (weight == kNeither)
2554 {
2555 // Is the root node being rebalanced (no parent)
2556 if (balance_parent == ETL_NULLPTR)
2557 {
2558 rotate_2node(root_node, 1 - balance->dir);
2559 root_node->weight = balance->dir;
2560 }
2561 else
2562 {
2563 rotate_2node(balance_parent->children[balance_parent->dir], 1 - balance->dir);
2564 balance_parent->children[balance_parent->dir]->weight = balance->dir;
2565 }
2566 // Update balance node weight in opposite direction of node removed
2567 balance->weight = 1 - balance->dir;
2568 }
2569 // Rebalance and leave it balanced
2570 else
2571 {
2572 // Is the root node being rebalanced (no parent)
2573 if (balance_parent == ETL_NULLPTR)
2574 {
2575 rotate_2node(root_node, 1 - balance->dir);
2576 }
2577 else
2578 {
2579 rotate_2node(balance_parent->children[balance_parent->dir], 1 - balance->dir);
2580 }
2581 }
2582
2583 // Is balance node the same as the target node found? then update
2584 // its parent after the rotation performed above
2585 if (balance == found)
2586 {
2587 if (balance_parent)
2588 {
2589 found_parent = balance_parent->children[balance_parent->dir];
2590 // Update dir since it is likely stale
2591 found_parent->dir = found_parent->children[kLeft] == found ? kLeft : kRight;
2592 }
2593 else
2594 {
2595 found_parent = root_node;
2596 root_node->dir = root_node->children[kLeft] == found ? kLeft : kRight;
2597 }
2598 }
2599 }
2600
2601 // Next balance node to consider
2602 balance_parent = balance;
2603 balance = balance->children[balance->dir];
2604 } // while(balance)
2605
2606 // Step 3: Swap found node with replacement node
2607 if (found_parent)
2608 {
2609 // Handle traditional case
2610 detach_node(found_parent->children[found_parent->dir],
2611 replace_parent->children[replace_parent->dir]);
2612 }
2613 // Handle root node removal
2614 else
2615 {
2616 // Valid replacement node for root node being removed?
2617 if (replace_parent)
2618 {
2619 detach_node(root_node, replace_parent->children[replace_parent->dir]);
2620 }
2621 else
2622 {
2623 // Target node and replacement node are both root node
2625 }
2626 }
2627
2628 // Downcast found into data node
2629 Data_Node& found_data_node = imap::data_cast(*found);
2630
2631 // One less.
2632 --current_size;
2633
2634 // Destroy the node removed
2635 destroy_data_node(found_data_node);
2636 } // if(found)
2637
2638 // Return node found (might be ETL_NULLPTR)
2639 return found;
2640 }
2641#endif
2642
2643 // Disable copy construction.
2644 imap(const imap&);
2645
2646 //*************************************************************************
2648 //*************************************************************************
2649#if defined(ETL_POLYMORPHIC_MAP) || defined(ETL_POLYMORPHIC_CONTAINERS)
2650 public:
2651 virtual ~imap()
2652 {
2653 }
2654#else
2655 protected:
2657 {
2658 }
2659#endif
2660 };
2661
2662 //*************************************************************************
2664 //*************************************************************************
2665 template <typename TKey, typename TValue, const size_t MAX_SIZE_, typename TCompare = etl::less<TKey> >
2666 class map : public etl::imap<TKey, TValue, TCompare>
2667 {
2668 public:
2669
2670 static ETL_CONSTANT size_t MAX_SIZE = MAX_SIZE_;
2671
2672 //*************************************************************************
2674 //*************************************************************************
2676 : etl::imap<TKey, TValue, TCompare>(node_pool, MAX_SIZE)
2677 {
2678 this->initialise();
2679 }
2680
2681 //*************************************************************************
2683 //*************************************************************************
2684 map(const map& other)
2685 : etl::imap<TKey, TValue, TCompare>(node_pool, MAX_SIZE)
2686 {
2687 if (this != &other)
2688 {
2689 this->assign(other.cbegin(), other.cend());
2690 }
2691 }
2692
2693#if ETL_USING_CPP11
2694 //*************************************************************************
2696 //*************************************************************************
2697 map(map&& other)
2698 : etl::imap<TKey, TValue, TCompare>(node_pool, MAX_SIZE)
2699 {
2700 if (this != &other)
2701 {
2703
2704 while (from != other.end())
2705 {
2707 ++temp;
2708
2709 this->insert(etl::move(*from));
2710 from = temp;
2711 }
2712 }
2713 }
2714#endif
2715
2716 //*************************************************************************
2721 //*************************************************************************
2722 template <typename TIterator>
2724 : etl::imap<TKey, TValue, TCompare>(node_pool, MAX_SIZE)
2725 {
2726 this->assign(first, last);
2727 }
2728
2729#if ETL_HAS_INITIALIZER_LIST
2730 //*************************************************************************
2732 //*************************************************************************
2733 map(std::initializer_list<typename etl::imap<TKey, TValue, TCompare>::value_type> init)
2734 : etl::imap<TKey, TValue, TCompare>(node_pool, MAX_SIZE)
2735 {
2736 this->assign(init.begin(), init.end());
2737 }
2738#endif
2739
2740 //*************************************************************************
2742 //*************************************************************************
2744 {
2745 this->initialise();
2746 }
2747
2748 //*************************************************************************
2750 //*************************************************************************
2752 {
2753 // Skip if doing self assignment
2754 if (this != &rhs)
2755 {
2756 this->assign(rhs.cbegin(), rhs.cend());
2757 }
2758
2759 return *this;
2760 }
2761
2762#if ETL_USING_CPP11
2763 //*************************************************************************
2765 //*************************************************************************
2767 {
2768 // Skip if doing self assignment
2769 if (this != &rhs)
2770 {
2771 this->clear();
2772
2774
2775 while (from != rhs.end())
2776 {
2778 ++temp;
2779
2780 this->insert(etl::move(*from));
2781 from = temp;
2782 }
2783 }
2784
2785 return *this;
2786 }
2787#endif
2788
2789 private:
2790
2793 };
2794
2795 template <typename TKey, typename TValue, const size_t MAX_SIZE_, typename TCompare>
2796 ETL_CONSTANT size_t map<TKey, TValue, MAX_SIZE_, TCompare>::MAX_SIZE;
2797
2798 //*************************************************************************
2800 //*************************************************************************
2801#if ETL_USING_CPP17 && ETL_HAS_INITIALIZER_LIST
2802 template <typename... TPairs>
2803 map(TPairs...) -> map<typename etl::nth_type_t<0, TPairs...>::first_type,
2804 typename etl::nth_type_t<0, TPairs...>::second_type,
2805 sizeof...(TPairs)>;
2806#endif
2807
2808 //*************************************************************************
2810 //*************************************************************************
2811#if ETL_USING_CPP11 && ETL_HAS_INITIALIZER_LIST
2812 template <typename TKey, typename TMapped, typename TKeyCompare = etl::less<TKey>, typename... TPairs>
2813 constexpr auto make_map(TPairs&&... pairs) -> etl::map<TKey, TMapped, sizeof...(TPairs), TKeyCompare>
2814 {
2815 return { etl::forward<TPairs>(pairs)... };
2816 }
2817#endif
2818
2819 //***************************************************************************
2825 //***************************************************************************
2826 template <typename TKey, typename TMapped, typename TKeyCompare>
2828 {
2829 return (lhs.size() == rhs.size()) && etl::equal(lhs.begin(), lhs.end(), rhs.begin());
2830 }
2831
2832 //***************************************************************************
2838 //***************************************************************************
2839 template <typename TKey, typename TMapped, typename TKeyCompare>
2844
2845 //*************************************************************************
2851 //*************************************************************************
2852 template <typename TKey, typename TMapped, typename TKeyCompare>
2854 {
2855 return etl::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
2856 }
2857
2858 //*************************************************************************
2864 //*************************************************************************
2865 template <typename TKey, typename TMapped, typename TKeyCompare>
2870
2871 //*************************************************************************
2877 //*************************************************************************
2878 template <typename TKey, typename TMapped, typename TKeyCompare>
2883
2884 //*************************************************************************
2890 //*************************************************************************
2891 template <typename TKey, typename TMapped, typename TKeyCompare>
2896}
2897
2898#include "private/minmax_pop.h"
2899
2900#endif
const_iterator
Definition map.h:705
iterator.
Definition map.h:598
Definition map.h:487
A templated map implementation that uses a fixed size buffer.
Definition map.h:2667
map(const map &other)
Copy constructor.
Definition map.h:2684
~map()
Destructor.
Definition map.h:2743
map(TIterator first, TIterator last)
Definition map.h:2723
map()
Default constructor.
Definition map.h:2675
ETL_CONSTEXPR14 bool operator==(const etl::expected< TValue, TError > &lhs, const etl::expected< TValue2, TError2 > &rhs)
Equivalence operators.
Definition expected.h:966
#define ETL_ASSERT(b, e)
Definition error_handler.h:316
Definition exception.h:47
const_reverse_iterator crend() const
Gets the reverse end of the list.
Definition map.h:915
void detach_node(Node *&position, Node *&replacement)
Detach the node at the position provided.
Definition map.h:429
imap & operator=(const imap &rhs)
Assignment operator.
Definition map.h:1400
void rotate_2node(Node *&position, uint_least8_t dir)
Rotate two nodes at the position provided the to balance the tree.
Definition map.h:310
void clear()
Clears the map.
Definition map.h:1053
bool empty() const
Checks to see if the map is empty.
Definition map.h:149
bool full() const
Checks to see if the map is full.
Definition map.h:157
size_type count(const_key_reference key) const
Definition map.h:1063
const_iterator end() const
Gets the end of the map.
Definition map.h:851
iterator erase(const_iterator first, const_iterator last)
Erases a range of elements.
Definition map.h:1154
const size_type CAPACITY
The maximum size of the map.
Definition map.h:451
void initialise()
Initialise the map.
Definition map.h:1482
size_t size_type
The type used for determining the size of map.
Definition map.h:128
reverse_iterator rend()
Gets the reverse end of the list.
Definition map.h:891
void assign(TIterator first, TIterator last)
Definition map.h:1044
void insert(TIterator first, TIterator last)
Definition map.h:1308
map_base(size_type max_size_)
The constructor that is called from derived classes.
Definition map.h:229
mapped_reference at(const_key_reference key)
Definition map.h:986
key_compare key_comp() const
How to compare two key elements.
Definition map.h:1438
size_type capacity() const
Definition map.h:166
ETL_OR_STD::pair< iterator, iterator > equal_range(const_key_reference key)
Definition map.h:1081
~imap()
Destructor.
Definition map.h:2656
const_mapped_reference at(const_key_reference key) const
Definition map.h:1014
ETL_OR_STD::pair< const_iterator, const_iterator > equal_range(const_key_reference key) const
Definition map.h:1101
ETL_OR_STD::pair< iterator, bool > insert(const_reference value)
Definition map.h:1207
const_iterator cbegin() const
Gets the beginning of the map.
Definition map.h:859
const_reverse_iterator rbegin() const
Gets the reverse beginning of the list.
Definition map.h:883
Node * root_node
The node that acts as the map root.
Definition map.h:452
size_type size() const
Gets the size of the map.
Definition map.h:133
const_iterator cend() const
Gets the end of the map.
Definition map.h:867
size_type max_size() const
Gets the maximum possible size of the map.
Definition map.h:141
iterator find(const_key_reference key)
Definition map.h:1169
const_iterator upper_bound(const_key_reference key) const
Definition map.h:1383
const key_type & const_key_reference
Defines the parameter types.
Definition map.h:479
void rotate_3node(Node *&position, uint_least8_t dir, uint_least8_t third)
Rotate three nodes at the position provided the to balance the tree.
Definition map.h:340
iterator upper_bound(const_key_reference key)
Definition map.h:1363
iterator lower_bound(const_key_reference key)
Definition map.h:1323
iterator begin()
Gets the beginning of the map.
Definition map.h:827
size_t available() const
Definition map.h:175
const_reverse_iterator crbegin() const
Gets the reverse beginning of the list.
Definition map.h:907
bool contains(const TKey &key) const
Check if the map contains the key.
Definition map.h:1454
iterator end()
Gets the end of the map.
Definition map.h:843
const_reverse_iterator rend() const
Gets the reverse end of the list.
Definition map.h:899
const_iterator lower_bound(const_key_reference key) const
Definition map.h:1343
reverse_iterator rbegin()
Gets the reverse beginning of the list.
Definition map.h:875
iterator erase(const_iterator position)
Erases the value at the specified position.
Definition map.h:1120
const Node * find_limit_node(const Node *position, const int8_t dir) const
Definition map.h:398
size_type current_size
The number of the used nodes.
Definition map.h:450
Node * find_limit_node(Node *position, const int8_t dir) const
Definition map.h:381
~map_base()
Destructor.
Definition map.h:240
const_iterator find(const_key_reference key) const
Definition map.h:1188
mapped_reference operator[](const_key_reference key)
Definition map.h:956
value_compare value_comp() const
How to compare two value elements.
Definition map.h:1446
imap(etl::ipool &node_pool, size_t max_size_)
Constructor.
Definition map.h:1473
void attach_node(Node *&position, Node &node)
Attach the provided node to the position provided.
Definition map.h:414
iterator insert(const_iterator, const_reference value)
Definition map.h:1258
const_iterator begin() const
Gets the beginning of the map.
Definition map.h:835
bool node_comp(const Data_Node &node1, const Data_Node &node2) const
How to compare node elements.
Definition map.h:523
void balance_node(Node *&critical_node)
Balance the critical node at the position provided as needed.
Definition map.h:247
Definition map.h:462
Definition map.h:125
Definition map.h:69
Definition map.h:83
Definition map.h:111
Definition map.h:97
ETL_CONSTEXPR17 etl::enable_if<!etl::is_same< T, etl::nullptr_t >::value, T >::type * addressof(T &t)
Definition addressof.h:52
Definition ipool.h:102
bitset_ext
Definition absolute.h:38
bool operator>(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition array.h:693
bool operator>=(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition array.h:705
bool operator!=(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition array.h:654
void swap(etl::array< T, SIZE > &lhs, etl::array< T, SIZE > &rhs)
Template deduction guides.
Definition array.h:630
bool operator==(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition array.h:642
bool operator<(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition array.h:666
bool operator<=(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition array.h:681
The data node element in the map.
Definition map.h:506
iterator
Definition iterator.h:399
The node element in the map.
Definition map.h:193
void mark_as_leaf()
Marks the node as a leaf.
Definition map.h:213
Node()
Constructor.
Definition map.h:197
pair holds two objects of arbitrary type
Definition utility.h:164
T1 first
first is a copy of the first object
Definition utility.h:168
T2 second
second is a copy of the second object
Definition utility.h:169