Branch data Line data Source code
1 : : // $Id: btree_multimap.h 128 2011-05-18 07:23:35Z tb $
2 : : /** \file btree_multimap.h
3 : : * Contains the specialized B+ tree template class btree_multimap
4 : : */
5 : :
6 : : /*
7 : : * STX B+ Tree Template Classes v0.8.6
8 : : * Copyright (C) 2008-2011 Timo Bingmann
9 : : *
10 : : * This library is free software; you can redistribute it and/or modify it
11 : : * under the terms of the GNU Lesser General Public License as published by the
12 : : * Free Software Foundation; either version 2.1 of the License, or (at your
13 : : * option) any later version.
14 : : *
15 : : * This library is distributed in the hope that it will be useful, but WITHOUT
16 : : * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 : : * FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License
18 : : * for more details.
19 : : *
20 : : * You should have received a copy of the GNU Lesser General Public License
21 : : * along with this library; if not, write to the Free Software Foundation,
22 : : * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
23 : : */
24 : :
25 : : #ifndef _STX_BTREE_MULTIMAP_H_
26 : : #define _STX_BTREE_MULTIMAP_H_
27 : :
28 : : #include <stx/btree.h>
29 : :
30 : : namespace stx {
31 : :
32 : : /** @brief Specialized B+ tree template class implementing STL's multimap
33 : : * container.
34 : : *
35 : : * Implements the STL multimap using a B+ tree. It can be used as a drop-in
36 : : * replacement for std::multimap. Not all asymptotic time requirements are met
37 : : * in theory. The class has a traits class defining B+ tree properties like
38 : : * slots and self-verification. Furthermore an allocator can be specified for
39 : : * tree nodes.
40 : : *
41 : : * Most noteworthy difference to the default red-black implementation of
42 : : * std::multimap is that the B+ tree does not hold key and data pair together
43 : : * in memory. Instead each B+ tree node has two arrays of keys and data
44 : : * values. This design directly generates many problems in implementing the
45 : : * iterator's operator's which return value_type composition pairs.
46 : : */
47 : : template <typename _Key, typename _Data,
48 : : typename _Compare = std::less<_Key>,
49 : : typename _Traits = btree_default_map_traits<_Key, _Data>,
50 : : typename _Alloc = std::allocator<std::pair<_Key, _Data> > >
51 : : class btree_multimap
52 : : {
53 : : public:
54 : : // *** Template Parameter Types
55 : :
56 : : /// First template parameter: The key type of the btree. This is stored in
57 : : /// inner nodes and leaves
58 : : typedef _Key key_type;
59 : :
60 : : /// Second template parameter: The data type associated with each
61 : : /// key. Stored in the B+ tree's leaves
62 : : typedef _Data data_type;
63 : :
64 : : /// Third template parameter: Key comparison function object
65 : : typedef _Compare key_compare;
66 : :
67 : : /// Fourth template parameter: Traits object used to define more parameters
68 : : /// of the B+ tree
69 : : typedef _Traits traits;
70 : :
71 : : /// Fifth template parameter: STL allocator
72 : : typedef _Alloc allocator_type;
73 : :
74 : : // The macro BTREE_FRIENDS can be used by outside class to access the B+
75 : : // tree internals. This was added for wxBTreeDemo to be able to draw the
76 : : // tree.
77 : : BTREE_FRIENDS
78 : :
79 : : public:
80 : : // *** Constructed Types
81 : :
82 : : /// Typedef of our own type
83 : : typedef btree_multimap<key_type, data_type, key_compare, traits, allocator_type> self;
84 : :
85 : : /// Construct the STL-required value_type as a composition pair of key and
86 : : /// data types
87 : : typedef std::pair<key_type, data_type> value_type;
88 : :
89 : : /// Implementation type of the btree_base
90 : : typedef stx::btree<key_type, data_type, value_type, key_compare, traits, true, 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 : : public:
102 : : // *** Static Constant Options and Values of the B+ Tree
103 : :
104 : : /// Base B+ tree parameter: The number of key/data slots in each leaf
105 : : static const unsigned short leafslotmax = btree_impl::leafslotmax;
106 : :
107 : : /// Base B+ tree parameter: The number of key slots in each inner node,
108 : : /// this can differ from slots in each leaf.
109 : : static const unsigned short innerslotmax = btree_impl::innerslotmax;
110 : :
111 : : /// Computed B+ tree parameter: The minimum number of key/data slots used
112 : : /// in a leaf. If fewer slots are used, the leaf will be merged or slots
113 : : /// shifted from it's siblings.
114 : : static const unsigned short minleafslots = btree_impl::minleafslots;
115 : :
116 : : /// Computed B+ tree parameter: The minimum number of key slots used
117 : : /// in an inner node. If fewer slots are used, the inner node will be
118 : : /// merged or slots shifted from it's siblings.
119 : : static const unsigned short mininnerslots = btree_impl::mininnerslots;
120 : :
121 : : /// Debug parameter: Enables expensive and thorough checking of the B+ tree
122 : : /// invariants after each insert/erase operation.
123 : : static const bool selfverify = btree_impl::selfverify;
124 : :
125 : : /// Debug parameter: Prints out lots of debug information about how the
126 : : /// algorithms change the tree. Requires the header file to be compiled
127 : : /// with BTREE_DEBUG and the key type must be std::ostream printable.
128 : : static const bool debug = btree_impl::debug;
129 : :
130 : : /// Operational parameter: Allow duplicate keys in the btree.
131 : : static const bool allow_duplicates = btree_impl::allow_duplicates;
132 : :
133 : : public:
134 : : // *** Iterators and Reverse Iterators
135 : :
136 : : /// STL-like iterator object for B+ tree items. The iterator points to a
137 : : /// specific slot number in a leaf.
138 : : typedef typename btree_impl::iterator iterator;
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::const_iterator const_iterator;
143 : :
144 : : /// create mutable reverse iterator by using STL magic
145 : : typedef typename btree_impl::reverse_iterator reverse_iterator;
146 : :
147 : : /// create constant reverse iterator by using STL magic
148 : : typedef typename btree_impl::const_reverse_iterator const_reverse_iterator;
149 : :
150 : : private:
151 : : // *** Tree Implementation Object
152 : :
153 : : /// The contained implementation object
154 : : btree_impl tree;
155 : :
156 : : public:
157 : : // *** Constructors and Destructor
158 : :
159 : : /// Default constructor initializing an empty B+ tree with the standard key
160 : : /// comparison function
161 : 6 : explicit inline btree_multimap(const allocator_type &alloc = allocator_type())
162 : 6 : : tree(alloc)
163 : : {
164 : 6 : }
165 : :
166 : : /// Constructor initializing an empty B+ tree with a special key
167 : : /// comparison object
168 : 0 : explicit inline btree_multimap(const key_compare &kcf,
169 : : const allocator_type &alloc = allocator_type())
170 : 0 : : tree(kcf, alloc)
171 : : {
172 : 0 : }
173 : :
174 : : /// Constructor initializing a B+ tree with the range [first,last)
175 : : template <class InputIterator>
176 : 1 : inline btree_multimap(InputIterator first, InputIterator last,
177 : : const allocator_type &alloc = allocator_type())
178 : 1 : : tree(first, last, alloc)
179 : : {
180 : 1 : }
181 : :
182 : : /// Constructor initializing a B+ tree with the range [first,last) and a
183 : : /// special key comparison object
184 : : template <class InputIterator>
185 : : inline btree_multimap(InputIterator first, InputIterator last, const key_compare &kcf,
186 : : const allocator_type &alloc = allocator_type())
187 : : : tree(first, last, kcf, alloc)
188 : : {
189 : : }
190 : :
191 : : /// Frees up all used B+ tree memory pages
192 : 8 : inline ~btree_multimap()
193 : 8 : {
194 : 8 : }
195 : :
196 : : /// Fast swapping of two identical B+ tree objects.
197 : 0 : void swap(self& from)
198 : : {
199 : 0 : std::swap(tree, from.tree);
200 : 0 : }
201 : :
202 : : public:
203 : : // *** Key and Value Comparison Function Objects
204 : :
205 : : /// Constant access to the key comparison object sorting the B+ tree
206 : 0 : inline key_compare key_comp() const
207 : : {
208 : 0 : return tree.key_comp();
209 : : }
210 : :
211 : : /// Constant access to a constructed value_type comparison object. required
212 : : /// by the STL
213 : 0 : inline value_compare value_comp() const
214 : : {
215 : 0 : return tree.value_comp();
216 : : }
217 : :
218 : : public:
219 : : // *** Allocators
220 : :
221 : : /// Return the base node allocator provided during construction.
222 : 0 : allocator_type get_allocator() const
223 : : {
224 : 0 : return tree.get_allocator();
225 : : }
226 : :
227 : : public:
228 : : // *** Fast Destruction of the B+ Tree
229 : :
230 : : /// Frees all key/data pairs and all nodes of the tree
231 : 0 : void clear()
232 : : {
233 : 0 : tree.clear();
234 : 0 : }
235 : :
236 : : public:
237 : : // *** STL Iterator Construction Functions
238 : :
239 : : /// Constructs a read/data-write iterator that points to the first slot in
240 : : /// the first leaf of the B+ tree.
241 : 3 : inline iterator begin()
242 : : {
243 : 3 : return tree.begin();
244 : : }
245 : :
246 : : /// Constructs a read/data-write iterator that points to the first invalid
247 : : /// slot in the last leaf of the B+ tree.
248 : 61101 : inline iterator end()
249 : : {
250 : 61101 : return tree.end();
251 : : }
252 : :
253 : : /// Constructs a read-only constant iterator that points to the first slot
254 : : /// in the first leaf of the B+ tree.
255 : 0 : inline const_iterator begin() const
256 : : {
257 : 0 : return tree.begin();
258 : : }
259 : :
260 : : /// Constructs a read-only constant iterator that points to the first
261 : : /// invalid slot in the last leaf of the B+ tree.
262 : 0 : inline const_iterator end() const
263 : : {
264 : 0 : return tree.end();
265 : : }
266 : :
267 : : /// Constructs a read/data-write reverse iterator that points to the first
268 : : /// invalid slot in the last leaf of the B+ tree. Uses STL magic.
269 : 2 : inline reverse_iterator rbegin()
270 : : {
271 : 2 : return tree.rbegin();
272 : : }
273 : :
274 : : /// Constructs a read/data-write reverse iterator that points to the first
275 : : /// slot in the first leaf of the B+ tree. Uses STL magic.
276 : 2 : inline reverse_iterator rend()
277 : : {
278 : 2 : return tree.rend();
279 : : }
280 : :
281 : : /// Constructs a read-only reverse iterator that points to the first
282 : : /// invalid slot in the last leaf of the B+ tree. Uses STL magic.
283 : 0 : inline const_reverse_iterator rbegin() const
284 : : {
285 : 0 : return tree.rbegin();
286 : : }
287 : :
288 : : /// Constructs a read-only reverse iterator that points to the first slot
289 : : /// in the first leaf of the B+ tree. Uses STL magic.
290 : 0 : inline const_reverse_iterator rend() const
291 : : {
292 : 0 : return tree.rend();
293 : : }
294 : :
295 : : public:
296 : : // *** Access Functions to the Item Count
297 : :
298 : : /// Return the number of key/data pairs in the B+ tree
299 : 39429 : inline size_type size() const
300 : : {
301 : 39429 : return tree.size();
302 : : }
303 : :
304 : : /// Returns true if there is at least one key/data pair in the B+ tree
305 : 6 : inline bool empty() const
306 : : {
307 : 6 : return tree.empty();
308 : : }
309 : :
310 : : /// Returns the largest possible size of the B+ Tree. This is just a
311 : : /// function required by the STL standard, the B+ Tree can hold more items.
312 : 0 : inline size_type max_size() const
313 : : {
314 : 0 : return tree.max_size();
315 : : }
316 : :
317 : : /// Return a const reference to the current statistics.
318 : 0 : inline const tree_stats& get_stats() const
319 : : {
320 : 0 : return tree.get_stats();
321 : : }
322 : :
323 : : public:
324 : : // *** Standard Access Functions Querying the Tree by Descending to a Leaf
325 : :
326 : : /// Non-STL function checking whether a key is in the B+ tree. The same as
327 : : /// (find(k) != end()) or (count() != 0).
328 : 7040 : bool exists(const key_type &key) const
329 : : {
330 : 7040 : return tree.exists(key);
331 : : }
332 : :
333 : : /// Tries to locate a key in the B+ tree and returns an iterator to the
334 : : /// key/data slot if found. If unsuccessful it returns end().
335 : 8868 : iterator find(const key_type &key)
336 : : {
337 : 8868 : return tree.find(key);
338 : : }
339 : :
340 : : /// Tries to locate a key in the B+ tree and returns an constant iterator
341 : : /// to the key/data slot if found. If unsuccessful it returns end().
342 : 0 : const_iterator find(const key_type &key) const
343 : : {
344 : 0 : return tree.find(key);
345 : : }
346 : :
347 : : /// Tries to locate a key in the B+ tree and returns the number of
348 : : /// identical key entries found.
349 : 7040 : size_type count(const key_type &key) const
350 : : {
351 : 7040 : return tree.count(key);
352 : : }
353 : :
354 : : /// Searches the B+ tree and returns an iterator to the first pair
355 : : /// equal to or greater than key, or end() if all keys are smaller.
356 : 1210 : iterator lower_bound(const key_type& key)
357 : : {
358 : 1210 : return tree.lower_bound(key);
359 : : }
360 : :
361 : : /// Searches the B+ tree and returns a constant iterator to the
362 : : /// first pair equal to or greater than key, or end() if all keys
363 : : /// are smaller.
364 : 0 : const_iterator lower_bound(const key_type& key) const
365 : : {
366 : 0 : return tree.lower_bound(key);
367 : : }
368 : :
369 : : /// Searches the B+ tree and returns an iterator to the first pair
370 : : /// greater than key, or end() if all keys are smaller or equal.
371 : 1210 : iterator upper_bound(const key_type& key)
372 : : {
373 : 1210 : return tree.upper_bound(key);
374 : : }
375 : :
376 : : /// Searches the B+ tree and returns a constant iterator to the
377 : : /// first pair greater than key, or end() if all keys are smaller
378 : : /// or equal.
379 : 0 : const_iterator upper_bound(const key_type& key) const
380 : : {
381 : 0 : return tree.upper_bound(key);
382 : : }
383 : :
384 : : /// Searches the B+ tree and returns both lower_bound() and upper_bound().
385 : 1210 : inline std::pair<iterator, iterator> equal_range(const key_type& key)
386 : : {
387 : 1210 : return tree.equal_range(key);
388 : : }
389 : :
390 : : /// Searches the B+ tree and returns both lower_bound() and upper_bound().
391 : 0 : inline std::pair<const_iterator, const_iterator> equal_range(const key_type& key) const
392 : : {
393 : 0 : return tree.equal_range(key);
394 : : }
395 : :
396 : : public:
397 : : // *** B+ Tree Object Comparison Functions
398 : :
399 : : /// Equality relation of B+ trees of the same type. B+ trees of the same
400 : : /// size and equal elements (both key and data) are considered
401 : : /// equal. Beware of the random ordering of duplicate keys.
402 : 0 : inline bool operator==(const self &other) const
403 : : {
404 : 0 : return (tree == other.tree);
405 : : }
406 : :
407 : : /// Inequality relation. Based on operator==.
408 : 0 : inline bool operator!=(const self &other) const
409 : : {
410 : 0 : return (tree != other.tree);
411 : : }
412 : :
413 : : /// Total ordering relation of B+ trees of the same type. It uses
414 : : /// std::lexicographical_compare() for the actual comparison of elements.
415 : 0 : inline bool operator<(const self &other) const
416 : : {
417 : 0 : return (tree < other.tree);
418 : : }
419 : :
420 : : /// Greater relation. Based on operator<.
421 : 0 : inline bool operator>(const self &other) const
422 : : {
423 : 0 : return (tree > other.tree);
424 : : }
425 : :
426 : : /// Less-equal relation. Based on operator<.
427 : 0 : inline bool operator<=(const self &other) const
428 : : {
429 : 0 : return (tree <= other.tree);
430 : : }
431 : :
432 : : /// Greater-equal relation. Based on operator<.
433 : 0 : inline bool operator>=(const self &other) const
434 : : {
435 : 0 : return (tree >= other.tree);
436 : : }
437 : :
438 : : public:
439 : : /// *** Fast Copy: Assign Operator and Copy Constructors
440 : :
441 : : /// Assignment operator. All the key/data pairs are copied
442 : 0 : inline self& operator= (const self &other)
443 : : {
444 [ # # ]: 0 : if (this != &other)
445 : : {
446 : 0 : tree = other.tree;
447 : : }
448 : 0 : return *this;
449 : : }
450 : :
451 : : /// Copy constructor. The newly initialized B+ tree object will contain a
452 : : /// copy or all key/data pairs.
453 : 1 : inline btree_multimap(const self &other)
454 : 1 : : tree(other.tree)
455 : : {
456 : 1 : }
457 : :
458 : : public:
459 : : // *** Public Insertion Functions
460 : :
461 : : /// Attempt to insert a key/data pair into the B+ tree. As this tree allows
462 : : /// duplicates insertion never fails.
463 : 0 : inline iterator insert(const value_type& x)
464 : : {
465 : 0 : return tree.insert2(x.first, x.second).first;
466 : : }
467 : :
468 : : /// Attempt to insert a key/data pair into the B+ tree. Beware that if
469 : : /// key_type == data_type, then the template iterator insert() is called
470 : : /// instead. As this tree allows duplicates insertion never fails.
471 : 0 : inline iterator insert(const key_type& key, const data_type& data)
472 : : {
473 : 0 : return tree.insert2(key, data).first;
474 : : }
475 : :
476 : : /// Attempt to insert a key/data pair into the B+ tree. This function is the
477 : : /// same as the other insert, however if key_type == data_type then the
478 : : /// non-template function cannot be called. As this tree allows duplicates
479 : : /// insertion never fails.
480 : 13028 : inline iterator insert2(const key_type& key, const data_type& data)
481 : : {
482 : 13028 : return tree.insert2(key, data).first;
483 : : }
484 : :
485 : : /// Attempt to insert a key/data pair into the B+ tree. The iterator hint
486 : : /// is currently ignored by the B+ tree insertion routine.
487 : 0 : inline iterator insert(iterator hint, const value_type &x)
488 : : {
489 : 0 : return tree.insert2(hint, x.first, x.second);
490 : : }
491 : :
492 : : /// Attempt to insert a key/data pair into the B+ tree. The iterator hint is
493 : : /// currently ignored by the B+ tree insertion routine.
494 : 0 : inline iterator insert2(iterator hint, const key_type& key, const data_type& data)
495 : : {
496 : 0 : return tree.insert2(hint, key, data);
497 : : }
498 : :
499 : : /// Attempt to insert the range [first,last) of value_type pairs into the B+
500 : : /// tree. Each key/data pair is inserted individually.
501 : : template <typename InputIterator>
502 : : inline void insert(InputIterator first, InputIterator last)
503 : : {
504 : : return tree.insert(first, last);
505 : : }
506 : :
507 : : public:
508 : : // *** Public Erase Functions
509 : :
510 : : /// Erases one (the first) of the key/data pairs associated with the given
511 : : /// key.
512 : 8036 : bool erase_one(const key_type &key)
513 : : {
514 : 8036 : return tree.erase_one(key);
515 : : }
516 : :
517 : : /// Erases all the key/data pairs associated with the given key. This is
518 : : /// implemented using erase_one() and thus not very efficient.
519 : 0 : size_type erase(const key_type &key)
520 : : {
521 : 0 : return tree.erase(key);
522 : : }
523 : :
524 : : /// Erase the key/data pair referenced by the iterator.
525 : 8192 : void erase(iterator iter)
526 : : {
527 : 8192 : return tree.erase(iter);
528 : : }
529 : :
530 : : #ifdef BTREE_TODO
531 : : /// Erase all key/data pairs in the range [first,last). This function is
532 : : /// currently not implemented by the B+ Tree.
533 : : void erase(iterator /* first */, iterator /* last */)
534 : : {
535 : : abort();
536 : : }
537 : : #endif
538 : :
539 : : #ifdef BTREE_DEBUG
540 : : public:
541 : : // *** Debug Printing
542 : :
543 : : /// Print out the B+ tree structure with keys onto the given ostream. This function
544 : : /// requires that the header is compiled with BTREE_DEBUG and that key_type
545 : : /// is printable via std::ostream.
546 : 0 : void print(std::ostream &os) const
547 : : {
548 : 0 : tree.print(os);
549 : 0 : }
550 : :
551 : : /// Print out only the leaves via the double linked list.
552 : 0 : void print_leaves(std::ostream &os) const
553 : : {
554 : 0 : tree.print_leaves(os);
555 : 0 : }
556 : : #endif
557 : :
558 : : public:
559 : : // *** Verification of B+ Tree Invariants
560 : :
561 : : /// Run a thorough verification of all B+ tree invariants. The program
562 : : /// aborts via BTREE_ASSERT() if something is wrong.
563 : 3 : void verify() const
564 : : {
565 : 3 : tree.verify();
566 : 3 : }
567 : :
568 : : public:
569 : :
570 : : /// Dump the contents of the B+ tree out onto an ostream as a binary
571 : : /// image. The image contains memory pointers which will be fixed when the
572 : : /// image is restored. For this to work your key_type and data_type must be
573 : : /// integral types and contain no pointers or references.
574 : 0 : void dump(std::ostream &os) const
575 : : {
576 : 0 : tree.dump(os);
577 : 0 : }
578 : :
579 : : /// Restore a binary image of a dumped B+ tree from an istream. The B+ tree
580 : : /// pointers are fixed using the dump order. For dump and restore to work
581 : : /// your key_type and data_type must be integral types and contain no
582 : : /// pointers or references. Returns true if the restore was successful.
583 : 0 : bool restore(std::istream &is)
584 : : {
585 : 0 : return tree.restore(is);
586 : : }
587 : : };
588 : :
589 : : } // namespace stx
590 : :
591 : : #endif // _STX_BTREE_MULTIMAP_H_
|
