Embedded Template Library 1.0
Loading...
Searching...
No Matches
multimap.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) 2014 John Wellbelove, rlindeman
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_MULTIMAP_INCLUDED
32#define ETL_MULTIMAP_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//*****************************************************************************
59//*****************************************************************************
60
61namespace etl
62{
63 //***************************************************************************
66 //***************************************************************************
76
77 //***************************************************************************
80 //***************************************************************************
82 {
83 public:
84
86 : etl::multimap_exception(ETL_ERROR_TEXT("multimap:full", ETL_MULTIMAP_FILE_ID"A"), file_name_, line_number_)
87 {
88 }
89 };
90
91 //***************************************************************************
94 //***************************************************************************
96 {
97 public:
98
100 : etl::multimap_exception(ETL_ERROR_TEXT("multimap:bounds", ETL_MULTIMAP_FILE_ID"B"), file_name_, line_number_)
101 {
102 }
103 };
104
105 //***************************************************************************
108 //***************************************************************************
110 {
111 public:
112
114 : etl::multimap_exception(ETL_ERROR_TEXT("multimap:iterator", ETL_MULTIMAP_FILE_ID"C"), file_name_, line_number_)
115 {
116 }
117 };
118
119 //***************************************************************************
122 //***************************************************************************
124 {
125 public:
126
127 typedef size_t size_type;
128
129 //*************************************************************************
131 //*************************************************************************
133 {
134 return current_size;
135 }
136
137 //*************************************************************************
139 //*************************************************************************
141 {
142 return CAPACITY;
143 }
144
145 //*************************************************************************
147 //*************************************************************************
148 bool empty() const
149 {
150 return current_size == 0;
151 }
152
153 //*************************************************************************
155 //*************************************************************************
156 bool full() const
157 {
158 return current_size == CAPACITY;
159 }
160
161 //*************************************************************************
164 //*************************************************************************
166 {
167 return CAPACITY;
168 }
169
170 //*************************************************************************
173 //*************************************************************************
174 size_t available() const
175 {
176 return max_size() - size();
177 }
178
179 protected:
180
181 enum
182 {
183 kLeft,
184 kRight,
185 kNeither
186 };
187
188 //*************************************************************************
190 //*************************************************************************
191 struct Node
192 {
193 //***********************************************************************
195 //***********************************************************************
197 parent(ETL_NULLPTR),
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 //***********************************************************************
207 //***********************************************************************
209 {
210 weight = (uint_least8_t) kNeither;
211 dir = (uint_least8_t) kNeither;
212 parent = ETL_NULLPTR;
213 children[0] = ETL_NULLPTR;
214 children[1] = ETL_NULLPTR;
215 }
216
217 Node* parent;
218 Node* children[2];
219 uint_least8_t weight;
220 uint_least8_t dir;
221 };
222
223 //*************************************************************************
225 //*************************************************************************
227 : current_size(0)
229 , root_node(ETL_NULLPTR)
230 {
231 }
232
233 //*************************************************************************
235 //*************************************************************************
237 {
238 }
239
240 //*************************************************************************
242 //*************************************************************************
244 {
245 // Step 1: Update weights for all children of the critical node up to the
246 // newly inserted node. This step is costly (in terms of traversing nodes
247 // multiple times during insertion) but doesn't require as much recursion
248 Node* weight_node = critical_node->children[critical_node->dir];
249 while (weight_node)
250 {
251 // Keep going until we reach a terminal node (dir == (uint_least8_t) kNeither)
252 if ((uint_least8_t) kNeither != weight_node->dir)
253 {
254 // Does this insert balance the previous weight factor value?
255 if (weight_node->weight == 1 - weight_node->dir)
256 {
257 weight_node->weight = (uint_least8_t) kNeither;
258 }
259 else
260 {
261 weight_node->weight = weight_node->dir;
262 }
263
264 // Update weight factor node to point to next node
265 weight_node = weight_node->children[weight_node->dir];
266 }
267 else
268 {
269 // Stop loop, terminal node found
270 break;
271 }
272 } // while(weight_node)
273
274 // Step 2: Update weight for critical_node or rotate tree to balance node
275 if ((uint_least8_t) kNeither == critical_node->weight)
276 {
277 critical_node->weight = critical_node->dir;
278 }
279 // If direction is different than weight, then it will now be balanced
280 else if (critical_node->dir != critical_node->weight)
281 {
282 critical_node->weight = (uint_least8_t) kNeither;
283 }
284 // Rotate is required to balance the tree at the critical node
285 else
286 {
287 // If critical node matches child node direction then perform a two
288 // node rotate in the direction of the critical node
289 if (critical_node->weight == critical_node->children[critical_node->dir]->dir)
290 {
292 }
293 // Otherwise perform a three node rotation in the direction of the
294 // critical node
295 else
296 {
298 critical_node->children[critical_node->dir]->children[1 - critical_node->dir]->dir);
299 }
300 }
301 }
302
303 //*************************************************************************
305 //*************************************************************************
306 void rotate_2node(Node*& position, uint_least8_t dir)
307 {
308 // A C A B
309 // B C -> A E OR B C -> D A
310 // D E B D D E E C
311 // C (new position) becomes the root
312 // A (position) takes ownership of D as its children[kRight] child
313 // C (new position) takes ownership of A as its left child
314 // OR
315 // B (new position) becomes the root
316 // A (position) takes ownership of E as its left child
317 // B (new position) takes ownership of A as its right child
318
319 // Capture new root (either B or C depending on dir) and its parent
320 Node* new_root = position->children[dir];
321
322 // Replace position's previous child with new root's other child
323 position->children[dir] = new_root->children[1 - dir];
324 // Update new root's other child parent pointer
325 if (position->children[dir])
326 {
327 position->children[dir]->parent = position;
328 }
329
330 // New root's parent becomes current position's parent
331 new_root->parent = position->parent;
332 new_root->children[1 - dir] = position;
333 new_root->dir = 1 - dir;
334
335 // Clear weight factor from current position
336 position->weight = (uint_least8_t) kNeither;
337 // Position's parent becomes new_root
338 position->parent = new_root;
339 position = new_root;
340 // Clear weight factor from new root
341 position->weight = (uint_least8_t) kNeither;
342 }
343
344 //*************************************************************************
346 //*************************************************************************
348 {
349 // --A-- --E-- --A-- --D--
350 // _B_ C -> B A OR B _C_ -> A C
351 // D E D F G C D E B F G E
352 // F G F G
353 // E (new position) becomes the root
354 // B (position) takes ownership of F as its left child
355 // A takes ownership of G as its right child
356 // OR
357 // D (new position) becomes the root
358 // A (position) takes ownership of F as its right child
359 // C takes ownership of G as its left child
360
361 // Capture new root (either E or D depending on dir)
362 Node* new_root = position->children[dir]->children[1 - dir];
363 // Set weight factor for B or C based on F or G existing and being a different than dir
364 position->children[dir]->weight = third != (uint_least8_t) kNeither && third != dir ? dir : (uint_least8_t) kNeither;
365
366 // Detach new root from its tree (replace with new roots child)
367 position->children[dir]->children[1 - dir] = new_root->children[dir];
368 // Update new roots child parent pointer
369 if (new_root->children[dir])
370 {
371 new_root->children[dir]->parent = position->children[dir];
372 }
373
374 // Attach current left tree to new root and update its parent
375 new_root->children[dir] = position->children[dir];
376 position->children[dir]->parent = new_root;
377
378 // Set weight factor for A based on F or G
379 position->weight = third != (uint_least8_t) kNeither && third == dir ? 1 - dir : (uint_least8_t) kNeither;
380
381 // Move new root's right tree to current roots left tree
382 position->children[dir] = new_root->children[1 - dir];
383 if (new_root->children[1 - dir])
384 {
385 new_root->children[1 - dir]->parent = position;
386 }
387
388 // Attach current root to new roots right tree and assume its parent
389 new_root->parent = position->parent;
390 new_root->children[1 - dir] = position;
391 new_root->dir = 1 - dir;
392
393 // Update current position's parent and replace with new root
394 position->parent = new_root;
395 position = new_root;
396 // Clear weight factor for new current position
397 position->weight = (uint_least8_t) kNeither;
398 }
399
400 //*************************************************************************
402 //*************************************************************************
403 void next_node(Node*& position) const
404 {
405 if (position)
406 {
407 // Is there a tree on the right? then find the minimum of that tree
408 if (position->children[(uint_least8_t) kRight])
409 {
410 // Return minimum node found
411 position = find_limit_node(position->children[(uint_least8_t) kRight], kLeft);
412 }
413 // Otherwise find the parent of this node
414 else
415 {
416 // Start with current position as parent
417 Node* parent = position;
418 do {
419 // Update current position as previous parent
420 position = parent;
421 // Find parent of current position
422 parent = position->parent; // find_parent_node(root_node, position);
423 // Repeat while previous position was on right side of parent tree
424 } while (parent && parent->children[(uint_least8_t) kRight] == position);
425
426 // Set parent node as the next position
427 position = parent;
428 }
429 }
430 }
431
432 //*************************************************************************
434 //*************************************************************************
435 void next_node(const Node*& position) const
436 {
437 if (position)
438 {
439 // Is there a tree on the right? then find the minimum of that tree
440 if (position->children[(uint_least8_t) kRight])
441 {
442 // Return minimum node found
443 position = find_limit_node(position->children[(uint_least8_t) kRight], kLeft);
444 }
445 // Otherwise find the parent of this node
446 else
447 {
448 // Start with current position as parent
449 const Node* parent = position;
450 do {
451 // Update current position as previous parent
452 position = parent;
453 // Find parent of current position
454 parent = position->parent;
455 // Repeat while previous position was on right side of parent tree
456 } while (parent && parent->children[(uint_least8_t) kRight] == position);
457
458 // Set parent node as the next position
459 position = parent;
460 }
461 }
462 }
463
464 //*************************************************************************
466 //*************************************************************************
467 void prev_node(Node*& position) const
468 {
469 // If starting at the terminal end, the previous node is the maximum node
470 // from the root
471 if (!position)
472 {
473 position = find_limit_node(root_node, kRight);
474 }
475 else
476 {
477 // Is there a tree on the left? then find the maximum of that tree
478 if (position->children[(uint_least8_t) kLeft])
479 {
480 // Return maximum node found
481 position = find_limit_node(position->children[(uint_least8_t) kLeft], kRight);
482 }
483 // Otherwise find the parent of this node
484 else
485 {
486 // Start with current position as parent
487 Node* parent = position;
488 do {
489 // Update current position as previous parent
490 position = parent;
491 // Find parent of current position
492 parent = position->parent;
493 // Repeat while previous position was on left side of parent tree
494 } while (parent && parent->children[(uint_least8_t) kLeft] == position);
495
496 // Set parent node as the next position
497 position = parent;
498 }
499 }
500 }
501
502 //*************************************************************************
504 //*************************************************************************
505 void prev_node(const Node*& position) const
506 {
507 // If starting at the terminal end, the previous node is the maximum node
508 // from the root
509 if (!position)
510 {
511 position = find_limit_node(root_node, kRight);
512 }
513 else
514 {
515 // Is there a tree on the left? then find the maximum of that tree
516 if (position->children[(uint_least8_t) kLeft])
517 {
518 // Return maximum node found
519 position = find_limit_node(position->children[(uint_least8_t) kLeft], kRight);
520 }
521 // Otherwise find the parent of this node
522 else
523 {
524 // Start with current position as parent
525 const Node* parent = position;
526 do {
527 // Update current position as previous parent
528 position = parent;
529 // Find parent of current position
530 parent = position->parent;
531 // Repeat while previous position was on left side of parent tree
532 } while (parent && parent->children[(uint_least8_t) kLeft] == position);
533
534 // Set parent node as the next position
535 position = parent;
536 }
537 }
538 }
539
540 //*************************************************************************
543 //*************************************************************************
544 Node* find_limit_node(Node* position, const int8_t dir) const
545 {
546 // Something at this position and in the direction specified? keep going
547 Node* limit_node = position;
548 while (limit_node && limit_node->children[dir])
549 {
550 limit_node = limit_node->children[dir];
551 }
552
553 // Return the limit node position found
554 return limit_node;
555 }
556
557 //*************************************************************************
559 //*************************************************************************
560 void attach_node(Node* parent, Node*& position, Node& node)
561 {
562 // Mark new node as leaf on attach to tree at position provided
563 node.mark_as_leaf();
564
565 // Keep track of this node's parent
566 node.parent = parent;
567
568 // Add the node here
569 position = &node;
570
571 // One more.
572 ++current_size;
573 }
574
575 //*************************************************************************
577 //*************************************************************************
578 void detach_node(Node*& position, Node*& replacement)
579 {
580 // Make temporary copy of actual nodes involved because we might lose
581 // their references in the process (e.g. position is the same as
582 // replacement or replacement is a child of position)
583 Node* detached = position;
585
586 // Update current position to point to swap (replacement) node first
587 position = swap;
588
589 // Update replacement node to point to child in opposite direction
590 // otherwise we might lose the other child of the swap node
591 replacement = swap->children[1 - swap->dir];
592
593 if (replacement != ETL_NULLPTR)
594 {
595 replacement->parent = swap->parent;
596 }
597
598 // Point swap node to detached node's parent, children and weight
599 swap->parent = detached->parent;
600 swap->children[(uint_least8_t) kLeft] = detached->children[(uint_least8_t) kLeft];
601 swap->children[(uint_least8_t) kRight] = detached->children[(uint_least8_t) kRight];
602 if (swap->children[(uint_least8_t) kLeft])
603 {
604 swap->children[(uint_least8_t) kLeft]->parent = swap;
605 }
606 if (swap->children[(uint_least8_t) kRight])
607 {
608 swap->children[(uint_least8_t) kRight]->parent = swap;
609 }
610 swap->weight = detached->weight;
611 }
612
616 ETL_DECLARE_DEBUG_COUNT;
617 };
618
619 //***************************************************************************
622 //***************************************************************************
623 template <typename TKey, typename TMapped, typename TKeyCompare = etl::less<TKey> >
625 {
626 public:
627
628 typedef ETL_OR_STD::pair<const TKey, TMapped> value_type;
629 typedef const TKey key_type;
630 typedef TMapped mapped_type;
631 typedef TKeyCompare key_compare;
632 typedef value_type& reference;
633 typedef const value_type& const_reference;
634#if ETL_USING_CPP11
635 typedef value_type&& rvalue_reference;
636#endif
637 typedef value_type* pointer;
638 typedef const value_type* const_pointer;
639 typedef size_t size_type;
640
641 typedef const key_type& const_key_reference;
642#if ETL_USING_CPP11
644#endif
645
647 {
648 public:
649
650 bool operator()(const_reference lhs, const_reference rhs) const
651 {
652 return (kcompare(lhs.first, rhs.first));
653 }
654
655 private:
656
657 key_compare kcompare;
658 };
659
660 protected:
661
662 //*************************************************************************
664 //*************************************************************************
665 struct Data_Node : public Node
666 {
667 explicit Data_Node(value_type value_)
668 : value(value_)
669 {
670 }
671
672 value_type value;
673 };
674
675 //*************************************************************************
677 //*************************************************************************
678 bool node_comp(const Data_Node& node1, const Data_Node& node2) const
679 {
680 return kcompare(node1.value.first, node2.value.first);
681 }
682
683 bool node_comp(const Data_Node& node, const_key_reference key) const
684 {
685 return kcompare(node.value.first, key);
686 }
687
688 bool node_comp(const_key_reference key, const Data_Node& node) const
689 {
690 return kcompare(key, node.value.first);
691 }
692
693#if ETL_USING_CPP11
694 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
695 bool node_comp(const Data_Node& node, const K& key) const
696 {
697 return kcompare(node.value.first, key);
698 }
699
700 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
701 bool node_comp(const K& key, const Data_Node& node) const
702 {
703 return kcompare(key, node.value.first);
704 }
705#endif
706
707 private:
708
710 ipool* p_node_pool;
711
712 key_compare kcompare;
713 value_compare vcompare;
714
715 //*************************************************************************
717 //*************************************************************************
718 static Data_Node* data_cast(Node* p_node)
719 {
720 return static_cast<Data_Node*>(p_node);
721 }
722
723 //*************************************************************************
725 //*************************************************************************
726 static Data_Node& data_cast(Node& node)
727 {
728 return static_cast<Data_Node&>(node);
729 }
730
731 //*************************************************************************
733 //*************************************************************************
734 static const Data_Node* data_cast(const Node* p_node)
735 {
736 return static_cast<const Data_Node*>(p_node);
737 }
738
739 //*************************************************************************
741 //*************************************************************************
742 static const Data_Node& data_cast(const Node& node)
743 {
744 return static_cast<const Data_Node&>(node);
745 }
746
747 public:
748 //*************************************************************************
750 //*************************************************************************
751 class iterator : public etl::iterator<ETL_OR_STD::bidirectional_iterator_tag, value_type>
752 {
753 public:
754
755 friend class imultimap;
756 friend class const_iterator;
757
758 iterator()
759 : p_multimap(ETL_NULLPTR)
760 , p_node(ETL_NULLPTR)
761 {
762 }
763
765 : p_multimap(&multimap)
766 , p_node(ETL_NULLPTR)
767 {
768 }
769
771 : p_multimap(&multimap)
772 , p_node(node)
773 {
774 }
775
776 iterator(const iterator& other)
777 : p_multimap(other.p_multimap)
778 , p_node(other.p_node)
779 {
780 }
781
782 ~iterator()
783 {
784 }
785
787 {
788 p_multimap->next_node(p_node);
789 return *this;
790 }
791
793 {
794 iterator temp(*this);
795 p_multimap->next_node(p_node);
796 return temp;
797 }
798
800 {
801 p_multimap->prev_node(p_node);
802 return *this;
803 }
804
806 {
807 iterator temp(*this);
808 p_multimap->prev_node(p_node);
809 return temp;
810 }
811
813 {
814 p_multimap = other.p_multimap;
815 p_node = other.p_node;
816 return *this;
817 }
818
819 reference operator *() const
820 {
821 return imultimap::data_cast(p_node)->value;
822 }
823
824 pointer operator &() const
825 {
826 return &(imultimap::data_cast(p_node)->value);
827 }
828
829 pointer operator ->() const
830 {
831 return &(imultimap::data_cast(p_node)->value);
832 }
833
834 friend bool operator == (const iterator& lhs, const iterator& rhs)
835 {
836 return lhs.p_multimap == rhs.p_multimap && lhs.p_node == rhs.p_node;
837 }
838
839 friend bool operator != (const iterator& lhs, const iterator& rhs)
840 {
841 return !(lhs == rhs);
842 }
843
844 private:
845
846 // Pointer to multimap associated with this iterator
847 imultimap* p_multimap;
848
849 // Pointer to the current node for this iterator
850 Node* p_node;
851 };
852 friend class iterator;
853
854 //*************************************************************************
856 //*************************************************************************
857 class const_iterator : public etl::iterator<ETL_OR_STD::bidirectional_iterator_tag, const value_type>
858 {
859 public:
860
861 friend class imultimap;
862
864 : p_multimap(ETL_NULLPTR)
865 , p_node(ETL_NULLPTR)
866 {
867 }
868
870 : p_multimap(&multimap)
871 , p_node(ETL_NULLPTR)
872 {
873 }
874
876 : p_multimap(&multimap)
877 , p_node(node)
878 {
879 }
880
882 : p_multimap(other.p_multimap)
883 , p_node(other.p_node)
884 {
885 }
886
888 : p_multimap(other.p_multimap)
889 , p_node(other.p_node)
890 {
891 }
892
894 {
895 }
896
898 {
899 p_multimap->next_node(p_node);
900 return *this;
901 }
902
904 {
905 const_iterator temp(*this);
906 p_multimap->next_node(p_node);
907 return temp;
908 }
909
911 {
912 p_multimap->prev_node(p_node);
913 return *this;
914 }
915
917 {
918 const_iterator temp(*this);
919 p_multimap->prev_node(p_node);
920 return temp;
921 }
922
924 {
925 p_multimap = other.p_multimap;
926 p_node = other.p_node;
927 return *this;
928 }
929
930 const_reference operator *() const
931 {
932 return imultimap::data_cast(p_node)->value;
933 }
934
935 const_pointer operator &() const
936 {
937 return imultimap::data_cast(p_node)->value;
938 }
939
940 const_pointer operator ->() const
941 {
942 return &(imultimap::data_cast(p_node)->value);
943 }
944
945 friend bool operator == (const const_iterator& lhs, const const_iterator& rhs)
946 {
947 return lhs.p_multimap == rhs.p_multimap && lhs.p_node == rhs.p_node;
948 }
949
950 friend bool operator != (const const_iterator& lhs, const const_iterator& rhs)
951 {
952 return !(lhs == rhs);
953 }
954
955 private:
956
957 // Convert to an iterator.
958 imultimap::iterator to_iterator() const
959 {
960 return imultimap::iterator(const_cast<imultimap&>(*p_multimap), const_cast<Node*>(p_node));
961 }
962
963 // Pointer to multimap associated with this iterator
964 const imultimap* p_multimap;
965
966 // Pointer to the current node for this iterator
967 const Node* p_node;
968 };
969 friend class const_iterator;
970
971 typedef typename etl::iterator_traits<iterator>::difference_type difference_type;
972
973 typedef ETL_OR_STD::reverse_iterator<iterator> reverse_iterator;
974 typedef ETL_OR_STD::reverse_iterator<const_iterator> const_reverse_iterator;
975
976 //*************************************************************************
978 //*************************************************************************
980 {
981 return iterator(*this, find_limit_node(root_node, kLeft));
982 }
983
984 //*************************************************************************
986 //*************************************************************************
988 {
989 return const_iterator(*this, find_limit_node(root_node, kLeft));
990 }
991
992 //*************************************************************************
994 //*************************************************************************
996 {
997 return iterator(*this);
998 }
999
1000 //*************************************************************************
1002 //*************************************************************************
1004 {
1005 return const_iterator(*this);
1006 }
1007
1008 //*************************************************************************
1010 //*************************************************************************
1012 {
1013 return const_iterator(*this, find_limit_node(root_node, kLeft));
1014 }
1015
1016 //*************************************************************************
1018 //*************************************************************************
1020 {
1021 return const_iterator(*this);
1022 }
1023
1024 //*************************************************************************
1026 //*************************************************************************
1027 reverse_iterator rbegin()
1028 {
1029 return reverse_iterator(iterator(*this));
1030 }
1031
1032 //*************************************************************************
1034 //*************************************************************************
1035 const_reverse_iterator rbegin() const
1036 {
1037 return const_reverse_iterator(const_iterator(*this));
1038 }
1039
1040 //*************************************************************************
1042 //*************************************************************************
1043 reverse_iterator rend()
1044 {
1045 return reverse_iterator(iterator(*this, find_limit_node(root_node, kLeft)));
1046 }
1047
1048 //*************************************************************************
1050 //*************************************************************************
1051 const_reverse_iterator rend() const
1052 {
1053 return const_reverse_iterator(iterator(*this, find_limit_node(root_node, kLeft)));
1054 }
1055
1056 //*************************************************************************
1058 //*************************************************************************
1059 const_reverse_iterator crbegin() const
1060 {
1061 return const_reverse_iterator(const_iterator(*this));
1062 }
1063
1064 //*************************************************************************
1066 //*************************************************************************
1067 const_reverse_iterator crend() const
1068 {
1069 return const_reverse_iterator(const_iterator(*this, find_limit_node(root_node, kLeft)));
1070 }
1071
1072 //*********************************************************************
1078 //*********************************************************************
1079 template <typename TIterator>
1080 void assign(TIterator first, TIterator last)
1081 {
1082 initialise();
1083 insert(first, last);
1084 }
1085
1086 //*************************************************************************
1088 //*************************************************************************
1089 void clear()
1090 {
1091 initialise();
1092 }
1093
1094 //*********************************************************************
1098 //*********************************************************************
1100 {
1101 return count_nodes(key);
1102 }
1103
1104#if ETL_USING_CPP11
1105 //*********************************************************************
1107 size_type count(const K& key) const
1108 {
1109 return count_nodes(key);
1110 }
1111#endif
1112
1113 //*************************************************************************
1116 //*************************************************************************
1117 ETL_OR_STD::pair<iterator, iterator> equal_range(const_key_reference key)
1118 {
1119 return ETL_OR_STD::make_pair<iterator, iterator>(iterator(*this, find_lower_node(root_node, key)),
1120 iterator(*this, find_upper_node(root_node, key)));
1121 }
1122
1123#if ETL_USING_CPP11
1124 //*************************************************************************
1126 ETL_OR_STD::pair<iterator, iterator> equal_range(const K& key)
1127 {
1128 return ETL_OR_STD::make_pair<iterator, iterator>(iterator(*this, find_lower_node(root_node, key)),
1129 iterator(*this, find_upper_node(root_node, key)));
1130 }
1131#endif
1132
1133 //*************************************************************************
1136 //*************************************************************************
1137 ETL_OR_STD::pair<const_iterator, const_iterator> equal_range(const_key_reference key) const
1138 {
1139 return ETL_OR_STD::make_pair<const_iterator, const_iterator>(const_iterator(*this, find_lower_node(root_node, key)),
1140 const_iterator(*this, find_upper_node(root_node, key)));
1141 }
1142
1143#if ETL_USING_CPP11
1144 //*************************************************************************
1146 ETL_OR_STD::pair<const_iterator, const_iterator> equal_range(const K& key) const
1147 {
1148 return ETL_OR_STD::make_pair<const_iterator, const_iterator>(const_iterator(*this, find_lower_node(root_node, key)),
1149 const_iterator(*this, find_upper_node(root_node, key)));
1150 }
1151#endif
1152
1153 //*************************************************************************
1155 //*************************************************************************
1157 {
1158 // Remove the node by its node specified in iterator position
1159 return erase(const_iterator(position));
1160 }
1161
1162 //*************************************************************************
1164 //*************************************************************************
1166 {
1167 // Cast const away from node to be removed. This is necessary because the
1168 // STL definition of this method requires we provide the next node in the
1169 // sequence as an iterator.
1170 Node* node = const_cast<Node*>(position.p_node);
1171 iterator next(*this, node);
1172 ++next;
1173
1174 // Remove the non-const node provided
1175 remove_node(node);
1176
1177 return next;
1178 }
1179
1180 //*************************************************************************
1181 // Erase the key specified.
1182 //*************************************************************************
1183 size_type erase(const_key_reference key)
1184 {
1185 // Number of nodes removed
1186 size_type d = 0;
1187 const_iterator lower(*this, find_lower_node(root_node, key));
1188 const_iterator upper(*this, find_upper_node(root_node, key));
1189 while (lower != upper)
1190 {
1191 // Increment count for each node removed
1192 ++d;
1193 // Remove node using the other erase method
1194 lower = erase(lower);
1195 }
1196
1197 // Return the total count erased
1198 return d;
1199 }
1200
1201 //*************************************************************************
1202#if ETL_USING_CPP11
1203 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
1204 size_type erase(K&& key)
1205 {
1206 // Number of nodes removed
1207 size_type d = 0;
1208 const_iterator lower(*this, find_lower_node(root_node, etl::forward<K>(key)));
1209 const_iterator upper(*this, find_upper_node(root_node, etl::forward<K>(key)));
1210 while (lower != upper)
1211 {
1212 // Increment count for each node removed
1213 ++d;
1214 // Remove node using the other erase method
1215 lower = erase(lower);
1216 }
1217
1218 // Return the total count erased
1219 return d;
1220 }
1221#endif
1222
1223 //*************************************************************************
1225 //*************************************************************************
1227 {
1228 while (first != last)
1229 {
1230 first = erase(first);
1231 }
1232
1233 return last.to_iterator();
1234 }
1235
1236 //*********************************************************************
1240 //*********************************************************************
1242 {
1243 return iterator(*this, find_node(root_node, key));
1244 }
1245
1246#if ETL_USING_CPP11
1247 //*********************************************************************
1249 iterator find(const K& k)
1250 {
1251 return iterator(*this, find_node(root_node, k));
1252 }
1253#endif
1254
1255 //*********************************************************************
1259 //*********************************************************************
1261 {
1262 return const_iterator(*this, find_node(root_node, key));
1263 }
1264
1265#if ETL_USING_CPP11
1266 //*********************************************************************
1268 const_iterator find(const K& k) const
1269 {
1270 return const_iterator(*this, find_node(root_node, k));
1271 }
1272#endif
1273
1274 //*********************************************************************
1278 //*********************************************************************
1279 iterator insert(const_reference value)
1280 {
1281 // Default to no inserted node
1282 Node* inserted_node = ETL_NULLPTR;
1283
1284 ETL_ASSERT(!full(), ETL_ERROR(multimap_full));
1285
1286 // Get next available free node
1287 Data_Node& node = allocate_data_node(value);
1288
1289 // Obtain the inserted node (might be ETL_NULLPTR if node was a duplicate)
1290 inserted_node = insert_node(root_node, node);
1291
1292 // Insert node into tree and return iterator to new node location in tree
1293 return iterator(*this, inserted_node);
1294 }
1295
1296#if ETL_USING_CPP11
1297 //*********************************************************************
1301 //*********************************************************************
1303 {
1304 // Default to no inserted node
1305 Node* inserted_node = ETL_NULLPTR;
1306
1307 ETL_ASSERT(!full(), ETL_ERROR(multimap_full));
1308
1309 // Get next available free node
1310 Data_Node& node = allocate_data_node(etl::move(value));
1311
1312 // Obtain the inserted node (might be ETL_NULLPTR if node was a duplicate)
1313 inserted_node = insert_node(root_node, node);
1314
1315 // Insert node into tree and return iterator to new node location in tree
1316 return iterator(*this, inserted_node);
1317 }
1318#endif
1319
1320 //*********************************************************************
1325 //*********************************************************************
1326 iterator insert(const_iterator /*position*/, const_reference value)
1327 {
1328 // Ignore position provided and just do a normal insert
1329 return insert(value);
1330 }
1331
1332#if ETL_USING_CPP11
1333 //*********************************************************************
1338 //*********************************************************************
1339 iterator insert(const_iterator /*position*/, rvalue_reference value)
1340 {
1341 // Ignore position provided and just do a normal insert
1342 return insert(etl::move(value));
1343 }
1344#endif
1345
1346 //*********************************************************************
1352 //*********************************************************************
1353 template <class TIterator>
1354 void insert(TIterator first, TIterator last)
1355 {
1356 while (first != last)
1357 {
1358 insert(*first);
1359 ++first;
1360 }
1361 }
1362
1363 //*********************************************************************
1368 //*********************************************************************
1370 {
1371 return iterator(*this, find_lower_node(root_node, key));
1372 }
1373
1374#if ETL_USING_CPP11
1375 //*********************************************************************
1377 iterator lower_bound(const K& key)
1378 {
1379 return iterator(*this, find_lower_node(root_node, key));
1380 }
1381#endif
1382
1383 //*********************************************************************
1388 //*********************************************************************
1390 {
1391 return const_iterator(*this, find_lower_node(root_node, key));
1392 }
1393
1394#if ETL_USING_CPP11
1395 //*********************************************************************
1397 const_iterator lower_bound(const K& key) const
1398 {
1399 return const_iterator(*this, find_lower_node(root_node, key));
1400 }
1401#endif
1402
1403 //*********************************************************************
1408 //*********************************************************************
1410 {
1411 return iterator(*this, find_upper_node(root_node, key));
1412 }
1413
1414#if ETL_USING_CPP11
1415 //*********************************************************************
1417 iterator upper_bound(const K& key)
1418 {
1419 return iterator(*this, find_upper_node(root_node, key));
1420 }
1421#endif
1422
1423 //*********************************************************************
1428 //*********************************************************************
1430 {
1431 return const_iterator(*this, find_upper_node(root_node, key));
1432 }
1433
1434#if ETL_USING_CPP11
1435 //*********************************************************************
1437 const_iterator upper_bound(const K& key) const
1438 {
1439 return const_iterator(*this, find_upper_node(root_node, key));
1440 }
1441#endif
1442
1443 //*************************************************************************
1445 //*************************************************************************
1447 {
1448 // Skip if doing self assignment
1449 if (this != &rhs)
1450 {
1451 assign(rhs.cbegin(), rhs.cend());
1452 }
1453
1454 return *this;
1455 }
1456
1457#if ETL_USING_CPP11
1458 //*************************************************************************
1460 //*************************************************************************
1462 {
1463 // Skip if doing self assignment
1464 if (this != &rhs)
1465 {
1466 this->clear();
1467
1468 iterator from = rhs.begin();
1469
1470 while (from != rhs.end())
1471 {
1472 this->insert(etl::move(*from));
1473 ++from;
1474 }
1475 }
1476
1477 return *this;
1478 }
1479#endif
1480
1481 //*************************************************************************
1483 //*************************************************************************
1485 {
1486 return kcompare;
1487 };
1488
1489 //*************************************************************************
1491 //*************************************************************************
1493 {
1494 return vcompare;
1495 };
1496
1497 //*************************************************************************
1499 //*************************************************************************
1500 bool contains(const TKey& key) const
1501 {
1502 return find(key) != end();
1503 }
1504
1505#if ETL_USING_CPP11
1506 //*************************************************************************
1508 bool contains(const K& k) const
1509 {
1510 return find(k) != end();
1511 }
1512#endif
1513
1514 protected:
1515
1516 //*************************************************************************
1518 //*************************************************************************
1519 imultimap(etl::ipool& node_pool, size_t max_size_)
1521 , p_node_pool(&node_pool)
1522 {
1523 }
1524
1525 //*************************************************************************
1527 //*************************************************************************
1529 {
1531
1532 while (item != end())
1533 {
1534 item = erase(item);
1535 }
1536 }
1537
1538 private:
1539
1540 //*************************************************************************
1542 //*************************************************************************
1543 Data_Node& allocate_data_node(const_reference value)
1544 {
1545 Data_Node* node = allocate_data_node();
1546 ::new (&node->value) const value_type(value);
1547 ETL_INCREMENT_DEBUG_COUNT;
1548 return *node;
1549 }
1550
1551#if ETL_USING_CPP11
1552 //*************************************************************************
1554 //*************************************************************************
1555 Data_Node& allocate_data_node(rvalue_reference value)
1556 {
1557 Data_Node* node = allocate_data_node();
1558 ::new (&node->value) const value_type(etl::move(value));
1559 ETL_INCREMENT_DEBUG_COUNT;
1560 return *node;
1561 }
1562#endif
1563
1564 //*************************************************************************
1566 //*************************************************************************
1567 Data_Node* allocate_data_node()
1568 {
1569 Data_Node* (etl::ipool::*func)() = &etl::ipool::allocate<Data_Node>;
1570 return (p_node_pool->*func)();
1571 }
1572
1573 //*************************************************************************
1575 //*************************************************************************
1576 void destroy_data_node(Data_Node& node)
1577 {
1578 node.value.~value_type();
1579 p_node_pool->release(&node);
1580 ETL_DECREMENT_DEBUG_COUNT;
1581 }
1582
1583 //*************************************************************************
1585 //*************************************************************************
1586 size_type count_nodes(const_key_reference key) const
1587 {
1588 // Number of nodes that match the key provided result
1589 size_type result = 0;
1590
1591 // Find lower and upper nodes for the key provided
1592 const Node* lower = find_lower_node(root_node, key);
1593 const Node* upper = find_upper_node(root_node, key);
1594
1595 // Loop from lower node to upper node and find nodes that match
1596 while (lower != upper)
1597 {
1598 // Downcast found to Data_Node class for comparison and other operations
1599 const Data_Node& data_node = imultimap::data_cast(*lower);
1600
1601 if (!node_comp(key, data_node) && !node_comp(data_node, key))
1602 {
1603 // This node matches the key provided
1604 ++result;
1605 }
1606
1607 // Move on to the next node
1608 next_node(lower);
1609 }
1610
1611 // Return the number of nodes that match
1612 return result;
1613 }
1614
1615#if ETL_USING_CPP11
1616 //*************************************************************************
1617 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
1618 size_type count_nodes(const K& key) const
1619 {
1620 // Number of nodes that match the key provided result
1621 size_type result = 0;
1622
1623 // Find lower and upper nodes for the key provided
1624 const Node* lower = find_lower_node(root_node, key);
1625 const Node* upper = find_upper_node(root_node, key);
1626
1627 // Loop from lower node to upper node and find nodes that match
1628 while (lower != upper)
1629 {
1630 // Downcast found to Data_Node class for comparison and other operations
1631 const Data_Node& data_node = imultimap::data_cast(*lower);
1632
1633 if (!node_comp(key, data_node) && !node_comp(data_node, key))
1634 {
1635 // This node matches the key provided
1636 ++result;
1637 }
1638
1639 // Move on to the next node
1640 next_node(lower);
1641 }
1642
1643 // Return the number of nodes that match
1644 return result;
1645 }
1646#endif
1647
1648 //*************************************************************************
1650 //*************************************************************************
1651 Node* find_node(Node* position, const_key_reference key)
1652 {
1653 Node* found = ETL_NULLPTR;
1654 while (position)
1655 {
1656 // Downcast found to Data_Node class for comparison and other operations
1657 Data_Node& data_node = imultimap::data_cast(*position);
1658 // Compare the node value to the current position value
1659 if (node_comp(key, data_node))
1660 {
1661 // Keep searching for the node on the left
1662 position = position->children[(uint_least8_t) kLeft];
1663 }
1664 else if (node_comp(data_node, key))
1665 {
1666 // Keep searching for the node on the right
1667 position = position->children[(uint_least8_t) kRight];
1668 }
1669 else
1670 {
1671 // We found one, keep looking for more on the left
1672 found = position;
1673 position = position->children[(uint_least8_t) kLeft];
1674 }
1675 }
1676
1677 // Return the node found (might be ETL_NULLPTR)
1678 return found;
1679 }
1680
1681#if ETL_USING_CPP11
1682 //*************************************************************************
1683 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
1684 Node* find_node(Node* position, const K& key)
1685 {
1686 Node* found = ETL_NULLPTR;
1687 while (position)
1688 {
1689 // Downcast found to Data_Node class for comparison and other operations
1690 Data_Node& data_node = imultimap::data_cast(*position);
1691 // Compare the node value to the current position value
1692 if (node_comp(key, data_node))
1693 {
1694 // Keep searching for the node on the left
1695 position = position->children[(uint_least8_t)kLeft];
1696 }
1697 else if (node_comp(data_node, key))
1698 {
1699 // Keep searching for the node on the right
1700 position = position->children[(uint_least8_t)kRight];
1701 }
1702 else
1703 {
1704 // We found one, keep looking for more on the left
1705 found = position;
1706 position = position->children[(uint_least8_t)kLeft];
1707 }
1708 }
1709
1710 // Return the node found (might be ETL_NULLPTR)
1711 return found;
1712 }
1713#endif
1714
1715 //*************************************************************************
1717 //*************************************************************************
1718 const Node* find_node(const Node* position, const_key_reference key) const
1719 {
1720 const Node* found = ETL_NULLPTR;
1721 while (position)
1722 {
1723 // Downcast found to Data_Node class for comparison and other operations
1724 const Data_Node& data_node = imultimap::data_cast(*position);
1725 // Compare the node value to the current position value
1726 if (node_comp(key, data_node))
1727 {
1728 // Keep searching for the node on the left
1729 position = position->children[(uint_least8_t) kLeft];
1730 }
1731 else if (node_comp(data_node, key))
1732 {
1733 // Keep searching for the node on the right
1734 position = position->children[(uint_least8_t) kRight];
1735 }
1736 else
1737 {
1738 // We found one, keep looking for more on the left
1739 found = position;
1740 position = position->children[(uint_least8_t) kLeft];
1741 }
1742 }
1743
1744 // Return the node found (might be ETL_NULLPTR)
1745 return found;
1746 }
1747
1748#if ETL_USING_CPP11
1749 //*************************************************************************
1751 //*************************************************************************
1752 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
1753 const Node* find_node(const Node* position, const K& key) const
1754 {
1755 const Node* found = ETL_NULLPTR;
1756 while (position)
1757 {
1758 // Downcast found to Data_Node class for comparison and other operations
1759 const Data_Node& data_node = imultimap::data_cast(*position);
1760 // Compare the node value to the current position value
1761 if (node_comp(key, data_node))
1762 {
1763 // Keep searching for the node on the left
1764 position = position->children[(uint_least8_t)kLeft];
1765 }
1766 else if (node_comp(data_node, key))
1767 {
1768 // Keep searching for the node on the right
1769 position = position->children[(uint_least8_t)kRight];
1770 }
1771 else
1772 {
1773 // We found one, keep looking for more on the left
1774 found = position;
1775 position = position->children[(uint_least8_t)kLeft];
1776 }
1777 }
1778
1779 // Return the node found (might be ETL_NULLPTR)
1780 return found;
1781 }
1782#endif
1783
1784 //*************************************************************************
1786 //*************************************************************************
1787 Node* find_lower_node(Node* position, const_key_reference key) const
1788 {
1789 // Something at this position? keep going
1790 Node* lower_node = ETL_NULLPTR;
1791 while (position)
1792 {
1793 // Downcast lower node to Data_Node reference for key comparisons
1794 Data_Node& data_node = imultimap::data_cast(*position);
1795 // Compare the key value to the current lower node key value
1796 if (node_comp(key, data_node))
1797 {
1798 lower_node = position;
1799 if (position->children[(uint_least8_t) kLeft])
1800 {
1801 position = position->children[(uint_least8_t) kLeft];
1802 }
1803 else
1804 {
1805 // Found lowest node
1806 break;
1807 }
1808 }
1809 else if (node_comp(data_node, key))
1810 {
1811 position = position->children[(uint_least8_t) kRight];
1812 }
1813 else
1814 {
1815 // Make note of current position, but keep looking to left for more
1816 lower_node = position;
1817 position = position->children[(uint_least8_t) kLeft];
1818 }
1819 }
1820
1821 // Return the lower_node position found
1822 return lower_node;
1823 }
1824
1825#if ETL_USING_CPP11
1826 //*************************************************************************
1827 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
1828 Node* find_lower_node(Node* position, const K& key) const
1829 {
1830 // Something at this position? keep going
1831 Node* lower_node = ETL_NULLPTR;
1832 while (position)
1833 {
1834 // Downcast lower node to Data_Node reference for key comparisons
1835 Data_Node& data_node = imultimap::data_cast(*position);
1836 // Compare the key value to the current lower node key value
1837 if (node_comp(key, data_node))
1838 {
1839 lower_node = position;
1840 if (position->children[(uint_least8_t)kLeft])
1841 {
1842 position = position->children[(uint_least8_t)kLeft];
1843 }
1844 else
1845 {
1846 // Found lowest node
1847 break;
1848 }
1849 }
1850 else if (node_comp(data_node, key))
1851 {
1852 position = position->children[(uint_least8_t)kRight];
1853 }
1854 else
1855 {
1856 // Make note of current position, but keep looking to left for more
1857 lower_node = position;
1858 position = position->children[(uint_least8_t)kLeft];
1859 }
1860 }
1861
1862 // Return the lower_node position found
1863 return lower_node;
1864 }
1865#endif
1866
1867 //*************************************************************************
1869 //*************************************************************************
1870 Node* find_upper_node(Node* position, const_key_reference key) const
1871 {
1872 // Keep track of parent of last upper node
1873 Node* upper_node = ETL_NULLPTR;
1874 // Has an equal node been found? start with no
1875 bool found = false;
1876 while (position)
1877 {
1878 // Downcast position to Data_Node reference for key comparisons
1879 Data_Node& data_node = imultimap::data_cast(*position);
1880 // Compare the key value to the current upper node key value
1881 if (node_comp(data_node, key))
1882 {
1883 position = position->children[(uint_least8_t) kRight];
1884 }
1885 else if (node_comp(key, data_node))
1886 {
1887 upper_node = position;
1888 // If a node equal to key hasn't been found go left
1889 if (!found && position->children[(uint_least8_t) kLeft])
1890 {
1891 position = position->children[(uint_least8_t) kLeft];
1892 }
1893 else
1894 {
1895 break;
1896 }
1897 }
1898 else
1899 {
1900 // We found an equal item, break on next bigger item
1901 found = true;
1902 next_node(position);
1903 }
1904 }
1905
1906 // Return the upper node position found (might be ETL_NULLPTR)
1907 return upper_node;
1908 }
1909
1910#if ETL_USING_CPP11
1911 //*************************************************************************
1912 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
1913 Node* find_upper_node(Node* position, const K& key) const
1914 {
1915 // Keep track of parent of last upper node
1916 Node* upper_node = ETL_NULLPTR;
1917 // Has an equal node been found? start with no
1918 bool found = false;
1919 while (position)
1920 {
1921 // Downcast position to Data_Node reference for key comparisons
1922 Data_Node& data_node = imultimap::data_cast(*position);
1923 // Compare the key value to the current upper node key value
1924 if (node_comp(data_node, key))
1925 {
1926 position = position->children[(uint_least8_t)kRight];
1927 }
1928 else if (node_comp(key, data_node))
1929 {
1930 upper_node = position;
1931 // If a node equal to key hasn't been found go left
1932 if (!found && position->children[(uint_least8_t)kLeft])
1933 {
1934 position = position->children[(uint_least8_t)kLeft];
1935 }
1936 else
1937 {
1938 break;
1939 }
1940 }
1941 else
1942 {
1943 // We found an equal item, break on next bigger item
1944 found = true;
1945 next_node(position);
1946 }
1947 }
1948
1949 // Return the upper node position found (might be ETL_NULLPTR)
1950 return upper_node;
1951 }
1952#endif
1953
1954 //*************************************************************************
1956 //*************************************************************************
1957 Node* insert_node(Node*& position, Data_Node& node)
1958 {
1959 // Find the location where the node belongs
1960 Node* found = position;
1961
1962 // Was position provided not empty? then find where the node belongs
1963 if (position)
1964 {
1965 // Find the critical parent node (default to ETL_NULLPTR)
1966 Node* critical_parent_node = ETL_NULLPTR;
1967 Node* critical_node = root_node;
1968
1969 while (found)
1970 {
1971 // Search for critical weight node (all nodes whose weight factor
1972 // is set to (uint_least8_t) kNeither (balanced)
1973 if ((uint_least8_t) kNeither != found->weight)
1974 {
1975 critical_node = found;
1976 }
1977
1978 // Downcast found to Data_Node class for comparison and other operations
1979 Data_Node& found_data_node = imultimap::data_cast(*found);
1980
1981 // Is the node provided to the left of the current position?
1982 if (node_comp(node, found_data_node))
1983 {
1984 // Update direction taken to insert new node in parent node
1985 found->dir = (uint_least8_t) kLeft;
1986 }
1987 // Is the node provided to the right of the current position?
1988 else if (node_comp(found_data_node, node))
1989 {
1990 // Update direction taken to insert new node in parent node
1991 found->dir = (uint_least8_t) kRight;
1992 }
1993 else
1994 {
1995 // Update direction taken to insert new node in parent (and
1996 // duplicate) node to the right.
1997 found->dir = (uint_least8_t) kRight;
1998 }
1999
2000 // Is there a child of this parent node?
2001 if (found->children[found->dir])
2002 {
2003 // Will this node be the parent of the next critical node whose
2004 // weight factor is set to (uint_least8_t) kNeither (balanced)?
2005 if ((uint_least8_t) kNeither != found->children[found->dir]->weight)
2006 {
2007 critical_parent_node = found;
2008 }
2009
2010 // Keep looking for empty spot to insert new node
2011 found = found->children[found->dir];
2012 }
2013 else
2014 {
2015 // Attach node as a child of the parent node found
2016 attach_node(found, found->children[found->dir], node);
2017
2018 // Return newly added node
2019 found = found->children[found->dir];
2020
2021 // Exit loop
2022 break;
2023 }
2024 }
2025
2026 // Was a critical node found that should be checked for balance?
2027 if (critical_node)
2028 {
2029 if (critical_parent_node == ETL_NULLPTR && critical_node == root_node)
2030 {
2032 }
2033 else if (critical_parent_node == ETL_NULLPTR && critical_node == position)
2034 {
2035 balance_node(position);
2036 }
2037 else
2038 {
2039 if (critical_parent_node != ETL_NULLPTR)
2040 {
2041 balance_node(critical_parent_node->children[critical_parent_node->dir]);
2042 }
2043 }
2044 }
2045 }
2046 else
2047 {
2048 // Attach node to current position (which is assumed to be root)
2049 attach_node(ETL_NULLPTR, position, node);
2050
2051 // Return newly added node at current position
2052 found = position;
2053 }
2054
2055 // Return the node found (might be ETL_NULLPTR)
2056 return found;
2057 }
2058
2059 //*************************************************************************
2062 //*************************************************************************
2063 void remove_node(Node* node)
2064 {
2065 // If valid found node was provided then proceed with steps 1 through 5
2066 if (node)
2067 {
2068 // Downcast found node provided to Data_Node class
2069 Data_Node& data_node = imultimap::data_cast(*node);
2070
2071 // Keep track of node as found node
2072 Node* found = node;
2073
2074 // Step 1: Mark path from node provided back to the root node using the
2075 // internal temporary dir member value and using the parent pointer. This
2076 // will allow us to avoid recursion in finding the node in a tree that
2077 //might contain duplicate keys to be found.
2078 while (node)
2079 {
2080 if (node->parent)
2081 {
2082 // Which direction does parent use to get to this node?
2083 node->parent->dir =
2084 node->parent->children[(uint_least8_t) kLeft] == node ? (uint_least8_t) kLeft : (uint_least8_t) kRight;
2085
2086 // Make this nodes parent the next node
2087 node = node->parent;
2088 }
2089 else
2090 {
2091 // Root node found - break loop
2092 break;
2093 }
2094 }
2095
2096 // Step 2: Follow the path provided above until we reach the node
2097 // provided and look for the balance node to start rebalancing the tree
2098 // from (up to the replacement node that will be found in step 3)
2099 Node* balance = root_node;
2100 while (node)
2101 {
2102 // Did we reach the node provided originally (found) then go to step 3
2103 if (node == found)
2104 {
2105 // Update the direction towards a replacement node at the found node
2106 node->dir = node->children[(uint_least8_t) kLeft] ? (uint_least8_t) kLeft : (uint_least8_t) kRight;
2107
2108 // Exit loop and proceed with step 3
2109 break;
2110 }
2111 else
2112 {
2113 // If this nodes weight is (uint_least8_t) kNeither or we are taking the shorter path
2114 // to the next node and our sibling (on longer path) is balanced then
2115 // we need to update the balance node to this node but all our
2116 // ancestors will not require rebalancing
2117 if ((node->weight == (uint_least8_t) kNeither) ||
2118 (node->weight == (1 - node->dir) &&
2119 node->children[1 - node->dir]->weight == (uint_least8_t) kNeither))
2120 {
2121 // Update balance node to this node
2122 balance = node;
2123 }
2124
2125 // Keep searching for found in the direction provided in step 1
2126 node = node->children[node->dir];
2127 }
2128 }
2129 // The value for node should not be ETL_NULLPTR at this point otherwise
2130 // step 1 failed to provide the correct path to found. Step 5 will fail
2131 // (probably subtly) if node should be ETL_NULLPTR at this point
2132
2133 // Step 3: Find the node (node should be equal to found at this point)
2134 // to replace found with (might end up equal to found) while also
2135 // continuing to update balance the same as in step 2 above.
2136 while (node)
2137 {
2138 // Replacement node found if its missing a child in the replace->dir
2139 // value set at the end of step 2 above
2140 if (node->children[node->dir] == ETL_NULLPTR)
2141 {
2142 // Exit loop once node to replace found is determined
2143 break;
2144 }
2145
2146 // If this nodes weight is (uint_least8_t) kNeither or we are taking the shorter path
2147 // to the next node and our sibling (on longer path) is balanced then
2148 // we need to update the balance node to this node but all our
2149 // ancestors will not require rebalancing
2150 if ((node->weight == (uint_least8_t) kNeither) ||
2151 (node->weight == (1 - node->dir) &&
2152 node->children[1 - node->dir]->weight == (uint_least8_t) kNeither))
2153 {
2154 // Update balance node to this node
2155 balance = node;
2156 }
2157
2158 // Keep searching for replacement node in the direction specified above
2159 node = node->children[node->dir];
2160
2161 // Downcast node to Data_Node class for comparison operations
2162 Data_Node& replace_data_node = imultimap::data_cast(*node);
2163
2164 // Compare the key provided to the replace data node key
2165 if (node_comp(data_node, replace_data_node))
2166 {
2167 // Update the direction to the replace node
2168 node->dir = (uint_least8_t) kLeft;
2169 }
2170 else if (node_comp(replace_data_node, data_node))
2171 {
2172 // Update the direction to the replace node
2173 node->dir = (uint_least8_t) kRight;
2174 }
2175 else
2176 {
2177 // Update the direction to the replace node
2178 node->dir = node->children[(uint_least8_t) kLeft] ? (uint_least8_t) kLeft : (uint_least8_t) kRight;
2179 }
2180 } // while(node)
2181
2182 // Step 4: Update weights from balance to parent of node determined
2183 // in step 3 above rotating (2 or 3 node rotations) as needed.
2184 while (balance)
2185 {
2186 // Break when balance node reaches the parent of replacement node
2187 if (balance->children[balance->dir] == ETL_NULLPTR)
2188 {
2189 break;
2190 }
2191
2192 // If balance node is balanced already ((uint_least8_t) kNeither) then just imbalance
2193 // the node in the opposite direction of the node being removed
2194 if (balance->weight == (uint_least8_t) kNeither)
2195 {
2196 balance->weight = 1 - balance->dir;
2197 }
2198 // If balance node is imbalanced in the opposite direction of the
2199 // node being removed then the node now becomes balanced
2200 else if (balance->weight == balance->dir)
2201 {
2202 balance->weight = (uint_least8_t) kNeither;
2203 }
2204 // Otherwise a rotation is required at this node
2205 else
2206 {
2207 int weight = balance->children[1 - balance->dir]->weight;
2208 // Perform a 3 node rotation if weight is same as balance->dir
2209 if (weight == balance->dir)
2210 {
2211 // Is the root node being rebalanced (no parent)
2212 if (balance->parent == ETL_NULLPTR)
2213 {
2214 rotate_3node(root_node, 1 - balance->dir,
2215 balance->children[1 - balance->dir]->children[balance->dir]->weight);
2216 }
2217 else
2218 {
2219 rotate_3node(balance->parent->children[balance->parent->dir], 1 - balance->dir,
2220 balance->children[1 - balance->dir]->children[balance->dir]->weight);
2221 }
2222 }
2223 // Already balanced, rebalance and make it heavy in opposite
2224 // direction of the node being removed
2225 else if (weight == (uint_least8_t) kNeither)
2226 {
2227 // Is the root node being rebalanced (no parent)
2228 if (balance->parent == ETL_NULLPTR)
2229 {
2230 rotate_2node(root_node, 1 - balance->dir);
2231 root_node->weight = balance->dir;
2232 }
2233 else
2234 {
2235 // Balance parent might change during rotate, keep local copy
2236 // to old parent so its weight can be updated after the 2 node
2237 // rotate is completed
2238 Node* old_parent = balance->parent;
2239 rotate_2node(balance->parent->children[balance->parent->dir], 1 - balance->dir);
2240 old_parent->children[old_parent->dir]->weight = balance->dir;
2241 }
2242 // Update balance node weight in opposite direction of node removed
2243 balance->weight = 1 - balance->dir;
2244 }
2245 // Rebalance and leave it balanced
2246 else
2247 {
2248 // Is the root node being rebalanced (no parent)
2249 if (balance->parent == ETL_NULLPTR)
2250 {
2251 rotate_2node(root_node, 1 - balance->dir);
2252 }
2253 else
2254 {
2255 rotate_2node(balance->parent->children[balance->parent->dir], 1 - balance->dir);
2256 }
2257 }
2258 }
2259
2260 // Next balance node to consider
2261 balance = balance->children[balance->dir];
2262 } // while(balance)
2263
2264 // Step 5: Swap found with node (replacement)
2265 if (found->parent)
2266 {
2267 // Handle traditional case
2268 detach_node(found->parent->children[found->parent->dir],
2269 node->parent->children[node->parent->dir]);
2270 }
2271 // Handle root node removal
2272 else
2273 {
2274 // Valid replacement node for root node being removed?
2275 if (node->parent)
2276 {
2277 detach_node(root_node, node->parent->children[node->parent->dir]);
2278 }
2279 else
2280 {
2281 // Found node and replacement node are both root node
2283 }
2284 }
2285
2286 // One less.
2287 --current_size;
2288
2289 // Destroy the node detached above
2290 destroy_data_node(data_node);
2291 } // if(found)
2292 }
2293
2294 // Disable copy construction.
2295 imultimap(const imultimap&);
2296
2297 //*************************************************************************
2299 //*************************************************************************
2300#if defined(ETL_POLYMORPHIC_MULTIMAP) || defined(ETL_POLYMORPHIC_CONTAINERS)
2301 public:
2302 virtual ~imultimap()
2303 {
2304 }
2305#else
2306 protected:
2308 {
2309 }
2310#endif
2311 };
2312
2313 //*************************************************************************
2315 //*************************************************************************
2316 template <typename TKey, typename TValue, const size_t MAX_SIZE_, typename TCompare = etl::less<TKey> >
2317 class multimap : public etl::imultimap<TKey, TValue, TCompare>
2318 {
2319 public:
2320
2321 static ETL_CONSTANT size_t MAX_SIZE = MAX_SIZE_;
2322
2323 //*************************************************************************
2325 //*************************************************************************
2327 : etl::imultimap<TKey, TValue, TCompare>(node_pool, MAX_SIZE)
2328 {
2329 this->initialise();
2330 }
2331
2332 //*************************************************************************
2334 //*************************************************************************
2336 : etl::imultimap<TKey, TValue, TCompare>(node_pool, MAX_SIZE)
2337 {
2338 if (this != &other)
2339 {
2340 this->assign(other.cbegin(), other.cend());
2341 }
2342 }
2343
2344#if ETL_USING_CPP11
2345 //*************************************************************************
2347 //*************************************************************************
2349 : etl::imultimap<TKey, TValue, TCompare>(node_pool, MAX_SIZE)
2350 {
2351 if (this != &other)
2352 {
2354
2355 while (from != other.end())
2356 {
2358 ++temp;
2359
2360 this->insert(etl::move(*from));
2361 from = temp;
2362 }
2363 }
2364 }
2365#endif
2366
2367 //*************************************************************************
2372 //*************************************************************************
2373 template <typename TIterator>
2375 : etl::imultimap<TKey, TValue, TCompare>(node_pool, MAX_SIZE)
2376 {
2377 this->assign(first, last);
2378 }
2379
2380#if ETL_HAS_INITIALIZER_LIST
2381 //*************************************************************************
2383 //*************************************************************************
2384 multimap(std::initializer_list<typename etl::imultimap<TKey, TValue, TCompare>::value_type> init)
2385 : etl::imultimap<TKey, TValue, TCompare>(node_pool, MAX_SIZE)
2386 {
2387 this->assign(init.begin(), init.end());
2388 }
2389#endif
2390
2391 //*************************************************************************
2393 //*************************************************************************
2395 {
2396 this->initialise();
2397 }
2398
2399 //*************************************************************************
2401 //*************************************************************************
2403 {
2404 // Skip if doing self assignment
2405 if (this != &rhs)
2406 {
2407 this->assign(rhs.cbegin(), rhs.cend());
2408 }
2409
2410 return *this;
2411 }
2412
2413#if ETL_USING_CPP11
2414 //*************************************************************************
2416 //*************************************************************************
2418 {
2419 if (this != &rhs)
2420 {
2422
2423 while (from != rhs.end())
2424 {
2426 ++temp;
2427
2428 this->insert(etl::move(*from));
2429 from = temp;
2430 }
2431 }
2432
2433 return *this;
2434 }
2435#endif
2436
2437 private:
2438
2441 };
2442
2443 template <typename TKey, typename TValue, const size_t MAX_SIZE_, typename TCompare>
2444 ETL_CONSTANT size_t multimap<TKey, TValue, MAX_SIZE_, TCompare>::MAX_SIZE;
2445
2446 //*************************************************************************
2448 //*************************************************************************
2449#if ETL_USING_CPP17 && ETL_HAS_INITIALIZER_LIST
2450 template <typename... TPairs>
2451 multimap(TPairs...) -> multimap<typename etl::nth_type_t<0, TPairs...>::first_type,
2452 typename etl::nth_type_t<0, TPairs...>::second_type,
2453 sizeof...(TPairs)>;
2454#endif
2455
2456 //*************************************************************************
2458 //*************************************************************************
2459#if ETL_USING_CPP11 && ETL_HAS_INITIALIZER_LIST
2460 template <typename TKey, typename TMapped, typename TKeyCompare = etl::less<TKey>, typename... TPairs>
2461 constexpr auto make_multimap(TPairs&&... pairs) -> etl::multimap<TKey, TMapped, sizeof...(TPairs), TKeyCompare>
2462 {
2463 return { etl::forward<TPairs>(pairs)... };
2464 }
2465#endif
2466
2467 //***************************************************************************
2473 //***************************************************************************
2474 template <typename TKey, typename TMapped, typename TKeyCompare>
2476 {
2477 return (lhs.size() == rhs.size()) && etl::equal(lhs.begin(), lhs.end(), rhs.begin());
2478 }
2479
2480 //***************************************************************************
2486 //***************************************************************************
2487 template <typename TKey, typename TMapped, typename TKeyCompare>
2492
2493 //*************************************************************************
2499 //*************************************************************************
2500 template <typename TKey, typename TMapped, typename TKeyCompare>
2502 {
2503 return etl::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
2504 }
2505
2506 //*************************************************************************
2512 //*************************************************************************
2513 template <typename TKey, typename TMapped, typename TKeyCompare>
2518
2519 //*************************************************************************
2525 //*************************************************************************
2526 template <typename TKey, typename TMapped, typename TKeyCompare>
2531
2532 //*************************************************************************
2538 //*************************************************************************
2539 template <typename TKey, typename TMapped, typename TKeyCompare>
2544}
2545
2546#include "private/minmax_pop.h"
2547
2548#endif
const_iterator
Definition multimap.h:858
iterator.
Definition multimap.h:752
Definition multimap.h:647
A templated multimap implementation that uses a fixed size buffer.
Definition multimap.h:2318
multimap(TIterator first, TIterator last)
Definition multimap.h:2374
multimap()
Default constructor.
Definition multimap.h:2326
~multimap()
Destructor.
Definition multimap.h:2394
multimap(const multimap &other)
Copy constructor.
Definition multimap.h:2335
ETL_CONSTEXPR14 bool operator==(const etl::expected< TValue, TError > &lhs, const etl::expected< TValue2, TError2 > &rhs)
Equivalence operators.
Definition expected.h:968
#define ETL_ASSERT(b, e)
Definition error_handler.h:356
Definition exception.h:47
void assign(TIterator first, TIterator last)
Definition multimap.h:1080
bool contains(const TKey &key) const
Check if the map contains the key.
Definition multimap.h:1500
iterator find(const_key_reference key)
Definition multimap.h:1241
void attach_node(Node *parent, Node *&position, Node &node)
Attach the provided node to the position provided.
Definition multimap.h:560
reverse_iterator rend()
Gets the reverse end of the list.
Definition multimap.h:1043
reverse_iterator rbegin()
Gets the reverse beginning of the list.
Definition multimap.h:1027
size_type size() const
Gets the size of the map.
Definition multimap.h:132
size_type current_size
The number of the used nodes.
Definition multimap.h:613
void next_node(const Node *&position) const
Find the next node in sequence from the node provided.
Definition multimap.h:435
iterator lower_bound(const_key_reference key)
Definition multimap.h:1369
const_reverse_iterator rbegin() const
Gets the reverse beginning of the list.
Definition multimap.h:1035
const_iterator upper_bound(const_key_reference key) const
Definition multimap.h:1429
multimap_base(size_type max_size_)
The constructor that is called from derived classes.
Definition multimap.h:226
const_iterator find(const_key_reference key) const
Definition multimap.h:1260
imultimap & operator=(const imultimap &rhs)
Assignment operator.
Definition multimap.h:1446
iterator insert(const_reference value)
Definition multimap.h:1279
bool node_comp(const Data_Node &node1, const Data_Node &node2) const
How to compare node elements.
Definition multimap.h:678
iterator erase(const_iterator first, const_iterator last)
Erases a range of elements.
Definition multimap.h:1226
ETL_OR_STD::pair< iterator, iterator > equal_range(const_key_reference key)
Definition multimap.h:1117
~multimap_base()
The constructor that is called from derived classes.
Definition multimap.h:236
void prev_node(const Node *&position) const
Find the previous node in sequence from the node provided.
Definition multimap.h:505
size_t available() const
Definition multimap.h:174
iterator end()
Gets the end of the multimap.
Definition multimap.h:995
void clear()
Clears the multimap.
Definition multimap.h:1089
void rotate_2node(Node *&position, uint_least8_t dir)
Rotate two nodes at the position provided the to balance the tree.
Definition multimap.h:306
iterator erase(iterator position)
Erases the value at the specified position.
Definition multimap.h:1156
const size_type CAPACITY
The maximum size of the map.
Definition multimap.h:614
void detach_node(Node *&position, Node *&replacement)
Detach the node at the position provided.
Definition multimap.h:578
const_reverse_iterator rend() const
Gets the reverse end of the list.
Definition multimap.h:1051
const_iterator end() const
Gets the end of the multimap.
Definition multimap.h:1003
key_compare key_comp() const
How to compare two key elements.
Definition multimap.h:1484
const_iterator cend() const
Gets the end of the multimap.
Definition multimap.h:1019
iterator insert(const_iterator, const_reference value)
Definition multimap.h:1326
bool empty() const
Checks to see if the map is empty.
Definition multimap.h:148
void next_node(Node *&position) const
Find the next node in sequence from the node provided.
Definition multimap.h:403
size_type capacity() const
Definition multimap.h:165
void prev_node(Node *&position) const
Find the previous node in sequence from the node provided.
Definition multimap.h:467
Node * root_node
The node that acts as the multimap root.
Definition multimap.h:615
size_t size_type
The type used for determining the size of map.
Definition multimap.h:127
const_reverse_iterator crbegin() const
Gets the reverse beginning of the list.
Definition multimap.h:1059
iterator begin()
Gets the beginning of the multimap.
Definition multimap.h:979
void insert(TIterator first, TIterator last)
Definition multimap.h:1354
const_iterator lower_bound(const_key_reference key) const
Definition multimap.h:1389
size_type max_size() const
Gets the maximum possible size of the map.
Definition multimap.h:140
ETL_OR_STD::pair< const_iterator, const_iterator > equal_range(const_key_reference key) const
Definition multimap.h:1137
const_iterator cbegin() const
Gets the beginning of the multimap.
Definition multimap.h:1011
iterator upper_bound(const_key_reference key)
Definition multimap.h:1409
size_type count(const_key_reference key) const
Definition multimap.h:1099
const_reverse_iterator crend() const
Gets the reverse end of the list.
Definition multimap.h:1067
void initialise()
Initialise the multimap.
Definition multimap.h:1528
imultimap(etl::ipool &node_pool, size_t max_size_)
Constructor.
Definition multimap.h:1519
value_compare value_comp() const
How to compare two value elements.
Definition multimap.h:1492
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 multimap.h:347
Node * find_limit_node(Node *position, const int8_t dir) const
Definition multimap.h:544
const_iterator begin() const
Gets the beginning of the multimap.
Definition multimap.h:987
bool full() const
Checks to see if the map is full.
Definition multimap.h:156
~imultimap()
Destructor.
Definition multimap.h:2307
iterator erase(const_iterator position)
Erases the value at the specified position.
Definition multimap.h:1165
void balance_node(Node *&critical_node)
Balance the critical node at the position provided as needed.
Definition multimap.h:243
Definition multimap.h:625
Definition multimap.h:124
Definition multimap.h:68
Definition multimap.h:82
Definition multimap.h:110
Definition multimap.h:96
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 multimap.
Definition multimap.h:666
iterator
Definition iterator.h:399
The node element in the multimap.
Definition multimap.h:192
Node()
Constructor.
Definition multimap.h:196
void mark_as_leaf()
Marks the node as a leaf.
Definition multimap.h:208
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