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