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