509 return compare(key, node.value);
513 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
514 bool node_comp(
const Data_Node& node,
const K& key)
const
516 return compare(node.value, key);
519 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
520 bool node_comp(
const K& key,
const Data_Node& node)
const
523 return compare(key, node.value);
537 static Data_Node* data_cast(Node* p_node)
539 return static_cast<Data_Node*
>(p_node);
545 static Data_Node& data_cast(Node& node)
547 return static_cast<Data_Node&
>(node);
553 static const Data_Node* data_cast(
const Node* p_node)
555 return static_cast<const Data_Node*
>(p_node);
561 static const Data_Node& data_cast(
const Node& node)
563 return static_cast<const Data_Node&
>(node);
579 , p_node(ETL_NULLPTR)
585 , p_node(ETL_NULLPTR)
597 , p_node(
other.p_node)
607 p_set->next_node(p_node);
614 p_set->next_node(p_node);
620 p_set->prev_node(p_node);
627 p_set->prev_node(p_node);
634 p_node =
other.p_node;
640 return iset::data_cast(p_node)->value;
645 return &(iset::data_cast(p_node)->value);
650 return &(iset::data_cast(p_node)->value);
655 return lhs.p_set ==
rhs.p_set &&
lhs.p_node ==
rhs.p_node;
684 , p_node(ETL_NULLPTR)
690 , p_node(ETL_NULLPTR)
702 , p_node(
other.p_node)
708 , p_node(
other.p_node)
718 p_set->next_node(p_node);
725 p_set->next_node(p_node);
731 p_set->prev_node(p_node);
738 p_set->prev_node(p_node);
745 p_node =
other.p_node;
751 return iset::data_cast(p_node)->value;
756 return iset::data_cast(p_node)->value;
761 return &(iset::data_cast(p_node)->value);
766 return lhs.p_set ==
rhs.p_set &&
lhs.p_node ==
rhs.p_node;
790 typedef typename etl::iterator_traits<iterator>::difference_type difference_type;
792 typedef ETL_OR_STD::reverse_iterator<iterator> reverse_iterator;
793 typedef ETL_OR_STD::reverse_iterator<const_iterator> const_reverse_iterator;
889 return reverse_iterator(
iterator(*
this));
911 const_reverse_iterator
rend()
const
927 const_reverse_iterator
crend()
const
939 template <
typename TIterator>
961 return find_node(
root_node, key) ? 1 : 0;
967 size_type
count(
const K& key)
const
969 return find_node(
root_node, key) ? 1 : 0;
979 return ETL_OR_STD::make_pair<iterator, iterator>(
iterator(*
this, find_lower_node(
root_node, key)),
986 ETL_OR_STD::pair<iterator, iterator>
equal_range(
const K& key)
988 return ETL_OR_STD::make_pair<iterator, iterator>(
iterator(*
this, find_lower_node(
root_node, key)),
999 return ETL_OR_STD::make_pair<const_iterator, const_iterator>(
const_iterator(*
this, find_lower_node(
root_node, key)),
1006 ETL_OR_STD::pair<const_iterator, const_iterator>
equal_range(
const K& key)
const
1008 return ETL_OR_STD::make_pair<const_iterator, const_iterator>(const_iterator(*
this, find_lower_node(
root_node, key)),
1009 const_iterator(*
this, find_upper_node(
root_node, key)));
1048 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1049 size_type
erase(K&& key_value)
1061 while (first != last)
1063 first =
erase(first);
1066 return last.to_iterator();
1123 ETL_ASSERT_FAIL(ETL_ERROR(
set_full));
1127 return ETL_OR_STD::make_pair(iter,
false);
1159 ETL_ASSERT_FAIL(ETL_ERROR(
set_full));
1163 return ETL_OR_STD::make_pair(iter,
false);
1168 Data_Node& node = allocate_data_node(etl::move(value));
1171 inserted_node = insert_node(
root_node, node);
1172 inserted = inserted_node == &node;
1175 return ETL_OR_STD::make_pair(iterator(*
this, inserted_node), inserted);
1195 ETL_ASSERT_FAIL(ETL_ERROR(
set_full));
1230 ETL_ASSERT_FAIL(ETL_ERROR(
set_full));
1239 Data_Node& node = allocate_data_node(etl::move(value));
1242 inserted_node = insert_node(
root_node, node);
1245 return iterator(*
this, inserted_node);
1256 template <
class TIterator>
1259 while (first != last)
1302 return const_iterator(*
this, find_lower_node(
root_node, key));
1342 return const_iterator(*
this, find_upper_node(
root_node, key));
1386 , p_node_pool(&node_pool)
1408 Data_Node& allocate_data_node(const_reference value)
1410 Data_Node*
node = allocate_data_node();
1411 ::new ((
void*)&
node->value) value_type(value);
1412 ETL_INCREMENT_DEBUG_COUNT;
1420 Data_Node& allocate_data_node(rvalue_reference value)
1422 Data_Node* node = allocate_data_node();
1423 ::new ((
void*)&node->value) value_type(etl::move(value));
1424 ETL_INCREMENT_DEBUG_COUNT;
1432 Data_Node* allocate_data_node()
1434 Data_Node* (
etl::ipool::*func)() = &etl::ipool::allocate<Data_Node>;
1435 return (p_node_pool->*func)();
1441 void destroy_data_node(Data_Node& node)
1443 node.value.~value_type();
1445 ETL_DECREMENT_DEBUG_COUNT;
1453 Node* found = position;
1457 Data_Node& found_data_node = iset::data_cast(*found);
1463 found = found->children[kLeft];
1465 else if (
node_comp(found_data_node, key))
1468 found = found->children[kRight];
1483 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1484 Node* find_node(Node* position,
const K& key)
1486 Node* found = position;
1490 Data_Node& found_data_node = iset::data_cast(*found);
1496 found = found->children[kLeft];
1498 else if (
node_comp(found_data_node, key))
1501 found = found->children[kRight];
1518 const Node* find_node(
const Node* position,
key_parameter_t key)
const
1520 const Node* found = position;
1524 const Data_Node& found_data_node = iset::data_cast(*found);
1530 found = found->children[kLeft];
1532 else if (
node_comp(found_data_node, key))
1535 found = found->children[kRight];
1550 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1551 const Node* find_node(
const Node* position,
const K& key)
const
1553 const Node* found = position;
1557 const Data_Node& found_data_node = iset::data_cast(*found);
1563 found = found->children[kLeft];
1565 else if (
node_comp(found_data_node, key))
1568 found = found->children[kRight];
1585 Node*& find_node(Node*& position,
const Node* node)
1587 Node* found = position;
1590 if (found->children[kLeft] == node)
1592 return found->children[kLeft];
1594 else if (found->children[kRight] == node)
1596 return found->children[kRight];
1601 Data_Node& found_data_node = iset::data_cast(*found);
1602 const Data_Node& data_node = iset::data_cast(*node);
1605 if (
node_comp(data_node, found_data_node))
1608 found = found->children[kLeft];
1610 else if (
node_comp(found_data_node, data_node))
1613 found = found->children[kRight];
1631 Node* find_parent_node(Node* position,
const Node* node)
1634 Node* found = ETL_NULLPTR;
1637 if (position && node && position != node)
1642 if (position->children[kLeft] != node &&
1643 position->children[kRight] != node)
1646 const Data_Node& node_data_node = iset::data_cast(*node);
1647 Data_Node& position_data_node = iset::data_cast(*position);
1649 if (
node_comp(node_data_node, position_data_node))
1652 position = position->children[kLeft];
1654 else if (
node_comp(position_data_node, node_data_node))
1657 position = position->children[kRight];
1679 const Node* find_parent_node(
const Node* position,
const Node* node)
const
1682 const Node* found = ETL_NULLPTR;
1685 if (position && node && position != node)
1690 if (position->children[kLeft] != node &&
1691 position->children[kRight] != node)
1694 const Data_Node& node_data_node = iset::data_cast(*node);
1695 const Data_Node& position_data_node = iset::data_cast(*position);
1697 if (
node_comp(node_data_node, position_data_node))
1700 position = position->children[kLeft];
1702 else if (
node_comp(position_data_node, node_data_node))
1705 position = position->children[kRight];
1729 Node* lower_node = ETL_NULLPTR;
1733 Data_Node& data_node = iset::data_cast(*position);
1737 lower_node = position;
1738 if (position->children[kLeft])
1740 position = position->children[kLeft];
1750 position = position->children[kRight];
1755 lower_node = position;
1756 position = position->children[kLeft];
1766 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1767 Node* find_lower_node(Node* position,
const K& key)
const
1770 Node* lower_node = ETL_NULLPTR;
1774 Data_Node& data_node = iset::data_cast(*position);
1778 lower_node = position;
1779 if (position->children[kLeft])
1781 position = position->children[kLeft];
1791 position = position->children[kRight];
1796 lower_node = position;
1797 position = position->children[kLeft];
1812 Node* upper_node = ETL_NULLPTR;
1814 Node* node = position;
1818 Data_Node& data_node = iset::data_cast(*node);
1823 node = node->children[kLeft];
1827 node = node->children[kRight];
1829 else if (node->children[kRight])
1846 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1847 Node* find_upper_node(Node* position,
const K& key)
const
1850 Node* upper_node = ETL_NULLPTR;
1852 Node* node = position;
1856 Data_Node& data_node = iset::data_cast(*node);
1861 node = node->children[kLeft];
1865 node = node->children[kRight];
1867 else if (node->children[kRight])
1886 Node* insert_node(Node*& position, Data_Node& node)
1889 Node* found = position;
1895 Node* critical_parent_node = ETL_NULLPTR;
1902 if (kNeither != found->weight)
1904 critical_node = found;
1908 Data_Node& found_data_node = iset::data_cast(*found);
1917 else if (
node_comp(found_data_node, node))
1920 found->dir = kRight;
1925 found->dir = kNeither;
1928 critical_node = ETL_NULLPTR;
1931 destroy_data_node(node);
1938 if (found->children[found->dir])
1942 if (kNeither != found->children[found->dir]->weight)
1944 critical_parent_node = found;
1948 found = found->children[found->dir];
1956 found = found->children[found->dir];
1966 if (critical_parent_node == ETL_NULLPTR && critical_node ==
root_node)
1970 else if (critical_parent_node == ETL_NULLPTR && critical_node == position)
1976 if (critical_parent_node != ETL_NULLPTR)
1978 balance_node(critical_parent_node->children[critical_parent_node->dir]);
1999 void next_node(Node*&position)
2004 if (position->children[kRight])
2013 Node* parent = position;
2018 parent = find_parent_node(
root_node, position);
2020 }
while (parent && parent->children[kRight] == position);
2031 void next_node(
const Node*& position)
const
2036 if (position->children[kRight])
2045 const Node* parent = position;
2050 parent = find_parent_node(
root_node, position);
2052 }
while (parent && parent->children[kRight] == position);
2063 void prev_node(Node*&position)
2074 if (position->children[kLeft])
2083 Node* parent = position;
2088 parent = find_parent_node(
root_node, position);
2090 }
while (parent && parent->children[kLeft] == position);
2101 void prev_node(
const Node*& position)
const
2112 if (position->children[kLeft])
2121 const Node* parent = position;
2126 parent = find_parent_node(
root_node, position);
2128 }
while (parent && parent->children[kLeft] == position);
2145 Node* found_parent = ETL_NULLPTR;
2146 Node* found = ETL_NULLPTR;
2147 Node* replace_parent = ETL_NULLPTR;
2148 Node* replace = position;
2149 Node* balance_parent = ETL_NULLPTR;
2154 Data_Node& replace_data_node = iset::data_cast(*replace);
2160 replace->dir = kLeft;
2162 else if (
node_comp(replace_data_node, key))
2165 replace->dir = kRight;
2170 replace->dir = replace->children[kLeft] ? kLeft : kRight;
2173 found_parent = replace_parent;
2178 if (replace->children[replace->dir] == ETL_NULLPTR)
2188 if ((replace->weight == kNeither) ||
2189 (replace->weight == (1 - replace->dir) &&
2190 replace->children[1 - replace->dir]->weight == kNeither))
2193 balance_parent = replace_parent;
2198 replace_parent = replace;
2199 replace = replace->children[replace->dir];
2208 if (balance->children[balance->dir] == ETL_NULLPTR)
2213 if (balance->weight == kNeither)
2215 balance->weight = 1 - balance->dir;
2217 else if (balance->weight == balance->dir)
2219 balance->weight = kNeither;
2223 int weight = balance->children[1 - balance->dir]->weight;
2225 if (weight == balance->dir)
2228 if (balance_parent == ETL_NULLPTR)
2231 balance->children[1 - balance->dir]->children[balance->dir]->weight);
2235 rotate_3node(balance_parent->children[balance_parent->dir], 1 - balance->dir,
2236 balance->children[1 - balance->dir]->children[balance->dir]->weight);
2241 else if (weight == kNeither)
2244 if (balance_parent == ETL_NULLPTR)
2251 rotate_2node(balance_parent->children[balance_parent->dir], 1 - balance->dir);
2252 balance_parent->children[balance_parent->dir]->weight = balance->dir;
2255 balance->weight = 1 - balance->dir;
2261 if (balance_parent == ETL_NULLPTR)
2267 rotate_2node(balance_parent->children[balance_parent->dir], 1 - balance->dir);
2273 if (balance == found)
2277 found_parent = balance_parent->children[balance_parent->dir];
2279 found_parent->dir = found_parent->children[kLeft] == found ? kLeft : kRight;
2290 balance_parent = balance;
2291 balance = balance->children[balance->dir];
2298 detach_node(found_parent->children[found_parent->dir],
2299 replace_parent->children[replace_parent->dir]);
2317 Data_Node& found_data_node = iset::data_cast(*found);
2323 destroy_data_node(found_data_node);
2332 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
2333 Node* remove_node(Node*& position,
const K& key)
2338 Node* found_parent = ETL_NULLPTR;
2339 Node* found = ETL_NULLPTR;
2340 Node* replace_parent = ETL_NULLPTR;
2341 Node* replace = position;
2342 Node* balance_parent = ETL_NULLPTR;
2347 Data_Node& replace_data_node = iset::data_cast(*replace);
2353 replace->dir = kLeft;
2355 else if (
node_comp(replace_data_node, key))
2358 replace->dir = kRight;
2363 replace->dir = replace->children[kLeft] ? kLeft : kRight;
2366 found_parent = replace_parent;
2371 if (replace->children[replace->dir] == ETL_NULLPTR)
2381 if ((replace->weight == kNeither) ||
2382 (replace->weight == (1 - replace->dir) &&
2383 replace->children[1 - replace->dir]->weight == kNeither))
2386 balance_parent = replace_parent;
2391 replace_parent = replace;
2392 replace = replace->children[replace->dir];
2401 if (balance->children[balance->dir] == ETL_NULLPTR)
2406 if (balance->weight == kNeither)
2408 balance->weight = 1 - balance->dir;
2410 else if (balance->weight == balance->dir)
2412 balance->weight = kNeither;
2416 int weight = balance->children[1 - balance->dir]->weight;
2418 if (weight == balance->dir)
2421 if (balance_parent == ETL_NULLPTR)
2424 balance->children[1 - balance->dir]->children[balance->dir]->weight);
2428 rotate_3node(balance_parent->children[balance_parent->dir], 1 - balance->dir,
2429 balance->children[1 - balance->dir]->children[balance->dir]->weight);
2434 else if (weight == kNeither)
2437 if (balance_parent == ETL_NULLPTR)
2444 rotate_2node(balance_parent->children[balance_parent->dir], 1 - balance->dir);
2445 balance_parent->children[balance_parent->dir]->weight = balance->dir;
2448 balance->weight = 1 - balance->dir;
2454 if (balance_parent == ETL_NULLPTR)
2460 rotate_2node(balance_parent->children[balance_parent->dir], 1 - balance->dir);
2466 if (balance == found)
2470 found_parent = balance_parent->children[balance_parent->dir];
2472 found_parent->dir = found_parent->children[kLeft] == found ? kLeft : kRight;
2483 balance_parent = balance;
2484 balance = balance->children[balance->dir];
2491 detach_node(found_parent->children[found_parent->dir],
2492 replace_parent->children[replace_parent->dir]);
2510 Data_Node& found_data_node = iset::data_cast(*found);
2516 destroy_data_node(found_data_node);
2530#if defined(ETL_POLYMORPHIC_SET) || defined(ETL_POLYMORPHIC_CONTAINERS)