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