31#ifndef ETL_MULTISET_INCLUDED
32#define ETL_MULTISET_INCLUDED
200 children[0] = ETL_NULLPTR;
201 children[1] = ETL_NULLPTR;
211 parent = ETL_NULLPTR;
212 children[0] = ETL_NULLPTR;
213 children[1] = ETL_NULLPTR;
248 node.parent = parent;
284 if (
swap->children[kLeft])
286 swap->children[kLeft]->parent =
swap;
288 if (
swap->children[kRight])
290 swap->children[kRight]->parent =
swap;
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);
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;
548 position->weight = kNeither;
553 position->weight = kNeither;
574 Node*
new_root = position->children[dir]->children[1 - dir];
579 position->children[dir]->children[1 - dir] =
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];
597 new_root->children[1 - dir]->parent = position;
601 new_root->parent = position->parent;
602 new_root->children[1 - dir] = position;
609 position->weight = kNeither;
615 ETL_DECLARE_DEBUG_COUNT;
622 template <
typename TKey,
typename TCompare = ETL_OR_STD::less<TKey> >
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;
803 return imultiset::data_cast(p_node)->value;
808 return &(imultiset::data_cast(p_node)->value);
813 return &(imultiset::data_cast(p_node)->value);
818 return lhs.p_multiset ==
rhs.p_multiset &&
lhs.p_node ==
rhs.p_node;
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)
882 p_multiset->next_node(p_node);
889 p_multiset->next_node(p_node);
895 p_multiset->prev_node(p_node);
902 p_multiset->prev_node(p_node);
908 p_multiset =
other.p_multiset;
909 p_node =
other.p_node;
915 return imultiset::data_cast(p_node)->value;
920 return imultiset::data_cast(p_node)->value;
925 return &(imultiset::data_cast(p_node)->value);
930 return lhs.p_multiset ==
rhs.p_multiset &&
lhs.p_node ==
rhs.p_node;
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);
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)),
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)),
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)));
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)
1194 while (lower != upper)
1199 lower =
erase(lower);
1213 while (first != last)
1215 first =
erase(first);
1218 return last.to_iterator();
1253 const_iterator
find(
const K&
k)
const
1255 return const_iterator(*
this, find_node(
root_node,
k));
1295 Data_Node&
node = allocate_data_node(etl::move(value));
1327 return insert(etl::move(value));
1338 template <
class TIterator>
1341 while (first != last)
1384 return const_iterator(*
this, find_lower_node(
root_node, key));
1424 return const_iterator(*
this, find_upper_node(
root_node, key));
1509 , p_node_pool(&node_pool)
1531 Data_Node& allocate_data_node(const_reference value)
1533 Data_Node*
node = allocate_data_node();
1534 ::new ((
void*)&
node->value) value_type(value);
1535 ETL_INCREMENT_DEBUG_COUNT;
1543 Data_Node& allocate_data_node(rvalue_reference value)
1545 Data_Node* node = allocate_data_node();
1546 ::new ((
void*)&node->value) value_type(etl::move(value));
1547 ETL_INCREMENT_DEBUG_COUNT;
1555 Data_Node* allocate_data_node()
1557 Data_Node* (
etl::ipool::*func)() = &etl::ipool::allocate<Data_Node>;
1558 return (p_node_pool->*func)();
1564 void destroy_data_node(Data_Node& node)
1566 node.value.~value_type();
1567 p_node_pool->release(&node);
1568 ETL_DECREMENT_DEBUG_COUNT;
1577 size_type result = 0;
1580 const Node* lower = find_lower_node(
root_node, key);
1581 const Node* upper = find_upper_node(
root_node, key);
1584 while (lower != upper)
1587 const Data_Node& data_node = imultiset::data_cast(*lower);
1605 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1606 size_type count_nodes(
const K& key)
const
1609 size_type result = 0;
1612 const Node* lower = find_lower_node(
root_node, key);
1613 const Node* upper = find_upper_node(
root_node, key);
1616 while (lower != upper)
1619 const Data_Node& data_node = imultiset::data_cast(*lower);
1641 Node* found = ETL_NULLPTR;
1645 Data_Node& data_node = imultiset::data_cast(*position);
1650 position = position->children[kLeft];
1655 position = position->children[kRight];
1661 position = position->children[kLeft];
1671 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1672 Node* find_node(Node* position,
const K& key)
1674 Node* found = ETL_NULLPTR;
1678 Data_Node& data_node = imultiset::data_cast(*position);
1683 position = position->children[kLeft];
1688 position = position->children[kRight];
1694 position = position->children[kLeft];
1706 const Node* find_node(
const Node* position,
key_parameter_t key)
const
1708 const Node* found = ETL_NULLPTR;
1712 const Data_Node& data_node = imultiset::data_cast(*position);
1717 position = position->children[kLeft];
1722 position = position->children[kRight];
1728 position = position->children[kLeft];
1738 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1739 const Node* find_node(
const Node* position,
const K& key)
const
1741 const Node* found = ETL_NULLPTR;
1745 const Data_Node& data_node = imultiset::data_cast(*position);
1750 position = position->children[kLeft];
1755 position = position->children[kRight];
1761 position = position->children[kLeft];
1776 Node* lower_node = ETL_NULLPTR;
1780 Data_Node& data_node = imultiset::data_cast(*position);
1784 lower_node = position;
1785 if (position->children[kLeft])
1787 position = position->children[kLeft];
1797 position = position->children[kRight];
1802 lower_node = position;
1803 position = position->children[kLeft];
1813 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1814 Node* find_lower_node(Node* position,
const K& key)
const
1817 Node* lower_node = ETL_NULLPTR;
1821 Data_Node& data_node = imultiset::data_cast(*position);
1825 lower_node = position;
1826 if (position->children[kLeft])
1828 position = position->children[kLeft];
1838 position = position->children[kRight];
1843 lower_node = position;
1844 position = position->children[kLeft];
1859 Node* upper_node = ETL_NULLPTR;
1865 Data_Node& data_node = imultiset::data_cast(*position);
1869 position = position->children[kRight];
1873 upper_node = position;
1875 if (!found && position->children[kLeft])
1877 position = position->children[kLeft];
1898 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1899 Node* find_upper_node(Node* position,
const K& key)
const
1902 Node* upper_node = ETL_NULLPTR;
1908 Data_Node& data_node = imultiset::data_cast(*position);
1912 position = position->children[kRight];
1916 upper_node = position;
1918 if (!found && position->children[kLeft])
1920 position = position->children[kLeft];
1943 Node* insert_node(Node*& position, Data_Node& node)
1946 Node* found = position;
1952 Node* critical_parent_node = ETL_NULLPTR;
1959 if (kNeither != found->weight)
1961 critical_node = found;
1965 Data_Node& found_data_node = imultiset::data_cast(*found);
1974 else if (
node_comp(found_data_node, node))
1977 found->dir = kRight;
1983 found->dir = kRight;
1987 if (found->children[found->dir])
1991 if (kNeither != found->children[found->dir]->weight)
1993 critical_parent_node = found;
1997 found = found->children[found->dir];
2002 attach_node(found, found->children[found->dir], node);
2005 found = found->children[found->dir];
2015 if (critical_parent_node == ETL_NULLPTR && critical_node ==
root_node)
2019 else if (critical_parent_node == ETL_NULLPTR && critical_node == position)
2025 if (critical_parent_node != ETL_NULLPTR)
2027 balance_node(critical_parent_node->children[critical_parent_node->dir]);
2049 void remove_node(Node* node)
2055 Data_Node& data_node = imultiset::data_cast(*node);
2070 node->parent->children[kLeft] == node ? kLeft : kRight;
2073 node = node->parent;
2092 node->dir = node->children[kLeft] ? kLeft : kRight;
2103 if ((node->weight == kNeither) ||
2104 (node->weight == (1 - node->dir) &&
2105 node->children[1 - node->dir]->weight == kNeither))
2112 node = node->children[node->dir];
2126 if (node->children[node->dir] == ETL_NULLPTR)
2136 if ((node->weight == kNeither) ||
2137 (node->weight == (1 - node->dir) &&
2138 node->children[1 - node->dir]->weight == kNeither))
2145 node = node->children[node->dir];
2148 Data_Node& replace_data_node = imultiset::data_cast(*node);
2151 if (
node_comp(data_node, replace_data_node))
2156 else if (
node_comp(replace_data_node, data_node))
2164 node->dir = node->children[kLeft] ? kLeft : kRight;
2173 if (balance->children[balance->dir] == ETL_NULLPTR)
2180 if (balance->weight == kNeither)
2182 balance->weight = 1 - balance->dir;
2186 else if (balance->weight == balance->dir)
2188 balance->weight = kNeither;
2193 int weight = balance->children[1 - balance->dir]->weight;
2195 if (weight == balance->dir)
2198 if (balance->parent == ETL_NULLPTR)
2201 balance->children[1 - balance->dir]->children[balance->dir]->weight);
2205 rotate_3node(balance->parent->children[balance->parent->dir], 1 - balance->dir,
2206 balance->children[1 - balance->dir]->children[balance->dir]->weight);
2211 else if (weight == kNeither)
2214 if (balance->parent == ETL_NULLPTR)
2224 Node* old_parent = balance->parent;
2225 rotate_2node(balance->parent->children[balance->parent->dir], 1 - balance->dir);
2226 old_parent->children[old_parent->dir]->weight = balance->dir;
2229 balance->weight = 1 - balance->dir;
2235 if (balance->parent == ETL_NULLPTR)
2241 rotate_2node(balance->parent->children[balance->parent->dir], 1 - balance->dir);
2247 balance = balance->children[balance->dir];
2254 detach_node(found->parent->children[found->parent->dir],
2255 node->parent->children[node->parent->dir]);
2276 destroy_data_node(data_node);
2286#if defined(ETL_POLYMORPHIC_MULTISET) || defined(ETL_POLYMORPHIC_CONTAINERS)
2302 template <
typename TKey, const
size_t MAX_SIZE_,
typename TCompare = ETL_OR_STD::less<TKey> >
2307 static ETL_CONSTANT
size_t MAX_SIZE =
MAX_SIZE_;
2356 template <
typename TIterator>
2360 this->
assign(first, last);
2363#if ETL_HAS_INITIALIZER_LIST
2425 template <
typename TKey, const
size_t MAX_SIZE_,
typename TCompare>
2426 ETL_CONSTANT
size_t multiset<TKey, MAX_SIZE_, TCompare>::MAX_SIZE;
2431#if ETL_USING_CPP17 && ETL_HAS_INITIALIZER_LIST
2432 template <
typename... T>
2439#if ETL_USING_CPP11 && ETL_HAS_INITIALIZER_LIST
2440 template <
typename TKey,
typename TKeyCompare = etl::less<TKey>,
typename... T>
2441 constexpr auto make_multiset(T&&... keys) ->
etl::multiset<TKey,
sizeof...(T), TKeyCompare>
2454 template <
typename TKey,
typename TCompare>
2457 return (
lhs.size() ==
rhs.size()) && ETL_OR_STD::equal(
lhs.begin(),
lhs.end(),
rhs.begin());
2467 template <
typename TKey,
typename TCompare>
2480 template <
typename TKey,
typename TCompare>
2483 return ETL_OR_STD::lexicographical_compare(
lhs.begin(),
2496 template <
typename TKey,
typename TCompare>
2509 template <
typename TKey,
typename TCompare>
2522 template <
typename TKey,
typename TCompare>
const_iterator
Definition multiset.h:841
iterator.
Definition multiset.h:734
A templated multiset implementation that uses a fixed size buffer.
Definition multiset.h:2304
multiset(const multiset &other)
Copy constructor.
Definition multiset.h:2321
multiset()
Default constructor.
Definition multiset.h:2312
~multiset()
Destructor.
Definition multiset.h:2377
multiset & operator=(const multiset &rhs)
Assignment operator.
Definition multiset.h:2385
multiset(TIterator first, TIterator last)
Definition multiset.h:2357
ETL_CONSTEXPR14 bool operator==(const etl::expected< TValue, TError > &lhs, const etl::expected< TValue2, TError2 > &rhs)
Equivalence operators.
Definition expected.h:968
#define ETL_ASSERT(b, e)
Definition error_handler.h:356
Definition exception.h:47
iterator begin()
Gets the beginning of the multiset.
Definition multiset.h:963
iterator lower_bound(key_parameter_t key)
Definition multiset.h:1354
bool full() const
Checks to see if the set is full.
Definition multiset.h:155
void next_node(const Node *&position) const
Find the next node in sequence from the node provided.
Definition multiset.h:410
reverse_iterator rbegin()
Gets the reverse beginning of the list.
Definition multiset.h:1011
iterator insert(const_reference value)
Definition multiset.h:1264
void clear()
Clears the multiset.
Definition multiset.h:1073
const_iterator upper_bound(key_parameter_t key) const
Definition multiset.h:1414
size_type count(key_parameter_t key) const
Definition multiset.h:1083
imultiset & operator=(const imultiset &rhs)
Assignment operator.
Definition multiset.h:1431
bool contains(key_parameter_t key) const
Check if the set contains the key.
Definition multiset.h:1488
bool node_comp(const Data_Node &node1, const Data_Node &node2) const
How to compare node elements.
Definition multiset.h:661
const size_type CAPACITY
The maximum size of the set.
Definition multiset.h:613
size_t size_type
The type used for determining the size of set.
Definition multiset.h:126
const TKey & key_parameter_t
Defines the key value parameter type.
Definition multiset.h:656
void rotate_2node(Node *&position, uint_least8_t dir)
Rotate two nodes at the position provided the to balance the tree.
Definition multiset.h:518
const_reverse_iterator crbegin() const
Gets the reverse beginning of the list.
Definition multiset.h:1043
Node * find_limit_node(Node *position, const int8_t dir) const
Definition multiset.h:362
iterator erase(const_iterator first, const_iterator last)
Erases a range of elements.
Definition multiset.h:1210
iterator end()
Gets the end of the multiset.
Definition multiset.h:979
ETL_OR_STD::pair< const_iterator, const_iterator > equal_range(key_parameter_t key) const
Definition multiset.h:1121
const_iterator lower_bound(key_parameter_t key) const
Definition multiset.h:1374
size_type size() const
Gets the size of the set.
Definition multiset.h:131
void balance_node(Node *&critical_node)
Balance the critical node at the position provided as needed.
Definition multiset.h:298
const_iterator end() const
Gets the end of the multiset.
Definition multiset.h:987
const_iterator cend() const
Gets the end of the multiset.
Definition multiset.h:1003
const_iterator cbegin() const
Gets the beginning of the multiset.
Definition multiset.h:995
iterator find(key_parameter_t key_value)
Definition multiset.h:1226
void next_node(Node *&position) const
Find the next node in sequence from the node provided.
Definition multiset.h:378
void initialise()
Initialise the multiset.
Definition multiset.h:1516
void assign(TIterator first, TIterator last)
Definition multiset.h:1064
const_iterator find(key_parameter_t key_value) const
Definition multiset.h:1245
size_type capacity() const
Definition multiset.h:164
reverse_iterator rend()
Gets the reverse end of the list.
Definition multiset.h:1027
void attach_node(Node *parent, Node *&position, Node &node)
Attach the provided node to the position provided.
Definition multiset.h:242
const_iterator begin() const
Gets the beginning of the multiset.
Definition multiset.h:971
ETL_OR_STD::pair< iterator, iterator > equal_range(key_parameter_t key)
Definition multiset.h:1101
void prev_node(Node *&position) const
Find the previous node in sequence from the node provided.
Definition multiset.h:442
void prev_node(const Node *&position) const
Find the previous node in sequence from the node provided.
Definition multiset.h:480
imultiset(etl::ipool &node_pool, size_t max_size_)
Constructor.
Definition multiset.h:1507
Node * root_node
The node that acts as the multiset root.
Definition multiset.h:614
size_type max_size() const
Gets the maximum possible size of the set.
Definition multiset.h:139
const_reverse_iterator rend() const
Gets the reverse end of the list.
Definition multiset.h:1035
~imultiset()
Destructor.
Definition multiset.h:2293
void insert(TIterator first, TIterator last)
Definition multiset.h:1339
value_compare value_comp() const
How to compare two value elements.
Definition multiset.h:1480
~multiset_base()
Destructor.
Definition multiset.h:235
iterator insert(const_iterator, const_reference value)
Definition multiset.h:1311
multiset_base(size_type max_size_)
The constructor that is called from derived classes.
Definition multiset.h:225
iterator upper_bound(key_parameter_t key)
Definition multiset.h:1394
key_compare key_comp() const
How to compare two key elements.
Definition multiset.h:1472
iterator erase(const_iterator position)
Erases the value at the specified position.
Definition multiset.h:1149
const_reverse_iterator rbegin() const
Gets the reverse beginning of the list.
Definition multiset.h:1019
void detach_node(Node *&position, Node *&replacement)
Detach the node at the position provided.
Definition multiset.h:260
iterator erase(iterator position)
Erases the value at the specified position.
Definition multiset.h:1140
const_reverse_iterator crend() const
Gets the reverse end of the list.
Definition multiset.h:1051
bool empty() const
Checks to see if the set is empty.
Definition multiset.h:147
size_type current_size
The number of the used nodes.
Definition multiset.h:612
size_t available() const
Definition multiset.h:173
void rotate_3node(Node *&position, uint_least8_t dir, uint_least8_t third)
Rotate three nodes at the position provided the to balance the tree.
Definition multiset.h:559
Definition multiset.h:624
Definition multiset.h:123
Definition multiset.h:109
bitset_ext
Definition absolute.h:38
bool operator>(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition array.h:693
bool operator>=(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition array.h:705
bool operator!=(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition array.h:654
void swap(etl::array< T, SIZE > &lhs, etl::array< T, SIZE > &rhs)
Template deduction guides.
Definition array.h:630
bool operator==(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition array.h:642
bool operator<(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition array.h:666
bool operator<=(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition array.h:681
The data node element in the multiset.
Definition multiset.h:646
iterator
Definition iterator.h:399
The node element in the multiset.
Definition multiset.h:191
void mark_as_leaf()
Marks the node as a leaf.
Definition multiset.h:207
Node()
Constructor.
Definition multiset.h:195
pair holds two objects of arbitrary type
Definition utility.h:164