31#ifndef ETL_SET_INCLUDED
32#define ETL_SET_INCLUDED
73 set_exception(string_type reason_, string_type file_name_, numeric_type line_number_)
87 set_full(string_type file_name_, numeric_type line_number_)
88 :
etl::set_exception(ETL_ERROR_TEXT(
"set:full", ETL_SET_FILE_ID
"A"), file_name_, line_number_)
102 :
etl::set_exception(ETL_ERROR_TEXT(
"set:bounds", ETL_SET_FILE_ID
"B"), file_name_, line_number_)
115 set_iterator(string_type file_name_, numeric_type line_number_)
116 :
etl::set_exception(ETL_ERROR_TEXT(
"set:iterator problem", ETL_SET_FILE_ID
"C"), file_name_, line_number_)
202 children[0] = ETL_NULLPTR;
203 children[1] = ETL_NULLPTR;
213 children[0] = ETL_NULLPTR;
214 children[1] = ETL_NULLPTR;
218 uint_least8_t weight;
263 Node* detached = position;
271 replacement =
swap->children[1 -
swap->dir];
274 swap->children[kLeft] = detached->children[kLeft];
275 swap->children[kRight] = detached->children[kRight];
276 swap->weight = detached->weight;
287 Node* weight_node = critical_node->children[critical_node->dir];
291 if (uint_least8_t(kNeither) != weight_node->dir)
294 if (weight_node->weight == 1 - weight_node->dir)
296 weight_node->weight = uint_least8_t(kNeither);
300 weight_node->weight = weight_node->dir;
304 weight_node = weight_node->children[weight_node->dir];
314 if (uint_least8_t(kNeither) == critical_node->weight)
316 critical_node->weight = critical_node->dir;
319 else if (critical_node->dir != critical_node->weight)
321 critical_node->weight = uint_least8_t(kNeither);
328 if (critical_node->weight == critical_node->children[critical_node->dir]->dir)
337 critical_node->children[critical_node->dir]->children[1 - critical_node->dir]->dir);
349 Node* limit_node = position;
350 while (limit_node && limit_node->children[dir])
352 limit_node = limit_node->children[dir];
366 const Node* limit_node = position;
367 while (limit_node && limit_node->children[dir])
369 limit_node = limit_node->children[dir];
393 Node* new_root = position->children[dir];
395 position->children[dir] = new_root->children[1 - dir];
397 new_root->children[1 - dir] = position;
399 position->weight = uint_least8_t(kNeither);
403 position->weight = uint_least8_t(kNeither);
424 Node* new_root = position->children[dir]->children[1 - dir];
426 position->children[dir]->weight = third != uint_least8_t(kNeither) && third != dir ? dir : uint_least8_t(kNeither);
429 position->children[dir]->children[1 - dir] =
430 new_root->children[dir];
432 new_root->children[dir] = position->children[dir];
434 position->weight = third != uint_least8_t(kNeither) && third == dir ? 1 - dir : uint_least8_t(kNeither);
437 position->children[dir] = new_root->children[1 - dir];
439 new_root->children[1 - dir] = position;
443 position->weight = uint_least8_t(kNeither);
449 ETL_DECLARE_DEBUG_COUNT
457 template <
typename TKey,
typename TCompare = etl::less<TKey> >
462 typedef TKey key_type;
463 typedef TKey value_type;
464 typedef TCompare key_compare;
465 typedef TCompare value_compare;
466 typedef value_type& reference;
467 typedef const value_type& const_reference;
469 typedef value_type&& rvalue_reference;
471 typedef value_type* pointer;
472 typedef const value_type* const_pointer;
498 return compare(node1.value, node2.value);
503 return compare(node.value, key);
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;
638 reference operator *()
const
640 return iset::data_cast(p_node)->value;
645 return &(iset::data_cast(p_node)->value);
648 pointer operator ->()
const
650 return &(iset::data_cast(p_node)->value);
655 return lhs.p_set == rhs.p_set && lhs.p_node == rhs.p_node;
660 return !(lhs == rhs);
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;
749 const_reference operator *()
const
751 return iset::data_cast(p_node)->value;
756 return iset::data_cast(p_node)->value;
759 const_pointer operator ->()
const
761 return &(iset::data_cast(p_node)->value);
766 return lhs.p_set == rhs.p_set && lhs.p_node == rhs.p_node;
771 return !(lhs == rhs);
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;
820 while (from != rhs.end())
825 this->
insert(etl::move(*from));
887 return reverse_iterator(
iterator(*
this));
909 const_reverse_iterator
rend()
const
925 const_reverse_iterator
crend()
const
937 template <
typename TIterator>
938 void assign(TIterator first, TIterator last)
959 return find_node(
root_node, key) ? 1 : 0;
964 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
965 size_type
count(
const K& key)
const
967 return find_node(
root_node, key) ? 1 : 0;
977 return ETL_OR_STD::make_pair<iterator, iterator>(
iterator(*
this, find_lower_node(
root_node, key)),
983 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
984 ETL_OR_STD::pair<iterator, iterator>
equal_range(
const K& key)
986 return ETL_OR_STD::make_pair<iterator, iterator>(
iterator(*
this, find_lower_node(
root_node, key)),
997 return ETL_OR_STD::make_pair<const_iterator, const_iterator>(
const_iterator(*
this, find_lower_node(
root_node, key)),
1003 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1004 ETL_OR_STD::pair<const_iterator, const_iterator>
equal_range(
const K& key)
const
1006 return ETL_OR_STD::make_pair<const_iterator, const_iterator>(const_iterator(*
this, find_lower_node(
root_node, key)),
1007 const_iterator(*
this, find_upper_node(
root_node, key)));
1026 Node*& reference_node = find_node(
root_node, position.p_node);
1027 iterator next(*
this, reference_node);
1041 return remove_node(
root_node, key_value) ? 1 : 0;
1046 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1047 size_type
erase(K&& key_value)
1050 return remove_node(
root_node, etl::forward<K>(key_value)) ? 1 : 0;
1059 while (first != last)
1061 first =
erase(first);
1064 return last.to_iterator();
1079 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1098 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1099 const_iterator
find(
const K& key_value)
const
1101 return const_iterator(*
this, find_node(
root_node, key_value));
1110 ETL_OR_STD::pair<iterator, bool>
insert(const_reference value)
1113 Node* inserted_node = ETL_NULLPTR;
1114 bool inserted =
false;
1119 Data_Node& node = allocate_data_node(value);
1122 inserted_node = insert_node(
root_node, node);
1123 inserted = inserted_node == &node;
1135 ETL_OR_STD::pair<iterator, bool>
insert(rvalue_reference value)
1138 Node* inserted_node = ETL_NULLPTR;
1139 bool inserted =
false;
1144 Data_Node& node = allocate_data_node(etl::move(value));
1147 inserted_node = insert_node(
root_node, node);
1148 inserted = inserted_node == &node;
1164 Node* inserted_node = ETL_NULLPTR;
1169 Data_Node& node = allocate_data_node(value);
1172 inserted_node = insert_node(
root_node, node);
1175 return iterator(*
this, inserted_node);
1188 Node* inserted_node = ETL_NULLPTR;
1193 Data_Node& node = allocate_data_node(etl::move(value));
1196 inserted_node = insert_node(
root_node, node);
1199 return iterator(*
this, inserted_node);
1210 template <
class TIterator>
1213 while (first != last)
1233 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1253 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1256 return const_iterator(*
this, find_lower_node(
root_node, key));
1273 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1293 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1296 return const_iterator(*
this, find_upper_node(
root_node, key));
1326 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1340 , p_node_pool(&node_pool)
1351 while (item !=
end())
1362 Data_Node& allocate_data_node(const_reference value)
1364 Data_Node& node = allocate_data_node();
1365 ::new ((
void*)&node.value) value_type(value);
1366 ETL_INCREMENT_DEBUG_COUNT
1374 Data_Node& allocate_data_node(rvalue_reference value)
1376 Data_Node& node = allocate_data_node();
1377 ::new ((
void*)&node.value) value_type(etl::move(value));
1378 ETL_INCREMENT_DEBUG_COUNT
1386 Data_Node& allocate_data_node()
1388 Data_Node* (
etl::ipool::*func)() = &etl::ipool::allocate<Data_Node>;
1389 return *(p_node_pool->*func)();
1395 void destroy_data_node(Data_Node& node)
1397 node.value.~value_type();
1399 ETL_DECREMENT_DEBUG_COUNT
1407 Node* found = position;
1411 Data_Node& found_data_node = iset::data_cast(*found);
1417 found = found->children[kLeft];
1419 else if (
node_comp(found_data_node, key))
1422 found = found->children[kRight];
1437 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1438 Node* find_node(Node* position,
const K& key)
1440 Node* found = position;
1444 Data_Node& found_data_node = iset::data_cast(*found);
1450 found = found->children[kLeft];
1452 else if (
node_comp(found_data_node, key))
1455 found = found->children[kRight];
1472 const Node* find_node(
const Node* position,
key_parameter_t key)
const
1474 const Node* found = position;
1478 const Data_Node& found_data_node = iset::data_cast(*found);
1484 found = found->children[kLeft];
1486 else if (
node_comp(found_data_node, key))
1489 found = found->children[kRight];
1504 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1505 const Node* find_node(
const Node* position,
const K& key)
const
1507 const Node* found = position;
1511 const Data_Node& found_data_node = iset::data_cast(*found);
1517 found = found->children[kLeft];
1519 else if (
node_comp(found_data_node, key))
1522 found = found->children[kRight];
1539 Node*& find_node(Node*& position,
const Node* node)
1541 Node* found = position;
1544 if (found->children[kLeft] == node)
1546 return found->children[kLeft];
1548 else if (found->children[kRight] == node)
1550 return found->children[kRight];
1555 Data_Node& found_data_node = iset::data_cast(*found);
1556 const Data_Node& data_node = iset::data_cast(*node);
1559 if (
node_comp(data_node, found_data_node))
1562 found = found->children[kLeft];
1564 else if (
node_comp(found_data_node, data_node))
1567 found = found->children[kRight];
1585 Node* find_parent_node(Node* position,
const Node* node)
1588 Node* found = ETL_NULLPTR;
1591 if (position && node && position != node)
1596 if (position->children[kLeft] != node &&
1597 position->children[kRight] != node)
1600 const Data_Node& node_data_node = iset::data_cast(*node);
1601 Data_Node& position_data_node = iset::data_cast(*position);
1603 if (
node_comp(node_data_node, position_data_node))
1606 position = position->children[kLeft];
1608 else if (
node_comp(position_data_node, node_data_node))
1611 position = position->children[kRight];
1633 const Node* find_parent_node(
const Node* position,
const Node* node)
const
1636 const Node* found = ETL_NULLPTR;
1639 if (position && node && position != node)
1644 if (position->children[kLeft] != node &&
1645 position->children[kRight] != node)
1648 const Data_Node& node_data_node = iset::data_cast(*node);
1649 const Data_Node& position_data_node = iset::data_cast(*position);
1651 if (
node_comp(node_data_node, position_data_node))
1654 position = position->children[kLeft];
1656 else if (
node_comp(position_data_node, node_data_node))
1659 position = position->children[kRight];
1683 Node* lower_node = ETL_NULLPTR;
1687 Data_Node& data_node = iset::data_cast(*position);
1691 lower_node = position;
1692 if (position->children[kLeft])
1694 position = position->children[kLeft];
1704 position = position->children[kRight];
1709 lower_node = position;
1710 position = position->children[kLeft];
1720 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1721 Node* find_lower_node(Node* position,
const K& key)
const
1724 Node* lower_node = ETL_NULLPTR;
1728 Data_Node& data_node = iset::data_cast(*position);
1732 lower_node = position;
1733 if (position->children[kLeft])
1735 position = position->children[kLeft];
1745 position = position->children[kRight];
1750 lower_node = position;
1751 position = position->children[kLeft];
1766 Node* upper_node = ETL_NULLPTR;
1768 Node* node = position;
1772 Data_Node& data_node = iset::data_cast(*node);
1777 node = node->children[kLeft];
1781 node = node->children[kRight];
1783 else if (node->children[kRight])
1800 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
1801 Node* find_upper_node(Node* position,
const K& key)
const
1804 Node* upper_node = ETL_NULLPTR;
1806 Node* node = position;
1810 Data_Node& data_node = iset::data_cast(*node);
1815 node = node->children[kLeft];
1819 node = node->children[kRight];
1821 else if (node->children[kRight])
1840 Node* insert_node(Node*& position, Data_Node& node)
1843 Node* found = position;
1849 Node* critical_parent_node = ETL_NULLPTR;
1856 if (kNeither != found->weight)
1858 critical_node = found;
1862 Data_Node& found_data_node = iset::data_cast(*found);
1871 else if (
node_comp(found_data_node, node))
1874 found->dir = kRight;
1879 found->dir = kNeither;
1882 critical_node = ETL_NULLPTR;
1885 destroy_data_node(node);
1892 if (found->children[found->dir])
1896 if (kNeither != found->children[found->dir]->weight)
1898 critical_parent_node = found;
1902 found = found->children[found->dir];
1910 found = found->children[found->dir];
1920 if (critical_parent_node == ETL_NULLPTR && critical_node ==
root_node)
1924 else if (critical_parent_node == ETL_NULLPTR && critical_node == position)
1930 if (critical_parent_node != ETL_NULLPTR)
1932 balance_node(critical_parent_node->children[critical_parent_node->dir]);
1953 void next_node(Node*&position)
1958 if (position->children[kRight])
1967 Node* parent = position;
1972 parent = find_parent_node(
root_node, position);
1974 }
while (parent && parent->children[kRight] == position);
1985 void next_node(
const Node*& position)
const
1990 if (position->children[kRight])
1999 const Node* parent = position;
2004 parent = find_parent_node(
root_node, position);
2006 }
while (parent && parent->children[kRight] == position);
2017 void prev_node(Node*&position)
2028 if (position->children[kLeft])
2037 Node* parent = position;
2042 parent = find_parent_node(
root_node, position);
2044 }
while (parent && parent->children[kLeft] == position);
2055 void prev_node(
const Node*& position)
const
2066 if (position->children[kLeft])
2075 const Node* parent = position;
2080 parent = find_parent_node(
root_node, position);
2082 }
while (parent && parent->children[kLeft] == position);
2099 Node* found_parent = ETL_NULLPTR;
2100 Node* found = ETL_NULLPTR;
2101 Node* replace_parent = ETL_NULLPTR;
2102 Node* replace = position;
2103 Node* balance_parent = ETL_NULLPTR;
2108 Data_Node& replace_data_node = iset::data_cast(*replace);
2114 replace->dir = kLeft;
2116 else if (
node_comp(replace_data_node, key))
2119 replace->dir = kRight;
2124 replace->dir = replace->children[kLeft] ? kLeft : kRight;
2127 found_parent = replace_parent;
2132 if (replace->children[replace->dir] == ETL_NULLPTR)
2142 if ((replace->weight == kNeither) ||
2143 (replace->weight == (1 - replace->dir) &&
2144 replace->children[1 - replace->dir]->weight == kNeither))
2147 balance_parent = replace_parent;
2152 replace_parent = replace;
2153 replace = replace->children[replace->dir];
2162 if (balance->children[balance->dir] == ETL_NULLPTR)
2167 if (balance->weight == kNeither)
2169 balance->weight = 1 - balance->dir;
2171 else if (balance->weight == balance->dir)
2173 balance->weight = kNeither;
2177 int weight = balance->children[1 - balance->dir]->weight;
2179 if (weight == balance->dir)
2182 if (balance_parent == ETL_NULLPTR)
2185 balance->children[1 - balance->dir]->children[balance->dir]->weight);
2189 rotate_3node(balance_parent->children[balance_parent->dir], 1 - balance->dir,
2190 balance->children[1 - balance->dir]->children[balance->dir]->weight);
2195 else if (weight == kNeither)
2198 if (balance_parent == ETL_NULLPTR)
2205 rotate_2node(balance_parent->children[balance_parent->dir], 1 - balance->dir);
2206 balance_parent->children[balance_parent->dir]->weight = balance->dir;
2209 balance->weight = 1 - balance->dir;
2215 if (balance_parent == ETL_NULLPTR)
2221 rotate_2node(balance_parent->children[balance_parent->dir], 1 - balance->dir);
2227 if (balance == found)
2231 found_parent = balance_parent->children[balance_parent->dir];
2233 found_parent->dir = found_parent->children[kLeft] == found ? kLeft : kRight;
2244 balance_parent = balance;
2245 balance = balance->children[balance->dir];
2252 detach_node(found_parent->children[found_parent->dir],
2253 replace_parent->children[replace_parent->dir]);
2271 Data_Node& found_data_node = iset::data_cast(*found);
2277 destroy_data_node(found_data_node);
2286 template <typename K, typename KC = TCompare, etl::enable_if_t<comparator_is_transparent<KC>::value,
int> = 0>
2287 Node* remove_node(Node*& position,
const K& key)
2292 Node* found_parent = ETL_NULLPTR;
2293 Node* found = ETL_NULLPTR;
2294 Node* replace_parent = ETL_NULLPTR;
2295 Node* replace = position;
2296 Node* balance_parent = ETL_NULLPTR;
2301 Data_Node& replace_data_node = iset::data_cast(*replace);
2307 replace->dir = kLeft;
2309 else if (
node_comp(replace_data_node, key))
2312 replace->dir = kRight;
2317 replace->dir = replace->children[kLeft] ? kLeft : kRight;
2320 found_parent = replace_parent;
2325 if (replace->children[replace->dir] == ETL_NULLPTR)
2335 if ((replace->weight == kNeither) ||
2336 (replace->weight == (1 - replace->dir) &&
2337 replace->children[1 - replace->dir]->weight == kNeither))
2340 balance_parent = replace_parent;
2345 replace_parent = replace;
2346 replace = replace->children[replace->dir];
2355 if (balance->children[balance->dir] == ETL_NULLPTR)
2360 if (balance->weight == kNeither)
2362 balance->weight = 1 - balance->dir;
2364 else if (balance->weight == balance->dir)
2366 balance->weight = kNeither;
2370 int weight = balance->children[1 - balance->dir]->weight;
2372 if (weight == balance->dir)
2375 if (balance_parent == ETL_NULLPTR)
2378 balance->children[1 - balance->dir]->children[balance->dir]->weight);
2382 rotate_3node(balance_parent->children[balance_parent->dir], 1 - balance->dir,
2383 balance->children[1 - balance->dir]->children[balance->dir]->weight);
2388 else if (weight == kNeither)
2391 if (balance_parent == ETL_NULLPTR)
2398 rotate_2node(balance_parent->children[balance_parent->dir], 1 - balance->dir);
2399 balance_parent->children[balance_parent->dir]->weight = balance->dir;
2402 balance->weight = 1 - balance->dir;
2408 if (balance_parent == ETL_NULLPTR)
2414 rotate_2node(balance_parent->children[balance_parent->dir], 1 - balance->dir);
2420 if (balance == found)
2424 found_parent = balance_parent->children[balance_parent->dir];
2426 found_parent->dir = found_parent->children[kLeft] == found ? kLeft : kRight;
2437 balance_parent = balance;
2438 balance = balance->children[balance->dir];
2445 detach_node(found_parent->children[found_parent->dir],
2446 replace_parent->children[replace_parent->dir]);
2464 Data_Node& found_data_node = iset::data_cast(*found);
2470 destroy_data_node(found_data_node);
2484#if defined(ETL_POLYMORPHIC_SET) || defined(ETL_POLYMORPHIC_CONTAINERS)
2500 template <
typename TKey, const
size_t MAX_SIZE_,
typename TCompare = etl::less<TKey> >
2505 static ETL_CONSTANT
size_t MAX_SIZE = MAX_SIZE_;
2511 :
etl::
iset<TKey, TCompare>(node_pool, MAX_SIZE)
2520 :
etl::
iset<TKey, TCompare>(node_pool, MAX_SIZE)
2533 :
etl::
iset<TKey, TCompare>(node_pool, MAX_SIZE)
2539 while (from != other.end())
2544 this->
insert(etl::move(*from));
2557 template <
typename TIterator>
2558 set(TIterator first, TIterator last)
2559 :
etl::
iset<TKey, TCompare>(node_pool, MAX_SIZE)
2561 this->
assign(first, last);
2564#if ETL_HAS_INITIALIZER_LIST
2568 set(std::initializer_list<
typename etl::iset<TKey, TCompare>::value_type> init)
2569 :
etl::
iset<TKey, TCompare>(node_pool, MAX_SIZE)
2571 this->
assign(init.begin(), init.end());
2608 while (from != rhs.end())
2613 this->
insert(etl::move(*from));
2628 template <
typename TKey, const
size_t MAX_SIZE_,
typename TCompare>
2629 ETL_CONSTANT
size_t set<TKey, MAX_SIZE_, TCompare>::MAX_SIZE;
2634#if ETL_USING_CPP17 && ETL_HAS_INITIALIZER_LIST
2635 template <
typename... T>
2636 set(T...) -> set<etl::nth_type_t<0, T...>,
sizeof...(T)>;
2642#if ETL_USING_CPP11 && ETL_HAS_INITIALIZER_LIST
2643 template <
typename TKey,
typename TCompare = etl::less<TKey>,
typename... T>
2644 constexpr auto make_set(T&&... keys) ->
etl::set<TKey,
sizeof...(T), TCompare>
2646 return { {etl::forward<T>(keys)...} };
2657 template <
typename TKey,
typename TCompare>
2670 template <
typename TKey,
typename TCompare>
2673 return !(lhs == rhs);
2683 template <
typename TKey,
typename TCompare>
2686 return etl::lexicographical_compare(lhs.
begin(), lhs.
end(), rhs.
begin(), rhs.
end());
2696 template <
typename TKey,
typename TCompare>
2709 template <
typename TKey,
typename TCompare>
2712 return !(lhs > rhs);
2722 template <
typename TKey,
typename TCompare>
2725 return !(lhs < rhs);
const_iterator
Definition: set.h:677
iterator.
Definition: set.h:571
A templated set implementation that uses a fixed size buffer.
Definition: set.h:2502
set(const set &other)
Copy constructor.
Definition: set.h:2519
set & operator=(const set &rhs)
Assignment operator.
Definition: set.h:2586
set()
Default constructor.
Definition: set.h:2510
set(TIterator first, TIterator last)
Definition: set.h:2558
~set()
Destructor.
Definition: set.h:2578
#define ETL_ASSERT(b, e)
Definition: error_handler.h:316
Definition: exception.h:47
void release(const void *const p_object)
Definition: ipool.h:239
size_type current_size
The number of the used nodes.
Definition: set.h:446
set_base(size_type max_size_)
The constructor that is called from derived classes.
Definition: set.h:225
~iset()
Destructor.
Definition: set.h:2491
void balance_node(Node *&critical_node)
Balance the critical node at the position provided as needed.
Definition: set.h:282
size_type count(key_parameter_t key) const
Definition: set.h:957
bool node_comp(const Data_Node &node1, const Data_Node &node2) const
How to compare node elements.
Definition: set.h:496
Node * find_limit_node(Node *position, const int8_t dir) const
Definition: set.h:346
const_reverse_iterator crbegin() const
Gets the reverse beginning of the list.
Definition: set.h:917
ETL_OR_STD::pair< iterator, bool > insert(const_reference value)
Definition: set.h:1110
size_type capacity() const
Definition: set.h:167
size_type size() const
Gets the size of the set.
Definition: set.h:134
const_reverse_iterator crend() const
Gets the reverse end of the list.
Definition: set.h:925
iterator erase(const_iterator first, const_iterator last)
Erases a range of elements.
Definition: set.h:1057
const_iterator find(key_parameter_t key_value) const
Definition: set.h:1091
iterator upper_bound(key_parameter_t key)
Definition: set.h:1266
const_iterator begin() const
Gets the beginning of the set.
Definition: set.h:845
size_type max_size() const
Gets the maximum possible size of the set.
Definition: set.h:142
void detach_node(Node *&position, Node *&replacement)
Detach the node at the position provided.
Definition: set.h:258
iterator end()
Gets the end of the set.
Definition: set.h:853
const_iterator cbegin() const
Gets the beginning of the set.
Definition: set.h:869
bool empty() const
Checks to see if the set is empty.
Definition: set.h:150
ETL_OR_STD::pair< iterator, iterator > equal_range(key_parameter_t key)
Definition: set.h:975
void insert(TIterator first, TIterator last)
Definition: set.h:1211
value_compare value_comp() const
How to compare two value elements.
Definition: set.h:1311
const_iterator end() const
Gets the end of the set.
Definition: set.h:861
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: set.h:409
iterator erase(iterator position)
Erases the value at the specified position.
Definition: set.h:1014
void assign(TIterator first, TIterator last)
Definition: set.h:938
key_compare key_comp() const
How to compare two key elements.
Definition: set.h:1303
reverse_iterator rbegin()
Gets the reverse beginning of the list.
Definition: set.h:885
const_reverse_iterator rbegin() const
Gets the reverse beginning of the list.
Definition: set.h:893
bool full() const
Checks to see if the set is full.
Definition: set.h:158
iterator lower_bound(key_parameter_t key)
Definition: set.h:1226
reverse_iterator rend()
Gets the reverse end of the list.
Definition: set.h:901
const_iterator upper_bound(key_parameter_t key) const
Definition: set.h:1286
const_iterator lower_bound(key_parameter_t key) const
Definition: set.h:1246
bool contains(const TKey &key) const
Check if the set contains the key.
Definition: set.h:1319
void rotate_2node(Node *&position, uint_least8_t dir)
Rotate two nodes at the position provided the to balance the tree.
Definition: set.h:379
~set_base()
The constructor that is called from derived classes.
Definition: set.h:236
iset(etl::ipool &node_pool, size_t max_size_)
Constructor.
Definition: set.h:1338
size_t size_type
The type used for determining the size of set.
Definition: set.h:129
iterator begin()
Gets the beginning of the set.
Definition: set.h:837
void initialise()
Initialise the set.
Definition: set.h:1347
void attach_node(Node *&position, Node &node)
Attach the provided node to the position provided.
Definition: set.h:243
size_t available() const
Definition: set.h:176
void clear()
Clears the set.
Definition: set.h:947
iterator erase(const_iterator position)
Erases the value at the specified position.
Definition: set.h:1023
iterator find(key_parameter_t key_value)
Definition: set.h:1072
const Node * find_limit_node(const Node *position, const int8_t dir) const
Definition: set.h:363
iterator insert(const_iterator, const_reference value)
Definition: set.h:1161
const_reverse_iterator rend() const
Gets the reverse end of the list.
Definition: set.h:909
Node * root_node
The node that acts as the set root.
Definition: set.h:448
const_iterator cend() const
Gets the end of the set.
Definition: set.h:877
ETL_OR_STD::pair< const_iterator, const_iterator > equal_range(key_parameter_t key) const
Definition: set.h:995
const size_type CAPACITY
The maximum size of the set.
Definition: set.h:447
iset & operator=(const iset &rhs)
Assignment operator.
Definition: set.h:798
etl::parameter_type< TKey >::type key_parameter_t
Defines the key value parameter type.
Definition: set.h:491
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::iset< TKey, TCompare > &lhs, const etl::iset< TKey, TCompare > &rhs)
Template deduction guides.
Definition: set.h:2658
bool operator==(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition: array.h:633
bool operator!=(const etl::iset< TKey, TCompare > &lhs, const etl::iset< TKey, TCompare > &rhs)
Definition: set.h:2671
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 set.
Definition: set.h:481
iterator
Definition: iterator.h:399
etl::conditional< etl::is_fundamental< T >::value||etl::is_pointer< T >::value, T, constT & >::type type
By default fundamental and pointer types are passed by value.
Definition: parameter_type.h:48
The node element in the set.
Definition: set.h:194
Node()
Constructor.
Definition: set.h:198
void mark_as_leaf()
Marks the node as a leaf.
Definition: set.h:209