31#ifndef ETL_MAP_INCLUDED
32#define ETL_MAP_INCLUDED
72 map_exception(string_type reason_, string_type file_name_, numeric_type line_number_)
73 :
exception(reason_, file_name_, line_number_)
86 map_full(string_type file_name_, numeric_type line_number_)
87 :
etl::map_exception(ETL_ERROR_TEXT(
"map:full", ETL_MAP_FILE_ID
"A"), file_name_, line_number_)
101 :
etl::map_exception(ETL_ERROR_TEXT(
"map:bounds", ETL_MAP_FILE_ID
"B"), file_name_, line_number_)
114 map_iterator(string_type file_name_, numeric_type line_number_)
115 :
etl::map_exception(ETL_ERROR_TEXT(
"map:iterator", ETL_MAP_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;
215 weight = uint_least8_t(kNeither);
216 dir = uint_least8_t(kNeither);
217 children[0] = ETL_NULLPTR;
218 children[1] = ETL_NULLPTR;
222 uint_least8_t weight;
252 Node* weight_node = critical_node->children[critical_node->dir];
256 if (uint_least8_t(kNeither) != weight_node->dir)
259 if (weight_node->weight == 1 - weight_node->dir)
261 weight_node->weight = uint_least8_t(kNeither);
265 weight_node->weight = weight_node->dir;
269 weight_node = weight_node->children[weight_node->dir];
279 if (uint_least8_t(kNeither) == critical_node->weight)
281 critical_node->weight = critical_node->dir;
284 else if (critical_node->dir != critical_node->weight)
286 critical_node->weight = uint_least8_t(kNeither);
293 if (critical_node->weight == critical_node->children[critical_node->dir]->dir)
302 critical_node->children[critical_node->dir]->children[1 - critical_node->dir]->dir);
324 Node* new_root = position->children[dir];
326 position->children[dir] = new_root->children[1 - dir];
328 new_root->children[1 - dir] = position;
330 position->weight = uint_least8_t(kNeither);
334 position->weight = uint_least8_t(kNeither);
355 Node* new_root = position->children[dir]->children[1 - dir];
357 position->children[dir]->weight = third != uint_least8_t(kNeither) && third != dir ? dir : uint_least8_t(kNeither);
360 position->children[dir]->children[1 - dir] =
361 new_root->children[dir];
363 new_root->children[dir] = position->children[dir];
365 position->weight = third != uint_least8_t(kNeither) && third == dir ? 1 - dir : uint_least8_t(kNeither);
368 position->children[dir] = new_root->children[1 - dir];
370 new_root->children[1 - dir] = position;
374 position->weight = uint_least8_t(kNeither);
384 Node* limit_node = position;
385 while (limit_node && limit_node->children[dir])
387 limit_node = limit_node->children[dir];
401 const Node* limit_node = position;
402 while (limit_node && limit_node->children[dir])
404 limit_node = limit_node->children[dir];
434 Node* detached = position;
442 replacement =
swap->children[1 -
swap->dir];
445 swap->children[kLeft] = detached->children[kLeft];
446 swap->children[kRight] = detached->children[kRight];
447 swap->weight = detached->weight;
453 ETL_DECLARE_DEBUG_COUNT
460 template <
typename TKey,
typename TMapped,
typename TKeyCompare = etl::less<TKey> >
465 typedef TKey key_type;
466 typedef ETL_OR_STD::pair<const TKey, TMapped> value_type;
467 typedef TMapped mapped_type;
468 typedef TKeyCompare key_compare;
469 typedef value_type& reference;
470 typedef const value_type& const_reference;
472 typedef value_type&& rvalue_reference;
474 typedef value_type* pointer;
475 typedef const value_type* const_pointer;
481 typedef key_type&& rvalue_key_reference;
483 typedef mapped_type& mapped_reference;
484 typedef const mapped_type& const_mapped_reference;
490 bool operator()(const_reference lhs, const_reference rhs)
const
492 return (kcompare(lhs.first, rhs.first));
497 key_compare kcompare;
525 return kcompare(node1.value.first, node2.value.first);
530 return kcompare(node.value.first, key);
535 return kcompare(key, node.value.first);
539 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
540 bool node_comp(
const Data_Node& node,
const K& key)
const
542 return kcompare(node.value.first, key);
545 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
546 bool node_comp(
const K& key,
const Data_Node& node)
const
548 return kcompare(key, node.value.first);
557 key_compare kcompare;
558 value_compare vcompare;
563 static Data_Node* data_cast(Node* p_node)
565 return static_cast<Data_Node*
>(p_node);
571 static Data_Node& data_cast(Node& node)
573 return static_cast<Data_Node&
>(node);
579 static const Data_Node* data_cast(
const Node* p_node)
581 return static_cast<const Data_Node*
>(p_node);
587 static const Data_Node& data_cast(
const Node& node)
589 return static_cast<const Data_Node&
>(node);
606 , p_node(ETL_NULLPTR)
612 , p_node(ETL_NULLPTR)
624 , p_node(other.p_node)
634 p_map->next_node(p_node);
641 p_map->next_node(p_node);
647 p_map->prev_node(p_node);
654 p_map->prev_node(p_node);
661 p_node = other.p_node;
665 reference operator *()
const
667 return imap::data_cast(p_node)->value;
672 return &(imap::data_cast(p_node)->value);
675 pointer operator ->()
const
677 return &(imap::data_cast(p_node)->value);
682 return lhs.p_map == rhs.p_map && lhs.p_node == rhs.p_node;
687 return !(lhs == rhs);
712 , p_node(ETL_NULLPTR)
718 , p_node(ETL_NULLPTR)
730 , p_node(other.p_node)
736 , p_node(other.p_node)
746 p_map->next_node(p_node);
753 p_map->next_node(p_node);
759 p_map->prev_node(p_node);
766 p_map->prev_node(p_node);
773 p_node = other.p_node;
777 const_reference operator *()
const
779 return imap::data_cast(p_node)->value;
784 return imap::data_cast(p_node)->value;
787 const_pointer operator ->()
const
789 return &(imap::data_cast(p_node)->value);
794 return lhs.p_map == rhs.p_map && lhs.p_node == rhs.p_node;
799 return !(lhs == rhs);
819 typedef typename etl::iterator_traits<iterator>::difference_type difference_type;
821 typedef ETL_OR_STD::reverse_iterator<iterator> reverse_iterator;
822 typedef ETL_OR_STD::reverse_iterator<const_iterator> const_reverse_iterator;
877 return reverse_iterator(
iterator(*
this));
899 const_reverse_iterator
rend()
const
915 const_reverse_iterator
crend()
const
926 mapped_reference
operator [](rvalue_key_reference key)
930 if (!i_element.p_node)
933 Node* inserted_node = ETL_NULLPTR;
938 Data_Node& node = allocate_data_node_with_key(etl::move(key));
941 inserted_node = insert_node(
root_node, node);
944 i_element =
iterator(*
this, inserted_node);
947 return i_element->second;
960 if (!i_element.p_node)
963 Node* inserted_node = ETL_NULLPTR;
968 Data_Node& node = allocate_data_node_with_key(key);
971 inserted_node = insert_node(
root_node, node);
974 i_element =
iterator(*
this, inserted_node);
977 return i_element->second;
992 return i_element->second;
997 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
998 mapped_reference
at(
const K& key)
1004 return i_element->second;
1020 return i_element->second;
1025 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1026 const_mapped_reference
at(
const K& key)
const
1028 const_iterator i_element =
find(key);
1032 return i_element->second;
1043 template <
typename TIterator>
1065 return find_node(
root_node, key) ? 1 : 0;
1070 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1071 size_type
count(
const K& key)
const
1073 return find_node(
root_node, key) ? 1 : 0;
1083 return ETL_OR_STD::make_pair<iterator, iterator>(
iterator(*
this, find_lower_node(
root_node, key)),
1089 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1090 ETL_OR_STD::pair<iterator, iterator>
equal_range(
const K& key)
1092 return ETL_OR_STD::make_pair<iterator, iterator>(
iterator(*
this, find_lower_node(
root_node, key)),
1103 return ETL_OR_STD::make_pair<const_iterator, const_iterator>(
const_iterator(*
this, find_lower_node(
root_node, key)),
1109 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1110 ETL_OR_STD::pair<const_iterator, const_iterator>
equal_range(
const K& key)
const
1112 return ETL_OR_STD::make_pair<const_iterator, const_iterator>(const_iterator(*
this, find_lower_node(
root_node, key)),
1113 const_iterator(*
this, find_upper_node(
root_node, key)));
1123 Node*& reference_node = find_node(
root_node, position.p_node);
1124 iterator next(*
this, reference_node);
1127 remove_node(
root_node, (*position).first);
1138 return remove_node(
root_node, key) ? 1 : 0;
1143 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1144 size_type
erase(K&& key)
1147 return remove_node(
root_node, etl::forward<K>(key)) ? 1 : 0;
1156 while (first != last)
1158 first =
erase(first);
1161 return last.to_iterator();
1176 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1195 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1196 const_iterator
find(
const K& k)
const
1198 return const_iterator(*
this, find_node(
root_node, k));
1207 ETL_OR_STD::pair<iterator, bool>
insert(const_reference value)
1210 Node* inserted_node = ETL_NULLPTR;
1211 bool inserted =
false;
1216 Data_Node& node = allocate_data_node(value);
1219 inserted_node = insert_node(
root_node, node);
1220 inserted = inserted_node == &node;
1232 ETL_OR_STD::pair<iterator, bool>
insert(rvalue_reference value)
1235 Node* inserted_node = ETL_NULLPTR;
1236 bool inserted =
false;
1241 Data_Node& node = allocate_data_node(etl::move(value));
1244 inserted_node = insert_node(
root_node, node);
1245 inserted = inserted_node == &node;
1261 Node* inserted_node = ETL_NULLPTR;
1266 Data_Node& node = allocate_data_node(value);
1269 inserted_node = insert_node(
root_node, node);
1272 return iterator(*
this, inserted_node);
1285 Node* inserted_node = ETL_NULLPTR;
1290 Data_Node& node = allocate_data_node(etl::move(value));
1293 inserted_node = insert_node(
root_node, node);
1296 return iterator(*
this, inserted_node);
1307 template <
class TIterator>
1310 while (first != last)
1330 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1350 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1353 return const_iterator(*
this, find_lower_node(
root_node, key));
1370 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1390 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1393 return const_iterator(*
this, find_upper_node(
root_node, key));
1424 while (from != rhs.end())
1426 this->
insert(etl::move(*from));
1461 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1475 , p_node_pool(&node_pool)
1486 while (item !=
end())
1497 Data_Node& allocate_data_node(const_reference value)
1499 Data_Node& node = allocate_data_node();
1500 ::new (&node.value) value_type(value);
1501 ETL_INCREMENT_DEBUG_COUNT
1510 Data_Node& node = allocate_data_node();
1513 ::new ((
void*)
etl::
addressof(node.value.second)) mapped_type();
1514 ETL_INCREMENT_DEBUG_COUNT
1522 Data_Node& allocate_data_node(rvalue_reference value)
1524 Data_Node& node = allocate_data_node();
1525 ::new (&node.value) value_type(
etl::move(value));
1526 ETL_INCREMENT_DEBUG_COUNT
1533 Data_Node& allocate_data_node_with_key(rvalue_key_reference key)
1535 Data_Node& node = allocate_data_node();
1538 ::new ((
void*)
etl::
addressof(node.value.second)) mapped_type();
1539 ETL_INCREMENT_DEBUG_COUNT
1548 Data_Node& allocate_data_node()
1550 Data_Node* (
etl::ipool::*func)() = &etl::ipool::allocate<Data_Node>;
1551 return *(p_node_pool->*func)();
1557 void destroy_data_node(Data_Node& node)
1559 node.value.~value_type();
1560 p_node_pool->release(&node);
1561 ETL_DECREMENT_DEBUG_COUNT
1569 Node* found = position;
1573 Data_Node& found_data_node = imap::data_cast(*found);
1579 found = found->children[kLeft];
1581 else if (
node_comp(found_data_node, key))
1584 found = found->children[kRight];
1599 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1600 Node* find_node(Node* position,
const K& key)
1602 Node* found = position;
1606 Data_Node& found_data_node = imap::data_cast(*found);
1612 found = found->children[kLeft];
1614 else if (
node_comp(found_data_node, key))
1617 found = found->children[kRight];
1636 const Node* found = position;
1640 const Data_Node& found_data_node = imap::data_cast(*found);
1646 found = found->children[kLeft];
1648 else if (
node_comp(found_data_node, key))
1651 found = found->children[kRight];
1666 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1667 const Node* find_node(
const Node* position,
const K& key)
const
1669 const Node* found = position;
1673 const Data_Node& found_data_node = imap::data_cast(*found);
1679 found = found->children[kLeft];
1681 else if (
node_comp(found_data_node, key))
1684 found = found->children[kRight];
1701 Node*& find_node(Node*& position,
const Node* node)
1703 Node* found = position;
1706 if (found->children[kLeft] == node)
1708 return found->children[kLeft];
1710 else if (found->children[kRight] == node)
1712 return found->children[kRight];
1717 Data_Node& found_data_node = imap::data_cast(*found);
1718 const Data_Node& data_node = imap::data_cast(*node);
1721 if (
node_comp(data_node, found_data_node))
1724 found = found->children[kLeft];
1726 else if (
node_comp(found_data_node, data_node))
1729 found = found->children[kRight];
1747 Node* find_parent_node(Node* position,
const Node* node)
1750 Node* found = ETL_NULLPTR;
1753 if (position && node && position != node)
1758 if (position->children[kLeft] != node &&
1759 position->children[kRight] != node)
1762 const Data_Node& node_data_node = imap::data_cast(*node);
1763 Data_Node& position_data_node = imap::data_cast(*position);
1765 if (
node_comp(node_data_node, position_data_node))
1768 position = position->children[kLeft];
1770 else if (
node_comp(position_data_node, node_data_node))
1773 position = position->children[kRight];
1795 const Node* find_parent_node(
const Node* position,
const Node* node)
const
1798 const Node* found = ETL_NULLPTR;
1801 if (position && node && position != node)
1806 if (position->children[kLeft] != node &&
1807 position->children[kRight] != node)
1810 const Data_Node& node_data_node = imap::data_cast(*node);
1811 const Data_Node& position_data_node = imap::data_cast(*position);
1813 if (
node_comp(node_data_node, position_data_node))
1816 position = position->children[kLeft];
1818 else if (
node_comp(position_data_node, node_data_node))
1821 position = position->children[kRight];
1845 Node* lower_node = ETL_NULLPTR;
1849 Data_Node& data_node = imap::data_cast(*position);
1853 lower_node = position;
1854 if (position->children[kLeft])
1856 position = position->children[kLeft];
1866 position = position->children[kRight];
1871 lower_node = position;
1872 position = position->children[kLeft];
1882 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1883 Node* find_lower_node(Node* position,
const K& key)
const
1886 Node* lower_node = ETL_NULLPTR;
1890 Data_Node& data_node = imap::data_cast(*position);
1894 lower_node = position;
1895 if (position->children[kLeft])
1897 position = position->children[kLeft];
1907 position = position->children[kRight];
1912 lower_node = position;
1913 position = position->children[kLeft];
1928 Node* upper_node = ETL_NULLPTR;
1930 Node* node = position;
1934 Data_Node& data_node = imap::data_cast(*node);
1939 node = node->children[kLeft];
1943 node = node->children[kRight];
1945 else if (node->children[kRight])
1962 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1963 Node* find_upper_node(Node* position,
const K& key)
const
1966 Node* upper_node = ETL_NULLPTR;
1968 Node* node = position;
1972 Data_Node& data_node = imap::data_cast(*node);
1977 node = node->children[kLeft];
1981 node = node->children[kRight];
1983 else if (node->children[kRight])
2002 Node* insert_node(Node*& position, Data_Node& node)
2005 Node* found = position;
2011 Node* critical_parent_node = ETL_NULLPTR;
2018 if (kNeither != found->weight)
2020 critical_node = found;
2024 Data_Node& found_data_node = imap::data_cast(*found);
2033 else if (
node_comp(found_data_node, node))
2036 found->dir = kRight;
2041 found->dir = kNeither;
2044 critical_node = ETL_NULLPTR;
2047 destroy_data_node(node);
2054 if (found->children[found->dir])
2058 if (kNeither != found->children[found->dir]->weight)
2060 critical_parent_node = found;
2064 found = found->children[found->dir];
2072 found = found->children[found->dir];
2082 if (critical_parent_node == ETL_NULLPTR && critical_node ==
root_node)
2086 else if (critical_parent_node == ETL_NULLPTR && critical_node == position)
2092 if (critical_parent_node != ETL_NULLPTR)
2094 balance_node(critical_parent_node->children[critical_parent_node->dir]);
2115 void next_node(Node*&position)
2120 if (position->children[kRight])
2129 Node* parent = position;
2134 parent = find_parent_node(
root_node, position);
2136 }
while (parent && parent->children[kRight] == position);
2147 void next_node(
const Node*& position)
const
2152 if (position->children[kRight])
2161 const Node* parent = position;
2166 parent = find_parent_node(
root_node, position);
2168 }
while (parent && parent->children[kRight] == position);
2179 void prev_node(Node*&position)
2190 if (position->children[kLeft])
2199 Node* parent = position;
2204 parent = find_parent_node(
root_node, position);
2206 }
while (parent && parent->children[kLeft] == position);
2217 void prev_node(
const Node*& position)
const
2228 if (position->children[kLeft])
2237 const Node* parent = position;
2242 parent = find_parent_node(
root_node, position);
2244 }
while (parent && parent->children[kLeft] == position);
2261 Node* found_parent = ETL_NULLPTR;
2262 Node* found = ETL_NULLPTR;
2263 Node* replace_parent = ETL_NULLPTR;
2264 Node* replace = position;
2265 Node* balance_parent = ETL_NULLPTR;
2270 Data_Node& replace_data_node = imap::data_cast(*replace);
2276 replace->dir = kLeft;
2278 else if (
node_comp(replace_data_node, key))
2281 replace->dir = kRight;
2286 replace->dir = replace->children[kLeft] ? kLeft : kRight;
2289 found_parent = replace_parent;
2294 if (replace->children[replace->dir] == ETL_NULLPTR)
2304 if ((replace->weight == kNeither) ||
2305 (replace->weight == (1 - replace->dir) &&
2306 replace->children[1 - replace->dir]->weight == kNeither))
2309 balance_parent = replace_parent;
2314 replace_parent = replace;
2315 replace = replace->children[replace->dir];
2324 if (balance->children[balance->dir] == ETL_NULLPTR)
2329 if (balance->weight == kNeither)
2331 balance->weight = 1 - balance->dir;
2333 else if (balance->weight == balance->dir)
2335 balance->weight = kNeither;
2339 int weight = balance->children[1 - balance->dir]->weight;
2341 if (weight == balance->dir)
2344 if (balance_parent == ETL_NULLPTR)
2347 balance->children[1 - balance->dir]->children[balance->dir]->weight);
2351 rotate_3node(balance_parent->children[balance_parent->dir], 1 - balance->dir,
2352 balance->children[1 - balance->dir]->children[balance->dir]->weight);
2357 else if (weight == kNeither)
2360 if (balance_parent == ETL_NULLPTR)
2367 rotate_2node(balance_parent->children[balance_parent->dir], 1 - balance->dir);
2368 balance_parent->children[balance_parent->dir]->weight = balance->dir;
2371 balance->weight = 1 - balance->dir;
2377 if (balance_parent == ETL_NULLPTR)
2383 rotate_2node(balance_parent->children[balance_parent->dir], 1 - balance->dir);
2389 if (balance == found)
2393 found_parent = balance_parent->children[balance_parent->dir];
2395 found_parent->dir = found_parent->children[kLeft] == found ? kLeft : kRight;
2406 balance_parent = balance;
2407 balance = balance->children[balance->dir];
2414 detach_node(found_parent->children[found_parent->dir],
2415 replace_parent->children[replace_parent->dir]);
2433 Data_Node& found_data_node = imap::data_cast(*found);
2439 destroy_data_node(found_data_node);
2451 template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
2452 Node* remove_node(Node*& position,
const K& key)
2457 Node* found_parent = ETL_NULLPTR;
2458 Node* found = ETL_NULLPTR;
2459 Node* replace_parent = ETL_NULLPTR;
2460 Node* replace = position;
2461 Node* balance_parent = ETL_NULLPTR;
2466 Data_Node& replace_data_node = imap::data_cast(*replace);
2472 replace->dir = kLeft;
2474 else if (
node_comp(replace_data_node, key))
2477 replace->dir = kRight;
2482 replace->dir = replace->children[kLeft] ? kLeft : kRight;
2485 found_parent = replace_parent;
2490 if (replace->children[replace->dir] == ETL_NULLPTR)
2500 if ((replace->weight == kNeither) ||
2501 (replace->weight == (1 - replace->dir) &&
2502 replace->children[1 - replace->dir]->weight == kNeither))
2505 balance_parent = replace_parent;
2510 replace_parent = replace;
2511 replace = replace->children[replace->dir];
2520 if (balance->children[balance->dir] == ETL_NULLPTR)
2525 if (balance->weight == kNeither)
2527 balance->weight = 1 - balance->dir;
2529 else if (balance->weight == balance->dir)
2531 balance->weight = kNeither;
2535 int weight = balance->children[1 - balance->dir]->weight;
2537 if (weight == balance->dir)
2540 if (balance_parent == ETL_NULLPTR)
2543 balance->children[1 - balance->dir]->children[balance->dir]->weight);
2547 rotate_3node(balance_parent->children[balance_parent->dir], 1 - balance->dir,
2548 balance->children[1 - balance->dir]->children[balance->dir]->weight);
2553 else if (weight == kNeither)
2556 if (balance_parent == ETL_NULLPTR)
2563 rotate_2node(balance_parent->children[balance_parent->dir], 1 - balance->dir);
2564 balance_parent->children[balance_parent->dir]->weight = balance->dir;
2567 balance->weight = 1 - balance->dir;
2573 if (balance_parent == ETL_NULLPTR)
2579 rotate_2node(balance_parent->children[balance_parent->dir], 1 - balance->dir);
2585 if (balance == found)
2589 found_parent = balance_parent->children[balance_parent->dir];
2591 found_parent->dir = found_parent->children[kLeft] == found ? kLeft : kRight;
2602 balance_parent = balance;
2603 balance = balance->children[balance->dir];
2610 detach_node(found_parent->children[found_parent->dir],
2611 replace_parent->children[replace_parent->dir]);
2629 Data_Node& found_data_node = imap::data_cast(*found);
2635 destroy_data_node(found_data_node);
2649#if defined(ETL_POLYMORPHIC_MAP) || defined(ETL_POLYMORPHIC_CONTAINERS)
2665 template <
typename TKey,
typename TValue, const
size_t MAX_SIZE_,
typename TCompare = etl::less<TKey> >
2670 static ETL_CONSTANT
size_t MAX_SIZE = MAX_SIZE_;
2676 :
etl::
imap<TKey, TValue, TCompare>(node_pool, MAX_SIZE)
2685 :
etl::
imap<TKey, TValue, TCompare>(node_pool, MAX_SIZE)
2698 :
etl::
imap<TKey, TValue, TCompare>(node_pool, MAX_SIZE)
2704 while (from != other.end())
2709 this->
insert(etl::move(*from));
2722 template <
typename TIterator>
2723 map(TIterator first, TIterator last)
2724 :
etl::
imap<TKey, TValue, TCompare>(node_pool, MAX_SIZE)
2726 this->
assign(first, last);
2729#if ETL_HAS_INITIALIZER_LIST
2733 map(std::initializer_list<
typename etl::imap<TKey, TValue, TCompare>::value_type> init)
2734 :
etl::
imap<TKey, TValue, TCompare>(node_pool, MAX_SIZE)
2736 this->
assign(init.begin(), init.end());
2775 while (from != rhs.end())
2780 this->
insert(etl::move(*from));
2795 template <
typename TKey,
typename TValue, const
size_t MAX_SIZE_,
typename TCompare>
2796 ETL_CONSTANT
size_t map<TKey, TValue, MAX_SIZE_, TCompare>::MAX_SIZE;
2801#if ETL_USING_CPP17 && ETL_HAS_INITIALIZER_LIST
2802 template <
typename... TPairs>
2803 map(TPairs...) -> map<
typename etl::nth_type_t<0, TPairs...>::first_type,
2804 typename etl::nth_type_t<0, TPairs...>::second_type,
2811#if ETL_USING_CPP11 && ETL_HAS_INITIALIZER_LIST
2812 template <
typename TKey,
typename TMapped,
typename TKeyCompare = etl::less<TKey>,
typename... TPairs>
2813 constexpr auto make_map(TPairs&&... pairs) ->
etl::map<TKey, TMapped,
sizeof...(TPairs), TKeyCompare>
2815 return { {etl::forward<TPairs>(pairs)...} };
2826 template <
typename TKey,
typename TMapped,
typename TKeyCompare>
2839 template <
typename TKey,
typename TMapped,
typename TKeyCompare>
2842 return !(lhs == rhs);
2852 template <
typename TKey,
typename TMapped,
typename TKeyCompare>
2855 return etl::lexicographical_compare(lhs.
begin(), lhs.
end(), rhs.
begin(), rhs.
end());
2865 template <
typename TKey,
typename TMapped,
typename TKeyCompare>
2878 template <
typename TKey,
typename TMapped,
typename TKeyCompare>
2881 return !(lhs > rhs);
2891 template <
typename TKey,
typename TMapped,
typename TKeyCompare>
2894 return !(lhs < rhs);
const_iterator
Definition: map.h:705
iterator.
Definition: map.h:598
A templated map implementation that uses a fixed size buffer.
Definition: map.h:2667
map(const map &other)
Copy constructor.
Definition: map.h:2684
~map()
Destructor.
Definition: map.h:2743
map(TIterator first, TIterator last)
Definition: map.h:2723
map()
Default constructor.
Definition: map.h:2675
#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
const_reverse_iterator crend() const
Gets the reverse end of the list.
Definition: map.h:915
void detach_node(Node *&position, Node *&replacement)
Detach the node at the position provided.
Definition: map.h:429
imap & operator=(const imap &rhs)
Assignment operator.
Definition: map.h:1400
void rotate_2node(Node *&position, uint_least8_t dir)
Rotate two nodes at the position provided the to balance the tree.
Definition: map.h:310
void clear()
Clears the map.
Definition: map.h:1053
bool empty() const
Checks to see if the map is empty.
Definition: map.h:149
bool full() const
Checks to see if the map is full.
Definition: map.h:157
size_type count(const_key_reference key) const
Definition: map.h:1063
const_iterator end() const
Gets the end of the map.
Definition: map.h:851
iterator erase(const_iterator first, const_iterator last)
Erases a range of elements.
Definition: map.h:1154
const size_type CAPACITY
The maximum size of the map.
Definition: map.h:451
void initialise()
Initialise the map.
Definition: map.h:1482
size_t size_type
The type used for determining the size of map.
Definition: map.h:128
reverse_iterator rend()
Gets the reverse end of the list.
Definition: map.h:891
void assign(TIterator first, TIterator last)
Definition: map.h:1044
void insert(TIterator first, TIterator last)
Definition: map.h:1308
map_base(size_type max_size_)
The constructor that is called from derived classes.
Definition: map.h:229
mapped_reference at(const_key_reference key)
Definition: map.h:986
key_compare key_comp() const
How to compare two key elements.
Definition: map.h:1438
size_type capacity() const
Definition: map.h:166
ETL_OR_STD::pair< iterator, iterator > equal_range(const_key_reference key)
Definition: map.h:1081
~imap()
Destructor.
Definition: map.h:2656
const_mapped_reference at(const_key_reference key) const
Definition: map.h:1014
ETL_OR_STD::pair< const_iterator, const_iterator > equal_range(const_key_reference key) const
Definition: map.h:1101
ETL_OR_STD::pair< iterator, bool > insert(const_reference value)
Definition: map.h:1207
const_iterator cbegin() const
Gets the beginning of the map.
Definition: map.h:859
const_reverse_iterator rbegin() const
Gets the reverse beginning of the list.
Definition: map.h:883
Node * root_node
The node that acts as the map root.
Definition: map.h:452
size_type size() const
Gets the size of the map.
Definition: map.h:133
const_iterator cend() const
Gets the end of the map.
Definition: map.h:867
size_type max_size() const
Gets the maximum possible size of the map.
Definition: map.h:141
iterator find(const_key_reference key)
Definition: map.h:1169
const_iterator upper_bound(const_key_reference key) const
Definition: map.h:1383
const key_type & const_key_reference
Defines the parameter types.
Definition: map.h:479
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: map.h:340
iterator upper_bound(const_key_reference key)
Definition: map.h:1363
iterator lower_bound(const_key_reference key)
Definition: map.h:1323
iterator begin()
Gets the beginning of the map.
Definition: map.h:827
size_t available() const
Definition: map.h:175
const_reverse_iterator crbegin() const
Gets the reverse beginning of the list.
Definition: map.h:907
bool contains(const TKey &key) const
Check if the map contains the key.
Definition: map.h:1454
iterator end()
Gets the end of the map.
Definition: map.h:843
const_reverse_iterator rend() const
Gets the reverse end of the list.
Definition: map.h:899
const_iterator lower_bound(const_key_reference key) const
Definition: map.h:1343
reverse_iterator rbegin()
Gets the reverse beginning of the list.
Definition: map.h:875
iterator erase(const_iterator position)
Erases the value at the specified position.
Definition: map.h:1120
const Node * find_limit_node(const Node *position, const int8_t dir) const
Definition: map.h:398
size_type current_size
The number of the used nodes.
Definition: map.h:450
Node * find_limit_node(Node *position, const int8_t dir) const
Definition: map.h:381
~map_base()
Destructor.
Definition: map.h:240
const_iterator find(const_key_reference key) const
Definition: map.h:1188
mapped_reference operator[](const_key_reference key)
Definition: map.h:956
value_compare value_comp() const
How to compare two value elements.
Definition: map.h:1446
imap(etl::ipool &node_pool, size_t max_size_)
Constructor.
Definition: map.h:1473
void attach_node(Node *&position, Node &node)
Attach the provided node to the position provided.
Definition: map.h:414
iterator insert(const_iterator, const_reference value)
Definition: map.h:1258
const_iterator begin() const
Gets the beginning of the map.
Definition: map.h:835
bool node_comp(const Data_Node &node1, const Data_Node &node2) const
How to compare node elements.
Definition: map.h:523
void balance_node(Node *&critical_node)
Balance the critical node at the position provided as needed.
Definition: map.h:247
ETL_CONSTEXPR17 T * addressof(T &t)
Definition: addressof.h:51
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::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition: array.h:633
bool operator==(const etl::imap< TKey, TMapped, TKeyCompare > &lhs, const etl::imap< TKey, TMapped, TKeyCompare > &rhs)
Template deduction guides.
Definition: map.h:2827
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
bool operator!=(const etl::imap< TKey, TMapped, TKeyCompare > &lhs, const etl::imap< TKey, TMapped, TKeyCompare > &rhs)
Definition: map.h:2840
The data node element in the map.
Definition: map.h:506
iterator
Definition: iterator.h:399
The node element in the map.
Definition: map.h:193
void mark_as_leaf()
Marks the node as a leaf.
Definition: map.h:213
Node()
Constructor.
Definition: map.h:197