31#ifndef ETL_MULTIMAP_INCLUDED
32#define ETL_MULTIMAP_INCLUDED
71 multimap_exception(string_type reason_, string_type file_name_, numeric_type line_number_)
72 :
exception(reason_, file_name_, line_number_)
85 multimap_full(string_type file_name_, numeric_type line_number_)
100 :
etl::multimap_exception(ETL_ERROR_TEXT(
"multimap:bounds", ETL_MULTIMAP_FILE_ID
"B"), file_name_, line_number_)
114 :
etl::multimap_exception(ETL_ERROR_TEXT(
"multimap:iterator", ETL_MULTIMAP_FILE_ID
"C"), file_name_, line_number_)
198 weight((uint_least8_t) kNeither),
199 dir((uint_least8_t) kNeither)
201 children[0] = ETL_NULLPTR;
202 children[1] = ETL_NULLPTR;
210 weight = (uint_least8_t) kNeither;
211 dir = (uint_least8_t) kNeither;
212 parent = ETL_NULLPTR;
213 children[0] = ETL_NULLPTR;
214 children[1] = ETL_NULLPTR;
219 uint_least8_t weight;
248 Node* weight_node = critical_node->children[critical_node->dir];
252 if ((uint_least8_t) kNeither != weight_node->dir)
255 if (weight_node->weight == 1 - weight_node->dir)
257 weight_node->weight = (uint_least8_t) kNeither;
261 weight_node->weight = weight_node->dir;
265 weight_node = weight_node->children[weight_node->dir];
275 if ((uint_least8_t) kNeither == critical_node->weight)
277 critical_node->weight = critical_node->dir;
280 else if (critical_node->dir != critical_node->weight)
282 critical_node->weight = (uint_least8_t) kNeither;
289 if (critical_node->weight == critical_node->children[critical_node->dir]->dir)
298 critical_node->children[critical_node->dir]->children[1 - critical_node->dir]->dir);
320 Node* new_root = position->children[dir];
323 position->children[dir] = new_root->children[1 - dir];
325 if (position->children[dir])
327 position->children[dir]->parent = position;
331 new_root->parent = position->parent;
332 new_root->children[1 - dir] = position;
333 new_root->dir = 1 - dir;
336 position->weight = (uint_least8_t) kNeither;
338 position->parent = new_root;
341 position->weight = (uint_least8_t) kNeither;
362 Node* new_root = position->children[dir]->children[1 - dir];
364 position->children[dir]->weight = third != (uint_least8_t) kNeither && third != dir ? dir : (uint_least8_t) kNeither;
367 position->children[dir]->children[1 - dir] = new_root->children[dir];
369 if (new_root->children[dir])
371 new_root->children[dir]->parent = position->children[dir];
375 new_root->children[dir] = position->children[dir];
376 position->children[dir]->parent = new_root;
379 position->weight = third != (uint_least8_t) kNeither && third == dir ? 1 - dir : (uint_least8_t) kNeither;
382 position->children[dir] = new_root->children[1 - dir];
383 if (new_root->children[1 - dir])
385 new_root->children[1 - dir]->parent = position;
389 new_root->parent = position->parent;
390 new_root->children[1 - dir] = position;
391 new_root->dir = 1 - dir;
394 position->parent = new_root;
397 position->weight = (uint_least8_t) kNeither;
408 if (position->children[(uint_least8_t) kRight])
411 position =
find_limit_node(position->children[(uint_least8_t) kRight], kLeft);
417 Node* parent = position;
422 parent = position->parent;
424 }
while (parent && parent->children[(uint_least8_t) kRight] == position);
440 if (position->children[(uint_least8_t) kRight])
443 position =
find_limit_node(position->children[(uint_least8_t) kRight], kLeft);
449 const Node* parent = position;
454 parent = position->parent;
456 }
while (parent && parent->children[(uint_least8_t) kRight] == position);
478 if (position->children[(uint_least8_t) kLeft])
481 position =
find_limit_node(position->children[(uint_least8_t) kLeft], kRight);
487 Node* parent = position;
492 parent = position->parent;
494 }
while (parent && parent->children[(uint_least8_t) kLeft] == position);
516 if (position->children[(uint_least8_t) kLeft])
519 position =
find_limit_node(position->children[(uint_least8_t) kLeft], kRight);
525 const Node* parent = position;
530 parent = position->parent;
532 }
while (parent && parent->children[(uint_least8_t) kLeft] == position);
547 Node* limit_node = position;
548 while (limit_node && limit_node->children[dir])
550 limit_node = limit_node->children[dir];
566 node.parent = parent;
583 Node* detached = position;
591 replacement =
swap->children[1 -
swap->dir];
593 if (replacement != ETL_NULLPTR)
595 replacement->parent =
swap->parent;
599 swap->parent = detached->parent;
600 swap->children[(uint_least8_t) kLeft] = detached->children[(uint_least8_t) kLeft];
601 swap->children[(uint_least8_t) kRight] = detached->children[(uint_least8_t) kRight];
602 if (
swap->children[(uint_least8_t) kLeft])
604 swap->children[(uint_least8_t) kLeft]->parent =
swap;
606 if (
swap->children[(uint_least8_t) kRight])
608 swap->children[(uint_least8_t) kRight]->parent =
swap;
610 swap->weight = detached->weight;
616 ETL_DECLARE_DEBUG_COUNT
623 template <
typename TKey,
typename TMapped,
typename TKeyCompare = etl::less<TKey> >
628 typedef ETL_OR_STD::pair<const TKey, TMapped> value_type;
629 typedef const TKey key_type;
630 typedef TMapped mapped_type;
631 typedef TKeyCompare key_compare;
632 typedef value_type& reference;
633 typedef const value_type& const_reference;
635 typedef value_type&& rvalue_reference;
637 typedef value_type* pointer;
638 typedef const value_type* const_pointer;
641 typedef const key_type& const_key_reference;
643 typedef key_type&& rvalue_key_reference;
650 bool operator()(const_reference lhs, const_reference rhs)
const
652 return (kcompare(lhs.first, rhs.first));
657 key_compare kcompare;
680 return kcompare(node1.value.first, node2.value.first);
683 bool node_comp(
const Data_Node& node, const_key_reference key)
const
685 return kcompare(node.value.first, key);
688 bool node_comp(const_key_reference key,
const Data_Node& node)
const
690 return kcompare(key, node.value.first);
694 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
695 bool node_comp(
const Data_Node& node,
const K& key)
const
697 return kcompare(node.value.first, key);
700 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
701 bool node_comp(
const K& key,
const Data_Node& node)
const
703 return kcompare(key, node.value.first);
712 key_compare kcompare;
713 value_compare vcompare;
718 static Data_Node* data_cast(Node* p_node)
720 return static_cast<Data_Node*
>(p_node);
726 static Data_Node& data_cast(Node& node)
728 return static_cast<Data_Node&
>(node);
734 static const Data_Node* data_cast(
const Node* p_node)
736 return static_cast<const Data_Node*
>(p_node);
742 static const Data_Node& data_cast(
const Node& node)
744 return static_cast<const Data_Node&
>(node);
759 : p_multimap(ETL_NULLPTR)
760 , p_node(ETL_NULLPTR)
766 , p_node(ETL_NULLPTR)
777 : p_multimap(other.p_multimap)
778 , p_node(other.p_node)
814 p_multimap = other.p_multimap;
815 p_node = other.p_node;
819 reference operator *()
const
821 return imultimap::data_cast(p_node)->value;
826 return &(imultimap::data_cast(p_node)->value);
829 pointer operator ->()
const
831 return &(imultimap::data_cast(p_node)->value);
836 return lhs.p_multimap == rhs.p_multimap && lhs.p_node == rhs.p_node;
841 return !(lhs == rhs);
864 : p_multimap(ETL_NULLPTR)
865 , p_node(ETL_NULLPTR)
871 , p_node(ETL_NULLPTR)
882 : p_multimap(other.p_multimap)
883 , p_node(other.p_node)
888 : p_multimap(other.p_multimap)
889 , p_node(other.p_node)
925 p_multimap = other.p_multimap;
926 p_node = other.p_node;
930 const_reference operator *()
const
932 return imultimap::data_cast(p_node)->value;
937 return imultimap::data_cast(p_node)->value;
940 const_pointer operator ->()
const
942 return &(imultimap::data_cast(p_node)->value);
947 return lhs.p_multimap == rhs.p_multimap && lhs.p_node == rhs.p_node;
952 return !(lhs == rhs);
971 typedef typename etl::iterator_traits<iterator>::difference_type difference_type;
973 typedef ETL_OR_STD::reverse_iterator<iterator> reverse_iterator;
974 typedef ETL_OR_STD::reverse_iterator<const_iterator> const_reverse_iterator;
1029 return reverse_iterator(
iterator(*
this));
1051 const_reverse_iterator
rend()
const
1079 template <
typename TIterator>
1101 return count_nodes(key);
1106 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1107 size_type
count(
const K& key)
const
1109 return count_nodes(key);
1117 ETL_OR_STD::pair<iterator, iterator>
equal_range(const_key_reference key)
1119 return ETL_OR_STD::make_pair<iterator, iterator>(
iterator(*
this, find_lower_node(
root_node, key)),
1125 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1126 ETL_OR_STD::pair<iterator, iterator>
equal_range(
const K& key)
1128 return ETL_OR_STD::make_pair<iterator, iterator>(
iterator(*
this, find_lower_node(
root_node, key)),
1137 ETL_OR_STD::pair<const_iterator, const_iterator>
equal_range(const_key_reference key)
const
1139 return ETL_OR_STD::make_pair<const_iterator, const_iterator>(
const_iterator(*
this, find_lower_node(
root_node, key)),
1145 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1146 ETL_OR_STD::pair<const_iterator, const_iterator>
equal_range(
const K& key)
const
1148 return ETL_OR_STD::make_pair<const_iterator, const_iterator>(const_iterator(*
this, find_lower_node(
root_node, key)),
1149 const_iterator(*
this, find_upper_node(
root_node, key)));
1170 Node* node =
const_cast<Node*
>(position.p_node);
1183 size_type
erase(const_key_reference key)
1187 const_iterator lower(*
this, find_lower_node(
root_node, key));
1188 const_iterator upper(*
this, find_upper_node(
root_node, key));
1189 while (lower != upper)
1194 lower =
erase(lower);
1203 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1204 size_type
erase(K&& key)
1208 const_iterator lower(*
this, find_lower_node(
root_node, etl::forward<K>(key)));
1209 const_iterator upper(*
this, find_upper_node(
root_node, etl::forward<K>(key)));
1210 while (lower != upper)
1215 lower =
erase(lower);
1228 while (first != last)
1230 first =
erase(first);
1233 return last.to_iterator();
1248 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1267 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1268 const_iterator
find(
const K& k)
const
1270 return const_iterator(*
this, find_node(
root_node, k));
1282 Node* inserted_node = ETL_NULLPTR;
1287 Data_Node& node = allocate_data_node(value);
1290 inserted_node = insert_node(
root_node, node);
1293 return iterator(*
this, inserted_node);
1305 Node* inserted_node = ETL_NULLPTR;
1310 Data_Node& node = allocate_data_node(etl::move(value));
1313 inserted_node = insert_node(
root_node, node);
1316 return iterator(*
this, inserted_node);
1342 return insert(etl::move(value));
1353 template <
class TIterator>
1356 while (first != last)
1376 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1396 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1399 return const_iterator(*
this, find_lower_node(
root_node, key));
1416 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1436 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1439 return const_iterator(*
this, find_upper_node(
root_node, key));
1470 while (from != rhs.end())
1472 this->
insert(etl::move(*from));
1507 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1521 , p_node_pool(&node_pool)
1532 while (item !=
end())
1543 Data_Node& allocate_data_node(const_reference value)
1545 Data_Node& node = allocate_data_node();
1546 ::new (&node.value) const value_type(value);
1547 ETL_INCREMENT_DEBUG_COUNT
1555 Data_Node& allocate_data_node(rvalue_reference value)
1557 Data_Node& node = allocate_data_node();
1558 ::new (&node.value) const value_type(
etl::move(value));
1559 ETL_INCREMENT_DEBUG_COUNT
1567 Data_Node& allocate_data_node()
1569 Data_Node* (
etl::ipool::*func)() = &etl::ipool::allocate<Data_Node>;
1570 return *(p_node_pool->*func)();
1576 void destroy_data_node(Data_Node& node)
1578 node.value.~value_type();
1579 p_node_pool->release(&node);
1580 ETL_DECREMENT_DEBUG_COUNT
1586 size_type count_nodes(const_key_reference key)
const
1589 size_type result = 0;
1592 const Node* lower = find_lower_node(
root_node, key);
1593 const Node* upper = find_upper_node(
root_node, key);
1596 while (lower != upper)
1599 const Data_Node& data_node = imultimap::data_cast(*lower);
1617 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1618 size_type count_nodes(
const K& key)
const
1621 size_type result = 0;
1624 const Node* lower = find_lower_node(
root_node, key);
1625 const Node* upper = find_upper_node(
root_node, key);
1628 while (lower != upper)
1631 const Data_Node& data_node = imultimap::data_cast(*lower);
1651 Node* find_node(Node* position, const_key_reference key)
1653 Node* found = ETL_NULLPTR;
1657 Data_Node& data_node = imultimap::data_cast(*position);
1662 position = position->children[(uint_least8_t) kLeft];
1667 position = position->children[(uint_least8_t) kRight];
1673 position = position->children[(uint_least8_t) kLeft];
1683 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1684 Node* find_node(Node* position,
const K& key)
1686 Node* found = ETL_NULLPTR;
1690 Data_Node& data_node = imultimap::data_cast(*position);
1695 position = position->children[(uint_least8_t)kLeft];
1700 position = position->children[(uint_least8_t)kRight];
1706 position = position->children[(uint_least8_t)kLeft];
1718 const Node* find_node(
const Node* position, const_key_reference key)
const
1720 const Node* found = ETL_NULLPTR;
1724 const Data_Node& data_node = imultimap::data_cast(*position);
1729 position = position->children[(uint_least8_t) kLeft];
1734 position = position->children[(uint_least8_t) kRight];
1740 position = position->children[(uint_least8_t) kLeft];
1752 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1753 const Node* find_node(
const Node* position,
const K& key)
const
1755 const Node* found = ETL_NULLPTR;
1759 const Data_Node& data_node = imultimap::data_cast(*position);
1764 position = position->children[(uint_least8_t)kLeft];
1769 position = position->children[(uint_least8_t)kRight];
1775 position = position->children[(uint_least8_t)kLeft];
1787 Node* find_lower_node(Node* position, const_key_reference key)
const
1790 Node* lower_node = ETL_NULLPTR;
1794 Data_Node& data_node = imultimap::data_cast(*position);
1798 lower_node = position;
1799 if (position->children[(uint_least8_t) kLeft])
1801 position = position->children[(uint_least8_t) kLeft];
1811 position = position->children[(uint_least8_t) kRight];
1816 lower_node = position;
1817 position = position->children[(uint_least8_t) kLeft];
1827 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1828 Node* find_lower_node(Node* position,
const K& key)
const
1831 Node* lower_node = ETL_NULLPTR;
1835 Data_Node& data_node = imultimap::data_cast(*position);
1839 lower_node = position;
1840 if (position->children[(uint_least8_t)kLeft])
1842 position = position->children[(uint_least8_t)kLeft];
1852 position = position->children[(uint_least8_t)kRight];
1857 lower_node = position;
1858 position = position->children[(uint_least8_t)kLeft];
1870 Node* find_upper_node(Node* position, const_key_reference key)
const
1873 Node* upper_node = ETL_NULLPTR;
1879 Data_Node& data_node = imultimap::data_cast(*position);
1883 position = position->children[(uint_least8_t) kRight];
1887 upper_node = position;
1889 if (!found && position->children[(uint_least8_t) kLeft])
1891 position = position->children[(uint_least8_t) kLeft];
1912 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1913 Node* find_upper_node(Node* position,
const K& key)
const
1916 Node* upper_node = ETL_NULLPTR;
1922 Data_Node& data_node = imultimap::data_cast(*position);
1926 position = position->children[(uint_least8_t)kRight];
1930 upper_node = position;
1932 if (!found && position->children[(uint_least8_t)kLeft])
1934 position = position->children[(uint_least8_t)kLeft];
1957 Node* insert_node(Node*& position, Data_Node& node)
1960 Node* found = position;
1966 Node* critical_parent_node = ETL_NULLPTR;
1973 if ((uint_least8_t) kNeither != found->weight)
1975 critical_node = found;
1979 Data_Node& found_data_node = imultimap::data_cast(*found);
1985 found->dir = (uint_least8_t) kLeft;
1988 else if (
node_comp(found_data_node, node))
1991 found->dir = (uint_least8_t) kRight;
1997 found->dir = (uint_least8_t) kRight;
2001 if (found->children[found->dir])
2005 if ((uint_least8_t) kNeither != found->children[found->dir]->weight)
2007 critical_parent_node = found;
2011 found = found->children[found->dir];
2016 attach_node(found, found->children[found->dir], node);
2019 found = found->children[found->dir];
2029 if (critical_parent_node == ETL_NULLPTR && critical_node ==
root_node)
2033 else if (critical_parent_node == ETL_NULLPTR && critical_node == position)
2039 if (critical_parent_node != ETL_NULLPTR)
2041 balance_node(critical_parent_node->children[critical_parent_node->dir]);
2063 void remove_node(Node* node)
2069 Data_Node& data_node = imultimap::data_cast(*node);
2084 node->parent->children[(uint_least8_t) kLeft] == node ? (uint_least8_t) kLeft : (uint_least8_t) kRight;
2087 node = node->parent;
2106 node->dir = node->children[(uint_least8_t) kLeft] ? (uint_least8_t) kLeft : (uint_least8_t) kRight;
2117 if ((node->weight == (uint_least8_t) kNeither) ||
2118 (node->weight == (1 - node->dir) &&
2119 node->children[1 - node->dir]->weight == (uint_least8_t) kNeither))
2126 node = node->children[node->dir];
2140 if (node->children[node->dir] == ETL_NULLPTR)
2150 if ((node->weight == (uint_least8_t) kNeither) ||
2151 (node->weight == (1 - node->dir) &&
2152 node->children[1 - node->dir]->weight == (uint_least8_t) kNeither))
2159 node = node->children[node->dir];
2162 Data_Node& replace_data_node = imultimap::data_cast(*node);
2165 if (
node_comp(data_node, replace_data_node))
2168 node->dir = (uint_least8_t) kLeft;
2170 else if (
node_comp(replace_data_node, data_node))
2173 node->dir = (uint_least8_t) kRight;
2178 node->dir = node->children[(uint_least8_t) kLeft] ? (uint_least8_t) kLeft : (uint_least8_t) kRight;
2187 if (balance->children[balance->dir] == ETL_NULLPTR)
2194 if (balance->weight == (uint_least8_t) kNeither)
2196 balance->weight = 1 - balance->dir;
2200 else if (balance->weight == balance->dir)
2202 balance->weight = (uint_least8_t) kNeither;
2207 int weight = balance->children[1 - balance->dir]->weight;
2209 if (weight == balance->dir)
2212 if (balance->parent == ETL_NULLPTR)
2215 balance->children[1 - balance->dir]->children[balance->dir]->weight);
2219 rotate_3node(balance->parent->children[balance->parent->dir], 1 - balance->dir,
2220 balance->children[1 - balance->dir]->children[balance->dir]->weight);
2225 else if (weight == (uint_least8_t) kNeither)
2228 if (balance->parent == ETL_NULLPTR)
2238 Node* old_parent = balance->parent;
2239 rotate_2node(balance->parent->children[balance->parent->dir], 1 - balance->dir);
2240 old_parent->children[old_parent->dir]->weight = balance->dir;
2243 balance->weight = 1 - balance->dir;
2249 if (balance->parent == ETL_NULLPTR)
2255 rotate_2node(balance->parent->children[balance->parent->dir], 1 - balance->dir);
2261 balance = balance->children[balance->dir];
2268 detach_node(found->parent->children[found->parent->dir],
2269 node->parent->children[node->parent->dir]);
2290 destroy_data_node(data_node);
2300#if defined(ETL_POLYMORPHIC_MULTIMAP) || defined(ETL_POLYMORPHIC_CONTAINERS)
2316 template <
typename TKey,
typename TValue, const
size_t MAX_SIZE_,
typename TCompare = etl::less<TKey> >
2321 static ETL_CONSTANT
size_t MAX_SIZE = MAX_SIZE_;
2327 :
etl::
imultimap<TKey, TValue, TCompare>(node_pool, MAX_SIZE)
2336 :
etl::
imultimap<TKey, TValue, TCompare>(node_pool, MAX_SIZE)
2349 :
etl::
imultimap<TKey, TValue, TCompare>(node_pool, MAX_SIZE)
2355 while (from != other.end())
2360 this->
insert(etl::move(*from));
2373 template <
typename TIterator>
2375 :
etl::
imultimap<TKey, TValue, TCompare>(node_pool, MAX_SIZE)
2377 this->
assign(first, last);
2380#if ETL_HAS_INITIALIZER_LIST
2384 multimap(std::initializer_list<
typename etl::imultimap<TKey, TValue, TCompare>::value_type> init)
2385 :
etl::
imultimap<TKey, TValue, TCompare>(node_pool, MAX_SIZE)
2387 this->
assign(init.begin(), init.end());
2423 while (from != rhs.end())
2428 this->
insert(etl::move(*from));
2443 template <
typename TKey,
typename TValue, const
size_t MAX_SIZE_,
typename TCompare>
2444 ETL_CONSTANT
size_t multimap<TKey, TValue, MAX_SIZE_, TCompare>::MAX_SIZE;
2449#if ETL_USING_CPP17 && ETL_HAS_INITIALIZER_LIST
2450 template <
typename... TPairs>
2451 multimap(TPairs...) -> multimap<
typename etl::nth_type_t<0, TPairs...>::first_type,
2452 typename etl::nth_type_t<0, TPairs...>::second_type,
2459#if ETL_USING_CPP11 && ETL_HAS_INITIALIZER_LIST
2460 template <
typename TKey,
typename TMapped,
typename TKeyCompare = etl::less<TKey>,
typename... TPairs>
2461 constexpr auto make_multimap(TPairs&&... pairs) ->
etl::multimap<TKey, TMapped,
sizeof...(TPairs), TKeyCompare>
2463 return { {etl::forward<TPairs>(pairs)...} };
2474 template <
typename TKey,
typename TMapped,
typename TKeyCompare>
2487 template <
typename TKey,
typename TMapped,
typename TKeyCompare>
2490 return !(lhs == rhs);
2500 template <
typename TKey,
typename TMapped,
typename TKeyCompare>
2503 return etl::lexicographical_compare(lhs.
begin(), lhs.
end(), rhs.
begin(), rhs.
end());
2513 template <
typename TKey,
typename TMapped,
typename TKeyCompare>
2526 template <
typename TKey,
typename TMapped,
typename TKeyCompare>
2529 return !(lhs > rhs);
2539 template <
typename TKey,
typename TMapped,
typename TKeyCompare>
2542 return !(lhs < rhs);
const_iterator
Definition: multimap.h:858
iterator.
Definition: multimap.h:752
Definition: multimap.h:647
A templated multimap implementation that uses a fixed size buffer.
Definition: multimap.h:2318
multimap(TIterator first, TIterator last)
Definition: multimap.h:2374
multimap()
Default constructor.
Definition: multimap.h:2326
~multimap()
Destructor.
Definition: multimap.h:2394
multimap(const multimap &other)
Copy constructor.
Definition: multimap.h:2335
#define ETL_ASSERT(b, e)
Definition: error_handler.h:316
ETL_CONSTEXPR exception(string_type reason_, string_type, numeric_type line_)
Constructor.
Definition: exception.h:69
Definition: exception.h:47
void assign(TIterator first, TIterator last)
Definition: multimap.h:1080
bool contains(const TKey &key) const
Check if the map contains the key.
Definition: multimap.h:1500
iterator find(const_key_reference key)
Definition: multimap.h:1241
void attach_node(Node *parent, Node *&position, Node &node)
Attach the provided node to the position provided.
Definition: multimap.h:560
reverse_iterator rend()
Gets the reverse end of the list.
Definition: multimap.h:1043
reverse_iterator rbegin()
Gets the reverse beginning of the list.
Definition: multimap.h:1027
size_type size() const
Gets the size of the map.
Definition: multimap.h:132
size_type current_size
The number of the used nodes.
Definition: multimap.h:613
void next_node(const Node *&position) const
Find the next node in sequence from the node provided.
Definition: multimap.h:435
iterator lower_bound(const_key_reference key)
Definition: multimap.h:1369
const_reverse_iterator rbegin() const
Gets the reverse beginning of the list.
Definition: multimap.h:1035
const_iterator upper_bound(const_key_reference key) const
Definition: multimap.h:1429
multimap_base(size_type max_size_)
The constructor that is called from derived classes.
Definition: multimap.h:226
const_iterator find(const_key_reference key) const
Definition: multimap.h:1260
imultimap & operator=(const imultimap &rhs)
Assignment operator.
Definition: multimap.h:1446
iterator insert(const_reference value)
Definition: multimap.h:1279
bool node_comp(const Data_Node &node1, const Data_Node &node2) const
How to compare node elements.
Definition: multimap.h:678
iterator erase(const_iterator first, const_iterator last)
Erases a range of elements.
Definition: multimap.h:1226
ETL_OR_STD::pair< iterator, iterator > equal_range(const_key_reference key)
Definition: multimap.h:1117
~multimap_base()
The constructor that is called from derived classes.
Definition: multimap.h:236
void prev_node(const Node *&position) const
Find the previous node in sequence from the node provided.
Definition: multimap.h:505
size_t available() const
Definition: multimap.h:174
iterator end()
Gets the end of the multimap.
Definition: multimap.h:995
void clear()
Clears the multimap.
Definition: multimap.h:1089
void rotate_2node(Node *&position, uint_least8_t dir)
Rotate two nodes at the position provided the to balance the tree.
Definition: multimap.h:306
iterator erase(iterator position)
Erases the value at the specified position.
Definition: multimap.h:1156
const size_type CAPACITY
The maximum size of the map.
Definition: multimap.h:614
void detach_node(Node *&position, Node *&replacement)
Detach the node at the position provided.
Definition: multimap.h:578
const_reverse_iterator rend() const
Gets the reverse end of the list.
Definition: multimap.h:1051
const_iterator end() const
Gets the end of the multimap.
Definition: multimap.h:1003
key_compare key_comp() const
How to compare two key elements.
Definition: multimap.h:1484
const_iterator cend() const
Gets the end of the multimap.
Definition: multimap.h:1019
iterator insert(const_iterator, const_reference value)
Definition: multimap.h:1326
bool empty() const
Checks to see if the map is empty.
Definition: multimap.h:148
void next_node(Node *&position) const
Find the next node in sequence from the node provided.
Definition: multimap.h:403
size_type capacity() const
Definition: multimap.h:165
void prev_node(Node *&position) const
Find the previous node in sequence from the node provided.
Definition: multimap.h:467
Node * root_node
The node that acts as the multimap root.
Definition: multimap.h:615
size_t size_type
The type used for determining the size of map.
Definition: multimap.h:127
const_reverse_iterator crbegin() const
Gets the reverse beginning of the list.
Definition: multimap.h:1059
iterator begin()
Gets the beginning of the multimap.
Definition: multimap.h:979
void insert(TIterator first, TIterator last)
Definition: multimap.h:1354
const_iterator lower_bound(const_key_reference key) const
Definition: multimap.h:1389
size_type max_size() const
Gets the maximum possible size of the map.
Definition: multimap.h:140
ETL_OR_STD::pair< const_iterator, const_iterator > equal_range(const_key_reference key) const
Definition: multimap.h:1137
const_iterator cbegin() const
Gets the beginning of the multimap.
Definition: multimap.h:1011
iterator upper_bound(const_key_reference key)
Definition: multimap.h:1409
size_type count(const_key_reference key) const
Definition: multimap.h:1099
const_reverse_iterator crend() const
Gets the reverse end of the list.
Definition: multimap.h:1067
void initialise()
Initialise the multimap.
Definition: multimap.h:1528
imultimap(etl::ipool &node_pool, size_t max_size_)
Constructor.
Definition: multimap.h:1519
value_compare value_comp() const
How to compare two value elements.
Definition: multimap.h:1492
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: multimap.h:347
Node * find_limit_node(Node *position, const int8_t dir) const
Definition: multimap.h:544
const_iterator begin() const
Gets the beginning of the multimap.
Definition: multimap.h:987
bool full() const
Checks to see if the map is full.
Definition: multimap.h:156
~imultimap()
Destructor.
Definition: multimap.h:2307
iterator erase(const_iterator position)
Erases the value at the specified position.
Definition: multimap.h:1165
void balance_node(Node *&critical_node)
Balance the critical node at the position provided as needed.
Definition: multimap.h:243
Definition: multimap.h:625
Definition: multimap.h:124
Definition: multimap.h:68
Definition: multimap.h:82
Definition: multimap.h:110
Definition: multimap.h:96
bitset_ext
Definition: absolute.h:38
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
bool operator==(const etl::imultimap< TKey, TMapped, TKeyCompare > &lhs, const etl::imultimap< TKey, TMapped, TKeyCompare > &rhs)
Template deduction guides.
Definition: multimap.h:2475
void swap(etl::array< T, SIZE > &lhs, etl::array< T, SIZE > &rhs)
Template deduction guides.
Definition: array.h:621
bool operator!=(const etl::imultimap< TKey, TMapped, TKeyCompare > &lhs, const etl::imultimap< TKey, TMapped, TKeyCompare > &rhs)
Definition: multimap.h:2488
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 multimap.
Definition: multimap.h:666
iterator
Definition: iterator.h:399
The node element in the multimap.
Definition: multimap.h:192
Node()
Constructor.
Definition: multimap.h:196
void mark_as_leaf()
Marks the node as a leaf.
Definition: multimap.h:208