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