1 : // $Id: btree_multiset.h 35 2007-04-27 11:26:33Z 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.7
8 : * Copyright (C) 2007 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 : private:
70 : // *** The Data_Type
71 :
72 : /// \internal The empty struct used as a placeholder for the data_type
73 : struct empty_struct
74 : {
75 : };
76 :
77 : public:
78 : // *** Constructed Types
79 :
80 : /// The empty data_type
81 : typedef struct empty_struct data_type;
82 :
83 : /// Construct the set value_type: the key_type.
84 : typedef key_type value_type;
85 :
86 : /// Typedef of our own type
87 : typedef btree_multiset<key_type, key_compare, traits> self;
88 :
89 : /// Implementation type of the btree_base
90 : typedef stx::btree<key_type, data_type, value_type, key_compare, traits, true> btree_impl;
91 :
92 : /// Function class comparing two value_type keys.
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 slots used in a
112 : /// leaf. If fewer slots are used, the leaf will be merged or slots shifted
113 : /// 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_PRINT 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 12 : inline btree_multiset()
162 12 : : tree()
163 12 : {
164 : }
165 :
166 : /// Constructor initializing an empty B+ tree with a special key
167 : /// comparison object
168 1 : inline btree_multiset(const key_compare &kcf)
169 1 : : tree(kcf)
170 1 : {
171 : }
172 :
173 : /// Constructor initializing a B+ tree with the range [first,last)
174 : template <class InputIterator>
175 1 : inline btree_multiset(InputIterator first, InputIterator last)
176 1 : : tree()
177 : {
178 1 : insert(first, last);
179 : }
180 :
181 : /// Constructor initializing a B+ tree with the range [first,last) and a
182 : /// special key comparison object
183 : template <class InputIterator>
184 : inline btree_multiset(InputIterator first, InputIterator last, const key_compare &kcf)
185 : : tree(kcf)
186 : {
187 : insert(first, last);
188 : }
189 :
190 : /// Frees up all used B+ tree memory pages
191 16 : inline ~btree_multiset()
192 16 : {
193 : }
194 :
195 : /// Fast swapping of two identical B+ tree objects.
196 0 : void swap(self& from)
197 : {
198 0 : std::swap(tree, from.tree);
199 : }
200 :
201 : public:
202 : // *** Key and Value Comparison Function Objects
203 :
204 : /// Constant access to the key comparison object sorting the B+ tree
205 0 : inline key_compare key_comp() const
206 : {
207 0 : return tree.key_comp();
208 : }
209 :
210 : /// Constant access to a constructed value_type comparison object. Required
211 : /// by the STL
212 0 : inline value_compare value_comp() const
213 : {
214 0 : return tree.value_comp();
215 : }
216 :
217 : public:
218 : // *** Fast Destruction of the B+ Tree
219 :
220 : /// Frees all keys and all nodes of the tree
221 0 : void clear()
222 : {
223 0 : tree.clear();
224 : }
225 :
226 : public:
227 : // *** STL Iterator Construction Functions
228 :
229 : /// Constructs a read/data-write iterator that points to the first slot in
230 : /// the first leaf of the B+ tree.
231 5 : inline iterator begin()
232 : {
233 5 : return tree.begin();
234 : }
235 :
236 : /// Constructs a read/data-write iterator that points to the first invalid
237 : /// slot in the last leaf of the B+ tree.
238 13849 : inline iterator end()
239 : {
240 13849 : return tree.end();
241 : }
242 :
243 : /// Constructs a read-only constant iterator that points to the first slot
244 : /// in the first leaf of the B+ tree.
245 0 : inline const_iterator begin() const
246 : {
247 0 : return tree.begin();
248 : }
249 :
250 : /// Constructs a read-only constant iterator that points to the first
251 : /// invalid slot in the last leaf of the B+ tree.
252 0 : inline const_iterator end() const
253 : {
254 0 : return tree.end();
255 : }
256 :
257 : /// Constructs a read/data-write reverse iterator that points to the first
258 : /// invalid slot in the last leaf of the B+ tree. Uses STL magic.
259 2 : inline reverse_iterator rbegin()
260 : {
261 2 : return tree.rbegin();
262 : }
263 :
264 : /// Constructs a read/data-write reverse iterator that points to the first
265 : /// slot in the first leaf of the B+ tree. Uses STL magic.
266 2 : inline reverse_iterator rend()
267 : {
268 2 : return tree.rend();
269 : }
270 :
271 : /// Constructs a read-only reverse iterator that points to the first
272 : /// invalid slot in the last leaf of the B+ tree. Uses STL magic.
273 0 : inline const_reverse_iterator rbegin() const
274 : {
275 0 : return tree.rbegin();
276 : }
277 :
278 : /// Constructs a read-only reverse iterator that points to the first slot
279 : /// in the first leaf of the B+ tree. Uses STL magic.
280 0 : inline const_reverse_iterator rend() const
281 : {
282 0 : return tree.rend();
283 : }
284 :
285 : public:
286 : // *** Access Functions to the Item Count
287 :
288 : /// Return the number of keys in the B+ tree
289 63303 : inline size_type size() const
290 : {
291 63303 : return tree.size();
292 : }
293 :
294 : /// Returns true if there is at least one key in the B+ tree
295 5 : inline bool empty() const
296 : {
297 5 : return tree.empty();
298 : }
299 :
300 : /// Returns the largest possible size of the B+ Tree. This is just a
301 : /// function required by the STL standard, the B+ Tree can hold more items.
302 0 : inline size_type max_size() const
303 : {
304 0 : return tree.max_size();
305 : }
306 :
307 : /// Return a const reference to the current statistics.
308 0 : inline const tree_stats& get_stats() const
309 : {
310 0 : return tree.get_stats();
311 : }
312 :
313 : public:
314 : // *** Standard Access Functions Querying the Tree by Descending to a Leaf
315 :
316 : /// Non-STL function checking whether a key is in the B+ tree. The same as
317 : /// (find(k) != end()) or (count() != 0).
318 30880 : bool exists(const key_type &key) const
319 : {
320 30880 : return tree.exists(key);
321 : }
322 :
323 : /// Tries to locate a key in the B+ tree and returns an iterator to the
324 : /// key slot if found. If unsuccessful it returns end().
325 0 : iterator find(const key_type &key)
326 : {
327 0 : return tree.find(key);
328 : }
329 :
330 : /// Tries to locate a key in the B+ tree and returns an constant iterator
331 : /// to the key slot if found. If unsuccessful it returns end().
332 0 : const_iterator find(const key_type &key) const
333 : {
334 0 : return tree.find(key);
335 : }
336 :
337 : /// Tries to locate a key in the B+ tree and returns the number of
338 : /// identical key entries found.
339 27680 : size_type count(const key_type &key) const
340 : {
341 27680 : return tree.count(key);
342 : }
343 :
344 : /// Searches the B+ tree and returns an iterator to the first key less or
345 : /// equal to the parameter. If unsuccessful it returns end().
346 0 : iterator lower_bound(const key_type& key)
347 : {
348 0 : return tree.lower_bound(key);
349 : }
350 :
351 : /// Searches the B+ tree and returns an constant iterator to the first key
352 : /// less or equal to the parameter. If unsuccessful it returns end().
353 0 : const_iterator lower_bound(const key_type& key) const
354 : {
355 0 : return tree.lower_bound(key);
356 : }
357 :
358 : /// Searches the B+ tree and returns an iterator to the first key greater
359 : /// than the parameter. If unsuccessful it returns end().
360 0 : iterator upper_bound(const key_type& key)
361 : {
362 0 : return tree.upper_bound(key);
363 : }
364 :
365 : /// Searches the B+ tree and returns an constant iterator to the first key
366 : /// greater than the parameter. If unsuccessful it returns end().
367 0 : const_iterator upper_bound(const key_type& key) const
368 : {
369 0 : return tree.upper_bound(key);
370 : }
371 :
372 : /// Searches the B+ tree and returns both lower_bound() and upper_bound().
373 0 : inline std::pair<iterator, iterator> equal_range(const key_type& key)
374 : {
375 0 : return tree.equal_range(key);
376 : }
377 :
378 : /// Searches the B+ tree and returns both lower_bound() and upper_bound().
379 0 : inline std::pair<const_iterator, const_iterator> equal_range(const key_type& key) const
380 : {
381 0 : return tree.equal_range(key);
382 : }
383 :
384 : public:
385 : // *** B+ Tree Object Comparison Functions
386 :
387 : /// Equality relation of B+ trees of the same type. B+ trees of the same
388 : /// size and equal key (counts) are considered equal.
389 4 : inline bool operator==(const self &other) const
390 : {
391 4 : return (tree == other.tree);
392 : }
393 :
394 : /// Inequality relation. Based on operator==.
395 1 : inline bool operator!=(const self &other) const
396 : {
397 1 : return (tree != other.tree);
398 : }
399 :
400 : /// Total ordering relation of B+ trees of the same type. It uses
401 : /// std::lexicographical_compare() for the actual comparison of elements.
402 1 : inline bool operator<(const self &other) const
403 : {
404 1 : return (tree < other.tree);
405 : }
406 :
407 : /// Greater relation. Based on operator<.
408 1 : inline bool operator>(const self &other) const
409 : {
410 1 : return (tree > other.tree);
411 : }
412 :
413 : /// Less-equal relation. Based on operator<.
414 1 : inline bool operator<=(const self &other) const
415 : {
416 1 : return (tree <= other.tree);
417 : }
418 :
419 : /// Greater-equal relation. Based on operator<.
420 1 : inline bool operator>=(const self &other) const
421 : {
422 1 : return (tree >= other.tree);
423 : }
424 :
425 : public:
426 : /// *** Fast Copy: Assign Operator and Copy Constructors
427 :
428 : /// Assignment operator. All the keys are copied
429 1 : inline self& operator= (const self &other)
430 : {
431 1 : if (this != &other)
432 : {
433 1 : tree = other.tree;
434 : }
435 1 : return *this;
436 : }
437 :
438 : /// Copy constructor. The newly initialized B+ tree object will contain a
439 : /// copy of all keys.
440 2 : inline btree_multiset(const self &other)
441 2 : : tree(other.tree)
442 2 : {
443 : }
444 :
445 : public:
446 : // *** Public Insertion Functions
447 :
448 : /// Attempt to insert a key into the B+ tree. As this set allows
449 : /// duplicates, this function never fails.
450 21268 : inline iterator insert(const key_type& x)
451 : {
452 21268 : return tree.insert2(x, data_type()).first;
453 : }
454 :
455 : /// Attempt to insert a key into the B+ tree. The iterator hint is
456 : /// currently ignored by the B+ tree insertion routine.
457 0 : inline iterator insert(iterator hint, const key_type &x)
458 : {
459 0 : return tree.insert2(hint, x, data_type());
460 : }
461 :
462 : /// Attempt to insert the range [first,last) of key_type into the B+
463 : /// tree. Each key is inserted individually.
464 : template <typename InputIterator>
465 1 : inline void insert(InputIterator first, InputIterator last)
466 : {
467 1 : InputIterator iter = first;
468 3202 : while(iter != last)
469 : {
470 3200 : insert(*iter);
471 3201 : ++iter;
472 : }
473 : }
474 :
475 : public:
476 : // *** Public Erase Functions
477 :
478 : /// Erases one (the first) entry of the given key.
479 17424 : bool erase_one(const key_type &key)
480 : {
481 17424 : return tree.erase_one(key);
482 : }
483 :
484 : /// Erases all the entries of the given key. This is implemented using
485 : /// erase_one() and thus not very efficient.
486 0 : size_type erase(const key_type &key)
487 : {
488 0 : return tree.erase(key);
489 : }
490 :
491 : #ifdef BTREE_TODO
492 : /// Erase the key referenced by the iterator.
493 : void erase(iterator iter)
494 : {
495 :
496 : }
497 : #endif
498 :
499 : #ifdef BTREE_TODO
500 : /// Erase all keys in the range [first,last). This function is currently
501 : /// not implemented by the B+ Tree.
502 : void erase(iterator /* first */, iterator /* last */)
503 : {
504 : abort();
505 : }
506 : #endif
507 :
508 : public:
509 : // *** Debug Printing
510 :
511 : /// Print out the B+ tree structure with keys onto std::cout. This function
512 : /// requires that the header is compiled with BTREE_PRINT and that key_type
513 : /// is printable via std::ostream.
514 0 : void print() const
515 : {
516 0 : tree.print();
517 : }
518 :
519 : /// Print out only the leaves via the double linked list.
520 0 : void print_leaves() const
521 : {
522 0 : tree.print_leaves();
523 : }
524 :
525 : public:
526 : // *** Verification of B+ Tree Invariants
527 :
528 : /// Run a thorough verification of all B+ tree invariants. The program
529 : /// aborts via BTREE_ASSERT() if something is wrong.
530 0 : void verify() const
531 : {
532 0 : tree.verify();
533 : }
534 :
535 : public:
536 :
537 : /// Dump the contents of the B+ tree out onto an ostream as a binary
538 : /// image. The image contains memory pointers which will be fixed when the
539 : /// image is restored. For this to work your key_type must be an integral
540 : /// type and contain no pointers or references.
541 1 : void dump(std::ostream &os) const
542 : {
543 1 : tree.dump(os);
544 : }
545 :
546 : /// Restore a binary image of a dumped B+ tree from an istream. The B+ tree
547 : /// pointers are fixed using the dump order. For dump and restore to work
548 : /// your key_type must be an integral type and contain no pointers or
549 : /// references. Returns true if the restore was successful.
550 2 : bool restore(std::istream &is)
551 : {
552 2 : return tree.restore(is);
553 : }
554 : };
555 :
556 : } // namespace stx
557 :
558 : #endif // _STX_BTREE_MULTISET_H_
|
