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