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