31#ifndef ETL_MULTISET_INCLUDED
32#define ETL_MULTISET_INCLUDED
70 multiset_exception(string_type reason_, string_type file_name_, numeric_type line_number_)
84 multiset_full(string_type file_name_, numeric_type line_number_)
113 :
etl::multiset_exception(ETL_ERROR_TEXT(
"multiset:iterator", ETL_MULTISET_FILE_ID
"C"), file_name_, line_number_)
200 children[0] = ETL_NULLPTR;
201 children[1] = ETL_NULLPTR;
211 parent = ETL_NULLPTR;
212 children[0] = ETL_NULLPTR;
213 children[1] = ETL_NULLPTR;
218 uint_least8_t weight;
248 node.parent = parent;
265 Node* detached = position;
273 replacement =
swap->children[1 -
swap->dir];
275 if (replacement != ETL_NULLPTR)
277 replacement->parent =
swap->parent;
281 swap->parent = detached->parent;
282 swap->children[kLeft] = detached->children[kLeft];
283 swap->children[kRight] = detached->children[kRight];
284 if (
swap->children[kLeft])
286 swap->children[kLeft]->parent =
swap;
288 if (
swap->children[kRight])
290 swap->children[kRight]->parent =
swap;
292 swap->weight = detached->weight;
303 Node* weight_node = critical_node->children[critical_node->dir];
307 if (kNeither != weight_node->dir)
310 if (weight_node->weight == 1 - weight_node->dir)
312 weight_node->weight = kNeither;
316 weight_node->weight = weight_node->dir;
320 weight_node = weight_node->children[weight_node->dir];
330 if (kNeither == critical_node->weight)
332 critical_node->weight = critical_node->dir;
335 else if (critical_node->dir != critical_node->weight)
337 critical_node->weight = kNeither;
344 if (critical_node->weight == critical_node->children[critical_node->dir]->dir)
353 critical_node->children[critical_node->dir]->children[1 - critical_node->dir]->dir);
365 Node* limit_node = position;
366 while (limit_node && limit_node->children[dir])
368 limit_node = limit_node->children[dir];
383 if (position->children[kRight])
392 Node* parent = position;
397 parent = position->parent;
399 }
while (parent && parent->children[kRight] == position);
415 if (position->children[kRight])
424 const Node* parent = position;
429 parent = position->parent;
431 }
while (parent && parent->children[kRight] == position);
453 if (position->children[kLeft])
462 Node* parent = position;
467 parent = position->parent;
469 }
while (parent && parent->children[kLeft] == position);
491 if (position->children[kLeft])
500 const Node* parent = position;
505 parent = position->parent;
507 }
while (parent && parent->children[kLeft] == position);
532 Node* new_root = position->children[dir];
535 position->children[dir] = new_root->children[1 - dir];
537 if (position->children[dir])
539 position->children[dir]->parent = position;
543 new_root->parent = position->parent;
544 new_root->children[1 - dir] = position;
545 new_root->dir = 1 - dir;
548 position->weight = kNeither;
550 position->parent = new_root;
553 position->weight = kNeither;
574 Node* new_root = position->children[dir]->children[1 - dir];
576 position->children[dir]->weight = third != kNeither && third != dir ? dir : uint_least8_t(kNeither);
579 position->children[dir]->children[1 - dir] = new_root->children[dir];
581 if (new_root->children[dir])
583 new_root->children[dir]->parent = position->children[dir];
587 new_root->children[dir] = position->children[dir];
588 position->children[dir]->parent = new_root;
591 position->weight = third != kNeither && third == dir ? 1 - dir : kNeither;
594 position->children[dir] = new_root->children[1 - dir];
595 if (new_root->children[1 - dir])
597 new_root->children[1 - dir]->parent = position;
601 new_root->parent = position->parent;
602 new_root->children[1 - dir] = position;
603 new_root->dir = 1 - dir;
606 position->parent = new_root;
609 position->weight = kNeither;
615 ETL_DECLARE_DEBUG_COUNT
622 template <
typename TKey,
typename TCompare = ETL_OR_STD::less<TKey> >
627 typedef TKey key_type;
628 typedef TKey value_type;
629 typedef TCompare key_compare;
630 typedef TCompare value_compare;
631 typedef value_type& reference;
632 typedef const value_type& const_reference;
634 typedef value_type&& rvalue_reference;
636 typedef value_type* pointer;
637 typedef const value_type* const_pointer;
663 return compare(node1.value, node2.value);
668 return compare(node.value, key);
673 return compare(key, node.value);
677 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
678 bool node_comp(
const Data_Node& node,
const K& key)
const
680 return compare(node.value, key);
683 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
684 bool node_comp(
const K& key,
const Data_Node& node)
const
686 return compare(key, node.value);
700 static Data_Node* data_cast(Node* p_node)
702 return static_cast<Data_Node*
>(p_node);
708 static Data_Node& data_cast(Node& node)
710 return static_cast<Data_Node&
>(node);
716 static const Data_Node* data_cast(
const Node* p_node)
718 return static_cast<const Data_Node*
>(p_node);
724 static const Data_Node& data_cast(
const Node& node)
726 return static_cast<const Data_Node&
>(node);
741 : p_multiset(ETL_NULLPTR)
742 , p_node(ETL_NULLPTR)
748 , p_node(ETL_NULLPTR)
759 : p_multiset(other.p_multiset)
760 , p_node(other.p_node)
796 p_multiset = other.p_multiset;
797 p_node = other.p_node;
801 reference operator *()
const
803 return imultiset::data_cast(p_node)->value;
808 return &(imultiset::data_cast(p_node)->value);
811 pointer operator ->()
const
813 return &(imultiset::data_cast(p_node)->value);
818 return lhs.p_multiset == rhs.p_multiset && lhs.p_node == rhs.p_node;
823 return !(lhs == rhs);
847 : p_multiset(ETL_NULLPTR)
848 , p_node(ETL_NULLPTR)
854 , p_node(ETL_NULLPTR)
865 : p_multiset(other.p_multiset)
866 , p_node(other.p_node)
871 : p_multiset(other.p_multiset)
872 , p_node(other.p_node)
908 p_multiset = other.p_multiset;
909 p_node = other.p_node;
913 const_reference operator *()
const
915 return imultiset::data_cast(p_node)->value;
920 return imultiset::data_cast(p_node)->value;
923 const_pointer operator ->()
const
925 return &(imultiset::data_cast(p_node)->value);
930 return lhs.p_multiset == rhs.p_multiset && lhs.p_node == rhs.p_node;
935 return !(lhs == rhs);
955 typedef typename etl::iterator_traits<iterator>::difference_type difference_type;
957 typedef ETL_OR_STD::reverse_iterator<iterator> reverse_iterator;
958 typedef ETL_OR_STD::reverse_iterator<const_iterator> const_reverse_iterator;
1013 return reverse_iterator(
iterator(*
this));
1035 const_reverse_iterator
rend()
const
1063 template <
typename TIterator>
1085 return count_nodes(key);
1090 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1091 size_type
count(
const K& key)
const
1093 return count_nodes(key);
1103 return ETL_OR_STD::make_pair<iterator, iterator>(
iterator(*
this, find_lower_node(
root_node, key)),
1109 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1110 ETL_OR_STD::pair<iterator, iterator>
equal_range(
const K& key)
1112 return ETL_OR_STD::make_pair<iterator, iterator>(
iterator(*
this, find_lower_node(
root_node, key)),
1123 return ETL_OR_STD::make_pair<const_iterator, const_iterator>(
const_iterator(*
this, find_lower_node(
root_node, key)),
1129 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1132 return ETL_OR_STD::make_pair<const_iterator, const_iterator>(const_iterator(*
this, find_lower_node(
root_node, key)),
1133 const_iterator(*
this, find_upper_node(
root_node, key)));
1154 Node* node =
const_cast<Node*
>(position.p_node);
1171 const_iterator lower(*
this, find_lower_node(
root_node, key_value));
1172 const_iterator upper(*
this, find_upper_node(
root_node, key_value));
1173 while (lower != upper)
1178 lower =
erase(lower);
1187 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1188 size_type
erase(K&& key_value)
1192 const_iterator lower(*
this, find_lower_node(
root_node, etl::forward<K>(key_value)));
1193 const_iterator upper(*
this, find_upper_node(
root_node, etl::forward<K>(key_value)));
1194 while (lower != upper)
1199 lower =
erase(lower);
1213 while (first != last)
1215 first =
erase(first);
1218 return last.to_iterator();
1233 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1252 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1253 const_iterator
find(
const K& k)
const
1255 return const_iterator(*
this, find_node(
root_node, k));
1267 Node* inserted_node = ETL_NULLPTR;
1272 Data_Node& node = allocate_data_node(value);
1275 inserted_node = insert_node(
root_node, node);
1278 return iterator(*
this, inserted_node);
1290 Node* inserted_node = ETL_NULLPTR;
1295 Data_Node& node = allocate_data_node(etl::move(value));
1298 inserted_node = insert_node(
root_node, node);
1301 return iterator(*
this, inserted_node);
1327 return insert(etl::move(value));
1338 template <
class TIterator>
1341 while (first != last)
1361 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1381 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1384 return const_iterator(*
this, find_lower_node(
root_node, key));
1401 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1421 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1424 return const_iterator(*
this, find_upper_node(
root_node, key));
1453 while (from != rhs.end())
1458 this->
insert(etl::move(*from));
1493 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1507 , p_node_pool(&node_pool)
1518 while (item !=
end())
1529 Data_Node& allocate_data_node(const_reference value)
1531 Data_Node& node = allocate_data_node();
1532 ::new ((
void*)&node.value) value_type(value);
1533 ETL_INCREMENT_DEBUG_COUNT
1541 Data_Node& allocate_data_node(rvalue_reference value)
1543 Data_Node& node = allocate_data_node();
1544 ::new ((
void*)&node.value) value_type(etl::move(value));
1545 ETL_INCREMENT_DEBUG_COUNT
1553 Data_Node& allocate_data_node()
1555 Data_Node* (
etl::ipool::*func)() = &etl::ipool::allocate<Data_Node>;
1556 return *(p_node_pool->*func)();
1562 void destroy_data_node(Data_Node& node)
1564 node.value.~value_type();
1565 p_node_pool->release(&node);
1566 ETL_DECREMENT_DEBUG_COUNT
1575 size_type result = 0;
1578 const Node* lower = find_lower_node(
root_node, key);
1579 const Node* upper = find_upper_node(
root_node, key);
1582 while (lower != upper)
1585 const Data_Node& data_node = imultiset::data_cast(*lower);
1603 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1604 size_type count_nodes(
const K& key)
const
1607 size_type result = 0;
1610 const Node* lower = find_lower_node(
root_node, key);
1611 const Node* upper = find_upper_node(
root_node, key);
1614 while (lower != upper)
1617 const Data_Node& data_node = imultiset::data_cast(*lower);
1639 Node* found = ETL_NULLPTR;
1643 Data_Node& data_node = imultiset::data_cast(*position);
1648 position = position->children[kLeft];
1653 position = position->children[kRight];
1659 position = position->children[kLeft];
1669 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1670 Node* find_node(Node* position,
const K& key)
1672 Node* found = ETL_NULLPTR;
1676 Data_Node& data_node = imultiset::data_cast(*position);
1681 position = position->children[kLeft];
1686 position = position->children[kRight];
1692 position = position->children[kLeft];
1704 const Node* find_node(
const Node* position,
key_parameter_t key)
const
1706 const Node* found = ETL_NULLPTR;
1710 const Data_Node& data_node = imultiset::data_cast(*position);
1715 position = position->children[kLeft];
1720 position = position->children[kRight];
1726 position = position->children[kLeft];
1736 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1737 const Node* find_node(
const Node* position,
const K& key)
const
1739 const Node* found = ETL_NULLPTR;
1743 const Data_Node& data_node = imultiset::data_cast(*position);
1748 position = position->children[kLeft];
1753 position = position->children[kRight];
1759 position = position->children[kLeft];
1774 Node* lower_node = ETL_NULLPTR;
1778 Data_Node& data_node = imultiset::data_cast(*position);
1782 lower_node = position;
1783 if (position->children[kLeft])
1785 position = position->children[kLeft];
1795 position = position->children[kRight];
1800 lower_node = position;
1801 position = position->children[kLeft];
1811 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1812 Node* find_lower_node(Node* position,
const K& key)
const
1815 Node* lower_node = ETL_NULLPTR;
1819 Data_Node& data_node = imultiset::data_cast(*position);
1823 lower_node = position;
1824 if (position->children[kLeft])
1826 position = position->children[kLeft];
1836 position = position->children[kRight];
1841 lower_node = position;
1842 position = position->children[kLeft];
1857 Node* upper_node = ETL_NULLPTR;
1863 Data_Node& data_node = imultiset::data_cast(*position);
1867 position = position->children[kRight];
1871 upper_node = position;
1873 if (!found && position->children[kLeft])
1875 position = position->children[kLeft];
1896 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1897 Node* find_upper_node(Node* position,
const K& key)
const
1900 Node* upper_node = ETL_NULLPTR;
1906 Data_Node& data_node = imultiset::data_cast(*position);
1910 position = position->children[kRight];
1914 upper_node = position;
1916 if (!found && position->children[kLeft])
1918 position = position->children[kLeft];
1941 Node* insert_node(Node*& position, Data_Node& node)
1944 Node* found = position;
1950 Node* critical_parent_node = ETL_NULLPTR;
1957 if (kNeither != found->weight)
1959 critical_node = found;
1963 Data_Node& found_data_node = imultiset::data_cast(*found);
1972 else if (
node_comp(found_data_node, node))
1975 found->dir = kRight;
1981 found->dir = kRight;
1985 if (found->children[found->dir])
1989 if (kNeither != found->children[found->dir]->weight)
1991 critical_parent_node = found;
1995 found = found->children[found->dir];
2000 attach_node(found, found->children[found->dir], node);
2003 found = found->children[found->dir];
2013 if (critical_parent_node == ETL_NULLPTR && critical_node ==
root_node)
2017 else if (critical_parent_node == ETL_NULLPTR && critical_node == position)
2023 if (critical_parent_node != ETL_NULLPTR)
2025 balance_node(critical_parent_node->children[critical_parent_node->dir]);
2047 void remove_node(Node* node)
2053 Data_Node& data_node = imultiset::data_cast(*node);
2068 node->parent->children[kLeft] == node ? kLeft : kRight;
2071 node = node->parent;
2090 node->dir = node->children[kLeft] ? kLeft : kRight;
2101 if ((node->weight == kNeither) ||
2102 (node->weight == (1 - node->dir) &&
2103 node->children[1 - node->dir]->weight == kNeither))
2110 node = node->children[node->dir];
2124 if (node->children[node->dir] == ETL_NULLPTR)
2134 if ((node->weight == kNeither) ||
2135 (node->weight == (1 - node->dir) &&
2136 node->children[1 - node->dir]->weight == kNeither))
2143 node = node->children[node->dir];
2146 Data_Node& replace_data_node = imultiset::data_cast(*node);
2149 if (
node_comp(data_node, replace_data_node))
2154 else if (
node_comp(replace_data_node, data_node))
2162 node->dir = node->children[kLeft] ? kLeft : kRight;
2171 if (balance->children[balance->dir] == ETL_NULLPTR)
2178 if (balance->weight == kNeither)
2180 balance->weight = 1 - balance->dir;
2184 else if (balance->weight == balance->dir)
2186 balance->weight = kNeither;
2191 int weight = balance->children[1 - balance->dir]->weight;
2193 if (weight == balance->dir)
2196 if (balance->parent == ETL_NULLPTR)
2199 balance->children[1 - balance->dir]->children[balance->dir]->weight);
2203 rotate_3node(balance->parent->children[balance->parent->dir], 1 - balance->dir,
2204 balance->children[1 - balance->dir]->children[balance->dir]->weight);
2209 else if (weight == kNeither)
2212 if (balance->parent == ETL_NULLPTR)
2222 Node* old_parent = balance->parent;
2223 rotate_2node(balance->parent->children[balance->parent->dir], 1 - balance->dir);
2224 old_parent->children[old_parent->dir]->weight = balance->dir;
2227 balance->weight = 1 - balance->dir;
2233 if (balance->parent == ETL_NULLPTR)
2239 rotate_2node(balance->parent->children[balance->parent->dir], 1 - balance->dir);
2245 balance = balance->children[balance->dir];
2252 detach_node(found->parent->children[found->parent->dir],
2253 node->parent->children[node->parent->dir]);
2274 destroy_data_node(data_node);
2284#if defined(ETL_POLYMORPHIC_MULTISET) || defined(ETL_POLYMORPHIC_CONTAINERS)
2300 template <
typename TKey, const
size_t MAX_SIZE_,
typename TCompare = ETL_OR_STD::less<TKey> >
2305 static ETL_CONSTANT
size_t MAX_SIZE = MAX_SIZE_;
2336 while (from != other.end())
2341 this->
insert(etl::move(*from));
2354 template <
typename TIterator>
2358 this->
assign(first, last);
2361#if ETL_HAS_INITIALIZER_LIST
2365 multiset(std::initializer_list<
typename etl::imultiset<TKey, TCompare>::value_type> init)
2368 this->
assign(init.begin(), init.end());
2406 while (from != rhs.end())
2408 this->
insert(etl::move(*from));
2423 template <
typename TKey, const
size_t MAX_SIZE_,
typename TCompare>
2424 ETL_CONSTANT
size_t multiset<TKey, MAX_SIZE_, TCompare>::MAX_SIZE;
2429#if ETL_USING_CPP17 && ETL_HAS_INITIALIZER_LIST
2430 template <
typename... T>
2431 multiset(T...) -> multiset<etl::nth_type_t<0, T...>,
sizeof...(T)>;
2437#if ETL_USING_CPP11 && ETL_HAS_INITIALIZER_LIST
2438 template <
typename TKey,
typename TKeyCompare = etl::less<TKey>,
typename... T>
2439 constexpr auto make_multiset(T&&... keys) ->
etl::multiset<TKey,
sizeof...(T), TKeyCompare>
2441 return { {etl::forward<T>(keys)...} };
2452 template <
typename TKey,
typename TCompare>
2465 template <
typename TKey,
typename TCompare>
2468 return !(lhs == rhs);
2478 template <
typename TKey,
typename TCompare>
2481 return ETL_OR_STD::lexicographical_compare(lhs.
begin(),
2494 template <
typename TKey,
typename TCompare>
2507 template <
typename TKey,
typename TCompare>
2510 return !(lhs > rhs);
2520 template <
typename TKey,
typename TCompare>
2523 return !(lhs < rhs);
const_iterator
Definition: multiset.h:841
iterator.
Definition: multiset.h:734
A templated multiset implementation that uses a fixed size buffer.
Definition: multiset.h:2302
multiset(const multiset &other)
Copy constructor.
Definition: multiset.h:2319
multiset()
Default constructor.
Definition: multiset.h:2310
~multiset()
Destructor.
Definition: multiset.h:2375
multiset & operator=(const multiset &rhs)
Assignment operator.
Definition: multiset.h:2383
multiset(TIterator first, TIterator last)
Definition: multiset.h:2355
#define ETL_ASSERT(b, e)
Definition: error_handler.h:316
Definition: exception.h:47
iterator begin()
Gets the beginning of the multiset.
Definition: multiset.h:963
iterator lower_bound(key_parameter_t key)
Definition: multiset.h:1354
bool full() const
Checks to see if the set is full.
Definition: multiset.h:155
void next_node(const Node *&position) const
Find the next node in sequence from the node provided.
Definition: multiset.h:410
reverse_iterator rbegin()
Gets the reverse beginning of the list.
Definition: multiset.h:1011
iterator insert(const_reference value)
Definition: multiset.h:1264
void clear()
Clears the multiset.
Definition: multiset.h:1073
const_iterator upper_bound(key_parameter_t key) const
Definition: multiset.h:1414
size_type count(key_parameter_t key) const
Definition: multiset.h:1083
imultiset & operator=(const imultiset &rhs)
Assignment operator.
Definition: multiset.h:1431
bool contains(key_parameter_t key) const
Check if the set contains the key.
Definition: multiset.h:1486
bool node_comp(const Data_Node &node1, const Data_Node &node2) const
How to compare node elements.
Definition: multiset.h:661
const size_type CAPACITY
The maximum size of the set.
Definition: multiset.h:613
size_t size_type
The type used for determining the size of set.
Definition: multiset.h:126
const TKey & key_parameter_t
Defines the key value parameter type.
Definition: multiset.h:656
void rotate_2node(Node *&position, uint_least8_t dir)
Rotate two nodes at the position provided the to balance the tree.
Definition: multiset.h:518
const_reverse_iterator crbegin() const
Gets the reverse beginning of the list.
Definition: multiset.h:1043
Node * find_limit_node(Node *position, const int8_t dir) const
Definition: multiset.h:362
iterator erase(const_iterator first, const_iterator last)
Erases a range of elements.
Definition: multiset.h:1210
iterator end()
Gets the end of the multiset.
Definition: multiset.h:979
ETL_OR_STD::pair< const_iterator, const_iterator > equal_range(key_parameter_t key) const
Definition: multiset.h:1121
const_iterator lower_bound(key_parameter_t key) const
Definition: multiset.h:1374
size_type size() const
Gets the size of the set.
Definition: multiset.h:131
void balance_node(Node *&critical_node)
Balance the critical node at the position provided as needed.
Definition: multiset.h:298
const_iterator end() const
Gets the end of the multiset.
Definition: multiset.h:987
const_iterator cend() const
Gets the end of the multiset.
Definition: multiset.h:1003
const_iterator cbegin() const
Gets the beginning of the multiset.
Definition: multiset.h:995
iterator find(key_parameter_t key_value)
Definition: multiset.h:1226
void next_node(Node *&position) const
Find the next node in sequence from the node provided.
Definition: multiset.h:378
void initialise()
Initialise the multiset.
Definition: multiset.h:1514
void assign(TIterator first, TIterator last)
Definition: multiset.h:1064
const_iterator find(key_parameter_t key_value) const
Definition: multiset.h:1245
size_type capacity() const
Definition: multiset.h:164
reverse_iterator rend()
Gets the reverse end of the list.
Definition: multiset.h:1027
void attach_node(Node *parent, Node *&position, Node &node)
Attach the provided node to the position provided.
Definition: multiset.h:242
const_iterator begin() const
Gets the beginning of the multiset.
Definition: multiset.h:971
ETL_OR_STD::pair< iterator, iterator > equal_range(key_parameter_t key)
Definition: multiset.h:1101
void prev_node(Node *&position) const
Find the previous node in sequence from the node provided.
Definition: multiset.h:442
void prev_node(const Node *&position) const
Find the previous node in sequence from the node provided.
Definition: multiset.h:480
imultiset(etl::ipool &node_pool, size_t max_size_)
Constructor.
Definition: multiset.h:1505
Node * root_node
The node that acts as the multiset root.
Definition: multiset.h:614
size_type max_size() const
Gets the maximum possible size of the set.
Definition: multiset.h:139
const_reverse_iterator rend() const
Gets the reverse end of the list.
Definition: multiset.h:1035
~imultiset()
Destructor.
Definition: multiset.h:2291
void insert(TIterator first, TIterator last)
Definition: multiset.h:1339
value_compare value_comp() const
How to compare two value elements.
Definition: multiset.h:1478
~multiset_base()
Destructor.
Definition: multiset.h:235
iterator insert(const_iterator, const_reference value)
Definition: multiset.h:1311
multiset_base(size_type max_size_)
The constructor that is called from derived classes.
Definition: multiset.h:225
iterator upper_bound(key_parameter_t key)
Definition: multiset.h:1394
key_compare key_comp() const
How to compare two key elements.
Definition: multiset.h:1470
iterator erase(const_iterator position)
Erases the value at the specified position.
Definition: multiset.h:1149
const_reverse_iterator rbegin() const
Gets the reverse beginning of the list.
Definition: multiset.h:1019
void detach_node(Node *&position, Node *&replacement)
Detach the node at the position provided.
Definition: multiset.h:260
iterator erase(iterator position)
Erases the value at the specified position.
Definition: multiset.h:1140
const_reverse_iterator crend() const
Gets the reverse end of the list.
Definition: multiset.h:1051
bool empty() const
Checks to see if the set is empty.
Definition: multiset.h:147
size_type current_size
The number of the used nodes.
Definition: multiset.h:612
size_t available() const
Definition: multiset.h:173
void rotate_3node(Node *&position, uint_least8_t dir, uint_least8_t third)
Rotate three nodes at the position provided the to balance the tree.
Definition: multiset.h:559
Definition: multiset.h:624
Definition: multiset.h:123
Definition: multiset.h:67
Definition: multiset.h:81
Definition: multiset.h:109
Definition: multiset.h:95
bitset_ext
Definition: absolute.h:38
bool operator==(const etl::imultiset< TKey, TCompare > &lhs, const etl::imultiset< TKey, TCompare > &rhs)
Template deduction guides.
Definition: multiset.h:2453
bool operator>(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition: array.h:684
etl::byte operator&(etl::byte lhs, etl::byte rhs)
And.
Definition: byte.h:273
bool operator>=(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition: array.h:696
bool operator!=(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition: array.h:645
void swap(etl::array< T, SIZE > &lhs, etl::array< T, SIZE > &rhs)
Template deduction guides.
Definition: array.h:621
bool operator!=(const etl::imultiset< TKey, TCompare > &lhs, const etl::imultiset< TKey, TCompare > &rhs)
Definition: multiset.h:2466
bool operator==(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition: array.h:633
bool operator<(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition: array.h:657
bool operator<=(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition: array.h:672
The data node element in the multiset.
Definition: multiset.h:646
iterator
Definition: iterator.h:399
The node element in the multiset.
Definition: multiset.h:191
void mark_as_leaf()
Marks the node as a leaf.
Definition: multiset.h:207
Node()
Constructor.
Definition: multiset.h:195