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