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