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