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