1 /******************************************************************************* 2 * tlx/container/btree_map.hpp 3 * 4 * Part of tlx - http://panthema.net/tlx 5 * 6 * Copyright (C) 2008-2017 Timo Bingmann <tb@panthema.net> 7 * 8 * All rights reserved. Published under the Boost Software License, Version 1.0 9 ******************************************************************************/ 10 11 #ifndef TLX_CONTAINER_BTREE_MAP_HEADER 12 #define TLX_CONTAINER_BTREE_MAP_HEADER 13 14 #include <functional> 15 #include <memory> 16 #include <utility> 17 18 #include <tlx/container/btree.hpp> 19 20 namespace tlx { 21 22 //! \addtogroup tlx_container_btree 23 //! \{ 24 25 /*! 26 * Specialized B+ tree template class implementing STL's map container. 27 * 28 * Implements the STL map using a B+ tree. It can be used as a drop-in 29 * replacement for std::map. Not all asymptotic time requirements are met in 30 * theory. The class has a traits class defining B+ tree properties like slots 31 * and self-verification. Furthermore an allocator can be specified for tree 32 * nodes. 33 */ 34 template <typename Key_, typename Data_, 35 typename Compare_ = std::less<Key_>, 36 typename Traits_ = 37 btree_default_traits<Key_, std::pair<Key_, Data_> >, 38 typename Alloc_ = std::allocator<std::pair<Key_, Data_> > > 39 class btree_map 40 { 41 public: 42 //! \name Template Parameter Types 43 //! \{ 44 45 //! First template parameter: The key type of the btree. This is stored in 46 //! inner nodes. 47 typedef Key_ key_type; 48 49 //! Second template parameter: The value type associated with each key. 50 //! Stored in the B+ tree's leaves 51 typedef Data_ data_type; 52 53 //! Third template parameter: Key comparison function object 54 typedef Compare_ key_compare; 55 56 //! Fourth template parameter: Traits object used to define more parameters 57 //! of the B+ tree 58 typedef Traits_ traits; 59 60 //! Fifth template parameter: STL allocator 61 typedef Alloc_ allocator_type; 62 63 //! \} 64 65 // The macro TLX_BTREE_FRIENDS can be used by outside class to access the B+ 66 // tree internals. This was added for wxBTreeDemo to be able to draw the 67 // tree. 68 TLX_BTREE_FRIENDS; 69 70 public: 71 //! \name Constructed Types 72 //! \{ 73 74 //! Typedef of our own type 75 typedef btree_map<key_type, data_type, key_compare, 76 traits, allocator_type> self; 77 78 //! Construct the STL-required value_type as a composition pair of key and 79 //! data types 80 typedef std::pair<key_type, data_type> value_type; 81 82 //! Key Extractor Struct 83 struct key_of_value { 84 //! pull first out of pair gettlx::btree_map::key_of_value85 static const key_type& get(const value_type& v) { return v.first; } 86 }; 87 88 //! Implementation type of the btree_base 89 typedef BTree<key_type, value_type, key_of_value, key_compare, 90 traits, false, allocator_type> btree_impl; 91 92 //! Function class comparing two value_type pairs. 93 typedef typename btree_impl::value_compare value_compare; 94 95 //! Size type used to count keys 96 typedef typename btree_impl::size_type size_type; 97 98 //! Small structure containing statistics about the tree 99 typedef typename btree_impl::tree_stats tree_stats; 100 101 //! \} 102 103 public: 104 //! \name Static Constant Options and Values of the B+ Tree 105 //! \{ 106 107 //! Base B+ tree parameter: The number of key/data slots in each leaf 108 static const unsigned short leaf_slotmax = btree_impl::leaf_slotmax; 109 110 //! Base B+ tree parameter: The number of key slots in each inner node, 111 //! this can differ from slots in each leaf. 112 static const unsigned short inner_slotmax = btree_impl::inner_slotmax; 113 114 //! Computed B+ tree parameter: The minimum number of key/data slots used 115 //! in a leaf. If fewer slots are used, the leaf will be merged or slots 116 //! shifted from it's siblings. 117 static const unsigned short leaf_slotmin = btree_impl::leaf_slotmin; 118 119 //! Computed B+ tree parameter: The minimum number of key slots used 120 //! in an inner node. If fewer slots are used, the inner node will be 121 //! merged or slots shifted from it's siblings. 122 static const unsigned short inner_slotmin = btree_impl::inner_slotmin; 123 124 //! Debug parameter: Enables expensive and thorough checking of the B+ tree 125 //! invariants after each insert/erase operation. 126 static const bool self_verify = btree_impl::self_verify; 127 128 //! Debug parameter: Prints out lots of debug information about how the 129 //! algorithms change the tree. Requires the header file to be compiled 130 //! with TLX_BTREE_DEBUG and the key type must be std::ostream printable. 131 static const bool debug = btree_impl::debug; 132 133 //! Operational parameter: Allow duplicate keys in the btree. 134 static const bool allow_duplicates = btree_impl::allow_duplicates; 135 136 //! \} 137 138 public: 139 //! \name Iterators and Reverse Iterators 140 //! \{ 141 142 //! STL-like iterator object for B+ tree items. The iterator points to a 143 //! specific slot number in a leaf. 144 typedef typename btree_impl::iterator iterator; 145 146 //! STL-like iterator object for B+ tree items. The iterator points to a 147 //! specific slot number in a leaf. 148 typedef typename btree_impl::const_iterator const_iterator; 149 150 //! create mutable reverse iterator by using STL magic 151 typedef typename btree_impl::reverse_iterator reverse_iterator; 152 153 //! create constant reverse iterator by using STL magic 154 typedef typename btree_impl::const_reverse_iterator const_reverse_iterator; 155 156 //! \} 157 158 private: 159 //! \name Tree Implementation Object 160 //! \{ 161 162 //! The contained implementation object 163 btree_impl tree_; 164 165 //! \} 166 167 public: 168 //! \name Constructors and Destructor 169 //! \{ 170 171 //! Default constructor initializing an empty B+ tree with the standard key 172 //! comparison function btree_map(const allocator_type & alloc=allocator_type ())173 explicit btree_map(const allocator_type& alloc = allocator_type()) 174 : tree_(alloc) 175 { } 176 177 //! Constructor initializing an empty B+ tree with a special key 178 //! comparison object btree_map(const key_compare & kcf,const allocator_type & alloc=allocator_type ())179 explicit btree_map(const key_compare& kcf, 180 const allocator_type& alloc = allocator_type()) 181 : tree_(kcf, alloc) 182 { } 183 184 //! Constructor initializing a B+ tree with the range [first,last) 185 template <class InputIterator> btree_map(InputIterator first,InputIterator last,const allocator_type & alloc=allocator_type ())186 btree_map(InputIterator first, InputIterator last, 187 const allocator_type& alloc = allocator_type()) 188 : tree_(first, last, alloc) 189 { } 190 191 //! Constructor initializing a B+ tree with the range [first,last) and a 192 //! special key comparison object 193 template <class InputIterator> btree_map(InputIterator first,InputIterator last,const key_compare & kcf,const allocator_type & alloc=allocator_type ())194 btree_map(InputIterator first, InputIterator last, const key_compare& kcf, 195 const allocator_type& alloc = allocator_type()) 196 : tree_(first, last, kcf, alloc) 197 { } 198 199 //! Frees up all used B+ tree memory pages ~btree_map()200 ~btree_map() 201 { } 202 203 //! Fast swapping of two identical B+ tree objects. swap(btree_map & from)204 void swap(btree_map& from) { 205 std::swap(tree_, from.tree_); 206 } 207 208 //! \} 209 210 public: 211 //! \name Key and Value Comparison Function Objects 212 //! \{ 213 214 //! Constant access to the key comparison object sorting the B+ tree key_comp() const215 key_compare key_comp() const { 216 return tree_.key_comp(); 217 } 218 219 //! Constant access to a constructed value_type comparison object. required 220 //! by the STL value_comp() const221 value_compare value_comp() const { 222 return tree_.value_comp(); 223 } 224 225 //! \} 226 227 public: 228 //! \name Allocators 229 //! \{ 230 231 //! Return the base node allocator provided during construction. get_allocator() const232 allocator_type get_allocator() const { 233 return tree_.get_allocator(); 234 } 235 236 //! \} 237 238 public: 239 //! \name Fast Destruction of the B+ Tree 240 //! \{ 241 242 //! Frees all key/data pairs and all nodes of the tree clear()243 void clear() { 244 tree_.clear(); 245 } 246 247 //! \} 248 249 public: 250 //! \name STL Iterator Construction Functions 251 //! \{ 252 253 //! Constructs a read/data-write iterator that points to the first slot in 254 //! the first leaf of the B+ tree. begin()255 iterator begin() { 256 return tree_.begin(); 257 } 258 259 //! Constructs a read/data-write iterator that points to the first invalid 260 //! slot in the last leaf of the B+ tree. end()261 iterator end() { 262 return tree_.end(); 263 } 264 265 //! Constructs a read-only constant iterator that points to the first slot 266 //! in the first leaf of the B+ tree. begin() const267 const_iterator begin() const { 268 return tree_.begin(); 269 } 270 271 //! Constructs a read-only constant iterator that points to the first 272 //! invalid slot in the last leaf of the B+ tree. end() const273 const_iterator end() const { 274 return tree_.end(); 275 } 276 277 //! Constructs a read/data-write reverse iterator that points to the first 278 //! invalid slot in the last leaf of the B+ tree. Uses STL magic. rbegin()279 reverse_iterator rbegin() { 280 return tree_.rbegin(); 281 } 282 283 //! Constructs a read/data-write reverse iterator that points to the first 284 //! slot in the first leaf of the B+ tree. Uses STL magic. rend()285 reverse_iterator rend() { 286 return tree_.rend(); 287 } 288 289 //! Constructs a read-only reverse iterator that points to the first 290 //! invalid slot in the last leaf of the B+ tree. Uses STL magic. rbegin() const291 const_reverse_iterator rbegin() const { 292 return tree_.rbegin(); 293 } 294 295 //! Constructs a read-only reverse iterator that points to the first slot 296 //! in the first leaf of the B+ tree. Uses STL magic. rend() const297 const_reverse_iterator rend() const { 298 return tree_.rend(); 299 } 300 301 //! \} 302 303 public: 304 //! \name Access Functions to the Item Count 305 //! \{ 306 307 //! Return the number of key/data pairs in the B+ tree size() const308 size_type size() const { 309 return tree_.size(); 310 } 311 312 //! Returns true if there is at least one key/data pair in the B+ tree empty() const313 bool empty() const { 314 return tree_.empty(); 315 } 316 317 //! Returns the largest possible size of the B+ Tree. This is just a 318 //! function required by the STL standard, the B+ Tree can hold more items. max_size() const319 size_type max_size() const { 320 return tree_.max_size(); 321 } 322 323 //! Return a const reference to the current statistics. get_stats() const324 const tree_stats& get_stats() const { 325 return tree_.get_stats(); 326 } 327 328 //! \} 329 330 public: 331 //! \name STL Access Functions Querying the Tree by Descending to a Leaf 332 //! \{ 333 334 //! Non-STL function checking whether a key is in the B+ tree. The same as 335 //! (find(k) != end()) or (count() != 0). exists(const key_type & key) const336 bool exists(const key_type& key) const { 337 return tree_.exists(key); 338 } 339 340 //! Tries to locate a key in the B+ tree and returns an iterator to the 341 //! key/data slot if found. If unsuccessful it returns end(). find(const key_type & key)342 iterator find(const key_type& key) { 343 return tree_.find(key); 344 } 345 346 //! Tries to locate a key in the B+ tree and returns an constant iterator to 347 //! the key/data slot if found. If unsuccessful it returns end(). find(const key_type & key) const348 const_iterator find(const key_type& key) const { 349 return tree_.find(key); 350 } 351 352 //! Tries to locate a key in the B+ tree and returns the number of identical 353 //! key entries found. Since this is a unique map, count() returns either 0 354 //! or 1. count(const key_type & key) const355 size_type count(const key_type& key) const { 356 return tree_.count(key); 357 } 358 359 //! Searches the B+ tree and returns an iterator to the first pair equal to 360 //! or greater than key, or end() if all keys are smaller. lower_bound(const key_type & key)361 iterator lower_bound(const key_type& key) { 362 return tree_.lower_bound(key); 363 } 364 365 //! Searches the B+ tree and returns a constant iterator to the first pair 366 //! equal to or greater than key, or end() if all keys are smaller. lower_bound(const key_type & key) const367 const_iterator lower_bound(const key_type& key) const { 368 return tree_.lower_bound(key); 369 } 370 371 //! Searches the B+ tree and returns an iterator to the first pair greater 372 //! than key, or end() if all keys are smaller or equal. upper_bound(const key_type & key)373 iterator upper_bound(const key_type& key) { 374 return tree_.upper_bound(key); 375 } 376 377 //! Searches the B+ tree and returns a constant iterator to the first pair 378 //! greater than key, or end() if all keys are smaller or equal. upper_bound(const key_type & key) const379 const_iterator upper_bound(const key_type& key) const { 380 return tree_.upper_bound(key); 381 } 382 383 //! Searches the B+ tree and returns both lower_bound() and upper_bound(). equal_range(const key_type & key)384 std::pair<iterator, iterator> equal_range(const key_type& key) { 385 return tree_.equal_range(key); 386 } 387 388 //! Searches the B+ tree and returns both lower_bound() and upper_bound(). 389 std::pair<const_iterator, const_iterator> equal_range(const key_type & key) const390 equal_range(const key_type& key) const { 391 return tree_.equal_range(key); 392 } 393 394 //! \} 395 396 public: 397 //! \name B+ Tree Object Comparison Functions 398 //! \{ 399 400 //! Equality relation of B+ trees of the same type. B+ trees of the same 401 //! size and equal elements (both key and data) are considered equal. operator ==(const btree_map & other) const402 bool operator == (const btree_map& other) const { 403 return (tree_ == other.tree_); 404 } 405 406 //! Inequality relation. Based on operator==. operator !=(const btree_map & other) const407 bool operator != (const btree_map& other) const { 408 return (tree_ != other.tree_); 409 } 410 411 //! Total ordering relation of B+ trees of the same type. It uses 412 //! std::lexicographical_compare() for the actual comparison of elements. operator <(const btree_map & other) const413 bool operator < (const btree_map& other) const { 414 return (tree_ < other.tree_); 415 } 416 417 //! Greater relation. Based on operator<. operator >(const btree_map & other) const418 bool operator > (const btree_map& other) const { 419 return (tree_ > other.tree_); 420 } 421 422 //! Less-equal relation. Based on operator<. operator <=(const btree_map & other) const423 bool operator <= (const btree_map& other) const { 424 return (tree_ <= other.tree_); 425 } 426 427 //! Greater-equal relation. Based on operator<. operator >=(const btree_map & other) const428 bool operator >= (const btree_map& other) const { 429 return (tree_ >= other.tree_); 430 } 431 432 //! \} 433 434 public: 435 //! \name Fast Copy: Assign Operator and Copy Constructors 436 //! \{ 437 438 //! Assignment operator. All the key/data pairs are copied operator =(const btree_map & other)439 btree_map& operator = (const btree_map& other) { 440 if (this != &other) 441 tree_ = other.tree_; 442 return *this; 443 } 444 445 //! Copy constructor. The newly initialized B+ tree object will contain a 446 //! copy of all key/data pairs. btree_map(const btree_map & other)447 btree_map(const btree_map& other) 448 : tree_(other.tree_) 449 { } 450 451 //! \} 452 453 public: 454 //! \name Public Insertion Functions 455 //! \{ 456 457 //! Attempt to insert a key/data pair into the B+ tree. Fails if the pair is 458 //! already present. insert(const value_type & x)459 std::pair<iterator, bool> insert(const value_type& x) { 460 return tree_.insert(x); 461 } 462 463 //! Attempt to insert a key/data pair into the B+ tree. This function is the 464 //! same as the other insert. Fails if the inserted pair is already present. insert2(const key_type & key,const data_type & data)465 std::pair<iterator, bool> insert2( 466 const key_type& key, const data_type& data) { 467 return tree_.insert(value_type(key, data)); 468 } 469 470 //! Attempt to insert a key/data pair into the B+ tree. The iterator hint is 471 //! currently ignored by the B+ tree insertion routine. insert(iterator hint,const value_type & x)472 iterator insert(iterator hint, const value_type& x) { 473 return tree_.insert(hint, x); 474 } 475 476 //! Attempt to insert a key/data pair into the B+ tree. The iterator hint is 477 //! currently ignored by the B+ tree insertion routine. insert2(iterator hint,const key_type & key,const data_type & data)478 iterator insert2(iterator hint, 479 const key_type& key, const data_type& data) { 480 return tree_.insert(hint, value_type(key, data)); 481 } 482 483 //! Returns a reference to the object that is associated with a particular 484 //! key. If the map does not already contain such an object, operator[] 485 //! inserts the default object data_type(). operator [](const key_type & key)486 data_type& operator [] (const key_type& key) { 487 iterator i = insert(value_type(key, data_type())).first; 488 return i->second; 489 } 490 491 //! Attempt to insert the range [first,last) of value_type pairs into the B+ 492 //! tree. Each key/data pair is inserted individually. 493 template <typename InputIterator> insert(InputIterator first,InputIterator last)494 void insert(InputIterator first, InputIterator last) { 495 return tree_.insert(first, last); 496 } 497 498 //! Bulk load a sorted range [first,last). Loads items into leaves and 499 //! constructs a B-tree above them. The tree must be empty when calling this 500 //! function. 501 template <typename Iterator> bulk_load(Iterator first,Iterator last)502 void bulk_load(Iterator first, Iterator last) { 503 return tree_.bulk_load(first, last); 504 } 505 506 //! \} 507 508 public: 509 //! \name Public Erase Functions 510 //! \{ 511 512 //! Erases the key/data pairs associated with the given key. For this 513 //! unique-associative map there is no difference to erase(). erase_one(const key_type & key)514 bool erase_one(const key_type& key) { 515 return tree_.erase_one(key); 516 } 517 518 //! Erases all the key/data pairs associated with the given key. This is 519 //! implemented using erase_one(). erase(const key_type & key)520 size_type erase(const key_type& key) { 521 return tree_.erase(key); 522 } 523 524 //! Erase the key/data pair referenced by the iterator. erase(iterator iter)525 void erase(iterator iter) { 526 return tree_.erase(iter); 527 } 528 529 #ifdef TLX_BTREE_TODO 530 //! Erase all key/data pairs in the range [first,last). This function is 531 //! currently not implemented by the B+ Tree. erase(iterator,iterator)532 void erase(iterator /* first */, iterator /* last */) { 533 abort(); 534 } 535 #endif 536 537 //! \} 538 539 #ifdef TLX_BTREE_DEBUG 540 541 public: 542 //! \name Debug Printing 543 //! \{ 544 545 //! Print out the B+ tree structure with keys onto the given ostream. This 546 //! function requires that the header is compiled with TLX_BTREE_DEBUG and 547 //! that key_type is printable via std::ostream. print(std::ostream & os) const548 void print(std::ostream& os) const { 549 tree_.print(os); 550 } 551 552 //! Print out only the leaves via the double linked list. print_leaves(std::ostream & os) const553 void print_leaves(std::ostream& os) const { 554 tree_.print_leaves(os); 555 } 556 557 //! \} 558 #endif 559 560 public: 561 //! \name Verification of B+ Tree Invariants 562 //! \{ 563 564 //! Run a thorough verification of all B+ tree invariants. The program 565 //! aborts via TLX_BTREE_ASSERT() if something is wrong. verify() const566 void verify() const { 567 tree_.verify(); 568 } 569 570 //! \} 571 }; 572 573 //! \} 574 575 } // namespace tlx 576 577 #endif // !TLX_CONTAINER_BTREE_MAP_HEADER 578 579 /******************************************************************************/ 580