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