1 : // $Id: btree_set.h 35 2007-04-27 11:26:33Z 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.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_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 : private:
69 : // *** The data_type
70 :
71 : /// \internal The empty struct used as a placeholder for the data_type
72 : struct empty_struct
73 : {
74 : };
75 :
76 : public:
77 : // *** Constructed Types
78 :
79 : /// The empty data_type
80 : typedef struct empty_struct data_type;
81 :
82 : /// Construct the set value_type: the key_type.
83 : typedef key_type value_type;
84 :
85 : /// Typedef of our own type
86 : typedef btree_set<key_type, key_compare, traits> self;
87 :
88 : /// Implementation type of the btree_base
89 : typedef stx::btree<key_type, data_type, value_type, key_compare, traits, false> btree_impl;
90 :
91 : /// Function class comparing two value_type keys.
92 : typedef typename btree_impl::value_compare value_compare;
93 :
94 : /// Size type used to count keys
95 : typedef typename btree_impl::size_type size_type;
96 :
97 : /// Small structure containing statistics about the tree
98 : typedef typename btree_impl::tree_stats tree_stats;
99 :
100 : public:
101 : // *** Static Constant Options and Values of the B+ Tree
102 :
103 : /// Base B+ tree parameter: The number of key slots in each leaf
104 : static const unsigned short leafslotmax = btree_impl::leafslotmax;
105 :
106 : /// Base B+ tree parameter: The number of key slots in each inner node,
107 : /// this can differ from slots in each leaf.
108 : static const unsigned short innerslotmax = btree_impl::innerslotmax;
109 :
110 : /// Computed B+ tree parameter: The minimum number of key slots used in a
111 : /// leaf. If fewer slots are used, the leaf will be merged or slots shifted
112 : /// from it's siblings.
113 : static const unsigned short minleafslots = btree_impl::minleafslots;
114 :
115 : /// Computed B+ tree parameter: The minimum number of key slots used
116 : /// in an inner node. If fewer slots are used, the inner node will be
117 : /// merged or slots shifted from it's siblings.
118 : static const unsigned short mininnerslots = btree_impl::mininnerslots;
119 :
120 : /// Debug parameter: Enables expensive and thorough checking of the B+ tree
121 : /// invariants after each insert/erase operation.
122 : static const bool selfverify = btree_impl::selfverify;
123 :
124 : /// Debug parameter: Prints out lots of debug information about how the
125 : /// algorithms change the tree. Requires the header file to be compiled
126 : /// with BTREE_PRINT and the key type must be std::ostream printable.
127 : static const bool debug = btree_impl::debug;
128 :
129 : /// Operational parameter: Allow duplicate keys in the btree.
130 : static const bool allow_duplicates = btree_impl::allow_duplicates;
131 :
132 : public:
133 : // *** Iterators and Reverse Iterators
134 :
135 : /// STL-like iterator object for B+ tree items. The iterator points to a
136 : /// specific slot number in a leaf.
137 : typedef typename btree_impl::iterator iterator;
138 :
139 : /// STL-like iterator object for B+ tree items. The iterator points to a
140 : /// specific slot number in a leaf.
141 : typedef typename btree_impl::const_iterator const_iterator;
142 :
143 : /// create mutable reverse iterator by using STL magic
144 : typedef typename btree_impl::reverse_iterator reverse_iterator;
145 :
146 : /// create constant reverse iterator by using STL magic
147 : typedef typename btree_impl::const_reverse_iterator const_reverse_iterator;
148 :
149 : private:
150 : // *** Tree Implementation Object
151 :
152 : /// The contained implementation object
153 : btree_impl tree;
154 :
155 : public:
156 : // *** Constructors and Destructor
157 :
158 : /// Default constructor initializing an empty B+ tree with the standard key
159 : /// comparison function
160 0 : inline btree_set()
161 0 : : tree()
162 0 : {
163 : }
164 :
165 : /// Constructor initializing an empty B+ tree with a special key
166 : /// comparison object
167 0 : inline btree_set(const key_compare &kcf)
168 0 : : tree(kcf)
169 0 : {
170 : }
171 :
172 : /// Constructor initializing a B+ tree with the range [first,last)
173 : template <class InputIterator>
174 : inline btree_set(InputIterator first, InputIterator last)
175 : : tree()
176 : {
177 : insert(first, last);
178 : }
179 :
180 : /// Constructor initializing a B+ tree with the range [first,last) and a
181 : /// special key comparison object
182 : template <class InputIterator>
183 : inline btree_set(InputIterator first, InputIterator last, const key_compare &kcf)
184 : : tree(kcf)
185 : {
186 : insert(first, last);
187 : }
188 :
189 : /// Frees up all used B+ tree memory pages
190 0 : inline ~btree_set()
191 0 : {
192 : }
193 :
194 : /// Fast swapping of two identical B+ tree objects.
195 0 : void swap(self& from)
196 : {
197 0 : std::swap(tree, from.tree);
198 : }
199 :
200 : public:
201 : // *** Key and Value Comparison Function Objects
202 :
203 : /// Constant access to the key comparison object sorting the B+ tree
204 0 : inline key_compare key_comp() const
205 : {
206 0 : return tree.key_comp();
207 : }
208 :
209 : /// Constant access to a constructed value_type comparison object. required
210 : /// by the STL
211 0 : inline value_compare value_comp() const
212 : {
213 0 : return tree.value_comp();
214 : }
215 :
216 : public:
217 : // *** Fast Destruction of the B+ Tree
218 :
219 : /// Frees all keys and all nodes of the tree
220 0 : void clear()
221 : {
222 0 : tree.clear();
223 : }
224 :
225 : public:
226 : // *** STL Iterator Construction Functions
227 :
228 : /// Constructs a read/data-write iterator that points to the first slot in
229 : /// the first leaf of the B+ tree.
230 0 : inline iterator begin()
231 : {
232 0 : return tree.begin();
233 : }
234 :
235 : /// Constructs a read/data-write iterator that points to the first invalid
236 : /// slot in the last leaf of the B+ tree.
237 0 : inline iterator end()
238 : {
239 0 : return tree.end();
240 : }
241 :
242 : /// Constructs a read-only constant iterator that points to the first slot
243 : /// in the first leaf of the B+ tree.
244 0 : inline const_iterator begin() const
245 : {
246 0 : return tree.begin();
247 : }
248 :
249 : /// Constructs a read-only constant iterator that points to the first
250 : /// invalid slot in the last leaf of the B+ tree.
251 0 : inline const_iterator end() const
252 : {
253 0 : return tree.end();
254 : }
255 :
256 : /// Constructs a read/data-write reverse iterator that points to the first
257 : /// invalid slot in the last leaf of the B+ tree. Uses STL magic.
258 0 : inline reverse_iterator rbegin()
259 : {
260 0 : return tree.rbegin();
261 : }
262 :
263 : /// Constructs a read/data-write reverse iterator that points to the first
264 : /// slot in the first leaf of the B+ tree. Uses STL magic.
265 0 : inline reverse_iterator rend()
266 : {
267 0 : return tree.rend();
268 : }
269 :
270 : /// Constructs a read-only reverse iterator that points to the first
271 : /// invalid slot in the last leaf of the B+ tree. Uses STL magic.
272 0 : inline const_reverse_iterator rbegin() const
273 : {
274 0 : return tree.rbegin();
275 : }
276 :
277 : /// Constructs a read-only reverse iterator that points to the first slot
278 : /// in the first leaf of the B+ tree. Uses STL magic.
279 0 : inline const_reverse_iterator rend() const
280 : {
281 0 : return tree.rend();
282 : }
283 :
284 : public:
285 : // *** Access Functions to the Item Count
286 :
287 : /// Return the number of keys in the B+ tree
288 0 : inline size_type size() const
289 : {
290 0 : return tree.size();
291 : }
292 :
293 : /// Returns true if there is at least one key in the B+ tree
294 0 : inline bool empty() const
295 : {
296 0 : return tree.empty();
297 : }
298 :
299 : /// Returns the largest possible size of the B+ Tree. This is just a
300 : /// function required by the STL standard, the B+ Tree can hold more items.
301 0 : inline size_type max_size() const
302 : {
303 0 : return tree.max_size();
304 : }
305 :
306 : /// Return a const reference to the current statistics.
307 0 : inline const tree_stats& get_stats() const
308 : {
309 0 : return tree.get_stats();
310 : }
311 :
312 : public:
313 : // *** Standard Access Functions Querying the Tree by Descending to a Leaf
314 :
315 : /// Non-STL function checking whether a key is in the B+ tree. The same as
316 : /// (find(k) != end()) or (count() != 0).
317 0 : bool exists(const key_type &key) const
318 : {
319 0 : return tree.exists(key);
320 : }
321 :
322 : /// Tries to locate a key in the B+ tree and returns an iterator to the
323 : /// key slot if found. If unsuccessful it returns end().
324 0 : iterator find(const key_type &key)
325 : {
326 0 : return tree.find(key);
327 : }
328 :
329 : /// Tries to locate a key in the B+ tree and returns an constant iterator
330 : /// to the key slot if found. If unsuccessful it returns end().
331 0 : const_iterator find(const key_type &key) const
332 : {
333 0 : return tree.find(key);
334 : }
335 :
336 : /// Tries to locate a key in the B+ tree and returns the number of
337 : /// identical key entries found. As this is a unique set, count() returns
338 : /// either 0 or 1.
339 0 : size_type count(const key_type &key) const
340 : {
341 0 : 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 elements are considered equal.
389 0 : inline bool operator==(const self &other) const
390 : {
391 0 : return (tree == other.tree);
392 : }
393 :
394 : /// Inequality relation. Based on operator==.
395 0 : inline bool operator!=(const self &other) const
396 : {
397 0 : 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 0 : inline bool operator<(const self &other) const
403 : {
404 0 : return (tree < other.tree);
405 : }
406 :
407 : /// Greater relation. Based on operator<.
408 0 : inline bool operator>(const self &other) const
409 : {
410 0 : return (tree > other.tree);
411 : }
412 :
413 : /// Less-equal relation. Based on operator<.
414 0 : inline bool operator<=(const self &other) const
415 : {
416 0 : return (tree <= other.tree);
417 : }
418 :
419 : /// Greater-equal relation. Based on operator<.
420 0 : inline bool operator>=(const self &other) const
421 : {
422 0 : 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 0 : inline self& operator= (const self &other)
430 : {
431 0 : if (this != &other)
432 : {
433 0 : tree = other.tree;
434 : }
435 0 : return *this;
436 : }
437 :
438 : /// Copy constructor. The newly initialized B+ tree object will contain a
439 : /// copy of all keys.
440 0 : inline btree_set(const self &other)
441 0 : : tree(other.tree)
442 0 : {
443 : }
444 :
445 : public:
446 : // *** Public Insertion Functions
447 :
448 : /// Attempt to insert a key into the B+ tree. The insert will fail if it is
449 : /// already present.
450 0 : inline std::pair<iterator, bool> insert(const key_type& x)
451 : {
452 0 : return tree.insert2(x, data_type());
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 iterators dereferencing to
463 : /// key_type into the B+ tree. Each key/data pair is inserted individually.
464 : template <typename InputIterator>
465 : inline void insert(InputIterator first, InputIterator last)
466 : {
467 : InputIterator iter = first;
468 : while(iter != last)
469 : {
470 : insert(*iter);
471 : ++iter;
472 : }
473 : }
474 :
475 : public:
476 : // *** Public Erase Functions
477 :
478 : /// Erases the key from the set. As this is a unique set, there is no
479 : /// difference to erase().
480 0 : bool erase_one(const key_type &key)
481 : {
482 0 : return tree.erase_one(key);
483 : }
484 :
485 : /// Erases all the key/data pairs associated with the given key.
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 keys 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 0 : void dump(std::ostream &os) const
542 : {
543 0 : 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 0 : bool restore(std::istream &is)
551 : {
552 0 : return tree.restore(is);
553 : }
554 : };
555 :
556 : } // namespace stx
557 :
558 : #endif // _STX_BTREE_SET_H_
|
