Stefan Scholz
/
ETL
Important changes to repositories hosted on mbed.com
Mbed hosted mercurial repositories are deprecated and are due to be permanently deleted in July 2026.
To keep a copy of this software download the repository Zip archive or clone locally using Mercurial.
It is also possible to export all your personal repositories from the account settings page.
Embed:
(wiki syntax)
Show/hide line numbers
set.h
Go to the documentation of this file.
00001 ///\file 00002 00003 /****************************************************************************** 00004 The MIT License(MIT) 00005 00006 Embedded Template Library. 00007 https://github.com/ETLCPP/etl 00008 http://www.etlcpp.com 00009 00010 Copyright(c) 2014 jwellbelove, rlindeman 00011 00012 Permission is hereby granted, free of charge, to any person obtaining a copy 00013 of this software and associated documentation files(the "Software"), to deal 00014 in the Software without restriction, including without limitation the rights 00015 to use, copy, modify, merge, publish, distribute, sublicense, and / or sell 00016 copies of the Software, and to permit persons to whom the Software is 00017 furnished to do so, subject to the following conditions : 00018 00019 The above copyright notice and this permission notice shall be included in all 00020 copies or substantial portions of the Software. 00021 00022 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 00023 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 00024 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE 00025 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 00026 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 00027 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 00028 SOFTWARE. 00029 ******************************************************************************/ 00030 00031 #ifndef __ETL_SET__ 00032 #define __ETL_SET__ 00033 00034 #include <stddef.h> 00035 #include <iterator> 00036 #include <algorithm> 00037 #include <functional> 00038 00039 #include "platform.h " 00040 #include "container.h " 00041 #include "pool.h " 00042 #include "exception.h " 00043 #include "error_handler.h " 00044 #include "debug_count.h " 00045 #include "nullptr.h " 00046 #include "type_traits.h " 00047 #include "parameter_type.h " 00048 00049 #ifdef ETL_COMPILER_MICROSOFT 00050 #undef min 00051 #endif 00052 00053 #undef ETL_FILE 00054 #define ETL_FILE "14" 00055 00056 //***************************************************************************** 00057 ///\defgroup set set 00058 /// A set with the capacity defined at compile time. 00059 ///\ingroup containers 00060 //***************************************************************************** 00061 00062 namespace etl 00063 { 00064 //*************************************************************************** 00065 /// Exception for the set. 00066 ///\ingroup set 00067 //*************************************************************************** 00068 class set_exception : public etl::exception 00069 { 00070 public: 00071 00072 set_exception(string_type reason_, string_type file_name_, numeric_type line_number_) 00073 : etl::exception(reason_, file_name_, line_number_) 00074 { 00075 } 00076 }; 00077 00078 //*************************************************************************** 00079 /// Full exception for the set. 00080 ///\ingroup set 00081 //*************************************************************************** 00082 class set_full : public etl::set_exception 00083 { 00084 public: 00085 00086 set_full(string_type file_name_, numeric_type line_number_) 00087 : etl::set_exception(ETL_ERROR_TEXT("set:full", ETL_FILE"A"), file_name_, line_number_) 00088 { 00089 } 00090 }; 00091 00092 //*************************************************************************** 00093 /// Map out of bounds exception. 00094 ///\ingroup set 00095 //*************************************************************************** 00096 class set_out_of_bounds : public etl::set_exception 00097 { 00098 public: 00099 00100 set_out_of_bounds(string_type file_name_, numeric_type line_number_) 00101 : etl::set_exception(ETL_ERROR_TEXT("set:bounds", ETL_FILE"B"), file_name_, line_number_) 00102 { 00103 } 00104 }; 00105 00106 //*************************************************************************** 00107 /// Iterator exception for the set. 00108 ///\ingroup set 00109 //*************************************************************************** 00110 class set_iterator : public etl::set_exception 00111 { 00112 public: 00113 00114 set_iterator(string_type file_name_, numeric_type line_number_) 00115 : etl::set_exception(ETL_ERROR_TEXT("set:iterator problem", ETL_FILE"C"), file_name_, line_number_) 00116 { 00117 } 00118 }; 00119 00120 //*************************************************************************** 00121 /// The base class for all sets. 00122 ///\ingroup set 00123 //*************************************************************************** 00124 class set_base 00125 { 00126 public: 00127 00128 typedef size_t size_type; ///< The type used for determining the size of set. 00129 00130 //************************************************************************* 00131 /// Gets the size of the set. 00132 //************************************************************************* 00133 size_type size() const 00134 { 00135 return current_size; 00136 } 00137 00138 //************************************************************************* 00139 /// Gets the maximum possible size of the set. 00140 //************************************************************************* 00141 size_type max_size() const 00142 { 00143 return CAPACITY; 00144 } 00145 00146 //************************************************************************* 00147 /// Checks to see if the set is empty. 00148 //************************************************************************* 00149 bool empty() const 00150 { 00151 return current_size == 0; 00152 } 00153 00154 //************************************************************************* 00155 /// Checks to see if the set is full. 00156 //************************************************************************* 00157 bool full() const 00158 { 00159 return current_size == CAPACITY; 00160 } 00161 00162 //************************************************************************* 00163 /// Returns the capacity of the vector. 00164 ///\return The capacity of the vector. 00165 //************************************************************************* 00166 size_type capacity() const 00167 { 00168 return CAPACITY; 00169 } 00170 00171 //************************************************************************* 00172 /// Returns the remaining capacity. 00173 ///\return The remaining capacity. 00174 //************************************************************************* 00175 size_t available() const 00176 { 00177 return max_size() - size(); 00178 } 00179 00180 protected: 00181 00182 enum 00183 { 00184 kLeft = 0, 00185 kRight = 1, 00186 kNeither = 2 00187 }; 00188 00189 //************************************************************************* 00190 /// The node element in the set. 00191 //************************************************************************* 00192 struct Node 00193 { 00194 //*********************************************************************** 00195 /// Constructor 00196 //*********************************************************************** 00197 Node() : 00198 weight(kNeither), 00199 dir(kNeither) 00200 { 00201 } 00202 00203 //*********************************************************************** 00204 /// Marks the node as a leaf. 00205 //*********************************************************************** 00206 void mark_as_leaf() 00207 { 00208 weight = kNeither; 00209 dir = kNeither; 00210 children[0] =std::nullptr; 00211 children[1] =std::nullptr; 00212 } 00213 00214 Node* children[2]; 00215 uint_least8_t weight; 00216 uint_least8_t dir; 00217 }; 00218 00219 //************************************************************************* 00220 /// The constructor that is called from derived classes. 00221 //************************************************************************* 00222 set_base(size_type max_size_) 00223 : current_size(0) 00224 , CAPACITY(max_size_) 00225 , root_node(std::nullptr) 00226 00227 { 00228 } 00229 00230 //************************************************************************* 00231 /// Attach the provided node to the position provided 00232 //************************************************************************* 00233 void attach_node(Node*& position, Node& node) 00234 { 00235 // Mark new node as leaf on attach to tree at position provided 00236 node.mark_as_leaf(); 00237 00238 // Add the node here 00239 position = &node; 00240 00241 // One more. 00242 ++current_size; 00243 } 00244 00245 //************************************************************************* 00246 /// Detach the node at the position provided 00247 //************************************************************************* 00248 void detach_node(Node*& position, Node*& replacement) 00249 { 00250 // Make temporary copy of actual nodes involved because we might lose 00251 // their references in the process (e.g. position is the same as 00252 // replacement or replacement is a child of position) 00253 Node* detached = position; 00254 Node* swap = replacement; 00255 00256 // Update current position to point to swap (replacement) node first 00257 position = swap; 00258 00259 // Update replacement node to point to child in opposite direction 00260 // otherwise we might lose the other child of the swap node 00261 replacement = swap->children[1 - swap->dir]; 00262 00263 // Point swap node to detached node's children and weight 00264 swap->children[kLeft] = detached->children[kLeft]; 00265 swap->children[kRight] = detached->children[kRight]; 00266 swap->weight = detached->weight; 00267 } 00268 00269 //************************************************************************* 00270 /// Balance the critical node at the position provided as needed 00271 //************************************************************************* 00272 void balance_node(Node*& critical_node) 00273 { 00274 // Step 1: Update weights for all children of the critical node up to the 00275 // newly inserted node. This step is costly (in terms of traversing nodes 00276 // multiple times during insertion) but doesn't require as much recursion 00277 Node* weight_node = critical_node->children[critical_node->dir]; 00278 while (weight_node) 00279 { 00280 // Keep going until we reach a terminal node (dir == kNeither) 00281 if (uint_least8_t(kNeither) != weight_node->dir) 00282 { 00283 // Does this insert balance the previous weight factor value? 00284 if (weight_node->weight == 1 - weight_node->dir) 00285 { 00286 weight_node->weight = uint_least8_t(kNeither); 00287 } 00288 else 00289 { 00290 weight_node->weight = weight_node->dir; 00291 } 00292 00293 // Update weight factor node to point to next node 00294 weight_node = weight_node->children[weight_node->dir]; 00295 } 00296 else 00297 { 00298 // Stop loop, terminal node found 00299 break; 00300 } 00301 } // while(weight_node) 00302 00303 // Step 2: Update weight for critical_node or rotate tree to balance node 00304 if (uint_least8_t(kNeither) == critical_node->weight) 00305 { 00306 critical_node->weight = critical_node->dir; 00307 } 00308 // If direction is different than weight, then it will now be balanced 00309 else if (critical_node->dir != critical_node->weight) 00310 { 00311 critical_node->weight = uint_least8_t(kNeither); 00312 } 00313 // Rotate is required to balance the tree at the critical node 00314 else 00315 { 00316 // If critical node matches child node direction then perform a two 00317 // node rotate in the direction of the critical node 00318 if (critical_node->weight == critical_node->children[critical_node->dir]->dir) 00319 { 00320 rotate_2node(critical_node, critical_node->dir); 00321 } 00322 // Otherwise perform a three node rotation in the direction of the 00323 // critical node 00324 else 00325 { 00326 rotate_3node(critical_node, critical_node->dir, 00327 critical_node->children[critical_node->dir]->children[1 - critical_node->dir]->dir); 00328 } 00329 } 00330 } 00331 00332 //************************************************************************* 00333 /// Find the node whose key would go before all the other keys from the 00334 /// position provided 00335 //************************************************************************* 00336 Node* find_limit_node(Node* position, const int8_t dir) const 00337 { 00338 // Something at this position and in the direction specified? keep going 00339 Node* limit_node = position; 00340 while (limit_node && limit_node->children[dir]) 00341 { 00342 limit_node = limit_node->children[dir]; 00343 } 00344 00345 // Return the limit node position found 00346 return limit_node; 00347 } 00348 00349 //************************************************************************* 00350 /// Find the node whose key would go before all the other keys from the 00351 /// position provided 00352 //************************************************************************* 00353 const Node* find_limit_node(const Node* position, const int8_t dir) const 00354 { 00355 // Something at this position and in the direction specified? keep going 00356 const Node* limit_node = position; 00357 while (limit_node && limit_node->children[dir]) 00358 { 00359 limit_node = limit_node->children[dir]; 00360 } 00361 00362 // Return the limit node position found 00363 return limit_node; 00364 } 00365 00366 //************************************************************************* 00367 /// Rotate two nodes at the position provided the to balance the tree 00368 //************************************************************************* 00369 void rotate_2node(Node*& position, uint_least8_t dir) 00370 { 00371 // A C A B 00372 // B C -> A E OR B C -> D A 00373 // D E B D D E E C 00374 // C (new position) becomes the root 00375 // A (position) takes ownership of D as its children[kRight] child 00376 // C (new position) takes ownership of A as its left child 00377 // OR 00378 // B (new position) becomes the root 00379 // A (position) takes ownership of E as its left child 00380 // B (new position) takes ownership of A as its right child 00381 00382 // Capture new root 00383 Node* new_root = position->children[dir]; 00384 // Replace position's previous child with new root's other child 00385 position->children[dir] = new_root->children[1 - dir]; 00386 // New root now becomes parent of current position 00387 new_root->children[1 - dir] = position; 00388 // Clear weight factor from current position 00389 position->weight = uint_least8_t(kNeither); 00390 // Newly detached right now becomes current position 00391 position = new_root; 00392 // Clear weight factor from new root 00393 position->weight = uint_least8_t(kNeither); 00394 } 00395 00396 //************************************************************************* 00397 /// Rotate three nodes at the position provided the to balance the tree 00398 //************************************************************************* 00399 void rotate_3node(Node*& position, uint_least8_t dir, uint_least8_t third) 00400 { 00401 // __A__ __E__ __A__ __D__ 00402 // _B_ C -> B A OR B _C_ -> A C 00403 // D E D F G C D E B F G E 00404 // F G F G 00405 // E (new position) becomes the root 00406 // B (position) takes ownership of F as its left child 00407 // A takes ownership of G as its right child 00408 // OR 00409 // D (new position) becomes the root 00410 // A (position) takes ownership of F as its right child 00411 // C takes ownership of G as its left child 00412 00413 // Capture new root (either E or D depending on dir) 00414 Node* new_root = position->children[dir]->children[1 - dir]; 00415 // Set weight factor for B or C based on F or G existing and being a different than dir 00416 position->children[dir]->weight = third != uint_least8_t(kNeither) && third != dir ? dir : uint_least8_t(kNeither); 00417 00418 // Detach new root from its tree (replace with new roots child) 00419 position->children[dir]->children[1 - dir] = 00420 new_root->children[dir]; 00421 // Attach current left tree to new root 00422 new_root->children[dir] = position->children[dir]; 00423 // Set weight factor for A based on F or G 00424 position->weight = third != uint_least8_t(kNeither) && third == dir ? 1 - dir : uint_least8_t(kNeither); 00425 00426 // Move new root's right tree to current roots left tree 00427 position->children[dir] = new_root->children[1 - dir]; 00428 // Attach current root to new roots right tree 00429 new_root->children[1 - dir] = position; 00430 // Replace current position with new root 00431 position = new_root; 00432 // Clear weight factor for new current position 00433 position->weight = uint_least8_t(kNeither); 00434 } 00435 00436 size_type current_size; ///< The number of the used nodes. 00437 const size_type CAPACITY; ///< The maximum size of the set. 00438 Node* root_node; ///< The node that acts as the set root. 00439 etl::debug_count construct_count; 00440 }; 00441 00442 //*************************************************************************** 00443 /// A templated base for all etl::set types. 00444 ///\ingroup set 00445 //*************************************************************************** 00446 template <typename T, typename TCompare> 00447 class iset : public etl::set_base 00448 { 00449 public: 00450 00451 typedef const T key_type; 00452 typedef const T value_type; 00453 typedef TCompare key_compare; 00454 typedef TCompare value_compare; 00455 typedef value_type& const_reference; 00456 typedef value_type* const_pointer; 00457 typedef size_t size_type; 00458 00459 //************************************************************************* 00460 /// How to compare two key elements. 00461 //************************************************************************* 00462 struct key_comp 00463 { 00464 bool operator ()(key_type& key1, key_type& key2) const 00465 { 00466 return key_compare()(key1, key2); 00467 } 00468 }; 00469 00470 //************************************************************************* 00471 /// How to compare two value elements. 00472 //************************************************************************* 00473 struct value_comp 00474 { 00475 bool operator ()(value_type& value1, value_type& value2) const 00476 { 00477 return value_compare()(value1, value2); 00478 } 00479 }; 00480 00481 protected: 00482 00483 //************************************************************************* 00484 /// The data node element in the set. 00485 //************************************************************************* 00486 struct Data_Node : public Node 00487 { 00488 explicit Data_Node(value_type value_) 00489 : value(value_) 00490 { 00491 } 00492 00493 value_type value; 00494 }; 00495 00496 /// Defines the key value parameter type 00497 typedef typename etl::parameter_type<T>::type key_parameter_t; 00498 00499 //************************************************************************* 00500 /// How to compare node elements. 00501 //************************************************************************* 00502 bool node_comp(const Data_Node& node1, const Data_Node& node2) const 00503 { 00504 return key_compare()(node1.value, node2.value); 00505 } 00506 00507 bool node_comp(const Data_Node& node, key_parameter_t key) const 00508 { 00509 return key_compare()(node.value, key); 00510 } 00511 bool node_comp(key_parameter_t key, const Data_Node& node) const 00512 00513 { 00514 return key_compare()(key, node.value); 00515 } 00516 00517 private: 00518 00519 /// The pool of data nodes used in the set. 00520 etl::ipool* p_node_pool; 00521 00522 //************************************************************************* 00523 /// Downcast a Node* to a Data_Node* 00524 //************************************************************************* 00525 static Data_Node* data_cast(Node* p_node) 00526 { 00527 return static_cast<Data_Node*>(p_node); 00528 } 00529 00530 //************************************************************************* 00531 /// Downcast a Node& to a Data_Node& 00532 //************************************************************************* 00533 static Data_Node& data_cast(Node& node) 00534 { 00535 return static_cast<Data_Node&>(node); 00536 } 00537 00538 //************************************************************************* 00539 /// Downcast a const Node* to a const Data_Node* 00540 //************************************************************************* 00541 static const Data_Node* data_cast(const Node* p_node) 00542 { 00543 return static_cast<const Data_Node*>(p_node); 00544 } 00545 00546 //************************************************************************* 00547 /// Downcast a const Node& to a const Data_Node& 00548 //************************************************************************* 00549 static const Data_Node& data_cast(const Node& node) 00550 { 00551 return static_cast<const Data_Node&>(node); 00552 } 00553 00554 public: 00555 //************************************************************************* 00556 /// iterator. 00557 //************************************************************************* 00558 class iterator : public std::iterator<std::bidirectional_iterator_tag, value_type> 00559 { 00560 public: 00561 00562 friend class iset; 00563 00564 iterator() 00565 : p_set(std::nullptr) 00566 , p_node(std::nullptr) 00567 { 00568 } 00569 00570 iterator(iset& set) 00571 : p_set(&set) 00572 , p_node(std::nullptr) 00573 { 00574 } 00575 00576 iterator(iset& set, Node* node) 00577 : p_set(&set) 00578 , p_node(node) 00579 { 00580 } 00581 00582 iterator(const iterator& other) 00583 : p_set(other.p_set) 00584 , p_node(other.p_node) 00585 { 00586 } 00587 00588 ~iterator() 00589 { 00590 } 00591 00592 iterator& operator ++() 00593 { 00594 p_set->next_node(p_node); 00595 return *this; 00596 } 00597 00598 iterator operator ++(int) 00599 { 00600 iterator temp(*this); 00601 p_set->next_node(p_node); 00602 return temp; 00603 } 00604 00605 iterator& operator --() 00606 { 00607 p_set->prev_node(p_node); 00608 return *this; 00609 } 00610 00611 iterator operator --(int) 00612 { 00613 iterator temp(*this); 00614 p_set->prev_node(p_node); 00615 return temp; 00616 } 00617 00618 iterator operator =(const iterator& other) 00619 { 00620 p_set = other.p_set; 00621 p_node = other.p_node; 00622 return *this; 00623 } 00624 00625 const_reference operator *() const 00626 { 00627 return iset::data_cast(p_node)->value; 00628 } 00629 00630 const_pointer operator &() const 00631 { 00632 return &(iset::data_cast(p_node)->value); 00633 } 00634 00635 const_pointer operator ->() const 00636 { 00637 return &(iset::data_cast(p_node)->value); 00638 } 00639 00640 friend bool operator == (const iterator& lhs, const iterator& rhs) 00641 { 00642 return lhs.p_set == rhs.p_set && lhs.p_node == rhs.p_node; 00643 } 00644 00645 friend bool operator != (const iterator& lhs, const iterator& rhs) 00646 { 00647 return !(lhs == rhs); 00648 } 00649 00650 private: 00651 00652 // Pointer to set associated with this iterator 00653 iset* p_set; 00654 00655 // Pointer to the current node for this iterator 00656 Node* p_node; 00657 }; 00658 friend class iterator; 00659 00660 //************************************************************************* 00661 /// const_iterator 00662 //************************************************************************* 00663 class const_iterator : public std::iterator<std::bidirectional_iterator_tag, const value_type> 00664 { 00665 public: 00666 00667 friend class iset; 00668 00669 const_iterator() 00670 : p_set(nullptr) 00671 , p_node(nullptr) 00672 { 00673 } 00674 00675 const_iterator(const iset& set) 00676 : p_set(&set) 00677 , p_node(nullptr) 00678 { 00679 } 00680 00681 const_iterator(const iset& set, const Node* node) 00682 : p_set(&set) 00683 , p_node(node) 00684 { 00685 } 00686 00687 const_iterator(const typename iset::iterator& other) 00688 : p_set(other.p_set) 00689 , p_node(other.p_node) 00690 { 00691 } 00692 00693 const_iterator(const const_iterator& other) 00694 : p_set(other.p_set) 00695 , p_node(other.p_node) 00696 { 00697 } 00698 00699 ~const_iterator() 00700 { 00701 } 00702 00703 const_iterator& operator ++() 00704 { 00705 p_set->next_node(p_node); 00706 return *this; 00707 } 00708 00709 const_iterator operator ++(int) 00710 { 00711 const_iterator temp(*this); 00712 p_set->next_node(p_node); 00713 return temp; 00714 } 00715 00716 const_iterator& operator --() 00717 { 00718 p_set->prev_node(p_node); 00719 return *this; 00720 } 00721 00722 const_iterator operator --(int) 00723 { 00724 const_iterator temp(*this); 00725 p_set->prev_node(p_node); 00726 return temp; 00727 } 00728 00729 const_iterator operator =(const const_iterator& other) 00730 { 00731 p_set = other.p_set; 00732 p_node = other.p_node; 00733 return *this; 00734 } 00735 00736 const_reference operator *() const 00737 { 00738 return iset::data_cast(p_node)->value; 00739 } 00740 00741 const_pointer operator &() const 00742 { 00743 return iset::data_cast(p_node)->value; 00744 } 00745 00746 const_pointer operator ->() const 00747 { 00748 return &(iset::data_cast(p_node)->value); 00749 } 00750 00751 friend bool operator == (const const_iterator& lhs, const const_iterator& rhs) 00752 { 00753 return lhs.p_set == rhs.p_set && lhs.p_node == rhs.p_node; 00754 } 00755 00756 friend bool operator != (const const_iterator& lhs, const const_iterator& rhs) 00757 { 00758 return !(lhs == rhs); 00759 } 00760 00761 private: 00762 // Pointer to set associated with this iterator 00763 const iset* p_set; 00764 00765 // Pointer to the current node for this iterator 00766 const Node* p_node; 00767 }; 00768 friend class const_iterator; 00769 00770 typedef typename std::iterator_traits<iterator>::difference_type difference_type; 00771 00772 typedef std::reverse_iterator<iterator> reverse_iterator; 00773 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 00774 00775 00776 //************************************************************************* 00777 /// Assignment operator. 00778 //************************************************************************* 00779 iset& operator = (const iset& rhs) 00780 { 00781 if (this != &rhs) 00782 { 00783 assign(rhs.cbegin(), rhs.cend()); 00784 } 00785 00786 return *this; 00787 } 00788 00789 //************************************************************************* 00790 /// Gets the beginning of the set. 00791 //************************************************************************* 00792 iterator begin() 00793 { 00794 return iterator(*this, find_limit_node(root_node, kLeft)); 00795 } 00796 00797 //************************************************************************* 00798 /// Gets the beginning of the set. 00799 //************************************************************************* 00800 const_iterator begin() const 00801 { 00802 return const_iterator(*this, find_limit_node(root_node, kLeft)); 00803 } 00804 00805 //************************************************************************* 00806 /// Gets the end of the set. 00807 //************************************************************************* 00808 iterator end() 00809 { 00810 return iterator(*this); 00811 } 00812 00813 //************************************************************************* 00814 /// Gets the end of the set. 00815 //************************************************************************* 00816 const_iterator end() const 00817 { 00818 return const_iterator(*this); 00819 } 00820 00821 //************************************************************************* 00822 /// Gets the beginning of the set. 00823 //************************************************************************* 00824 const_iterator cbegin() const 00825 { 00826 return const_iterator(*this, find_limit_node(root_node, kLeft)); 00827 } 00828 00829 //************************************************************************* 00830 /// Gets the end of the set. 00831 //************************************************************************* 00832 const_iterator cend() const 00833 { 00834 return const_iterator(*this); 00835 } 00836 00837 //************************************************************************* 00838 /// Gets the reverse beginning of the list. 00839 //************************************************************************* 00840 reverse_iterator rbegin() 00841 { 00842 return reverse_iterator(iterator(*this)); 00843 } 00844 00845 //************************************************************************* 00846 /// Gets the reverse beginning of the list. 00847 //************************************************************************* 00848 const_reverse_iterator rbegin() const 00849 { 00850 return const_reverse_iterator(const_iterator(*this)); 00851 } 00852 00853 //************************************************************************* 00854 /// Gets the reverse end of the list. 00855 //************************************************************************* 00856 reverse_iterator rend() 00857 { 00858 return reverse_iterator(iterator(*this, find_limit_node(root_node, kLeft))); 00859 } 00860 00861 //************************************************************************* 00862 /// Gets the reverse end of the list. 00863 //************************************************************************* 00864 const_reverse_iterator rend() const 00865 { 00866 return const_reverse_iterator(iterator(*this, find_limit_node(root_node, kLeft))); 00867 } 00868 00869 //************************************************************************* 00870 /// Gets the reverse beginning of the list. 00871 //************************************************************************* 00872 const_reverse_iterator crbegin() const 00873 { 00874 return const_reverse_iterator(const_iterator(*this)); 00875 } 00876 00877 //************************************************************************* 00878 /// Gets the reverse end of the list. 00879 //************************************************************************* 00880 const_reverse_iterator crend() const 00881 { 00882 return const_reverse_iterator(const_iterator(*this, find_limit_node(root_node, kLeft))); 00883 } 00884 00885 //********************************************************************* 00886 /// Assigns values to the set. 00887 /// If asserts or exceptions are enabled, emits set_full if the set does not have enough free space. 00888 /// If asserts or exceptions are enabled, emits set_iterator if the iterators are reversed. 00889 ///\param first The iterator to the first element. 00890 ///\param last The iterator to the last element + 1. 00891 //********************************************************************* 00892 template <typename TIterator> 00893 void assign(TIterator first, TIterator last) 00894 { 00895 initialise(); 00896 insert(first, last); 00897 } 00898 00899 //************************************************************************* 00900 /// Clears the set. 00901 //************************************************************************* 00902 void clear() 00903 { 00904 initialise(); 00905 } 00906 00907 //********************************************************************* 00908 /// Counts the number of elements that contain the key specified. 00909 ///\param key The key to search for. 00910 ///\return 1 if element was found, 0 otherwise. 00911 //********************************************************************* 00912 size_type count(key_parameter_t key) const 00913 { 00914 return find_node(root_node, key) ? 1 : 0; 00915 } 00916 00917 //************************************************************************* 00918 /// Returns two iterators with bounding (lower bound, upper bound) the 00919 /// value provided 00920 //************************************************************************* 00921 std::pair<iterator, iterator> equal_range(const value_type& value) 00922 { 00923 return std::make_pair<iterator, iterator>( 00924 iterator(*this, find_lower_node(root_node, value)), 00925 iterator(*this, find_upper_node(root_node, value))); 00926 } 00927 00928 //************************************************************************* 00929 /// Returns two const iterators with bounding (lower bound, upper bound) 00930 /// the value provided. 00931 //************************************************************************* 00932 std::pair<const_iterator, const_iterator> equal_range(const value_type& value) const 00933 { 00934 return std::make_pair<const_iterator, const_iterator>( 00935 const_iterator(*this, find_lower_node(root_node, value)), 00936 const_iterator(*this, find_upper_node(root_node, value))); 00937 } 00938 00939 //************************************************************************* 00940 /// Erases the value at the specified position. 00941 //************************************************************************* 00942 void erase(iterator position) 00943 { 00944 // Remove the node by its key 00945 erase((*position)); 00946 } 00947 00948 //************************************************************************* 00949 /// Erases the value at the specified position. 00950 //************************************************************************* 00951 iterator erase(const_iterator position) 00952 { 00953 // Find the parent node to be removed 00954 Node*& reference_node = find_node(root_node, position.p_node); 00955 iterator next(*this, reference_node); 00956 ++next; 00957 00958 remove_node(root_node, (*position)); 00959 00960 return next; 00961 } 00962 00963 //************************************************************************* 00964 // Erase the key specified. 00965 //************************************************************************* 00966 size_type erase(key_parameter_t key_value) 00967 { 00968 // Return 1 if key value was found and removed 00969 return remove_node(root_node, key_value) ? 1 : 0; 00970 } 00971 00972 //************************************************************************* 00973 /// Erases a range of elements. 00974 //************************************************************************* 00975 iterator erase(iterator first, iterator last) 00976 { 00977 iterator next; 00978 while (first != last) 00979 { 00980 next = erase(const_iterator(first++)); 00981 } 00982 00983 return next; 00984 } 00985 00986 //************************************************************************* 00987 /// Erases a range of elements. 00988 //************************************************************************* 00989 iterator erase(const_iterator first, const_iterator last) 00990 { 00991 iterator next; 00992 while (first != last) 00993 { 00994 next = erase(first++); 00995 } 00996 00997 return next; 00998 } 00999 01000 //********************************************************************* 01001 /// Finds an element. 01002 ///\param key The key to search for. 01003 ///\return An iterator pointing to the element or end() if not found. 01004 //********************************************************************* 01005 iterator find(key_parameter_t key_value) 01006 { 01007 return iterator(*this, find_node(root_node, key_value)); 01008 } 01009 01010 //********************************************************************* 01011 /// Finds an element. 01012 ///\param key The key to search for. 01013 ///\return An iterator pointing to the element or end() if not found. 01014 //********************************************************************* 01015 const_iterator find(key_parameter_t key_value) const 01016 { 01017 return const_iterator(*this, find_node(root_node, key_value)); 01018 } 01019 01020 //********************************************************************* 01021 /// Inserts a value to the set. 01022 /// If asserts or exceptions are enabled, emits set_full if the set is already full. 01023 ///\param value The value to insert. 01024 //********************************************************************* 01025 std::pair<iterator, bool> insert(value_type& value) 01026 { 01027 // Default to no inserted node 01028 Node* inserted_node =std::nullptr; 01029 bool inserted = false; 01030 01031 ETL_ASSERT(!full(), ETL_ERROR(set_full)); 01032 01033 // Get next available free node 01034 Data_Node& node = allocate_data_node(value); 01035 01036 // Obtain the inserted node (might bestd::nullptr if node was a duplicate) 01037 inserted_node = insert_node(root_node, node); 01038 inserted = inserted_node == &node; 01039 01040 // Insert node into tree and return iterator to new node location in tree 01041 return std::make_pair(iterator(*this, inserted_node), inserted); 01042 } 01043 01044 //********************************************************************* 01045 /// Inserts a value to the set starting at the position recommended. 01046 /// If asserts or exceptions are enabled, emits set_full if the set is already full. 01047 ///\param position The position that would precede the value to insert. 01048 ///\param value The value to insert. 01049 //********************************************************************* 01050 iterator insert(iterator, value_type& value) 01051 { 01052 // Default to no inserted node 01053 Node* inserted_node =std::nullptr; 01054 01055 ETL_ASSERT(!full(), ETL_ERROR(set_full)); 01056 01057 // Get next available free node 01058 Data_Node& node = allocate_data_node(value); 01059 01060 // Obtain the inserted node (might bestd::nullptr if node was a duplicate) 01061 inserted_node = insert_node(root_node, node); 01062 01063 // Insert node into tree and return iterator to new node location in tree 01064 return iterator(*this, inserted_node); 01065 } 01066 01067 //********************************************************************* 01068 /// Inserts a value to the set starting at the position recommended. 01069 /// If asserts or exceptions are enabled, emits set_full if the set is already full. 01070 ///\param position The position that would precede the value to insert. 01071 ///\param value The value to insert. 01072 //********************************************************************* 01073 iterator insert(const_iterator, value_type& value) 01074 { 01075 // Default to no inserted node 01076 Node* inserted_node =std::nullptr; 01077 01078 ETL_ASSERT(!full(), ETL_ERROR(set_full)); 01079 01080 // Get next available free node 01081 Data_Node& node = allocate_data_node(value); 01082 01083 // Obtain the inserted node (might bestd::nullptr if node was a duplicate) 01084 inserted_node = insert_node(root_node, node); 01085 01086 // Insert node into tree and return iterator to new node location in tree 01087 return iterator(*this, inserted_node); 01088 } 01089 01090 //********************************************************************* 01091 /// Inserts a range of values to the set. 01092 /// If asserts or exceptions are enabled, emits set_full if the set does not have enough free space. 01093 ///\param position The position to insert at. 01094 ///\param first The first element to add. 01095 ///\param last The last + 1 element to add. 01096 //********************************************************************* 01097 template <class TIterator> 01098 void insert(TIterator first, TIterator last) 01099 { 01100 while (first != last) 01101 { 01102 insert(*first++); 01103 } 01104 } 01105 01106 //********************************************************************* 01107 /// Returns an iterator pointing to the first element in the container 01108 /// whose key is not considered to go before the key provided or end() 01109 /// if all keys are considered to go before the key provided. 01110 ///\return An iterator pointing to the element not before key or end() 01111 //********************************************************************* 01112 iterator lower_bound(key_parameter_t key) 01113 { 01114 return iterator(*this, find_lower_node(root_node, key)); 01115 } 01116 01117 //********************************************************************* 01118 /// Returns a const_iterator pointing to the first element in the 01119 /// container whose key is not considered to go before the key provided 01120 /// or end() if all keys are considered to go before the key provided. 01121 ///\return An const_iterator pointing to the element not before key or end() 01122 //********************************************************************* 01123 const_iterator lower_bound(key_parameter_t key) const 01124 { 01125 return const_iterator(*this, find_lower_node(root_node, key)); 01126 } 01127 01128 //********************************************************************* 01129 /// Returns an iterator pointing to the first element in the container 01130 /// whose key is not considered to go after the key provided or end() 01131 /// if all keys are considered to go after the key provided. 01132 ///\return An iterator pointing to the element after key or end() 01133 //********************************************************************* 01134 iterator upper_bound(key_parameter_t key) 01135 { 01136 return iterator(*this, find_upper_node(root_node, key)); 01137 } 01138 01139 //********************************************************************* 01140 /// Returns a const_iterator pointing to the first element in the 01141 /// container whose key is not considered to go after the key provided 01142 /// or end() if all keys are considered to go after the key provided. 01143 ///\return An const_iterator pointing to the element after key or end() 01144 //********************************************************************* 01145 const_iterator upper_bound(key_parameter_t key) const 01146 { 01147 return const_iterator(*this, find_upper_node(root_node, key)); 01148 } 01149 01150 protected: 01151 01152 //************************************************************************* 01153 /// Constructor. 01154 //************************************************************************* 01155 iset(etl::ipool& node_pool, size_t max_size_) 01156 : etl::set_base(max_size_) 01157 , p_node_pool(&node_pool) 01158 { 01159 } 01160 01161 //************************************************************************* 01162 /// Initialise the set. 01163 //************************************************************************* 01164 void initialise() 01165 { 01166 erase(begin(), end()); 01167 } 01168 01169 private: 01170 01171 //************************************************************************* 01172 /// Allocate a Data_Node. 01173 //************************************************************************* 01174 Data_Node& allocate_data_node(value_type value) 01175 { 01176 Data_Node& node = *p_node_pool->allocate<Data_Node>(); 01177 ::new ((void*)&node.value) value_type(value); 01178 ++construct_count; 01179 return node; 01180 } 01181 01182 //************************************************************************* 01183 /// Destroy a Data_Node. 01184 //************************************************************************* 01185 void destroy_data_node(Data_Node& node) 01186 { 01187 node.value.~value_type(); 01188 p_node_pool->release(&node); 01189 --construct_count; 01190 } 01191 01192 //************************************************************************* 01193 /// Find the value matching the node provided 01194 //************************************************************************* 01195 Node* find_node(Node* position, key_parameter_t key) 01196 { 01197 Node* found = position; 01198 while (found) 01199 { 01200 // Downcast found to Data_Node class for comparison and other operations 01201 Data_Node& found_data_node = iset::data_cast(*found); 01202 01203 // Compare the node value to the current position value 01204 if (node_comp(key, found_data_node)) 01205 { 01206 // Keep searching for the node on the left 01207 found = found->children[kLeft]; 01208 } 01209 else if (node_comp(found_data_node, key)) 01210 { 01211 // Keep searching for the node on the right 01212 found = found->children[kRight]; 01213 } 01214 else 01215 { 01216 // Node that matches the key provided was found, exit loop 01217 break; 01218 } 01219 } 01220 01221 // Return the node found (might bestd::nullptr) 01222 return found; 01223 } 01224 01225 //************************************************************************* 01226 /// Find the value matching the node provided 01227 //************************************************************************* 01228 const Node* find_node(const Node* position, key_parameter_t key) const 01229 { 01230 const Node* found = position; 01231 while (found) 01232 { 01233 // Downcast found to Data_Node class for comparison and other operations 01234 const Data_Node& found_data_node = iset::data_cast(*found); 01235 01236 // Compare the node value to the current position value 01237 if (node_comp(key, found_data_node)) 01238 { 01239 // Keep searching for the node on the left 01240 found = found->children[kLeft]; 01241 } 01242 else if (node_comp(found_data_node, key)) 01243 { 01244 // Keep searching for the node on the right 01245 found = found->children[kRight]; 01246 } 01247 else 01248 { 01249 // Node that matches the key provided was found, exit loop 01250 break; 01251 } 01252 } 01253 01254 // Return the node found (might bestd::nullptr) 01255 return found; 01256 } 01257 01258 //************************************************************************* 01259 /// Find the reference node matching the node provided 01260 //************************************************************************* 01261 Node*& find_node(Node*& position, const Node* node) 01262 { 01263 Node* found = position; 01264 while (found) 01265 { 01266 if (found->children[kLeft] == node) 01267 { 01268 return found->children[kLeft]; 01269 } 01270 else if (found->children[kRight] == node) 01271 { 01272 return found->children[kRight]; 01273 } 01274 else 01275 { 01276 // Downcast found to Data_Node class for comparison and other operations 01277 Data_Node& found_data_node = iset::data_cast(*found); 01278 const Data_Node& data_node = iset::data_cast(*node); 01279 01280 // Compare the node value to the current position value 01281 if (node_comp(data_node, found_data_node)) 01282 { 01283 // Keep searching for the node on the left 01284 found = found->children[kLeft]; 01285 } 01286 else if (node_comp(found_data_node, data_node)) 01287 { 01288 // Keep searching for the node on the right 01289 found = found->children[kRight]; 01290 } 01291 else 01292 { 01293 // Return position provided (it matches the node) 01294 return position; 01295 } 01296 } 01297 } 01298 01299 // Return root node if nothing was found 01300 return root_node; 01301 } 01302 01303 //************************************************************************* 01304 /// Find the parent node that contains the node provided in its left or 01305 /// right tree 01306 //************************************************************************* 01307 Node* find_parent_node(Node* position, const Node* node) 01308 { 01309 // Default to no parent node found 01310 Node* found =std::nullptr; 01311 01312 // If the position provided is the same as the node then there is no parent 01313 if (position && node && position != node) 01314 { 01315 while (position) 01316 { 01317 // Is this position not the parent of the node we are looking for? 01318 if (position->children[kLeft] != node && 01319 position->children[kRight] != node) 01320 { 01321 // Downcast node and position to Data_Node references for key comparisons 01322 const Data_Node& node_data_node = iset::data_cast(*node); 01323 Data_Node& position_data_node = iset::data_cast(*position); 01324 // Compare the node value to the current position value 01325 if (node_comp(node_data_node, position_data_node)) 01326 { 01327 // Keep looking for parent on the left 01328 position = position->children[kLeft]; 01329 } 01330 else if (node_comp(position_data_node, node_data_node)) 01331 { 01332 // Keep looking for parent on the right 01333 position = position->children[kRight]; 01334 } 01335 } 01336 else 01337 { 01338 // Return the current position as the parent node found 01339 found = position; 01340 01341 // Parent node found, exit loop 01342 break; 01343 } 01344 } 01345 } 01346 01347 // Return the parent node found (might bestd::nullptr) 01348 return found; 01349 } 01350 01351 //************************************************************************* 01352 /// Find the parent node that contains the node provided in its left or 01353 /// right tree 01354 //************************************************************************* 01355 const Node* find_parent_node(const Node* position, const Node* node) const 01356 { 01357 // Default to no parent node found 01358 const Node* found =std::nullptr; 01359 01360 // If the position provided is the same as the node then there is no parent 01361 if (position && node && position != node) 01362 { 01363 while (position) 01364 { 01365 // Is this position not the parent of the node we are looking for? 01366 if (position->children[kLeft] != node && 01367 position->children[kRight] != node) 01368 { 01369 // Downcast node and position to Data_Node references for key comparisons 01370 const Data_Node& node_data_node = iset::data_cast(*node); 01371 const Data_Node& position_data_node = iset::data_cast(*position); 01372 // Compare the node value to the current position value 01373 if (node_comp(node_data_node, position_data_node)) 01374 { 01375 // Keep looking for parent on the left 01376 position = position->children[kLeft]; 01377 } 01378 else if (node_comp(position_data_node, node_data_node)) 01379 { 01380 // Keep looking for parent on the right 01381 position = position->children[kRight]; 01382 } 01383 } 01384 else 01385 { 01386 // Return the current position as the parent node found 01387 found = position; 01388 01389 // Parent node found, exit loop 01390 break; 01391 } 01392 } 01393 } 01394 01395 // Return the parent node found (might bestd::nullptr) 01396 return found; 01397 } 01398 01399 //************************************************************************* 01400 /// Find the node whose key is not considered to go before the key provided 01401 //************************************************************************* 01402 Node* find_lower_node(Node* position, key_parameter_t key) const 01403 { 01404 // Something at this position? keep going 01405 Node* lower_node = position; 01406 while (lower_node) 01407 { 01408 // Downcast lower node to Data_Node reference for key comparisons 01409 Data_Node& data_node = iset::data_cast(*lower_node); 01410 // Compare the key value to the current lower node key value 01411 if (node_comp(key, data_node)) 01412 { 01413 if (lower_node->children[kLeft]) 01414 { 01415 lower_node = lower_node->children[kLeft]; 01416 } 01417 else 01418 { 01419 // Found lowest node 01420 break; 01421 } 01422 } 01423 else if (node_comp(data_node, key)) 01424 { 01425 lower_node = lower_node->children[kRight]; 01426 } 01427 else 01428 { 01429 // Found equal node 01430 break; 01431 } 01432 } 01433 01434 // Return the lower_node position found 01435 return lower_node; 01436 } 01437 01438 //************************************************************************* 01439 /// Find the node whose key is considered to go after the key provided 01440 //************************************************************************* 01441 Node* find_upper_node(Node* position, key_parameter_t key) const 01442 { 01443 // Keep track of parent of last upper node 01444 Node* upper_node =std::nullptr; 01445 // Start with position provided 01446 Node* node = position; 01447 while (node) 01448 { 01449 // Downcast position to Data_Node reference for key comparisons 01450 Data_Node& data_node = iset::data_cast(*node); 01451 // Compare the key value to the current upper node key value 01452 if (node_comp(key, data_node)) 01453 { 01454 upper_node = node; 01455 node = node->children[kLeft]; 01456 } 01457 else if (node_comp(data_node, key)) 01458 { 01459 node = node->children[kRight]; 01460 } 01461 else if (node->children[kRight]) 01462 { 01463 upper_node = find_limit_node(node->children[kRight], kLeft); 01464 break; 01465 } 01466 else 01467 { 01468 break; 01469 } 01470 } 01471 01472 // Return the upper node position found (might bestd::nullptr) 01473 return upper_node; 01474 } 01475 01476 //************************************************************************* 01477 /// Insert a node. 01478 //************************************************************************* 01479 Node* insert_node(Node*& position, Data_Node& node) 01480 { 01481 // Find the location where the node belongs 01482 Node* found = position; 01483 01484 // Was position provided not empty? then find where the node belongs 01485 if (position) 01486 { 01487 // Find the critical parent node (default tostd::nullptr) 01488 Node* critical_parent_node =std::nullptr; 01489 Node* critical_node = root_node; 01490 01491 while (found) 01492 { 01493 // Search for critical weight node (all nodes whose weight factor 01494 // is set to kNeither (balanced) 01495 if (kNeither != found->weight) 01496 { 01497 critical_node = found; 01498 } 01499 01500 // Downcast found to Data_Node class for comparison and other operations 01501 Data_Node& found_data_node = iset::data_cast(*found); 01502 01503 // Is the node provided to the left of the current position? 01504 if (node_comp(node, found_data_node)) 01505 { 01506 // Update direction taken to insert new node in parent node 01507 found->dir = kLeft; 01508 } 01509 // Is the node provided to the right of the current position? 01510 else if (node_comp(found_data_node, node)) 01511 { 01512 // Update direction taken to insert new node in parent node 01513 found->dir = kRight; 01514 } 01515 else 01516 { 01517 // Update direction taken to insert new node in parent node 01518 found->dir = kNeither; 01519 01520 // Clear critical node value to skip weight step below 01521 critical_node =std::nullptr; 01522 01523 // Destroy the node provided (its a duplicate) 01524 destroy_data_node(node); 01525 01526 // Exit loop, duplicate node found 01527 break; 01528 } 01529 01530 // Is there a child of this parent node? 01531 if (found->children[found->dir]) 01532 { 01533 // Will this node be the parent of the next critical node whose 01534 // weight factor is set to kNeither (balanced)? 01535 if (kNeither != found->children[found->dir]->weight) 01536 { 01537 critical_parent_node = found; 01538 } 01539 01540 // Keep looking for empty spot to insert new node 01541 found = found->children[found->dir]; 01542 } 01543 else 01544 { 01545 // Attatch node to right 01546 attach_node(found->children[found->dir], node); 01547 01548 // Return newly added node 01549 found = found->children[found->dir]; 01550 01551 // Exit loop 01552 break; 01553 } 01554 } 01555 01556 // Was a critical node found that should be checked for balance? 01557 if (critical_node) 01558 { 01559 if (critical_parent_node ==std::nullptr && critical_node == root_node) 01560 { 01561 balance_node(root_node); 01562 } 01563 else if (critical_parent_node ==std::nullptr && critical_node == position) 01564 { 01565 balance_node(position); 01566 } 01567 else 01568 { 01569 balance_node(critical_parent_node->children[critical_parent_node->dir]); 01570 } 01571 } 01572 } 01573 else 01574 { 01575 // Attatch node to current position 01576 attach_node(position, node); 01577 01578 // Return newly added node at current position 01579 found = position; 01580 } 01581 01582 // Return the node found (might bestd::nullptr) 01583 return found; 01584 } 01585 01586 //************************************************************************* 01587 /// Find the next node in sequence from the node provided 01588 //************************************************************************* 01589 void next_node(Node*&position) 01590 { 01591 if (position) 01592 { 01593 // Is there a tree on the right? then find the minimum of that tree 01594 if (position->children[kRight]) 01595 { 01596 // Return minimum node found 01597 position = find_limit_node(position->children[kRight], kLeft); 01598 } 01599 // Otherwise find the parent of this node 01600 else 01601 { 01602 // Start with current position as parent 01603 Node* parent = position; 01604 do { 01605 // Update current position as previous parent 01606 position = parent; 01607 // Find parent of current position 01608 parent = find_parent_node(root_node, position); 01609 // Repeat while previous position was on right side of parent tree 01610 } while (parent && parent->children[kRight] == position); 01611 01612 // Set parent node as the next position 01613 position = parent; 01614 } 01615 } 01616 } 01617 01618 //************************************************************************* 01619 /// Find the next node in sequence from the node provided 01620 //************************************************************************* 01621 void next_node(const Node*& position) const 01622 { 01623 if (position) 01624 { 01625 // Is there a tree on the right? then find the minimum of that tree 01626 if (position->children[kRight]) 01627 { 01628 // Return minimum node found 01629 position = find_limit_node(position->children[kRight], kLeft); 01630 } 01631 // Otherwise find the parent of this node 01632 else 01633 { 01634 // Start with current position as parent 01635 const Node* parent = position; 01636 do { 01637 // Update current position as previous parent 01638 position = parent; 01639 // Find parent of current position 01640 parent = find_parent_node(root_node, position); 01641 // Repeat while previous position was on right side of parent tree 01642 } while (parent && parent->children[kRight] == position); 01643 01644 // Set parent node as the next position 01645 position = parent; 01646 } 01647 } 01648 } 01649 01650 //************************************************************************* 01651 /// Find the previous node in sequence from the node provided 01652 //************************************************************************* 01653 void prev_node(Node*&position) 01654 { 01655 // If starting at the terminal end, the previous node is the maximum node 01656 // from the root 01657 if (!position) 01658 { 01659 position = find_limit_node(root_node, kRight); 01660 } 01661 else 01662 { 01663 // Is there a tree on the left? then find the maximum of that tree 01664 if (position->children[kLeft]) 01665 { 01666 // Return maximum node found 01667 position = find_limit_node(position->children[kLeft], kRight); 01668 } 01669 // Otherwise find the parent of this node 01670 else 01671 { 01672 // Start with current position as parent 01673 Node* parent = position; 01674 do { 01675 // Update current position as previous parent 01676 position = parent; 01677 // Find parent of current position 01678 parent = find_parent_node(root_node, position); 01679 // Repeat while previous position was on left side of parent tree 01680 } while (parent && parent->children[kLeft] == position); 01681 01682 // Set parent node as the next position 01683 position = parent; 01684 } 01685 } 01686 } 01687 01688 //************************************************************************* 01689 /// Find the previous node in sequence from the node provided 01690 //************************************************************************* 01691 void prev_node(const Node*& position) const 01692 { 01693 // If starting at the terminal end, the previous node is the maximum node 01694 // from the root 01695 if (!position) 01696 { 01697 position = find_limit_node(root_node, kRight); 01698 } 01699 else 01700 { 01701 // Is there a tree on the left? then find the maximum of that tree 01702 if (position->children[kLeft]) 01703 { 01704 // Return maximum node found 01705 position = find_limit_node(position->children[kLeft], kRight); 01706 } 01707 // Otherwise find the parent of this node 01708 else 01709 { 01710 // Start with current position as parent 01711 const Node* parent = position; 01712 do { 01713 // Update current position as previous parent 01714 position = parent; 01715 // Find parent of current position 01716 parent = find_parent_node(root_node, position); 01717 // Repeat while previous position was on left side of parent tree 01718 } while (parent && parent->children[kLeft] == position); 01719 01720 // Set parent node as the next position 01721 position = parent; 01722 } 01723 } 01724 } 01725 01726 //************************************************************************* 01727 /// Remove the node specified from somewhere starting at the position 01728 /// provided 01729 //************************************************************************* 01730 Node* remove_node(Node*& position, key_parameter_t key) 01731 { 01732 // Step 1: Find the target node that matches the key provided, the 01733 // replacement node (might be the same as target node), and the critical 01734 // node to start rebalancing the tree from (up to the replacement node) 01735 Node* found_parent =std::nullptr; 01736 Node* found =std::nullptr; 01737 Node* replace_parent =std::nullptr; 01738 Node* replace = position; 01739 Node* balance_parent =std::nullptr; 01740 Node* balance = root_node; 01741 while (replace) 01742 { 01743 // Downcast found to Data_Node class for comparison and other operations 01744 Data_Node& replace_data_node = iset::data_cast(*replace); 01745 01746 // Compare the key provided to the replace data node key 01747 if (node_comp(key, replace_data_node)) 01748 { 01749 // Update the direction to the target/replace node 01750 replace->dir = kLeft; 01751 } 01752 else if (node_comp(replace_data_node, key)) 01753 { 01754 // Update the direction to the target/replace node 01755 replace->dir = kRight; 01756 } 01757 else 01758 { 01759 // Update the direction to the replace node (target node found here) 01760 replace->dir = replace->children[kLeft] ? kLeft : kRight; 01761 01762 // Note the target node was found (and its parent) 01763 found_parent = replace_parent; 01764 found = replace; 01765 } 01766 // Replacement node found if its missing a child in the replace->dir 01767 // value set above 01768 if (replace->children[replace->dir] ==std::nullptr) 01769 { 01770 // Exit loop once replace node is found (target might not have been) 01771 break; 01772 } 01773 01774 // If replacement node weight is kNeither or we are taking the shorter 01775 // path of replacement node and our sibling (on longer path) is 01776 // balanced then we need to update the balance node to match this 01777 // replacement node but all our ancestors will not require rebalancing 01778 if ((replace->weight == kNeither) || 01779 (replace->weight == (1 - replace->dir) && 01780 replace->children[1 - replace->dir]->weight == kNeither)) 01781 { 01782 // Update balance node (and its parent) to replacement node 01783 balance_parent = replace_parent; 01784 balance = replace; 01785 } 01786 01787 // Keep searching for the replacement node 01788 replace_parent = replace; 01789 replace = replace->children[replace->dir]; 01790 } 01791 01792 // If target node was found, proceed with rebalancing and replacement 01793 if (found) 01794 { 01795 // Step 2: Update weights from critical node to replacement parent node 01796 while (balance) 01797 { 01798 if (balance->children[balance->dir] ==std::nullptr) 01799 { 01800 break; 01801 } 01802 01803 if (balance->weight == kNeither) 01804 { 01805 balance->weight = 1 - balance->dir; 01806 } 01807 else if (balance->weight == balance->dir) 01808 { 01809 balance->weight = kNeither; 01810 } 01811 else 01812 { 01813 int weight = balance->children[1 - balance->dir]->weight; 01814 // Perform a 3 node rotation if weight is same as balance->dir 01815 if (weight == balance->dir) 01816 { 01817 // Is the root node being rebalanced (no parent) 01818 if (balance_parent ==std::nullptr) 01819 { 01820 rotate_3node(root_node, 1 - balance->dir, 01821 balance->children[1 - balance->dir]->children[balance->dir]->weight); 01822 } 01823 else 01824 { 01825 rotate_3node(balance_parent->children[balance_parent->dir], 1 - balance->dir, 01826 balance->children[1 - balance->dir]->children[balance->dir]->weight); 01827 } 01828 } 01829 // Already balanced, rebalance and make it heavy in opposite 01830 // direction of the node being removed 01831 else if (weight == kNeither) 01832 { 01833 // Is the root node being rebalanced (no parent) 01834 if (balance_parent ==std::nullptr) 01835 { 01836 rotate_2node(root_node, 1 - balance->dir); 01837 root_node->weight = balance->dir; 01838 } 01839 else 01840 { 01841 rotate_2node(balance_parent->children[balance_parent->dir], 1 - balance->dir); 01842 balance_parent->children[balance_parent->dir]->weight = balance->dir; 01843 } 01844 // Update balance node weight in opposite direction of node removed 01845 balance->weight = 1 - balance->dir; 01846 } 01847 // Rebalance and leave it balanced 01848 else 01849 { 01850 // Is the root node being rebalanced (no parent) 01851 if (balance_parent ==std::nullptr) 01852 { 01853 rotate_2node(root_node, 1 - balance->dir); 01854 } 01855 else 01856 { 01857 rotate_2node(balance_parent->children[balance_parent->dir], 1 - balance->dir); 01858 } 01859 } 01860 01861 // Is balance node the same as the target node found? then update 01862 // its parent after the rotation performed above 01863 if (balance == found) 01864 { 01865 if (balance_parent) 01866 { 01867 found_parent = balance_parent->children[balance_parent->dir]; 01868 // Update dir since it is likely stale 01869 found_parent->dir = found_parent->children[kLeft] == found ? kLeft : kRight; 01870 } 01871 else 01872 { 01873 found_parent = root_node; 01874 root_node->dir = root_node->children[kLeft] == found ? kLeft : kRight; 01875 } 01876 } 01877 } 01878 01879 // Next balance node to consider 01880 balance_parent = balance; 01881 balance = balance->children[balance->dir]; 01882 } // while(balance) 01883 01884 // Step 3: Swap found node with replacement node 01885 if (found_parent) 01886 { 01887 // Handle traditional case 01888 detach_node(found_parent->children[found_parent->dir], 01889 replace_parent->children[replace_parent->dir]); 01890 } 01891 // Handle root node removal 01892 else 01893 { 01894 // Valid replacement node for root node being removed? 01895 if (replace_parent) 01896 { 01897 detach_node(root_node, replace_parent->children[replace_parent->dir]); 01898 } 01899 else 01900 { 01901 // Target node and replacement node are both root node 01902 detach_node(root_node, root_node); 01903 } 01904 } 01905 01906 // Downcast found into data node 01907 Data_Node& found_data_node = iset::data_cast(*found); 01908 01909 // One less. 01910 --current_size; 01911 01912 // Destroy the node removed 01913 destroy_data_node(found_data_node); 01914 } // if(found) 01915 01916 // Return node found (might bestd::nullptr) 01917 return found; 01918 } 01919 01920 // Disable copy construction. 01921 iset(const iset&); 01922 }; 01923 01924 //************************************************************************* 01925 /// A templated set implementation that uses a fixed size buffer. 01926 //************************************************************************* 01927 template <typename T, const size_t MAX_SIZE_, typename TCompare = std::less<T> > 01928 class set : public etl::iset<T, TCompare> 01929 { 01930 public: 01931 01932 static const size_t MAX_SIZE = MAX_SIZE_; 01933 01934 //************************************************************************* 01935 /// Default constructor. 01936 //************************************************************************* 01937 set() 01938 : etl::iset<T, TCompare>(node_pool, MAX_SIZE) 01939 { 01940 etl::iset<T, TCompare>::initialise(); 01941 } 01942 01943 //************************************************************************* 01944 /// Copy constructor. 01945 //************************************************************************* 01946 set(const set& other) 01947 : etl::iset<T, TCompare>(node_pool, MAX_SIZE) 01948 { 01949 etl::iset<T, TCompare>::assign(other.cbegin(), other.cend()); 01950 } 01951 01952 //************************************************************************* 01953 /// Constructor, from an iterator range. 01954 ///\tparam TIterator The iterator type. 01955 ///\param first The iterator to the first element. 01956 ///\param last The iterator to the last element + 1. 01957 //************************************************************************* 01958 template <typename TIterator> 01959 set(TIterator first, TIterator last) 01960 : etl::iset<T, TCompare>(node_pool, MAX_SIZE) 01961 { 01962 etl::iset<T, TCompare>::assign(first, last); 01963 } 01964 01965 //************************************************************************* 01966 /// Destructor. 01967 //************************************************************************* 01968 ~set() 01969 { 01970 etl::iset<T, TCompare>::initialise(); 01971 } 01972 01973 //************************************************************************* 01974 /// Assignment operator. 01975 //************************************************************************* 01976 set& operator = (const set& rhs) 01977 { 01978 // Skip if doing self assignment 01979 if (this != &rhs) 01980 { 01981 etl::iset<T, TCompare>::assign(rhs.cbegin(), rhs.cend()); 01982 } 01983 01984 return *this; 01985 } 01986 01987 private: 01988 01989 /// The pool of data nodes used for the set. 01990 etl::pool<typename etl::iset<T, TCompare>::Data_Node, MAX_SIZE> node_pool; 01991 }; 01992 } 01993 01994 //*************************************************************************** 01995 /// Equal operator. 01996 ///\param lhs Reference to the first lookup. 01997 ///\param rhs Reference to the second lookup. 01998 ///\return <b>true</b> if the arrays are equal, otherwise <b>false</b> 01999 ///\ingroup lookup 02000 //*************************************************************************** 02001 template <typename T, typename TCompare> 02002 bool operator ==(const etl::iset<T, TCompare>& lhs, const etl::iset<T, TCompare>& rhs) 02003 { 02004 return (lhs.size() == rhs.size()) && std::equal(lhs.begin(), lhs.end(), rhs.begin()); 02005 } 02006 02007 //*************************************************************************** 02008 /// Not equal operator. 02009 ///\param lhs Reference to the first lookup. 02010 ///\param rhs Reference to the second lookup. 02011 ///\return <b>true</b> if the arrays are not equal, otherwise <b>false</b> 02012 ///\ingroup lookup 02013 //*************************************************************************** 02014 template <typename T, typename TCompare> 02015 bool operator !=(const etl::iset<T, TCompare>& lhs, const etl::iset<T, TCompare>& rhs) 02016 { 02017 return !(lhs == rhs); 02018 } 02019 02020 //************************************************************************* 02021 /// Less than operator. 02022 ///\param lhs Reference to the first list. 02023 ///\param rhs Reference to the second list. 02024 ///\return <b>true</b> if the first list is lexicographically less than the 02025 /// second, otherwise <b>false</b>. 02026 //************************************************************************* 02027 template <typename T, typename TCompare> 02028 bool operator <(const etl::iset<T, TCompare>& lhs, const etl::iset<T, TCompare>& rhs) 02029 { 02030 return std::lexicographical_compare(lhs.begin(), 02031 lhs.end(), 02032 rhs.begin(), 02033 rhs.end()); 02034 } 02035 02036 //************************************************************************* 02037 /// Greater than operator. 02038 ///\param lhs Reference to the first list. 02039 ///\param rhs Reference to the second list. 02040 ///\return <b>true</b> if the first list is lexicographically greater than the 02041 /// second, otherwise <b>false</b>. 02042 //************************************************************************* 02043 template <typename T, typename TCompare> 02044 bool operator >(const etl::iset<T, TCompare>& lhs, const etl::iset<T, TCompare>& rhs) 02045 { 02046 return (rhs < lhs); 02047 } 02048 02049 //************************************************************************* 02050 /// Less than or equal operator. 02051 ///\param lhs Reference to the first list. 02052 ///\param rhs Reference to the second list. 02053 ///\return <b>true</b> if the first list is lexicographically less than or equal 02054 /// to the second, otherwise <b>false</b>. 02055 //************************************************************************* 02056 template <typename T, typename TCompare> 02057 bool operator <=(const etl::iset<T, TCompare>& lhs, const etl::iset<T, TCompare>& rhs) 02058 { 02059 return !(lhs > rhs); 02060 } 02061 02062 //************************************************************************* 02063 /// Greater than or equal operator. 02064 ///\param lhs Reference to the first list. 02065 ///\param rhs Reference to the second list. 02066 ///\return <b>true</b> if the first list is lexicographically greater than or 02067 /// equal to the second, otherwise <b>false</b>. 02068 //************************************************************************* 02069 template <typename T, typename TCompare> 02070 bool operator >=(const etl::iset<T, TCompare>& lhs, const etl::iset<T, TCompare>& rhs) 02071 { 02072 return !(lhs < rhs); 02073 } 02074 02075 #ifdef ETL_COMPILER_MICROSOFT 02076 #define min(a,b) (((a) < (b)) ? (a) : (b)) 02077 #endif 02078 02079 #undef ETL_FILE 02080 02081 #endif 02082
Generated on Tue Jul 12 2022 14:05:44 by
1.7.2