Embedded Template Library 1.0
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 //***************************************************************************
70 {
71 public:
72
73 set_exception(string_type reason_, string_type file_name_, numeric_type line_number_)
74 : etl::exception(reason_, file_name_, line_number_)
75 {
76 }
77 };
78
79 //***************************************************************************
82 //***************************************************************************
84 {
85 public:
86
87 set_full(string_type file_name_, numeric_type line_number_)
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
101 set_out_of_bounds(string_type file_name_, numeric_type line_number_)
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
115 set_iterator(string_type file_name_, numeric_type line_number_)
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)
227 , CAPACITY(max_size_)
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;
264 Node* swap = replacement;
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 //*************************************************************************
282 void balance_node(Node*& critical_node)
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 {
330 rotate_2node(critical_node, critical_node->dir);
331 }
332 // Otherwise perform a three node rotation in the direction of the
333 // critical node
334 else
335 {
336 rotate_3node(critical_node, critical_node->dir,
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 //*************************************************************************
409 void rotate_3node(Node*& position, uint_least8_t dir, uint_least8_t third)
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
469 typedef value_type&& rvalue_reference;
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
589 iterator(iset& set, Node* node)
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
605 iterator& operator ++()
606 {
607 p_set->next_node(p_node);
608 return *this;
609 }
610
611 iterator operator ++(int)
612 {
613 iterator temp(*this);
614 p_set->next_node(p_node);
615 return temp;
616 }
617
618 iterator& operator --()
619 {
620 p_set->prev_node(p_node);
621 return *this;
622 }
623
624 iterator operator --(int)
625 {
626 iterator temp(*this);
627 p_set->prev_node(p_node);
628 return temp;
629 }
630
631 iterator& operator =(const iterator& other)
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
706 const_iterator(const const_iterator& other)
707 : p_set(other.p_set)
708 , p_node(other.p_node)
709 {
710 }
711
713 {
714 }
715
716 const_iterator& operator ++()
717 {
718 p_set->next_node(p_node);
719 return *this;
720 }
721
722 const_iterator operator ++(int)
723 {
724 const_iterator temp(*this);
725 p_set->next_node(p_node);
726 return temp;
727 }
728
729 const_iterator& operator --()
730 {
731 p_set->prev_node(p_node);
732 return *this;
733 }
734
735 const_iterator operator --(int)
736 {
737 const_iterator temp(*this);
738 p_set->prev_node(p_node);
739 return temp;
740 }
741
742 const_iterator& operator =(const const_iterator& other)
743 {
744 p_set = other.p_set;
745 p_node = other.p_node;
746 return *this;
747 }
748
749 const_reference operator *() const
750 {
751 return iset::data_cast(p_node)->value;
752 }
753
754 const_pointer operator &() const
755 {
756 return iset::data_cast(p_node)->value;
757 }
758
759 const_pointer operator ->() const
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 //*************************************************************************
798 iset& operator = (const iset& rhs)
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 //*************************************************************************
813 iset& operator = (iset&& rhs)
814 {
815 // Skip if doing self assignment
816 if (this != &rhs)
817 {
818 typename etl::iset<TKey, TCompare>::iterator from = rhs.begin();
819
820 while (from != rhs.end())
821 {
822 typename etl::iset<TKey, TCompare>::iterator temp = from;
823 ++temp;
824
825 this->insert(etl::move(*from));
826 from = temp;
827 }
828 }
829
830 return *this;
831 }
832#endif
833
834 //*************************************************************************
836 //*************************************************************************
838 {
839 return iterator(*this, find_limit_node(root_node, kLeft));
840 }
841
842 //*************************************************************************
844 //*************************************************************************
846 {
847 return const_iterator(*this, find_limit_node(root_node, kLeft));
848 }
849
850 //*************************************************************************
852 //*************************************************************************
854 {
855 return iterator(*this);
856 }
857
858 //*************************************************************************
860 //*************************************************************************
862 {
863 return const_iterator(*this);
864 }
865
866 //*************************************************************************
868 //*************************************************************************
870 {
871 return const_iterator(*this, find_limit_node(root_node, kLeft));
872 }
873
874 //*************************************************************************
876 //*************************************************************************
878 {
879 return const_iterator(*this);
880 }
881
882 //*************************************************************************
884 //*************************************************************************
885 reverse_iterator rbegin()
886 {
887 return reverse_iterator(iterator(*this));
888 }
889
890 //*************************************************************************
892 //*************************************************************************
893 const_reverse_iterator rbegin() const
894 {
895 return const_reverse_iterator(const_iterator(*this));
896 }
897
898 //*************************************************************************
900 //*************************************************************************
901 reverse_iterator rend()
902 {
903 return reverse_iterator(iterator(*this, find_limit_node(root_node, kLeft)));
904 }
905
906 //*************************************************************************
908 //*************************************************************************
909 const_reverse_iterator rend() const
910 {
911 return const_reverse_iterator(iterator(*this, find_limit_node(root_node, kLeft)));
912 }
913
914 //*************************************************************************
916 //*************************************************************************
917 const_reverse_iterator crbegin() const
918 {
919 return const_reverse_iterator(const_iterator(*this));
920 }
921
922 //*************************************************************************
924 //*************************************************************************
925 const_reverse_iterator crend() const
926 {
927 return const_reverse_iterator(const_iterator(*this, find_limit_node(root_node, kLeft)));
928 }
929
930 //*********************************************************************
936 //*********************************************************************
937 template <typename TIterator>
938 void assign(TIterator first, TIterator last)
939 {
940 initialise();
941 insert(first, last);
942 }
943
944 //*************************************************************************
946 //*************************************************************************
947 void clear()
948 {
949 initialise();
950 }
951
952 //*********************************************************************
956 //*********************************************************************
958 {
959 return find_node(root_node, key) ? 1 : 0;
960 }
961
962#if ETL_USING_CPP11
963 //*********************************************************************
964 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
965 size_type count(const K& key) const
966 {
967 return find_node(root_node, key) ? 1 : 0;
968 }
969#endif
970
971 //*************************************************************************
974 //*************************************************************************
975 ETL_OR_STD::pair<iterator, iterator> equal_range(key_parameter_t key)
976 {
977 return ETL_OR_STD::make_pair<iterator, iterator>(iterator(*this, find_lower_node(root_node, key)),
978 iterator(*this, find_upper_node(root_node, key)));
979 }
980
981#if ETL_USING_CPP11
982 //*************************************************************************
983 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
984 ETL_OR_STD::pair<iterator, iterator> equal_range(const K& key)
985 {
986 return ETL_OR_STD::make_pair<iterator, iterator>(iterator(*this, find_lower_node(root_node, key)),
987 iterator(*this, find_upper_node(root_node, key)));
988 }
989#endif
990
991 //*************************************************************************
994 //*************************************************************************
995 ETL_OR_STD::pair<const_iterator, const_iterator> equal_range(key_parameter_t key) const
996 {
997 return ETL_OR_STD::make_pair<const_iterator, const_iterator>(const_iterator(*this, find_lower_node(root_node, key)),
998 const_iterator(*this, find_upper_node(root_node, key)));
999 }
1000
1001#if ETL_USING_CPP11
1002 //*************************************************************************
1003 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
1004 ETL_OR_STD::pair<const_iterator, const_iterator> equal_range(const K& key) const
1005 {
1006 return ETL_OR_STD::make_pair<const_iterator, const_iterator>(const_iterator(*this, find_lower_node(root_node, key)),
1007 const_iterator(*this, find_upper_node(root_node, key)));
1008 }
1009#endif
1010
1011 //*************************************************************************
1013 //*************************************************************************
1015 {
1016 // Remove the node by its node specified in iterator position
1017 return erase(const_iterator(position));
1018 }
1019
1020 //*************************************************************************
1022 //*************************************************************************
1024 {
1025 // Find the parent node to be removed
1026 Node*& reference_node = find_node(root_node, position.p_node);
1027 iterator next(*this, reference_node);
1028 ++next;
1029
1030 remove_node(root_node, (*position));
1031
1032 return next;
1033 }
1034
1035 //*************************************************************************
1036 // Erase the key specified.
1037 //*************************************************************************
1038 size_type erase(key_parameter_t key_value)
1039 {
1040 // Return 1 if key value was found and removed
1041 return remove_node(root_node, key_value) ? 1 : 0;
1042 }
1043
1044 //*************************************************************************
1045#if ETL_USING_CPP11
1046 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
1047 size_type erase(K&& key_value)
1048 {
1049 // Return 1 if key value was found and removed
1050 return remove_node(root_node, etl::forward<K>(key_value)) ? 1 : 0;
1051 }
1052#endif
1053
1054 //*************************************************************************
1056 //*************************************************************************
1058 {
1059 while (first != last)
1060 {
1061 first = erase(first);
1062 }
1063
1064 return last.to_iterator();
1065 }
1066
1067 //*********************************************************************
1071 //*********************************************************************
1073 {
1074 return iterator(*this, find_node(root_node, key_value));
1075 }
1076
1077#if ETL_USING_CPP11
1078 //*********************************************************************
1079 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
1080 iterator find(const K& k)
1081 {
1082 return iterator(*this, find_node(root_node, k));
1083 }
1084#endif
1085
1086 //*********************************************************************
1090 //*********************************************************************
1092 {
1093 return const_iterator(*this, find_node(root_node, key_value));
1094 }
1095
1096#if ETL_USING_CPP11
1097 //*********************************************************************
1098 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
1099 const_iterator find(const K& key_value) const
1100 {
1101 return const_iterator(*this, find_node(root_node, key_value));
1102 }
1103#endif
1104
1105 //*********************************************************************
1109 //*********************************************************************
1110 ETL_OR_STD::pair<iterator, bool> insert(const_reference value)
1111 {
1112 // Default to no inserted node
1113 Node* inserted_node = ETL_NULLPTR;
1114 bool inserted = false;
1115
1116 ETL_ASSERT(!full(), ETL_ERROR(set_full));
1117
1118 // Get next available free node
1119 Data_Node& node = allocate_data_node(value);
1120
1121 // Obtain the inserted node (might be ETL_NULLPTR if node was a duplicate)
1122 inserted_node = insert_node(root_node, node);
1123 inserted = inserted_node == &node;
1124
1125 // Insert node into tree and return iterator to new node location in tree
1126 return ETL_OR_STD::make_pair(iterator(*this, inserted_node), inserted);
1127 }
1128
1129#if ETL_USING_CPP11
1130 //*********************************************************************
1134 //*********************************************************************
1135 ETL_OR_STD::pair<iterator, bool> insert(rvalue_reference value)
1136 {
1137 // Default to no inserted node
1138 Node* inserted_node = ETL_NULLPTR;
1139 bool inserted = false;
1140
1141 ETL_ASSERT(!full(), ETL_ERROR(set_full));
1142
1143 // Get next available free node
1144 Data_Node& node = allocate_data_node(etl::move(value));
1145
1146 // Obtain the inserted node (might be ETL_NULLPTR if node was a duplicate)
1147 inserted_node = insert_node(root_node, node);
1148 inserted = inserted_node == &node;
1149
1150 // Insert node into tree and return iterator to new node location in tree
1151 return ETL_OR_STD::make_pair(iterator(*this, inserted_node), inserted);
1152 }
1153#endif
1154
1155 //*********************************************************************
1160 //*********************************************************************
1161 iterator insert(const_iterator, const_reference value)
1162 {
1163 // Default to no inserted node
1164 Node* inserted_node = ETL_NULLPTR;
1165
1166 ETL_ASSERT(!full(), ETL_ERROR(set_full));
1167
1168 // Get next available free node
1169 Data_Node& node = allocate_data_node(value);
1170
1171 // Obtain the inserted node (might be ETL_NULLPTR if node was a duplicate)
1172 inserted_node = insert_node(root_node, node);
1173
1174 // Insert node into tree and return iterator to new node location in tree
1175 return iterator(*this, inserted_node);
1176 }
1177
1178#if ETL_USING_CPP11
1179 //*********************************************************************
1184 //*********************************************************************
1185 iterator insert(const_iterator, rvalue_reference value)
1186 {
1187 // Default to no inserted node
1188 Node* inserted_node = ETL_NULLPTR;
1189
1190 ETL_ASSERT(!full(), ETL_ERROR(set_full));
1191
1192 // Get next available free node
1193 Data_Node& node = allocate_data_node(etl::move(value));
1194
1195 // Obtain the inserted node (might be ETL_NULLPTR if node was a duplicate)
1196 inserted_node = insert_node(root_node, node);
1197
1198 // Insert node into tree and return iterator to new node location in tree
1199 return iterator(*this, inserted_node);
1200 }
1201#endif
1202
1203 //*********************************************************************
1209 //*********************************************************************
1210 template <class TIterator>
1211 void insert(TIterator first, TIterator last)
1212 {
1213 while (first != last)
1214 {
1215 insert(*first);
1216 ++first;
1217 }
1218 }
1219
1220 //*********************************************************************
1225 //*********************************************************************
1227 {
1228 return iterator(*this, find_lower_node(root_node, key));
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 lower_bound(const K& key)
1235 {
1236 return iterator(*this, find_lower_node(root_node, key));
1237 }
1238#endif
1239
1240 //*********************************************************************
1245 //*********************************************************************
1247 {
1248 return const_iterator(*this, find_lower_node(root_node, key));
1249 }
1250
1251#if ETL_USING_CPP11
1252 //*********************************************************************
1253 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
1254 const_iterator lower_bound(const K& key) const
1255 {
1256 return const_iterator(*this, find_lower_node(root_node, key));
1257 }
1258#endif
1259
1260 //*********************************************************************
1265 //*********************************************************************
1267 {
1268 return iterator(*this, find_upper_node(root_node, key));
1269 }
1270
1271#if ETL_USING_CPP11
1272 //*********************************************************************
1273 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
1274 iterator upper_bound(const K& key)
1275 {
1276 return iterator(*this, find_upper_node(root_node, key));
1277 }
1278#endif
1279
1280 //*********************************************************************
1285 //*********************************************************************
1287 {
1288 return const_iterator(*this, find_upper_node(root_node, key));
1289 }
1290
1291#if ETL_USING_CPP11
1292 //*********************************************************************
1293 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
1294 const_iterator upper_bound(const K& key) const
1295 {
1296 return const_iterator(*this, find_upper_node(root_node, key));
1297 }
1298#endif
1299
1300 //*************************************************************************
1302 //*************************************************************************
1303 key_compare key_comp() const
1304 {
1305 return compare;
1306 };
1307
1308 //*************************************************************************
1310 //*************************************************************************
1311 value_compare value_comp() const
1312 {
1313 return compare;
1314 };
1315
1316 //*************************************************************************
1318 //*************************************************************************
1319 bool contains(const TKey& key) const
1320 {
1321 return find(key) != end();
1322 }
1323
1324#if ETL_USING_CPP11
1325 //*************************************************************************
1326 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
1327 bool contains(const K& k) const
1328 {
1329 return find(k) != end();
1330 }
1331#endif
1332
1333 protected:
1334
1335 //*************************************************************************
1337 //*************************************************************************
1338 iset(etl::ipool& node_pool, size_t max_size_)
1339 : etl::set_base(max_size_)
1340 , p_node_pool(&node_pool)
1341 {
1342 }
1343
1344 //*************************************************************************
1346 //*************************************************************************
1348 {
1349 const_iterator item = begin();
1350
1351 while (item != end())
1352 {
1353 item = erase(item);
1354 }
1355 }
1356
1357 private:
1358
1359 //*************************************************************************
1361 //*************************************************************************
1362 Data_Node& allocate_data_node(const_reference value)
1363 {
1364 Data_Node& node = allocate_data_node();
1365 ::new ((void*)&node.value) value_type(value);
1366 ETL_INCREMENT_DEBUG_COUNT
1367 return node;
1368 }
1369
1370#if ETL_USING_CPP11
1371 //*************************************************************************
1373 //*************************************************************************
1374 Data_Node& allocate_data_node(rvalue_reference value)
1375 {
1376 Data_Node& node = allocate_data_node();
1377 ::new ((void*)&node.value) value_type(etl::move(value));
1378 ETL_INCREMENT_DEBUG_COUNT
1379 return node;
1380 }
1381#endif
1382
1383 //*************************************************************************
1385 //*************************************************************************
1386 Data_Node& allocate_data_node()
1387 {
1388 Data_Node* (etl::ipool::*func)() = &etl::ipool::allocate<Data_Node>;
1389 return *(p_node_pool->*func)();
1390 }
1391
1392 //*************************************************************************
1394 //*************************************************************************
1395 void destroy_data_node(Data_Node& node)
1396 {
1397 node.value.~value_type();
1398 p_node_pool->release(&node);
1399 ETL_DECREMENT_DEBUG_COUNT
1400 }
1401
1402 //*************************************************************************
1404 //*************************************************************************
1405 Node* find_node(Node* position, key_parameter_t key)
1406 {
1407 Node* found = position;
1408 while (found)
1409 {
1410 // Downcast found to Data_Node class for comparison and other operations
1411 Data_Node& found_data_node = iset::data_cast(*found);
1412
1413 // Compare the node value to the current position value
1414 if (node_comp(key, found_data_node))
1415 {
1416 // Keep searching for the node on the left
1417 found = found->children[kLeft];
1418 }
1419 else if (node_comp(found_data_node, key))
1420 {
1421 // Keep searching for the node on the right
1422 found = found->children[kRight];
1423 }
1424 else
1425 {
1426 // Node that matches the key provided was found, exit loop
1427 break;
1428 }
1429 }
1430
1431 // Return the node found (might be ETL_NULLPTR)
1432 return found;
1433 }
1434
1435#if ETL_USING_CPP11
1436 //*************************************************************************
1437 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
1438 Node* find_node(Node* position, const K& key)
1439 {
1440 Node* found = position;
1441 while (found)
1442 {
1443 // Downcast found to Data_Node class for comparison and other operations
1444 Data_Node& found_data_node = iset::data_cast(*found);
1445
1446 // Compare the node value to the current position value
1447 if (node_comp(key, found_data_node))
1448 {
1449 // Keep searching for the node on the left
1450 found = found->children[kLeft];
1451 }
1452 else if (node_comp(found_data_node, key))
1453 {
1454 // Keep searching for the node on the right
1455 found = found->children[kRight];
1456 }
1457 else
1458 {
1459 // Node that matches the key provided was found, exit loop
1460 break;
1461 }
1462 }
1463
1464 // Return the node found (might be ETL_NULLPTR)
1465 return found;
1466 }
1467#endif
1468
1469 //*************************************************************************
1471 //*************************************************************************
1472 const Node* find_node(const Node* position, key_parameter_t key) const
1473 {
1474 const Node* found = position;
1475 while (found)
1476 {
1477 // Downcast found to Data_Node class for comparison and other operations
1478 const Data_Node& found_data_node = iset::data_cast(*found);
1479
1480 // Compare the node value to the current position value
1481 if (node_comp(key, found_data_node))
1482 {
1483 // Keep searching for the node on the left
1484 found = found->children[kLeft];
1485 }
1486 else if (node_comp(found_data_node, key))
1487 {
1488 // Keep searching for the node on the right
1489 found = found->children[kRight];
1490 }
1491 else
1492 {
1493 // Node that matches the key provided was found, exit loop
1494 break;
1495 }
1496 }
1497
1498 // Return the node found (might be ETL_NULLPTR)
1499 return found;
1500 }
1501
1502#if ETL_USING_CPP11
1503 //*************************************************************************
1504 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
1505 const Node* find_node(const Node* position, const K& key) const
1506 {
1507 const Node* found = position;
1508 while (found)
1509 {
1510 // Downcast found to Data_Node class for comparison and other operations
1511 const Data_Node& found_data_node = iset::data_cast(*found);
1512
1513 // Compare the node value to the current position value
1514 if (node_comp(key, found_data_node))
1515 {
1516 // Keep searching for the node on the left
1517 found = found->children[kLeft];
1518 }
1519 else if (node_comp(found_data_node, key))
1520 {
1521 // Keep searching for the node on the right
1522 found = found->children[kRight];
1523 }
1524 else
1525 {
1526 // Node that matches the key provided was found, exit loop
1527 break;
1528 }
1529 }
1530
1531 // Return the node found (might be ETL_NULLPTR)
1532 return found;
1533 }
1534#endif
1535
1536 //*************************************************************************
1538 //*************************************************************************
1539 Node*& find_node(Node*& position, const Node* node)
1540 {
1541 Node* found = position;
1542 while (found)
1543 {
1544 if (found->children[kLeft] == node)
1545 {
1546 return found->children[kLeft];
1547 }
1548 else if (found->children[kRight] == node)
1549 {
1550 return found->children[kRight];
1551 }
1552 else
1553 {
1554 // Downcast found to Data_Node class for comparison and other operations
1555 Data_Node& found_data_node = iset::data_cast(*found);
1556 const Data_Node& data_node = iset::data_cast(*node);
1557
1558 // Compare the node value to the current position value
1559 if (node_comp(data_node, found_data_node))
1560 {
1561 // Keep searching for the node on the left
1562 found = found->children[kLeft];
1563 }
1564 else if (node_comp(found_data_node, data_node))
1565 {
1566 // Keep searching for the node on the right
1567 found = found->children[kRight];
1568 }
1569 else
1570 {
1571 // Return position provided (it matches the node)
1572 return position;
1573 }
1574 }
1575 }
1576
1577 // Return root node if nothing was found
1578 return root_node;
1579 }
1580
1581 //*************************************************************************
1584 //*************************************************************************
1585 Node* find_parent_node(Node* position, const Node* node)
1586 {
1587 // Default to no parent node found
1588 Node* found = ETL_NULLPTR;
1589
1590 // If the position provided is the same as the node then there is no parent
1591 if (position && node && position != node)
1592 {
1593 while (position)
1594 {
1595 // Is this position not the parent of the node we are looking for?
1596 if (position->children[kLeft] != node &&
1597 position->children[kRight] != node)
1598 {
1599 // Downcast node and position to Data_Node references for key comparisons
1600 const Data_Node& node_data_node = iset::data_cast(*node);
1601 Data_Node& position_data_node = iset::data_cast(*position);
1602 // Compare the node value to the current position value
1603 if (node_comp(node_data_node, position_data_node))
1604 {
1605 // Keep looking for parent on the left
1606 position = position->children[kLeft];
1607 }
1608 else if (node_comp(position_data_node, node_data_node))
1609 {
1610 // Keep looking for parent on the right
1611 position = position->children[kRight];
1612 }
1613 }
1614 else
1615 {
1616 // Return the current position as the parent node found
1617 found = position;
1618
1619 // Parent node found, exit loop
1620 break;
1621 }
1622 }
1623 }
1624
1625 // Return the parent node found (might be ETL_NULLPTR)
1626 return found;
1627 }
1628
1629 //*************************************************************************
1632 //*************************************************************************
1633 const Node* find_parent_node(const Node* position, const Node* node) const
1634 {
1635 // Default to no parent node found
1636 const Node* found = ETL_NULLPTR;
1637
1638 // If the position provided is the same as the node then there is no parent
1639 if (position && node && position != node)
1640 {
1641 while (position)
1642 {
1643 // Is this position not the parent of the node we are looking for?
1644 if (position->children[kLeft] != node &&
1645 position->children[kRight] != node)
1646 {
1647 // Downcast node and position to Data_Node references for key comparisons
1648 const Data_Node& node_data_node = iset::data_cast(*node);
1649 const Data_Node& position_data_node = iset::data_cast(*position);
1650 // Compare the node value to the current position value
1651 if (node_comp(node_data_node, position_data_node))
1652 {
1653 // Keep looking for parent on the left
1654 position = position->children[kLeft];
1655 }
1656 else if (node_comp(position_data_node, node_data_node))
1657 {
1658 // Keep looking for parent on the right
1659 position = position->children[kRight];
1660 }
1661 }
1662 else
1663 {
1664 // Return the current position as the parent node found
1665 found = position;
1666
1667 // Parent node found, exit loop
1668 break;
1669 }
1670 }
1671 }
1672
1673 // Return the parent node found (might be ETL_NULLPTR)
1674 return found;
1675 }
1676
1677 //*************************************************************************
1679 //*************************************************************************
1680 Node* find_lower_node(Node* position, key_parameter_t key) const
1681 {
1682 // Something at this position? keep going
1683 Node* lower_node = ETL_NULLPTR;
1684 while (position)
1685 {
1686 // Downcast lower node to Data_Node reference for key comparisons
1687 Data_Node& data_node = iset::data_cast(*position);
1688 // Compare the key value to the current lower node key value
1689 if (node_comp(key, data_node))
1690 {
1691 lower_node = position;
1692 if (position->children[kLeft])
1693 {
1694 position = position->children[kLeft];
1695 }
1696 else
1697 {
1698 // Found lowest node
1699 break;
1700 }
1701 }
1702 else if (node_comp(data_node, key))
1703 {
1704 position = position->children[kRight];
1705 }
1706 else
1707 {
1708 // Make note of current position, but keep looking to left for more
1709 lower_node = position;
1710 position = position->children[kLeft];
1711 }
1712 }
1713
1714 // Return the lower_node position found
1715 return lower_node;
1716 }
1717
1718#if ETL_USING_CPP11
1719 //*************************************************************************
1720 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
1721 Node* find_lower_node(Node* position, const K& key) const
1722 {
1723 // Something at this position? keep going
1724 Node* lower_node = ETL_NULLPTR;
1725 while (position)
1726 {
1727 // Downcast lower node to Data_Node reference for key comparisons
1728 Data_Node& data_node = iset::data_cast(*position);
1729 // Compare the key value to the current lower node key value
1730 if (node_comp(key, data_node))
1731 {
1732 lower_node = position;
1733 if (position->children[kLeft])
1734 {
1735 position = position->children[kLeft];
1736 }
1737 else
1738 {
1739 // Found lowest node
1740 break;
1741 }
1742 }
1743 else if (node_comp(data_node, key))
1744 {
1745 position = position->children[kRight];
1746 }
1747 else
1748 {
1749 // Make note of current position, but keep looking to left for more
1750 lower_node = position;
1751 position = position->children[kLeft];
1752 }
1753 }
1754
1755 // Return the lower_node position found
1756 return lower_node;
1757 }
1758#endif
1759
1760 //*************************************************************************
1762 //*************************************************************************
1763 Node* find_upper_node(Node* position, key_parameter_t key) const
1764 {
1765 // Keep track of parent of last upper node
1766 Node* upper_node = ETL_NULLPTR;
1767 // Start with position provided
1768 Node* node = position;
1769 while (node)
1770 {
1771 // Downcast position to Data_Node reference for key comparisons
1772 Data_Node& data_node = iset::data_cast(*node);
1773 // Compare the key value to the current upper node key value
1774 if (node_comp(key, data_node))
1775 {
1776 upper_node = node;
1777 node = node->children[kLeft];
1778 }
1779 else if (node_comp(data_node, key))
1780 {
1781 node = node->children[kRight];
1782 }
1783 else if (node->children[kRight])
1784 {
1785 upper_node = find_limit_node(node->children[kRight], kLeft);
1786 break;
1787 }
1788 else
1789 {
1790 break;
1791 }
1792 }
1793
1794 // Return the upper node position found (might be ETL_NULLPTR)
1795 return upper_node;
1796 }
1797
1798#if ETL_USING_CPP11
1799 //*************************************************************************
1800 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
1801 Node* find_upper_node(Node* position, const K& key) const
1802 {
1803 // Keep track of parent of last upper node
1804 Node* upper_node = ETL_NULLPTR;
1805 // Start with position provided
1806 Node* node = position;
1807 while (node)
1808 {
1809 // Downcast position to Data_Node reference for key comparisons
1810 Data_Node& data_node = iset::data_cast(*node);
1811 // Compare the key value to the current upper node key value
1812 if (node_comp(key, data_node))
1813 {
1814 upper_node = node;
1815 node = node->children[kLeft];
1816 }
1817 else if (node_comp(data_node, key))
1818 {
1819 node = node->children[kRight];
1820 }
1821 else if (node->children[kRight])
1822 {
1823 upper_node = find_limit_node(node->children[kRight], kLeft);
1824 break;
1825 }
1826 else
1827 {
1828 break;
1829 }
1830 }
1831
1832 // Return the upper node position found (might be ETL_NULLPTR)
1833 return upper_node;
1834 }
1835#endif
1836
1837 //*************************************************************************
1839 //*************************************************************************
1840 Node* insert_node(Node*& position, Data_Node& node)
1841 {
1842 // Find the location where the node belongs
1843 Node* found = position;
1844
1845 // Was position provided not empty? then find where the node belongs
1846 if (position)
1847 {
1848 // Find the critical parent node (default to ETL_NULLPTR)
1849 Node* critical_parent_node = ETL_NULLPTR;
1850 Node* critical_node = root_node;
1851
1852 while (found)
1853 {
1854 // Search for critical weight node (all nodes whose weight factor
1855 // is set to kNeither (balanced)
1856 if (kNeither != found->weight)
1857 {
1858 critical_node = found;
1859 }
1860
1861 // Downcast found to Data_Node class for comparison and other operations
1862 Data_Node& found_data_node = iset::data_cast(*found);
1863
1864 // Is the node provided to the left of the current position?
1865 if (node_comp(node, found_data_node))
1866 {
1867 // Update direction taken to insert new node in parent node
1868 found->dir = kLeft;
1869 }
1870 // Is the node provided to the right of the current position?
1871 else if (node_comp(found_data_node, node))
1872 {
1873 // Update direction taken to insert new node in parent node
1874 found->dir = kRight;
1875 }
1876 else
1877 {
1878 // Update direction taken to insert new node in parent node
1879 found->dir = kNeither;
1880
1881 // Clear critical node value to skip weight step below
1882 critical_node = ETL_NULLPTR;
1883
1884 // Destroy the node provided (its a duplicate)
1885 destroy_data_node(node);
1886
1887 // Exit loop, duplicate node found
1888 break;
1889 }
1890
1891 // Is there a child of this parent node?
1892 if (found->children[found->dir])
1893 {
1894 // Will this node be the parent of the next critical node whose
1895 // weight factor is set to kNeither (balanced)?
1896 if (kNeither != found->children[found->dir]->weight)
1897 {
1898 critical_parent_node = found;
1899 }
1900
1901 // Keep looking for empty spot to insert new node
1902 found = found->children[found->dir];
1903 }
1904 else
1905 {
1906 // Attach node to right
1907 attach_node(found->children[found->dir], node);
1908
1909 // Return newly added node
1910 found = found->children[found->dir];
1911
1912 // Exit loop
1913 break;
1914 }
1915 }
1916
1917 // Was a critical node found that should be checked for balance?
1918 if (critical_node)
1919 {
1920 if (critical_parent_node == ETL_NULLPTR && critical_node == root_node)
1921 {
1923 }
1924 else if (critical_parent_node == ETL_NULLPTR && critical_node == position)
1925 {
1926 balance_node(position);
1927 }
1928 else
1929 {
1930 if (critical_parent_node != ETL_NULLPTR)
1931 {
1932 balance_node(critical_parent_node->children[critical_parent_node->dir]);
1933 }
1934 }
1935 }
1936 }
1937 else
1938 {
1939 // Attach node to current position
1940 attach_node(position, node);
1941
1942 // Return newly added node at current position
1943 found = position;
1944 }
1945
1946 // Return the node found (might be ETL_NULLPTR)
1947 return found;
1948 }
1949
1950 //*************************************************************************
1952 //*************************************************************************
1953 void next_node(Node*&position)
1954 {
1955 if (position)
1956 {
1957 // Is there a tree on the right? then find the minimum of that tree
1958 if (position->children[kRight])
1959 {
1960 // Return minimum node found
1961 position = find_limit_node(position->children[kRight], kLeft);
1962 }
1963 // Otherwise find the parent of this node
1964 else
1965 {
1966 // Start with current position as parent
1967 Node* parent = position;
1968 do {
1969 // Update current position as previous parent
1970 position = parent;
1971 // Find parent of current position
1972 parent = find_parent_node(root_node, position);
1973 // Repeat while previous position was on right side of parent tree
1974 } while (parent && parent->children[kRight] == position);
1975
1976 // Set parent node as the next position
1977 position = parent;
1978 }
1979 }
1980 }
1981
1982 //*************************************************************************
1984 //*************************************************************************
1985 void next_node(const Node*& position) const
1986 {
1987 if (position)
1988 {
1989 // Is there a tree on the right? then find the minimum of that tree
1990 if (position->children[kRight])
1991 {
1992 // Return minimum node found
1993 position = find_limit_node(position->children[kRight], kLeft);
1994 }
1995 // Otherwise find the parent of this node
1996 else
1997 {
1998 // Start with current position as parent
1999 const Node* parent = position;
2000 do {
2001 // Update current position as previous parent
2002 position = parent;
2003 // Find parent of current position
2004 parent = find_parent_node(root_node, position);
2005 // Repeat while previous position was on right side of parent tree
2006 } while (parent && parent->children[kRight] == position);
2007
2008 // Set parent node as the next position
2009 position = parent;
2010 }
2011 }
2012 }
2013
2014 //*************************************************************************
2016 //*************************************************************************
2017 void prev_node(Node*&position)
2018 {
2019 // If starting at the terminal end, the previous node is the maximum node
2020 // from the root
2021 if (!position)
2022 {
2023 position = find_limit_node(root_node, kRight);
2024 }
2025 else
2026 {
2027 // Is there a tree on the left? then find the maximum of that tree
2028 if (position->children[kLeft])
2029 {
2030 // Return maximum node found
2031 position = find_limit_node(position->children[kLeft], kRight);
2032 }
2033 // Otherwise find the parent of this node
2034 else
2035 {
2036 // Start with current position as parent
2037 Node* parent = position;
2038 do {
2039 // Update current position as previous parent
2040 position = parent;
2041 // Find parent of current position
2042 parent = find_parent_node(root_node, position);
2043 // Repeat while previous position was on left side of parent tree
2044 } while (parent && parent->children[kLeft] == position);
2045
2046 // Set parent node as the next position
2047 position = parent;
2048 }
2049 }
2050 }
2051
2052 //*************************************************************************
2054 //*************************************************************************
2055 void prev_node(const Node*& position) const
2056 {
2057 // If starting at the terminal end, the previous node is the maximum node
2058 // from the root
2059 if (!position)
2060 {
2061 position = find_limit_node(root_node, kRight);
2062 }
2063 else
2064 {
2065 // Is there a tree on the left? then find the maximum of that tree
2066 if (position->children[kLeft])
2067 {
2068 // Return maximum node found
2069 position = find_limit_node(position->children[kLeft], kRight);
2070 }
2071 // Otherwise find the parent of this node
2072 else
2073 {
2074 // Start with current position as parent
2075 const Node* parent = position;
2076 do {
2077 // Update current position as previous parent
2078 position = parent;
2079 // Find parent of current position
2080 parent = find_parent_node(root_node, position);
2081 // Repeat while previous position was on left side of parent tree
2082 } while (parent && parent->children[kLeft] == position);
2083
2084 // Set parent node as the next position
2085 position = parent;
2086 }
2087 }
2088 }
2089
2090 //*************************************************************************
2093 //*************************************************************************
2094 Node* remove_node(Node*& position, key_parameter_t key)
2095 {
2096 // Step 1: Find the target node that matches the key provided, the
2097 // replacement node (might be the same as target node), and the critical
2098 // node to start rebalancing the tree from (up to the replacement node)
2099 Node* found_parent = ETL_NULLPTR;
2100 Node* found = ETL_NULLPTR;
2101 Node* replace_parent = ETL_NULLPTR;
2102 Node* replace = position;
2103 Node* balance_parent = ETL_NULLPTR;
2104 Node* balance = root_node;
2105 while (replace)
2106 {
2107 // Downcast found to Data_Node class for comparison and other operations
2108 Data_Node& replace_data_node = iset::data_cast(*replace);
2109
2110 // Compare the key provided to the replace data node key
2111 if (node_comp(key, replace_data_node))
2112 {
2113 // Update the direction to the target/replace node
2114 replace->dir = kLeft;
2115 }
2116 else if (node_comp(replace_data_node, key))
2117 {
2118 // Update the direction to the target/replace node
2119 replace->dir = kRight;
2120 }
2121 else
2122 {
2123 // Update the direction to the replace node (target node found here)
2124 replace->dir = replace->children[kLeft] ? kLeft : kRight;
2125
2126 // Note the target node was found (and its parent)
2127 found_parent = replace_parent;
2128 found = replace;
2129 }
2130 // Replacement node found if its missing a child in the replace->dir
2131 // value set above
2132 if (replace->children[replace->dir] == ETL_NULLPTR)
2133 {
2134 // Exit loop once replace node is found (target might not have been)
2135 break;
2136 }
2137
2138 // If replacement node weight is kNeither or we are taking the shorter
2139 // path of replacement node and our sibling (on longer path) is
2140 // balanced then we need to update the balance node to match this
2141 // replacement node but all our ancestors will not require rebalancing
2142 if ((replace->weight == kNeither) ||
2143 (replace->weight == (1 - replace->dir) &&
2144 replace->children[1 - replace->dir]->weight == kNeither))
2145 {
2146 // Update balance node (and its parent) to replacement node
2147 balance_parent = replace_parent;
2148 balance = replace;
2149 }
2150
2151 // Keep searching for the replacement node
2152 replace_parent = replace;
2153 replace = replace->children[replace->dir];
2154 }
2155
2156 // If target node was found, proceed with rebalancing and replacement
2157 if (found)
2158 {
2159 // Step 2: Update weights from critical node to replacement parent node
2160 while (balance)
2161 {
2162 if (balance->children[balance->dir] == ETL_NULLPTR)
2163 {
2164 break;
2165 }
2166
2167 if (balance->weight == kNeither)
2168 {
2169 balance->weight = 1 - balance->dir;
2170 }
2171 else if (balance->weight == balance->dir)
2172 {
2173 balance->weight = kNeither;
2174 }
2175 else
2176 {
2177 int weight = balance->children[1 - balance->dir]->weight;
2178 // Perform a 3 node rotation if weight is same as balance->dir
2179 if (weight == balance->dir)
2180 {
2181 // Is the root node being rebalanced (no parent)
2182 if (balance_parent == ETL_NULLPTR)
2183 {
2184 rotate_3node(root_node, 1 - balance->dir,
2185 balance->children[1 - balance->dir]->children[balance->dir]->weight);
2186 }
2187 else
2188 {
2189 rotate_3node(balance_parent->children[balance_parent->dir], 1 - balance->dir,
2190 balance->children[1 - balance->dir]->children[balance->dir]->weight);
2191 }
2192 }
2193 // Already balanced, rebalance and make it heavy in opposite
2194 // direction of the node being removed
2195 else if (weight == kNeither)
2196 {
2197 // Is the root node being rebalanced (no parent)
2198 if (balance_parent == ETL_NULLPTR)
2199 {
2200 rotate_2node(root_node, 1 - balance->dir);
2201 root_node->weight = balance->dir;
2202 }
2203 else
2204 {
2205 rotate_2node(balance_parent->children[balance_parent->dir], 1 - balance->dir);
2206 balance_parent->children[balance_parent->dir]->weight = balance->dir;
2207 }
2208 // Update balance node weight in opposite direction of node removed
2209 balance->weight = 1 - balance->dir;
2210 }
2211 // Rebalance and leave it balanced
2212 else
2213 {
2214 // Is the root node being rebalanced (no parent)
2215 if (balance_parent == ETL_NULLPTR)
2216 {
2217 rotate_2node(root_node, 1 - balance->dir);
2218 }
2219 else
2220 {
2221 rotate_2node(balance_parent->children[balance_parent->dir], 1 - balance->dir);
2222 }
2223 }
2224
2225 // Is balance node the same as the target node found? then update
2226 // its parent after the rotation performed above
2227 if (balance == found)
2228 {
2229 if (balance_parent)
2230 {
2231 found_parent = balance_parent->children[balance_parent->dir];
2232 // Update dir since it is likely stale
2233 found_parent->dir = found_parent->children[kLeft] == found ? kLeft : kRight;
2234 }
2235 else
2236 {
2237 found_parent = root_node;
2238 root_node->dir = root_node->children[kLeft] == found ? kLeft : kRight;
2239 }
2240 }
2241 }
2242
2243 // Next balance node to consider
2244 balance_parent = balance;
2245 balance = balance->children[balance->dir];
2246 } // while(balance)
2247
2248 // Step 3: Swap found node with replacement node
2249 if (found_parent)
2250 {
2251 // Handle traditional case
2252 detach_node(found_parent->children[found_parent->dir],
2253 replace_parent->children[replace_parent->dir]);
2254 }
2255 // Handle root node removal
2256 else
2257 {
2258 // Valid replacement node for root node being removed?
2259 if (replace_parent)
2260 {
2261 detach_node(root_node, replace_parent->children[replace_parent->dir]);
2262 }
2263 else
2264 {
2265 // Target node and replacement node are both root node
2267 }
2268 }
2269
2270 // Downcast found into data node
2271 Data_Node& found_data_node = iset::data_cast(*found);
2272
2273 // One less.
2274 --current_size;
2275
2276 // Destroy the node removed
2277 destroy_data_node(found_data_node);
2278 } // if(found)
2279
2280 // Return node found (might be ETL_NULLPTR)
2281 return found;
2282 }
2283
2284#if ETL_USING_CPP11
2285 //*************************************************************************
2286 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
2287 Node* remove_node(Node*& position, const K& key)
2288 {
2289 // Step 1: Find the target node that matches the key provided, the
2290 // replacement node (might be the same as target node), and the critical
2291 // node to start rebalancing the tree from (up to the replacement node)
2292 Node* found_parent = ETL_NULLPTR;
2293 Node* found = ETL_NULLPTR;
2294 Node* replace_parent = ETL_NULLPTR;
2295 Node* replace = position;
2296 Node* balance_parent = ETL_NULLPTR;
2297 Node* balance = root_node;
2298 while (replace)
2299 {
2300 // Downcast found to Data_Node class for comparison and other operations
2301 Data_Node& replace_data_node = iset::data_cast(*replace);
2302
2303 // Compare the key provided to the replace data node key
2304 if (node_comp(key, replace_data_node))
2305 {
2306 // Update the direction to the target/replace node
2307 replace->dir = kLeft;
2308 }
2309 else if (node_comp(replace_data_node, key))
2310 {
2311 // Update the direction to the target/replace node
2312 replace->dir = kRight;
2313 }
2314 else
2315 {
2316 // Update the direction to the replace node (target node found here)
2317 replace->dir = replace->children[kLeft] ? kLeft : kRight;
2318
2319 // Note the target node was found (and its parent)
2320 found_parent = replace_parent;
2321 found = replace;
2322 }
2323 // Replacement node found if its missing a child in the replace->dir
2324 // value set above
2325 if (replace->children[replace->dir] == ETL_NULLPTR)
2326 {
2327 // Exit loop once replace node is found (target might not have been)
2328 break;
2329 }
2330
2331 // If replacement node weight is kNeither or we are taking the shorter
2332 // path of replacement node and our sibling (on longer path) is
2333 // balanced then we need to update the balance node to match this
2334 // replacement node but all our ancestors will not require rebalancing
2335 if ((replace->weight == kNeither) ||
2336 (replace->weight == (1 - replace->dir) &&
2337 replace->children[1 - replace->dir]->weight == kNeither))
2338 {
2339 // Update balance node (and its parent) to replacement node
2340 balance_parent = replace_parent;
2341 balance = replace;
2342 }
2343
2344 // Keep searching for the replacement node
2345 replace_parent = replace;
2346 replace = replace->children[replace->dir];
2347 }
2348
2349 // If target node was found, proceed with rebalancing and replacement
2350 if (found)
2351 {
2352 // Step 2: Update weights from critical node to replacement parent node
2353 while (balance)
2354 {
2355 if (balance->children[balance->dir] == ETL_NULLPTR)
2356 {
2357 break;
2358 }
2359
2360 if (balance->weight == kNeither)
2361 {
2362 balance->weight = 1 - balance->dir;
2363 }
2364 else if (balance->weight == balance->dir)
2365 {
2366 balance->weight = kNeither;
2367 }
2368 else
2369 {
2370 int weight = balance->children[1 - balance->dir]->weight;
2371 // Perform a 3 node rotation if weight is same as balance->dir
2372 if (weight == balance->dir)
2373 {
2374 // Is the root node being rebalanced (no parent)
2375 if (balance_parent == ETL_NULLPTR)
2376 {
2377 rotate_3node(root_node, 1 - balance->dir,
2378 balance->children[1 - balance->dir]->children[balance->dir]->weight);
2379 }
2380 else
2381 {
2382 rotate_3node(balance_parent->children[balance_parent->dir], 1 - balance->dir,
2383 balance->children[1 - balance->dir]->children[balance->dir]->weight);
2384 }
2385 }
2386 // Already balanced, rebalance and make it heavy in opposite
2387 // direction of the node being removed
2388 else if (weight == kNeither)
2389 {
2390 // Is the root node being rebalanced (no parent)
2391 if (balance_parent == ETL_NULLPTR)
2392 {
2393 rotate_2node(root_node, 1 - balance->dir);
2394 root_node->weight = balance->dir;
2395 }
2396 else
2397 {
2398 rotate_2node(balance_parent->children[balance_parent->dir], 1 - balance->dir);
2399 balance_parent->children[balance_parent->dir]->weight = balance->dir;
2400 }
2401 // Update balance node weight in opposite direction of node removed
2402 balance->weight = 1 - balance->dir;
2403 }
2404 // Rebalance and leave it balanced
2405 else
2406 {
2407 // Is the root node being rebalanced (no parent)
2408 if (balance_parent == ETL_NULLPTR)
2409 {
2410 rotate_2node(root_node, 1 - balance->dir);
2411 }
2412 else
2413 {
2414 rotate_2node(balance_parent->children[balance_parent->dir], 1 - balance->dir);
2415 }
2416 }
2417
2418 // Is balance node the same as the target node found? then update
2419 // its parent after the rotation performed above
2420 if (balance == found)
2421 {
2422 if (balance_parent)
2423 {
2424 found_parent = balance_parent->children[balance_parent->dir];
2425 // Update dir since it is likely stale
2426 found_parent->dir = found_parent->children[kLeft] == found ? kLeft : kRight;
2427 }
2428 else
2429 {
2430 found_parent = root_node;
2431 root_node->dir = root_node->children[kLeft] == found ? kLeft : kRight;
2432 }
2433 }
2434 }
2435
2436 // Next balance node to consider
2437 balance_parent = balance;
2438 balance = balance->children[balance->dir];
2439 } // while(balance)
2440
2441 // Step 3: Swap found node with replacement node
2442 if (found_parent)
2443 {
2444 // Handle traditional case
2445 detach_node(found_parent->children[found_parent->dir],
2446 replace_parent->children[replace_parent->dir]);
2447 }
2448 // Handle root node removal
2449 else
2450 {
2451 // Valid replacement node for root node being removed?
2452 if (replace_parent)
2453 {
2454 detach_node(root_node, replace_parent->children[replace_parent->dir]);
2455 }
2456 else
2457 {
2458 // Target node and replacement node are both root node
2460 }
2461 }
2462
2463 // Downcast found into data node
2464 Data_Node& found_data_node = iset::data_cast(*found);
2465
2466 // One less.
2467 --current_size;
2468
2469 // Destroy the node removed
2470 destroy_data_node(found_data_node);
2471 } // if(found)
2472
2473 // Return node found (might be ETL_NULLPTR)
2474 return found;
2475 }
2476#endif
2477
2478 // Disable copy construction.
2479 iset(const iset&);
2480
2481 //*************************************************************************
2483 //*************************************************************************
2484#if defined(ETL_POLYMORPHIC_SET) || defined(ETL_POLYMORPHIC_CONTAINERS)
2485 public:
2486 virtual ~iset()
2487 {
2488 }
2489#else
2490 protected:
2492 {
2493 }
2494#endif
2495 };
2496
2497 //*************************************************************************
2499 //*************************************************************************
2500 template <typename TKey, const size_t MAX_SIZE_, typename TCompare = etl::less<TKey> >
2501 class set : public etl::iset<TKey, TCompare>
2502 {
2503 public:
2504
2505 static ETL_CONSTANT size_t MAX_SIZE = MAX_SIZE_;
2506
2507 //*************************************************************************
2509 //*************************************************************************
2511 : etl::iset<TKey, TCompare>(node_pool, MAX_SIZE)
2512 {
2513 this->initialise();
2514 }
2515
2516 //*************************************************************************
2518 //*************************************************************************
2519 set(const set& other)
2520 : etl::iset<TKey, TCompare>(node_pool, MAX_SIZE)
2521 {
2522 if (this != &other)
2523 {
2524 this->assign(other.cbegin(), other.cend());
2525 }
2526 }
2527
2528#if ETL_USING_CPP11
2529 //*************************************************************************
2531 //*************************************************************************
2532 set(set&& other)
2533 : etl::iset<TKey, TCompare>(node_pool, MAX_SIZE)
2534 {
2535 if (this != &other)
2536 {
2537 typename etl::iset<TKey, TCompare>::iterator from = other.begin();
2538
2539 while (from != other.end())
2540 {
2541 typename etl::iset<TKey, TCompare>::iterator temp = from;
2542 ++temp;
2543
2544 this->insert(etl::move(*from));
2545 from = temp;
2546 }
2547 }
2548 }
2549#endif
2550
2551 //*************************************************************************
2556 //*************************************************************************
2557 template <typename TIterator>
2558 set(TIterator first, TIterator last)
2559 : etl::iset<TKey, TCompare>(node_pool, MAX_SIZE)
2560 {
2561 this->assign(first, last);
2562 }
2563
2564#if ETL_HAS_INITIALIZER_LIST
2565 //*************************************************************************
2567 //*************************************************************************
2568 set(std::initializer_list<typename etl::iset<TKey, TCompare>::value_type> init)
2569 : etl::iset<TKey, TCompare>(node_pool, MAX_SIZE)
2570 {
2571 this->assign(init.begin(), init.end());
2572 }
2573#endif
2574
2575 //*************************************************************************
2577 //*************************************************************************
2579 {
2580 this->initialise();
2581 }
2582
2583 //*************************************************************************
2585 //*************************************************************************
2586 set& operator = (const set& rhs)
2587 {
2588 // Skip if doing self assignment
2589 if (this != &rhs)
2590 {
2591 this->assign(rhs.cbegin(), rhs.cend());
2592 }
2593
2594 return *this;
2595 }
2596
2597#if ETL_USING_CPP11
2598 //*************************************************************************
2600 //*************************************************************************
2601 set& operator = (set&& rhs)
2602 {
2603 // Skip if doing self assignment
2604 if (this != &rhs)
2605 {
2606 typename etl::iset<TKey, TCompare>::iterator from = rhs.begin();
2607
2608 while (from != rhs.end())
2609 {
2610 typename etl::iset<TKey, TCompare>::iterator temp = from;
2611 ++temp;
2612
2613 this->insert(etl::move(*from));
2614 from = temp;
2615 }
2616 }
2617
2618 return *this;
2619 }
2620#endif
2621
2622 private:
2623
2626 };
2627
2628 template <typename TKey, const size_t MAX_SIZE_, typename TCompare>
2629 ETL_CONSTANT size_t set<TKey, MAX_SIZE_, TCompare>::MAX_SIZE;
2630
2631 //*************************************************************************
2633 //*************************************************************************
2634#if ETL_USING_CPP17 && ETL_HAS_INITIALIZER_LIST
2635 template <typename... T>
2636 set(T...) -> set<etl::nth_type_t<0, T...>, sizeof...(T)>;
2637#endif
2638
2639 //*************************************************************************
2641 //*************************************************************************
2642#if ETL_USING_CPP11 && ETL_HAS_INITIALIZER_LIST
2643 template <typename TKey, typename TCompare = etl::less<TKey>, typename... T>
2644 constexpr auto make_set(T&&... keys) -> etl::set<TKey, sizeof...(T), TCompare>
2645 {
2646 return { {etl::forward<T>(keys)...} };
2647 }
2648#endif
2649
2650 //***************************************************************************
2656 //***************************************************************************
2657 template <typename TKey, typename TCompare>
2659 {
2660 return (lhs.size() == rhs.size()) && etl::equal(lhs.begin(), lhs.end(), rhs.begin());
2661 }
2662
2663 //***************************************************************************
2669 //***************************************************************************
2670 template <typename TKey, typename TCompare>
2672 {
2673 return !(lhs == rhs);
2674 }
2675
2676 //*************************************************************************
2682 //*************************************************************************
2683 template <typename TKey, typename TCompare>
2685 {
2686 return etl::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
2687 }
2688
2689 //*************************************************************************
2695 //*************************************************************************
2696 template <typename TKey, typename TCompare>
2698 {
2699 return (rhs < lhs);
2700 }
2701
2702 //*************************************************************************
2708 //*************************************************************************
2709 template <typename TKey, typename TCompare>
2711 {
2712 return !(lhs > rhs);
2713 }
2714
2715 //*************************************************************************
2721 //*************************************************************************
2722 template <typename TKey, typename TCompare>
2724 {
2725 return !(lhs < rhs);
2726 }
2727}
2728
2729#include "private/minmax_pop.h"
2730
2731#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:2502
set(const set &other)
Copy constructor.
Definition: set.h:2519
set & operator=(const set &rhs)
Assignment operator.
Definition: set.h:2586
set()
Default constructor.
Definition: set.h:2510
set(TIterator first, TIterator last)
Definition: set.h:2558
~set()
Destructor.
Definition: set.h:2578
#define ETL_ASSERT(b, e)
Definition: error_handler.h:316
Definition: exception.h:47
void release(const void *const p_object)
Definition: ipool.h:239
Definition: ipool.h:102
Definition: pool.h:54
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:2491
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:957
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:917
ETL_OR_STD::pair< iterator, bool > insert(const_reference value)
Definition: set.h:1110
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:925
iterator erase(const_iterator first, const_iterator last)
Erases a range of elements.
Definition: set.h:1057
const_iterator find(key_parameter_t key_value) const
Definition: set.h:1091
iterator upper_bound(key_parameter_t key)
Definition: set.h:1266
const_iterator begin() const
Gets the beginning of the set.
Definition: set.h:845
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:853
const_iterator cbegin() const
Gets the beginning of the set.
Definition: set.h:869
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:975
void insert(TIterator first, TIterator last)
Definition: set.h:1211
value_compare value_comp() const
How to compare two value elements.
Definition: set.h:1311
const_iterator end() const
Gets the end of the set.
Definition: set.h:861
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:1014
void assign(TIterator first, TIterator last)
Definition: set.h:938
key_compare key_comp() const
How to compare two key elements.
Definition: set.h:1303
reverse_iterator rbegin()
Gets the reverse beginning of the list.
Definition: set.h:885
const_reverse_iterator rbegin() const
Gets the reverse beginning of the list.
Definition: set.h:893
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:1226
reverse_iterator rend()
Gets the reverse end of the list.
Definition: set.h:901
const_iterator upper_bound(key_parameter_t key) const
Definition: set.h:1286
const_iterator lower_bound(key_parameter_t key) const
Definition: set.h:1246
bool contains(const TKey &key) const
Check if the set contains the key.
Definition: set.h:1319
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:1338
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:837
void initialise()
Initialise the set.
Definition: set.h:1347
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:947
iterator erase(const_iterator position)
Erases the value at the specified position.
Definition: set.h:1023
iterator find(key_parameter_t key_value)
Definition: set.h:1072
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:1161
const_reverse_iterator rend() const
Gets the reverse end of the list.
Definition: set.h:909
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:877
ETL_OR_STD::pair< const_iterator, const_iterator > equal_range(key_parameter_t key) const
Definition: set.h:995
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
pair< T1, T2 > make_pair(T1 a, T2 b)
A convenience wrapper for creating a pair from two objects.
Definition: utility.h:322
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::iset< TKey, TCompare > &lhs, const etl::iset< TKey, TCompare > &rhs)
Template deduction guides.
Definition: set.h:2658
bool operator==(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition: array.h:633
bool operator!=(const etl::iset< TKey, TCompare > &lhs, const etl::iset< TKey, TCompare > &rhs)
Definition: set.h:2671
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 set.
Definition: set.h:481
iterator
Definition: iterator.h:399
etl::conditional< etl::is_fundamental< T >::value||etl::is_pointer< T >::value, T, constT & >::type type
By default fundamental and pointer types are passed by value.
Definition: parameter_type.h:48
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