Branch data Line data Source code
1 : : // $Id: btree_set.h 128 2011-05-18 07:23:35Z tb $
2 : : /** \file btree_set.h
3 : : * Contains the specialized B+ tree template class btree_set
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_SET_H_
26 : : #define _STX_BTREE_SET_H_
27 : :
28 : : #include <stx/btree.h>
29 : :
30 : : namespace stx {
31 : :
32 : : /** @brief Specialized B+ tree template class implementing STL's set container.
33 : : *
34 : : * Implements the STL set using a B+ tree. It can be used as a drop-in
35 : : * replacement for std::set. Not all asymptotic time requirements are met in
36 : : * theory. The class has a traits class defining B+ tree properties like slots
37 : : * and self-verification. Furthermore an allocator can be specified for tree
38 : : * nodes.
39 : : *
40 : : * It is somewhat inefficient to implement a set using a B+ tree, a plain B
41 : : * 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 : : typename _Alloc = std::allocator<_Key> >
54 : : class btree_set
55 : : {
56 : : public:
57 : : // *** Template Parameter Types
58 : :
59 : : /// First template parameter: The key type of the B+ tree. This is stored
60 : : /// in inner nodes and leaves
61 : : typedef _Key key_type;
62 : :
63 : : /// Second template parameter: Key comparison function object
64 : : typedef _Compare key_compare;
65 : :
66 : : /// Third template parameter: Traits object used to define more parameters
67 : : /// of the B+ tree
68 : : typedef _Traits traits;
69 : :
70 : : /// Fourth template parameter: STL allocator
71 : : typedef _Alloc allocator_type;
72 : :
73 : : /// The macro BTREE_FRIENDS can be used by outside class to access the B+
74 : : /// tree internals. This was added for wxBTreeDemo to be able to draw the
75 : : /// tree.
76 : : BTREE_FRIENDS
77 : :
78 : : private:
79 : : // *** The data_type
80 : :
81 : : /// \internal The empty struct used as a placeholder for the data_type
82 : : struct empty_struct
83 : : {
84 : : };
85 : :
86 : : public:
87 : : // *** Constructed Types
88 : :
89 : : /// The empty data_type
90 : : typedef struct empty_struct data_type;
91 : :
92 : : /// Construct the set value_type: the key_type.
93 : : typedef key_type value_type;
94 : :
95 : : /// Typedef of our own type
96 : : typedef btree_set<key_type, key_compare, traits, allocator_type> self;
97 : :
98 : : /// Implementation type of the btree_base
99 : : typedef stx::btree<key_type, data_type, value_type, key_compare, traits, false, allocator_type> btree_impl;
100 : :
101 : : /// Function class comparing two value_type keys.
102 : : typedef typename btree_impl::value_compare value_compare;
103 : :
104 : : /// Size type used to count keys
105 : : typedef typename btree_impl::size_type size_type;
106 : :
107 : : /// Small structure containing statistics about the tree
108 : : typedef typename btree_impl::tree_stats tree_stats;
109 : :
110 : : public:
111 : : // *** Static Constant Options and Values of the B+ Tree
112 : :
113 : : /// Base B+ tree parameter: The number of key slots in each leaf
114 : : static const unsigned short leafslotmax = btree_impl::leafslotmax;
115 : :
116 : : /// Base B+ tree parameter: The number of key slots in each inner node,
117 : : /// this can differ from slots in each leaf.
118 : : static const unsigned short innerslotmax = btree_impl::innerslotmax;
119 : :
120 : : /// Computed B+ tree parameter: The minimum number of key slots used in a
121 : : /// leaf. If fewer slots are used, the leaf will be merged or slots shifted
122 : : /// from it's siblings.
123 : : static const unsigned short minleafslots = btree_impl::minleafslots;
124 : :
125 : : /// Computed B+ tree parameter: The minimum number of key slots used
126 : : /// in an inner node. If fewer slots are used, the inner node will be
127 : : /// merged or slots shifted from it's siblings.
128 : : static const unsigned short mininnerslots = btree_impl::mininnerslots;
129 : :
130 : : /// Debug parameter: Enables expensive and thorough checking of the B+ tree
131 : : /// invariants after each insert/erase operation.
132 : : static const bool selfverify = btree_impl::selfverify;
133 : :
134 : : /// Debug parameter: Prints out lots of debug information about how the
135 : : /// algorithms change the tree. Requires the header file to be compiled
136 : : /// with BTREE_DEBUG and the key type must be std::ostream printable.
137 : : static const bool debug = btree_impl::debug;
138 : :
139 : : /// Operational parameter: Allow duplicate keys in the btree.
140 : : static const bool allow_duplicates = btree_impl::allow_duplicates;
141 : :
142 : : public:
143 : : // *** Iterators and Reverse Iterators
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::iterator iterator;
148 : :
149 : : /// STL-like iterator object for B+ tree items. The iterator points to a
150 : : /// specific slot number in a leaf.
151 : : typedef typename btree_impl::const_iterator const_iterator;
152 : :
153 : : /// create mutable reverse iterator by using STL magic
154 : : typedef typename btree_impl::reverse_iterator reverse_iterator;
155 : :
156 : : /// create constant reverse iterator by using STL magic
157 : : typedef typename btree_impl::const_reverse_iterator const_reverse_iterator;
158 : :
159 : : private:
160 : : // *** Tree Implementation Object
161 : :
162 : : /// The contained implementation object
163 : : btree_impl tree;
164 : :
165 : : public:
166 : : // *** Constructors and Destructor
167 : :
168 : : /// Default constructor initializing an empty B+ tree with the standard key
169 : : /// comparison function
170 : 2 : explicit inline btree_set(const allocator_type &alloc = allocator_type())
171 : 2 : : tree(alloc)
172 : : {
173 : 2 : }
174 : :
175 : : /// Constructor initializing an empty B+ tree with a special key
176 : : /// comparison object
177 : 0 : explicit inline btree_set(const key_compare &kcf,
178 : : const allocator_type &alloc = allocator_type())
179 : 0 : : tree(kcf, alloc)
180 : : {
181 : 0 : }
182 : :
183 : : /// Constructor initializing a B+ tree with the range [first,last)
184 : : template <class InputIterator>
185 : : inline btree_set(InputIterator first, InputIterator last,
186 : : const allocator_type &alloc = allocator_type())
187 : : : tree(alloc)
188 : : {
189 : : insert(first, last);
190 : : }
191 : :
192 : : /// Constructor initializing a B+ tree with the range [first,last) and a
193 : : /// special key comparison object
194 : : template <class InputIterator>
195 : : inline btree_set(InputIterator first, InputIterator last, const key_compare &kcf,
196 : : const allocator_type &alloc = allocator_type())
197 : : : tree(kcf, alloc)
198 : : {
199 : : insert(first, last);
200 : : }
201 : :
202 : : /// Frees up all used B+ tree memory pages
203 : 2 : inline ~btree_set()
204 : 2 : {
205 : 2 : }
206 : :
207 : : /// Fast swapping of two identical B+ tree objects.
208 : 0 : void swap(self& from)
209 : : {
210 : 0 : std::swap(tree, from.tree);
211 : 0 : }
212 : :
213 : : public:
214 : : // *** Key and Value Comparison Function Objects
215 : :
216 : : /// Constant access to the key comparison object sorting the B+ tree
217 : 0 : inline key_compare key_comp() const
218 : : {
219 : 0 : return tree.key_comp();
220 : : }
221 : :
222 : : /// Constant access to a constructed value_type comparison object. required
223 : : /// by the STL
224 : 0 : inline value_compare value_comp() const
225 : : {
226 : 0 : return tree.value_comp();
227 : : }
228 : :
229 : : public:
230 : : // *** Allocators
231 : :
232 : : /// Return the base node allocator provided during construction.
233 : 0 : allocator_type get_allocator() const
234 : : {
235 : 0 : return tree.get_allocator();
236 : : }
237 : :
238 : : public:
239 : : // *** Fast Destruction of the B+ Tree
240 : :
241 : : /// Frees all keys and all nodes of the tree
242 : 0 : void clear()
243 : : {
244 : 0 : tree.clear();
245 : 0 : }
246 : :
247 : : public:
248 : : // *** STL Iterator Construction Functions
249 : :
250 : : /// Constructs a read/data-write iterator that points to the first slot in
251 : : /// the first leaf of the B+ tree.
252 : 4012 : inline iterator begin()
253 : : {
254 : 4012 : return tree.begin();
255 : : }
256 : :
257 : : /// Constructs a read/data-write iterator that points to the first invalid
258 : : /// slot in the last leaf of the B+ tree.
259 : 4016 : inline iterator end()
260 : : {
261 : 4016 : return tree.end();
262 : : }
263 : :
264 : : /// Constructs a read-only constant iterator that points to the first slot
265 : : /// in the first leaf of the B+ tree.
266 : 0 : inline const_iterator begin() const
267 : : {
268 : 0 : return tree.begin();
269 : : }
270 : :
271 : : /// Constructs a read-only constant iterator that points to the first
272 : : /// invalid slot in the last leaf of the B+ tree.
273 : 0 : inline const_iterator end() const
274 : : {
275 : 0 : return tree.end();
276 : : }
277 : :
278 : : /// Constructs a read/data-write reverse iterator that points to the first
279 : : /// invalid slot in the last leaf of the B+ tree. Uses STL magic.
280 : 4012 : inline reverse_iterator rbegin()
281 : : {
282 : 4012 : return tree.rbegin();
283 : : }
284 : :
285 : : /// Constructs a read/data-write reverse iterator that points to the first
286 : : /// slot in the first leaf of the B+ tree. Uses STL magic.
287 : 4016 : inline reverse_iterator rend()
288 : : {
289 : 4016 : return tree.rend();
290 : : }
291 : :
292 : : /// Constructs a read-only reverse iterator that points to the first
293 : : /// invalid slot in the last leaf of the B+ tree. Uses STL magic.
294 : 0 : inline const_reverse_iterator rbegin() const
295 : : {
296 : 0 : return tree.rbegin();
297 : : }
298 : :
299 : : /// Constructs a read-only reverse iterator that points to the first slot
300 : : /// in the first leaf of the B+ tree. Uses STL magic.
301 : 0 : inline const_reverse_iterator rend() const
302 : : {
303 : 0 : return tree.rend();
304 : : }
305 : :
306 : : public:
307 : : // *** Access Functions to the Item Count
308 : :
309 : : /// Return the number of keys in the B+ tree
310 : 0 : inline size_type size() const
311 : : {
312 : 0 : return tree.size();
313 : : }
314 : :
315 : : /// Returns true if there is at least one key in the B+ tree
316 : 0 : inline bool empty() const
317 : : {
318 : 0 : return tree.empty();
319 : : }
320 : :
321 : : /// Returns the largest possible size of the B+ Tree. This is just a
322 : : /// function required by the STL standard, the B+ Tree can hold more items.
323 : 0 : inline size_type max_size() const
324 : : {
325 : 0 : return tree.max_size();
326 : : }
327 : :
328 : : /// Return a const reference to the current statistics.
329 : 0 : inline const tree_stats& get_stats() const
330 : : {
331 : 0 : return tree.get_stats();
332 : : }
333 : :
334 : : public:
335 : : // *** Standard Access Functions Querying the Tree by Descending to a Leaf
336 : :
337 : : /// Non-STL function checking whether a key is in the B+ tree. The same as
338 : : /// (find(k) != end()) or (count() != 0).
339 : 0 : bool exists(const key_type &key) const
340 : : {
341 : 0 : return tree.exists(key);
342 : : }
343 : :
344 : : /// Tries to locate a key in the B+ tree and returns an iterator to the
345 : : /// key slot if found. If unsuccessful it returns end().
346 : 0 : iterator find(const key_type &key)
347 : : {
348 : 0 : return tree.find(key);
349 : : }
350 : :
351 : : /// Tries to locate a key in the B+ tree and returns an constant iterator
352 : : /// to the key slot if found. If unsuccessful it returns end().
353 : 0 : const_iterator find(const key_type &key) const
354 : : {
355 : 0 : return tree.find(key);
356 : : }
357 : :
358 : : /// Tries to locate a key in the B+ tree and returns the number of
359 : : /// identical key entries found. As this is a unique set, count() returns
360 : : /// either 0 or 1.
361 : 0 : size_type count(const key_type &key) const
362 : : {
363 : 0 : 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 elements are considered equal.
413 : 0 : inline bool operator==(const self &other) const
414 : : {
415 : 0 : return (tree == other.tree);
416 : : }
417 : :
418 : : /// Inequality relation. Based on operator==.
419 : 0 : inline bool operator!=(const self &other) const
420 : : {
421 : 0 : 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 : 0 : inline bool operator<(const self &other) const
427 : : {
428 : 0 : return (tree < other.tree);
429 : : }
430 : :
431 : : /// Greater relation. Based on operator<.
432 : 0 : inline bool operator>(const self &other) const
433 : : {
434 : 0 : return (tree > other.tree);
435 : : }
436 : :
437 : : /// Less-equal relation. Based on operator<.
438 : 0 : inline bool operator<=(const self &other) const
439 : : {
440 : 0 : return (tree <= other.tree);
441 : : }
442 : :
443 : : /// Greater-equal relation. Based on operator<.
444 : 0 : inline bool operator>=(const self &other) const
445 : : {
446 : 0 : 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 : 0 : inline self& operator= (const self &other)
454 : : {
455 [ # # ]: 0 : if (this != &other)
456 : : {
457 : 0 : tree = other.tree;
458 : : }
459 : 0 : return *this;
460 : : }
461 : :
462 : : /// Copy constructor. The newly initialized B+ tree object will contain a
463 : : /// copy of all keys.
464 : 0 : inline btree_set(const self &other)
465 : 0 : : tree(other.tree)
466 : : {
467 : 0 : }
468 : :
469 : : public:
470 : : // *** Public Insertion Functions
471 : :
472 : : /// Attempt to insert a key into the B+ tree. The insert will fail if it is
473 : : /// already present.
474 : 1100 : inline std::pair<iterator, bool> insert(const key_type& x)
475 : : {
476 : 1100 : return tree.insert2(x, data_type());
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 iterators dereferencing to
487 : : /// key_type into the B+ tree. Each key/data pair is inserted individually.
488 : : template <typename InputIterator>
489 : : inline void insert(InputIterator first, InputIterator last)
490 : : {
491 : : InputIterator iter = first;
492 : : while(iter != last)
493 : : {
494 : : insert(*iter);
495 : : ++iter;
496 : : }
497 : : }
498 : :
499 : : public:
500 : : // *** Public Erase Functions
501 : :
502 : : /// Erases the key from the set. As this is a unique set, there is no
503 : : /// difference to erase().
504 : 0 : bool erase_one(const key_type &key)
505 : : {
506 : 0 : return tree.erase_one(key);
507 : : }
508 : :
509 : : /// Erases all the key/data pairs associated with the given key.
510 : 0 : size_type erase(const key_type &key)
511 : : {
512 : 0 : 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 : :
548 : : #endif
549 : :
550 : : public:
551 : : // *** Verification of B+ Tree Invariants
552 : :
553 : : /// Run a thorough verification of all B+ tree invariants. The program
554 : : /// aborts via BTREE_ASSERT() if something is wrong.
555 : 0 : void verify() const
556 : : {
557 : 0 : tree.verify();
558 : 0 : }
559 : :
560 : : public:
561 : :
562 : : /// Dump the contents of the B+ tree out onto an ostream as a binary
563 : : /// image. The image contains memory pointers which will be fixed when the
564 : : /// image is restored. For this to work your key_type must be an integral
565 : : /// type and contain no pointers or references.
566 : 0 : void dump(std::ostream &os) const
567 : : {
568 : 0 : tree.dump(os);
569 : 0 : }
570 : :
571 : : /// Restore a binary image of a dumped B+ tree from an istream. The B+ tree
572 : : /// pointers are fixed using the dump order. For dump and restore to work
573 : : /// your key_type must be an integral type and contain no pointers or
574 : : /// references. Returns true if the restore was successful.
575 : 0 : bool restore(std::istream &is)
576 : : {
577 : 0 : return tree.restore(is);
578 : : }
579 : : };
580 : :
581 : : } // namespace stx
582 : :
583 : : #endif // _STX_BTREE_SET_H_
|
