Embedded Template Library 1.0
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 //***************************************************************************
67 {
68 public:
69
70 multiset_exception(string_type reason_, string_type file_name_, numeric_type line_number_)
71 : etl::exception(reason_, file_name_, line_number_)
72 {
73 }
74 };
75
76 //***************************************************************************
79 //***************************************************************************
81 {
82 public:
83
84 multiset_full(string_type file_name_, numeric_type line_number_)
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
98 multiset_out_of_bounds(string_type file_name_, numeric_type line_number_)
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
112 multiset_iterator(string_type file_name_, numeric_type line_number_)
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)
227 , CAPACITY(max_size_)
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;
266 Node* swap = replacement;
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 //*************************************************************************
298 void balance_node(Node*& critical_node)
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 {
346 rotate_2node(critical_node, critical_node->dir);
347 }
348 // Otherwise perform a three node rotation in the direction of the
349 // critical node
350 else
351 {
352 rotate_3node(critical_node, critical_node->dir,
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 //*************************************************************************
559 void rotate_3node(Node*& position, uint_least8_t dir, uint_least8_t third)
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
634 typedef value_type&& rvalue_reference;
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
768 iterator& operator ++()
769 {
770 p_multiset->next_node(p_node);
771 return *this;
772 }
773
774 iterator operator ++(int)
775 {
776 iterator temp(*this);
777 p_multiset->next_node(p_node);
778 return temp;
779 }
780
781 iterator& operator --()
782 {
783 p_multiset->prev_node(p_node);
784 return *this;
785 }
786
787 iterator operator --(int)
788 {
789 iterator temp(*this);
790 p_multiset->prev_node(p_node);
791 return temp;
792 }
793
794 iterator& operator =(const iterator& other)
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
858 const_iterator(const imultiset& multiset, const Node* node)
859 : p_multiset(&multiset)
860 , p_node(node)
861 {
862 }
863
864 const_iterator(const typename imultiset::iterator& other)
865 : p_multiset(other.p_multiset)
866 , p_node(other.p_node)
867 {
868 }
869
870 const_iterator(const const_iterator& other)
871 : p_multiset(other.p_multiset)
872 , p_node(other.p_node)
873 {
874 }
875
877 {
878 }
879
880 const_iterator& operator ++()
881 {
882 p_multiset->next_node(p_node);
883 return *this;
884 }
885
886 const_iterator operator ++(int)
887 {
888 const_iterator temp(*this);
889 p_multiset->next_node(p_node);
890 return temp;
891 }
892
893 const_iterator& operator --()
894 {
895 p_multiset->prev_node(p_node);
896 return *this;
897 }
898
899 const_iterator operator --(int)
900 {
901 const_iterator temp(*this);
902 p_multiset->prev_node(p_node);
903 return temp;
904 }
905
906 const_iterator& operator =(const const_iterator& other)
907 {
908 p_multiset = other.p_multiset;
909 p_node = other.p_node;
910 return *this;
911 }
912
913 const_reference operator *() const
914 {
915 return imultiset::data_cast(p_node)->value;
916 }
917
918 const_pointer operator &() const
919 {
920 return imultiset::data_cast(p_node)->value;
921 }
922
923 const_pointer operator ->() const
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 //*********************************************************************
1090 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
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 //*************************************************************************
1109 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
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 //*************************************************************************
1129 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
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 //*************************************************************************
1167 size_type erase(key_parameter_t key_value)
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 //*********************************************************************
1233 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
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 //*********************************************************************
1252 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
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 //*********************************************************************
1264 iterator insert(const_reference value)
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 //*********************************************************************
1287 iterator insert(rvalue_reference value)
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 //*********************************************************************
1311 iterator insert(const_iterator /*position*/, const_reference value)
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 //*********************************************************************
1361 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
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 //*********************************************************************
1381 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
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 //*********************************************************************
1401 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
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 //*********************************************************************
1421 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
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 typename etl::imultiset<TKey, TCompare>::iterator from = rhs.begin();
1452
1453 while (from != rhs.end())
1454 {
1455 typename etl::imultiset<TKey, TCompare>::iterator temp = from;
1456 ++temp;
1457
1458 this->insert(etl::move(*from));
1459 from = temp;
1460 }
1461 }
1462
1463 return *this;
1464 }
1465#endif
1466
1467 //*************************************************************************
1469 //*************************************************************************
1470 key_compare key_comp() const
1471 {
1472 return compare;
1473 };
1474
1475 //*************************************************************************
1477 //*************************************************************************
1478 value_compare value_comp() const
1479 {
1480 return compare;
1481 };
1482
1483 //*************************************************************************
1485 //*************************************************************************
1487 {
1488 return find(key) != end();
1489 }
1490
1491#if ETL_USING_CPP11
1492 //*************************************************************************
1493 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
1494 bool contains(const K& k) const
1495 {
1496 return find(k) != end();
1497 }
1498#endif
1499
1500 protected:
1501
1502 //*************************************************************************
1504 //*************************************************************************
1505 imultiset(etl::ipool& node_pool, size_t max_size_)
1506 : etl::multiset_base(max_size_)
1507 , p_node_pool(&node_pool)
1508 {
1509 }
1510
1511 //*************************************************************************
1513 //*************************************************************************
1515 {
1516 const_iterator item = begin();
1517
1518 while (item != end())
1519 {
1520 item = erase(item);
1521 }
1522 }
1523
1524 private:
1525
1526 //*************************************************************************
1528 //*************************************************************************
1529 Data_Node& allocate_data_node(const_reference value)
1530 {
1531 Data_Node& node = allocate_data_node();
1532 ::new ((void*)&node.value) value_type(value);
1533 ETL_INCREMENT_DEBUG_COUNT
1534 return node;
1535 }
1536
1537#if ETL_USING_CPP11
1538 //*************************************************************************
1540 //*************************************************************************
1541 Data_Node& allocate_data_node(rvalue_reference value)
1542 {
1543 Data_Node& node = allocate_data_node();
1544 ::new ((void*)&node.value) value_type(etl::move(value));
1545 ETL_INCREMENT_DEBUG_COUNT
1546 return node;
1547 }
1548#endif
1549
1550 //*************************************************************************
1552 //*************************************************************************
1553 Data_Node& allocate_data_node()
1554 {
1555 Data_Node* (etl::ipool::*func)() = &etl::ipool::allocate<Data_Node>;
1556 return *(p_node_pool->*func)();
1557 }
1558
1559 //*************************************************************************
1561 //*************************************************************************
1562 void destroy_data_node(Data_Node& node)
1563 {
1564 node.value.~value_type();
1565 p_node_pool->release(&node);
1566 ETL_DECREMENT_DEBUG_COUNT
1567 }
1568
1569 //*************************************************************************
1571 //*************************************************************************
1572 size_type count_nodes(key_parameter_t key) const
1573 {
1574 // Number of nodes that match the key provided result
1575 size_type result = 0;
1576
1577 // Find lower and upper nodes for the key provided
1578 const Node* lower = find_lower_node(root_node, key);
1579 const Node* upper = find_upper_node(root_node, key);
1580
1581 // Loop from lower node to upper node and find nodes that match
1582 while (lower != upper)
1583 {
1584 // Downcast found to Data_Node class for comparison and other operations
1585 const Data_Node& data_node = imultiset::data_cast(*lower);
1586
1587 if (!node_comp(key, data_node) && !node_comp(data_node, key))
1588 {
1589 // This node matches the key provided
1590 ++result;
1591 }
1592
1593 // Move on to the next node
1594 next_node(lower);
1595 }
1596
1597 // Return the number of nodes that match
1598 return result;
1599 }
1600
1601#if ETL_USING_CPP11
1602 //*************************************************************************
1603 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
1604 size_type count_nodes(const K& key) const
1605 {
1606 // Number of nodes that match the key provided result
1607 size_type result = 0;
1608
1609 // Find lower and upper nodes for the key provided
1610 const Node* lower = find_lower_node(root_node, key);
1611 const Node* upper = find_upper_node(root_node, key);
1612
1613 // Loop from lower node to upper node and find nodes that match
1614 while (lower != upper)
1615 {
1616 // Downcast found to Data_Node class for comparison and other operations
1617 const Data_Node& data_node = imultiset::data_cast(*lower);
1618
1619 if (!node_comp(key, data_node) && !node_comp(data_node, key))
1620 {
1621 // This node matches the key provided
1622 ++result;
1623 }
1624
1625 // Move on to the next node
1626 next_node(lower);
1627 }
1628
1629 // Return the number of nodes that match
1630 return result;
1631 }
1632#endif
1633
1634 //*************************************************************************
1636 //*************************************************************************
1637 Node* find_node(Node* position, key_parameter_t key)
1638 {
1639 Node* found = ETL_NULLPTR;
1640 while (position)
1641 {
1642 // Downcast found to Data_Node class for comparison and other operations
1643 Data_Node& data_node = imultiset::data_cast(*position);
1644 // Compare the node value to the current position value
1645 if (node_comp(key, data_node))
1646 {
1647 // Keep searching for the node on the left
1648 position = position->children[kLeft];
1649 }
1650 else if (node_comp(data_node, key))
1651 {
1652 // Keep searching for the node on the right
1653 position = position->children[kRight];
1654 }
1655 else
1656 {
1657 // We found one, keep looking for more on the left
1658 found = position;
1659 position = position->children[kLeft];
1660 }
1661 }
1662
1663 // Return the node found (might be ETL_NULLPTR)
1664 return found;
1665 }
1666
1667#if ETL_USING_CPP11
1668 //*************************************************************************
1669 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
1670 Node* find_node(Node* position, const K& key)
1671 {
1672 Node* found = ETL_NULLPTR;
1673 while (position)
1674 {
1675 // Downcast found to Data_Node class for comparison and other operations
1676 Data_Node& data_node = imultiset::data_cast(*position);
1677 // Compare the node value to the current position value
1678 if (node_comp(key, data_node))
1679 {
1680 // Keep searching for the node on the left
1681 position = position->children[kLeft];
1682 }
1683 else if (node_comp(data_node, key))
1684 {
1685 // Keep searching for the node on the right
1686 position = position->children[kRight];
1687 }
1688 else
1689 {
1690 // We found one, keep looking for more on the left
1691 found = position;
1692 position = position->children[kLeft];
1693 }
1694 }
1695
1696 // Return the node found (might be ETL_NULLPTR)
1697 return found;
1698 }
1699#endif
1700
1701 //*************************************************************************
1703 //*************************************************************************
1704 const Node* find_node(const Node* position, key_parameter_t key) const
1705 {
1706 const Node* found = ETL_NULLPTR;
1707 while (position)
1708 {
1709 // Downcast found to Data_Node class for comparison and other operations
1710 const Data_Node& data_node = imultiset::data_cast(*position);
1711 // Compare the node value to the current position value
1712 if (node_comp(key, data_node))
1713 {
1714 // Keep searching for the node on the left
1715 position = position->children[kLeft];
1716 }
1717 else if (node_comp(data_node, key))
1718 {
1719 // Keep searching for the node on the right
1720 position = position->children[kRight];
1721 }
1722 else
1723 {
1724 // We found one, keep looking for more on the left
1725 found = position;
1726 position = position->children[kLeft];
1727 }
1728 }
1729
1730 // Return the node found (might be ETL_NULLPTR)
1731 return found;
1732 }
1733
1734#if ETL_USING_CPP11
1735 //*************************************************************************
1736 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
1737 const Node* find_node(const Node* position, const K& key) const
1738 {
1739 const Node* found = ETL_NULLPTR;
1740 while (position)
1741 {
1742 // Downcast found to Data_Node class for comparison and other operations
1743 const Data_Node& data_node = imultiset::data_cast(*position);
1744 // Compare the node value to the current position value
1745 if (node_comp(key, data_node))
1746 {
1747 // Keep searching for the node on the left
1748 position = position->children[kLeft];
1749 }
1750 else if (node_comp(data_node, key))
1751 {
1752 // Keep searching for the node on the right
1753 position = position->children[kRight];
1754 }
1755 else
1756 {
1757 // We found one, keep looking for more on the left
1758 found = position;
1759 position = position->children[kLeft];
1760 }
1761 }
1762
1763 // Return the node found (might be ETL_NULLPTR)
1764 return found;
1765 }
1766#endif
1767
1768 //*************************************************************************
1770 //*************************************************************************
1771 Node* find_lower_node(Node* position, key_parameter_t key) const
1772 {
1773 // Something at this position? keep going
1774 Node* lower_node = ETL_NULLPTR;
1775 while (position)
1776 {
1777 // Downcast lower node to Data_Node reference for key comparisons
1778 Data_Node& data_node = imultiset::data_cast(*position);
1779 // Compare the key value to the current lower node key value
1780 if (node_comp(key, data_node))
1781 {
1782 lower_node = position;
1783 if (position->children[kLeft])
1784 {
1785 position = position->children[kLeft];
1786 }
1787 else
1788 {
1789 // Found lowest node
1790 break;
1791 }
1792 }
1793 else if (node_comp(data_node, key))
1794 {
1795 position = position->children[kRight];
1796 }
1797 else
1798 {
1799 // Make note of current position, but keep looking to left for more
1800 lower_node = position;
1801 position = position->children[kLeft];
1802 }
1803 }
1804
1805 // Return the lower_node position found
1806 return lower_node;
1807 }
1808
1809#if ETL_USING_CPP11
1810 //*************************************************************************
1811 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
1812 Node* find_lower_node(Node* position, const K& key) const
1813 {
1814 // Something at this position? keep going
1815 Node* lower_node = ETL_NULLPTR;
1816 while (position)
1817 {
1818 // Downcast lower node to Data_Node reference for key comparisons
1819 Data_Node& data_node = imultiset::data_cast(*position);
1820 // Compare the key value to the current lower node key value
1821 if (node_comp(key, data_node))
1822 {
1823 lower_node = position;
1824 if (position->children[kLeft])
1825 {
1826 position = position->children[kLeft];
1827 }
1828 else
1829 {
1830 // Found lowest node
1831 break;
1832 }
1833 }
1834 else if (node_comp(data_node, key))
1835 {
1836 position = position->children[kRight];
1837 }
1838 else
1839 {
1840 // Make note of current position, but keep looking to left for more
1841 lower_node = position;
1842 position = position->children[kLeft];
1843 }
1844 }
1845
1846 // Return the lower_node position found
1847 return lower_node;
1848 }
1849#endif
1850
1851 //*************************************************************************
1853 //*************************************************************************
1854 Node* find_upper_node(Node* position, key_parameter_t key) const
1855 {
1856 // Keep track of parent of last upper node
1857 Node* upper_node = ETL_NULLPTR;
1858 // Has an equal node been found? start with no
1859 bool found = false;
1860 while (position)
1861 {
1862 // Downcast position to Data_Node reference for key comparisons
1863 Data_Node& data_node = imultiset::data_cast(*position);
1864 // Compare the key value to the current upper node key value
1865 if (node_comp(data_node, key))
1866 {
1867 position = position->children[kRight];
1868 }
1869 else if (node_comp(key, data_node))
1870 {
1871 upper_node = position;
1872 // If a node equal to key hasn't been found go left
1873 if (!found && position->children[kLeft])
1874 {
1875 position = position->children[kLeft];
1876 }
1877 else
1878 {
1879 break;
1880 }
1881 }
1882 else
1883 {
1884 // We found an equal item, break on next bigger item
1885 found = true;
1886 next_node(position);
1887 }
1888 }
1889
1890 // Return the upper node position found (might be ETL_NULLPTR)
1891 return upper_node;
1892 }
1893
1894#if ETL_USING_CPP11
1895 //*************************************************************************
1896 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
1897 Node* find_upper_node(Node* position, const K& key) const
1898 {
1899 // Keep track of parent of last upper node
1900 Node* upper_node = ETL_NULLPTR;
1901 // Has an equal node been found? start with no
1902 bool found = false;
1903 while (position)
1904 {
1905 // Downcast position to Data_Node reference for key comparisons
1906 Data_Node& data_node = imultiset::data_cast(*position);
1907 // Compare the key value to the current upper node key value
1908 if (node_comp(data_node, key))
1909 {
1910 position = position->children[kRight];
1911 }
1912 else if (node_comp(key, data_node))
1913 {
1914 upper_node = position;
1915 // If a node equal to key hasn't been found go left
1916 if (!found && position->children[kLeft])
1917 {
1918 position = position->children[kLeft];
1919 }
1920 else
1921 {
1922 break;
1923 }
1924 }
1925 else
1926 {
1927 // We found an equal item, break on next bigger item
1928 found = true;
1929 next_node(position);
1930 }
1931 }
1932
1933 // Return the upper node position found (might be ETL_NULLPTR)
1934 return upper_node;
1935 }
1936#endif
1937
1938 //*************************************************************************
1940 //*************************************************************************
1941 Node* insert_node(Node*& position, Data_Node& node)
1942 {
1943 // Find the location where the node belongs
1944 Node* found = position;
1945
1946 // Was position provided not empty? then find where the node belongs
1947 if (position)
1948 {
1949 // Find the critical parent node (default to ETL_NULLPTR)
1950 Node* critical_parent_node = ETL_NULLPTR;
1951 Node* critical_node = root_node;
1952
1953 while (found)
1954 {
1955 // Search for critical weight node (all nodes whose weight factor
1956 // is set to kNeither (balanced)
1957 if (kNeither != found->weight)
1958 {
1959 critical_node = found;
1960 }
1961
1962 // Downcast found to Data_Node class for comparison and other operations
1963 Data_Node& found_data_node = imultiset::data_cast(*found);
1964
1965 // Is the node provided to the left of the current position?
1966 if (node_comp(node, found_data_node))
1967 {
1968 // Update direction taken to insert new node in parent node
1969 found->dir = kLeft;
1970 }
1971 // Is the node provided to the right of the current position?
1972 else if (node_comp(found_data_node, node))
1973 {
1974 // Update direction taken to insert new node in parent node
1975 found->dir = kRight;
1976 }
1977 else
1978 {
1979 // Update direction taken to insert new node in parent (and
1980 // duplicate) node to the right.
1981 found->dir = kRight;
1982 }
1983
1984 // Is there a child of this parent node?
1985 if (found->children[found->dir])
1986 {
1987 // Will this node be the parent of the next critical node whose
1988 // weight factor is set to kNeither (balanced)?
1989 if (kNeither != found->children[found->dir]->weight)
1990 {
1991 critical_parent_node = found;
1992 }
1993
1994 // Keep looking for empty spot to insert new node
1995 found = found->children[found->dir];
1996 }
1997 else
1998 {
1999 // Attach node as a child of the parent node found
2000 attach_node(found, found->children[found->dir], node);
2001
2002 // Return newly added node
2003 found = found->children[found->dir];
2004
2005 // Exit loop
2006 break;
2007 }
2008 }
2009
2010 // Was a critical node found that should be checked for balance?
2011 if (critical_node)
2012 {
2013 if (critical_parent_node == ETL_NULLPTR && critical_node == root_node)
2014 {
2016 }
2017 else if (critical_parent_node == ETL_NULLPTR && critical_node == position)
2018 {
2019 balance_node(position);
2020 }
2021 else
2022 {
2023 if (critical_parent_node != ETL_NULLPTR)
2024 {
2025 balance_node(critical_parent_node->children[critical_parent_node->dir]);
2026 }
2027 }
2028 }
2029 }
2030 else
2031 {
2032 // Attach node to current position (which is assumed to be root)
2033 attach_node(ETL_NULLPTR, position, node);
2034
2035 // Return newly added node at current position
2036 found = position;
2037 }
2038
2039 // Return the node found (might be ETL_NULLPTR)
2040 return found;
2041 }
2042
2043 //*************************************************************************
2046 //*************************************************************************
2047 void remove_node(Node* node)
2048 {
2049 // If valid found node was provided then proceed with steps 1 through 5
2050 if (node)
2051 {
2052 // Downcast found node provided to Data_Node class
2053 Data_Node& data_node = imultiset::data_cast(*node);
2054
2055 // Keep track of node as found node
2056 Node* found = node;
2057
2058 // Step 1: Mark path from node provided back to the root node using the
2059 // internal temporary dir member value and using the parent pointer. This
2060 // will allow us to avoid recursion in finding the node in a tree that
2061 //might contain duplicate keys to be found.
2062 while (node)
2063 {
2064 if (node->parent)
2065 {
2066 // Which direction does parent use to get to this node?
2067 node->parent->dir =
2068 node->parent->children[kLeft] == node ? kLeft : kRight;
2069
2070 // Make this nodes parent the next node
2071 node = node->parent;
2072 }
2073 else
2074 {
2075 // Root node found - break loop
2076 break;
2077 }
2078 }
2079
2080 // Step 2: Follow the path provided above until we reach the node
2081 // provided and look for the balance node to start rebalancing the tree
2082 // from (up to the replacement node that will be found in step 3)
2083 Node* balance = root_node;
2084 while (node)
2085 {
2086 // Did we reach the node provided originally (found) then go to step 3
2087 if (node == found)
2088 {
2089 // Update the direction towards a replacement node at the found node
2090 node->dir = node->children[kLeft] ? kLeft : kRight;
2091
2092 // Exit loop and proceed with step 3
2093 break;
2094 }
2095 else
2096 {
2097 // If this nodes weight is kNeither or we are taking the shorter path
2098 // to the next node and our sibling (on longer path) is balanced then
2099 // we need to update the balance node to this node but all our
2100 // ancestors will not require rebalancing
2101 if ((node->weight == kNeither) ||
2102 (node->weight == (1 - node->dir) &&
2103 node->children[1 - node->dir]->weight == kNeither))
2104 {
2105 // Update balance node to this node
2106 balance = node;
2107 }
2108
2109 // Keep searching for found in the direction provided in step 1
2110 node = node->children[node->dir];
2111 }
2112 }
2113 // The value for node should not be ETL_NULLPTR at this point otherwise
2114 // step 1 failed to provide the correct path to found. Step 5 will fail
2115 // (probably subtly) if node should be ETL_NULLPTR at this point
2116
2117 // Step 3: Find the node (node should be equal to found at this point)
2118 // to replace found with (might end up equal to found) while also
2119 // continuing to update balance the same as in step 2 above.
2120 while (node)
2121 {
2122 // Replacement node found if its missing a child in the replace->dir
2123 // value set at the end of step 2 above
2124 if (node->children[node->dir] == ETL_NULLPTR)
2125 {
2126 // Exit loop once node to replace found is determined
2127 break;
2128 }
2129
2130 // If this nodes weight is kNeither or we are taking the shorter path
2131 // to the next node and our sibling (on longer path) is balanced then
2132 // we need to update the balance node to this node but all our
2133 // ancestors will not require rebalancing
2134 if ((node->weight == kNeither) ||
2135 (node->weight == (1 - node->dir) &&
2136 node->children[1 - node->dir]->weight == kNeither))
2137 {
2138 // Update balance node to this node
2139 balance = node;
2140 }
2141
2142 // Keep searching for replacement node in the direction specified above
2143 node = node->children[node->dir];
2144
2145 // Downcast node to Data_Node class for comparison operations
2146 Data_Node& replace_data_node = imultiset::data_cast(*node);
2147
2148 // Compare the key provided to the replace data node key
2149 if (node_comp(data_node, replace_data_node))
2150 {
2151 // Update the direction to the replace node
2152 node->dir = kLeft;
2153 }
2154 else if (node_comp(replace_data_node, data_node))
2155 {
2156 // Update the direction to the replace node
2157 node->dir = kRight;
2158 }
2159 else
2160 {
2161 // Update the direction to the replace node
2162 node->dir = node->children[kLeft] ? kLeft : kRight;
2163 }
2164 } // while(node)
2165
2166 // Step 4: Update weights from balance to parent of node determined
2167 // in step 3 above rotating (2 or 3 node rotations) as needed.
2168 while (balance)
2169 {
2170 // Break when balance node reaches the parent of replacement node
2171 if (balance->children[balance->dir] == ETL_NULLPTR)
2172 {
2173 break;
2174 }
2175
2176 // If balance node is balanced already (kNeither) then just imbalance
2177 // the node in the opposite direction of the node being removed
2178 if (balance->weight == kNeither)
2179 {
2180 balance->weight = 1 - balance->dir;
2181 }
2182 // If balance node is imbalanced in the opposite direction of the
2183 // node being removed then the node now becomes balanced
2184 else if (balance->weight == balance->dir)
2185 {
2186 balance->weight = kNeither;
2187 }
2188 // Otherwise a rotation is required at this node
2189 else
2190 {
2191 int weight = balance->children[1 - balance->dir]->weight;
2192 // Perform a 3 node rotation if weight is same as balance->dir
2193 if (weight == balance->dir)
2194 {
2195 // Is the root node being rebalanced (no parent)
2196 if (balance->parent == ETL_NULLPTR)
2197 {
2198 rotate_3node(root_node, 1 - balance->dir,
2199 balance->children[1 - balance->dir]->children[balance->dir]->weight);
2200 }
2201 else
2202 {
2203 rotate_3node(balance->parent->children[balance->parent->dir], 1 - balance->dir,
2204 balance->children[1 - balance->dir]->children[balance->dir]->weight);
2205 }
2206 }
2207 // Already balanced, rebalance and make it heavy in opposite
2208 // direction of the node being removed
2209 else if (weight == kNeither)
2210 {
2211 // Is the root node being rebalanced (no parent)
2212 if (balance->parent == ETL_NULLPTR)
2213 {
2214 rotate_2node(root_node, 1 - balance->dir);
2215 root_node->weight = balance->dir;
2216 }
2217 else
2218 {
2219 // Balance parent might change during rotate, keep local copy
2220 // to old parent so its weight can be updated after the 2 node
2221 // rotate is completed
2222 Node* old_parent = balance->parent;
2223 rotate_2node(balance->parent->children[balance->parent->dir], 1 - balance->dir);
2224 old_parent->children[old_parent->dir]->weight = balance->dir;
2225 }
2226 // Update balance node weight in opposite direction of node removed
2227 balance->weight = 1 - balance->dir;
2228 }
2229 // Rebalance and leave it balanced
2230 else
2231 {
2232 // Is the root node being rebalanced (no parent)
2233 if (balance->parent == ETL_NULLPTR)
2234 {
2235 rotate_2node(root_node, 1 - balance->dir);
2236 }
2237 else
2238 {
2239 rotate_2node(balance->parent->children[balance->parent->dir], 1 - balance->dir);
2240 }
2241 }
2242 }
2243
2244 // Next balance node to consider
2245 balance = balance->children[balance->dir];
2246 } // while(balance)
2247
2248 // Step 5: Swap found with node (replacement)
2249 if (found->parent)
2250 {
2251 // Handle traditional case
2252 detach_node(found->parent->children[found->parent->dir],
2253 node->parent->children[node->parent->dir]);
2254 }
2255 // Handle root node removal
2256 else
2257 {
2258 // Valid replacement node for root node being removed?
2259 if (node->parent)
2260 {
2261 detach_node(root_node, node->parent->children[node->parent->dir]);
2262 }
2263 else
2264 {
2265 // Found node and replacement node are both root node
2267 }
2268 }
2269
2270 // One less.
2271 --current_size;
2272
2273 // Destroy the node detached above
2274 destroy_data_node(data_node);
2275 } // if(found)
2276 }
2277
2278 // Disable copy construction.
2279 imultiset(const imultiset&);
2280
2281 //*************************************************************************
2283 //*************************************************************************
2284#if defined(ETL_POLYMORPHIC_MULTISET) || defined(ETL_POLYMORPHIC_CONTAINERS)
2285 public:
2286 virtual ~imultiset()
2287 {
2288 }
2289#else
2290 protected:
2292 {
2293 }
2294#endif
2295 };
2296
2297 //*************************************************************************
2299 //*************************************************************************
2300 template <typename TKey, const size_t MAX_SIZE_, typename TCompare = ETL_OR_STD::less<TKey> >
2301 class multiset : public etl::imultiset<TKey, TCompare>
2302 {
2303 public:
2304
2305 static ETL_CONSTANT size_t MAX_SIZE = MAX_SIZE_;
2306
2307 //*************************************************************************
2309 //*************************************************************************
2311 : etl::imultiset<TKey, TCompare>(node_pool, MAX_SIZE)
2312 {
2313 this->initialise();
2314 }
2315
2316 //*************************************************************************
2318 //*************************************************************************
2319 multiset(const multiset& other)
2320 : etl::imultiset<TKey, TCompare>(node_pool, MAX_SIZE)
2321 {
2322 this->assign(other.cbegin(), other.cend());
2323 }
2324
2325#if ETL_USING_CPP11
2326 //*************************************************************************
2328 //*************************************************************************
2329 multiset(multiset&& other)
2330 : etl::imultiset<TKey, TCompare>(node_pool, MAX_SIZE)
2331 {
2332 if (this != &other)
2333 {
2334 typename etl::imultiset<TKey, TCompare>::iterator from = other.begin();
2335
2336 while (from != other.end())
2337 {
2338 typename etl::imultiset<TKey, TCompare>::iterator temp = from;
2339 ++temp;
2340
2341 this->insert(etl::move(*from));
2342 from = temp;
2343 }
2344 }
2345 }
2346#endif
2347
2348 //*************************************************************************
2353 //*************************************************************************
2354 template <typename TIterator>
2355 multiset(TIterator first, TIterator last)
2356 : etl::imultiset<TKey, TCompare>(node_pool, MAX_SIZE)
2357 {
2358 this->assign(first, last);
2359 }
2360
2361#if ETL_HAS_INITIALIZER_LIST
2362 //*************************************************************************
2364 //*************************************************************************
2365 multiset(std::initializer_list<typename etl::imultiset<TKey, TCompare>::value_type> init)
2366 : etl::imultiset<TKey, TCompare>(node_pool, MAX_SIZE)
2367 {
2368 this->assign(init.begin(), init.end());
2369 }
2370#endif
2371
2372 //*************************************************************************
2374 //*************************************************************************
2376 {
2377 this->initialise();
2378 }
2379
2380 //*************************************************************************
2382 //*************************************************************************
2384 {
2385 // Skip if doing self assignment
2386 if (this != &rhs)
2387 {
2388 this->assign(rhs.cbegin(), rhs.cend());
2389 }
2390
2391 return *this;
2392 }
2393
2394#if ETL_USING_CPP11
2395 //*************************************************************************
2397 //*************************************************************************
2399 {
2400 if (this != &rhs)
2401 {
2402 this->clear();
2403
2404 typename etl::imultiset<TKey, TCompare>::iterator from = rhs.begin();
2405
2406 while (from != rhs.end())
2407 {
2408 this->insert(etl::move(*from));
2409 ++from;
2410 }
2411 }
2412
2413 return *this;
2414 }
2415#endif
2416
2417 private:
2418
2421 };
2422
2423 template <typename TKey, const size_t MAX_SIZE_, typename TCompare>
2424 ETL_CONSTANT size_t multiset<TKey, MAX_SIZE_, TCompare>::MAX_SIZE;
2425
2426 //*************************************************************************
2428 //*************************************************************************
2429#if ETL_USING_CPP17 && ETL_HAS_INITIALIZER_LIST
2430 template <typename... T>
2431 multiset(T...) -> multiset<etl::nth_type_t<0, T...>, sizeof...(T)>;
2432#endif
2433
2434 //*************************************************************************
2436 //*************************************************************************
2437#if ETL_USING_CPP11 && ETL_HAS_INITIALIZER_LIST
2438 template <typename TKey, typename TKeyCompare = etl::less<TKey>, typename... T>
2439 constexpr auto make_multiset(T&&... keys) -> etl::multiset<TKey, sizeof...(T), TKeyCompare>
2440 {
2441 return { {etl::forward<T>(keys)...} };
2442 }
2443#endif
2444
2445 //***************************************************************************
2451 //***************************************************************************
2452 template <typename TKey, typename TCompare>
2454 {
2455 return (lhs.size() == rhs.size()) && ETL_OR_STD::equal(lhs.begin(), lhs.end(), rhs.begin());
2456 }
2457
2458 //***************************************************************************
2464 //***************************************************************************
2465 template <typename TKey, typename TCompare>
2467 {
2468 return !(lhs == rhs);
2469 }
2470
2471 //*************************************************************************
2477 //*************************************************************************
2478 template <typename TKey, typename TCompare>
2480 {
2481 return ETL_OR_STD::lexicographical_compare(lhs.begin(),
2482 lhs.end(),
2483 rhs.begin(),
2484 rhs.end());
2485 }
2486
2487 //*************************************************************************
2493 //*************************************************************************
2494 template <typename TKey, typename TCompare>
2496 {
2497 return (rhs < lhs);
2498 }
2499
2500 //*************************************************************************
2506 //*************************************************************************
2507 template <typename TKey, typename TCompare>
2509 {
2510 return !(lhs > rhs);
2511 }
2512
2513 //*************************************************************************
2519 //*************************************************************************
2520 template <typename TKey, typename TCompare>
2522 {
2523 return !(lhs < rhs);
2524 }
2525}
2526
2527#include "private/minmax_pop.h"
2528
2529#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:2302
multiset(const multiset &other)
Copy constructor.
Definition: multiset.h:2319
multiset()
Default constructor.
Definition: multiset.h:2310
~multiset()
Destructor.
Definition: multiset.h:2375
multiset & operator=(const multiset &rhs)
Assignment operator.
Definition: multiset.h:2383
multiset(TIterator first, TIterator last)
Definition: multiset.h:2355
#define ETL_ASSERT(b, e)
Definition: error_handler.h:316
Definition: exception.h:47
Definition: ipool.h:102
Definition: pool.h:54
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:1486
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:1514
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:1505
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:2291
void insert(TIterator first, TIterator last)
Definition: multiset.h:1339
value_compare value_comp() const
How to compare two value elements.
Definition: multiset.h:1478
~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:1470
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::imultiset< TKey, TCompare > &lhs, const etl::imultiset< TKey, TCompare > &rhs)
Template deduction guides.
Definition: multiset.h:2453
bool operator>(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition: array.h:684
etl::byte operator&(etl::byte lhs, etl::byte rhs)
And.
Definition: byte.h:273
bool operator>=(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition: array.h:696
bool operator!=(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition: array.h:645
void swap(etl::array< T, SIZE > &lhs, etl::array< T, SIZE > &rhs)
Template deduction guides.
Definition: array.h:621
bool operator!=(const etl::imultiset< TKey, TCompare > &lhs, const etl::imultiset< TKey, TCompare > &rhs)
Definition: multiset.h:2466
bool operator==(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition: array.h:633
bool operator<(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition: array.h:657
bool operator<=(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition: array.h:672
Definition: compare.h:52
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