1 : // $Id: btree_map.h 113 2008-09-07 15:25:51Z tb $
2 : /** \file btree_map.h
3 : * Contains the specialized B+ tree template class btree_map
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_MAP_H_
26 : #define _STX_BTREE_MAP_H_
27 :
28 : #include <stx/btree.h>
29 :
30 : namespace stx {
31 :
32 : /** @brief Specialized B+ tree template class implementing STL's map container.
33 : *
34 : * Implements the STL map using a B+ tree. It can be used as a drop-in
35 : * replacement for std::map. 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 : * Most noteworthy difference to the default red-black implementation of
40 : * std::map is that the B+ tree does not hold key and data pair together in
41 : * memory. Instead each B+ tree node has two arrays of keys and data
42 : * values. This design directly generates many problems in implementing the
43 : * iterator's operator's which return value_type composition pairs.
44 : */
45 : template <typename _Key, typename _Data,
46 : typename _Compare = std::less<_Key>,
47 : typename _Traits = btree_default_map_traits<_Key, _Data> >
48 : class btree_map
49 : {
50 : public:
51 : // *** Template Parameter Types
52 :
53 : /// First template parameter: The key type of the btree. This is stored in
54 : /// inner nodes and leaves
55 : typedef _Key key_type;
56 :
57 : /// Second template parameter: The data type associated with each
58 : /// key. Stored in the B+ tree's leaves
59 : typedef _Data data_type;
60 :
61 : /// Third template parameter: Key comparison function object
62 : typedef _Compare key_compare;
63 :
64 : /// Fourth 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 : public:
74 : // *** Constructed Types
75 :
76 : /// Typedef of our own type
77 : typedef btree_map<key_type, data_type, key_compare, traits> self;
78 :
79 : /// Construct the STL-required value_type as a composition pair of key and
80 : /// data types
81 : typedef std::pair<key_type, data_type> value_type;
82 :
83 : /// Implementation type of the btree_base
84 : typedef stx::btree<key_type, data_type, value_type, key_compare, traits, false> btree_impl;
85 :
86 : /// Function class comparing two value_type pairs.
87 : typedef typename btree_impl::value_compare value_compare;
88 :
89 : /// Size type used to count keys
90 : typedef typename btree_impl::size_type size_type;
91 :
92 : /// Small structure containing statistics about the tree
93 : typedef typename btree_impl::tree_stats tree_stats;
94 :
95 : public:
96 : // *** Static Constant Options and Values of the B+ Tree
97 :
98 : /// Base B+ tree parameter: The number of key/data slots in each leaf
99 : static const unsigned short leafslotmax = btree_impl::leafslotmax;
100 :
101 : /// Base B+ tree parameter: The number of key slots in each inner node,
102 : /// this can differ from slots in each leaf.
103 : static const unsigned short innerslotmax = btree_impl::innerslotmax;
104 :
105 : /// Computed B+ tree parameter: The minimum number of key/data slots used
106 : /// in a leaf. If fewer slots are used, the leaf will be merged or slots
107 : /// shifted from it's siblings.
108 : static const unsigned short minleafslots = btree_impl::minleafslots;
109 :
110 : /// Computed B+ tree parameter: The minimum number of key slots used
111 : /// in an inner node. If fewer slots are used, the inner node will be
112 : /// merged or slots shifted from it's siblings.
113 : static const unsigned short mininnerslots = btree_impl::mininnerslots;
114 :
115 : /// Debug parameter: Enables expensive and thorough checking of the B+ tree
116 : /// invariants after each insert/erase operation.
117 : static const bool selfverify = btree_impl::selfverify;
118 :
119 : /// Debug parameter: Prints out lots of debug information about how the
120 : /// algorithms change the tree. Requires the header file to be compiled
121 : /// with BTREE_DEBUG and the key type must be std::ostream printable.
122 : static const bool debug = btree_impl::debug;
123 :
124 : /// Operational parameter: Allow duplicate keys in the btree.
125 : static const bool allow_duplicates = btree_impl::allow_duplicates;
126 :
127 : public:
128 : // *** Iterators and Reverse Iterators
129 :
130 : /// STL-like iterator object for B+ tree items. The iterator points to a
131 : /// specific slot number in a leaf.
132 : typedef typename btree_impl::iterator iterator;
133 :
134 : /// STL-like iterator object for B+ tree items. The iterator points to a
135 : /// specific slot number in a leaf.
136 : typedef typename btree_impl::const_iterator const_iterator;
137 :
138 : /// create mutable reverse iterator by using STL magic
139 : typedef typename btree_impl::reverse_iterator reverse_iterator;
140 :
141 : /// create constant reverse iterator by using STL magic
142 : typedef typename btree_impl::const_reverse_iterator const_reverse_iterator;
143 :
144 : private:
145 : // *** Tree Implementation Object
146 :
147 : /// The contained implementation object
148 : btree_impl tree;
149 :
150 : public:
151 : // *** Constructors and Destructor
152 :
153 : /// Default constructor initializing an empty B+ tree with the standard key
154 : /// comparison function
155 2 : inline btree_map()
156 2 : : tree()
157 2 : {
158 : }
159 :
160 : /// Constructor initializing an empty B+ tree with a special key
161 : /// comparison object
162 0 : inline btree_map(const key_compare &kcf)
163 0 : : tree(kcf)
164 0 : {
165 : }
166 :
167 : /// Constructor initializing a B+ tree with the range [first,last)
168 : template <class InputIterator>
169 : inline btree_map(InputIterator first, InputIterator last)
170 : : tree(first, last)
171 : {
172 : }
173 :
174 : /// Constructor initializing a B+ tree with the range [first,last) and a
175 : /// special key comparison object
176 : template <class InputIterator>
177 : inline btree_map(InputIterator first, InputIterator last, const key_compare &kcf)
178 : : tree(first, last, kcf)
179 : {
180 : }
181 :
182 : /// Frees up all used B+ tree memory pages
183 2 : inline ~btree_map()
184 2 : {
185 : }
186 :
187 : /// Fast swapping of two identical B+ tree objects.
188 0 : void swap(self& from)
189 : {
190 0 : std::swap(tree, from.tree);
191 : }
192 :
193 : public:
194 : // *** Key and Value Comparison Function Objects
195 :
196 : /// Constant access to the key comparison object sorting the B+ tree
197 0 : inline key_compare key_comp() const
198 : {
199 0 : return tree.key_comp();
200 : }
201 :
202 : /// Constant access to a constructed value_type comparison object. required
203 : /// by the STL
204 0 : inline value_compare value_comp() const
205 : {
206 0 : return tree.value_comp();
207 : }
208 :
209 : public:
210 : // *** Fast Destruction of the B+ Tree
211 :
212 : /// Frees all key/data pairs and all nodes of the tree
213 0 : void clear()
214 : {
215 0 : tree.clear();
216 : }
217 :
218 : public:
219 : // *** STL Iterator Construction Functions
220 :
221 : /// Constructs a read/data-write iterator that points to the first slot in
222 : /// the first leaf of the B+ tree.
223 4004 : inline iterator begin()
224 : {
225 4004 : return tree.begin();
226 : }
227 :
228 : /// Constructs a read/data-write iterator that points to the first invalid
229 : /// slot in the last leaf of the B+ tree.
230 103998 : inline iterator end()
231 : {
232 103998 : return tree.end();
233 : }
234 :
235 : /// Constructs a read-only constant iterator that points to the first slot
236 : /// in the first leaf of the B+ tree.
237 0 : inline const_iterator begin() const
238 : {
239 0 : return tree.begin();
240 : }
241 :
242 : /// Constructs a read-only constant iterator that points to the first
243 : /// invalid slot in the last leaf of the B+ tree.
244 0 : inline const_iterator end() const
245 : {
246 0 : return tree.end();
247 : }
248 :
249 : /// Constructs a read/data-write reverse iterator that points to the first
250 : /// invalid slot in the last leaf of the B+ tree. Uses STL magic.
251 4004 : inline reverse_iterator rbegin()
252 : {
253 4004 : return tree.rbegin();
254 : }
255 :
256 : /// Constructs a read/data-write reverse iterator that points to the first
257 : /// slot in the first leaf of the B+ tree. Uses STL magic.
258 4008 : inline reverse_iterator rend()
259 : {
260 4008 : return tree.rend();
261 : }
262 :
263 : /// Constructs a read-only reverse iterator that points to the first
264 : /// invalid slot in the last leaf of the B+ tree. Uses STL magic.
265 0 : inline const_reverse_iterator rbegin() const
266 : {
267 0 : return tree.rbegin();
268 : }
269 :
270 : /// Constructs a read-only reverse iterator that points to the first slot
271 : /// in the first leaf of the B+ tree. Uses STL magic.
272 0 : inline const_reverse_iterator rend() const
273 : {
274 0 : return tree.rend();
275 : }
276 :
277 : public:
278 : // *** Access Functions to the Item Count
279 :
280 : /// Return the number of key/data pairs in the B+ tree
281 1 : inline size_type size() const
282 : {
283 1 : return tree.size();
284 : }
285 :
286 : /// Returns true if there is at least one key/data pair in the B+ tree
287 0 : inline bool empty() const
288 : {
289 0 : return tree.empty();
290 : }
291 :
292 : /// Returns the largest possible size of the B+ Tree. This is just a
293 : /// function required by the STL standard, the B+ Tree can hold more items.
294 0 : inline size_type max_size() const
295 : {
296 0 : return tree.max_size();
297 : }
298 :
299 : /// Return a const reference to the current statistics.
300 0 : inline const tree_stats& get_stats() const
301 : {
302 0 : return tree.get_stats();
303 : }
304 :
305 : public:
306 : // *** Standard Access Functions Querying the Tree by Descending to a Leaf
307 :
308 : /// Non-STL function checking whether a key is in the B+ tree. The same as
309 : /// (find(k) != end()) or (count() != 0).
310 0 : bool exists(const key_type &key) const
311 : {
312 0 : return tree.exists(key);
313 : }
314 :
315 : /// Tries to locate a key in the B+ tree and returns an iterator to the
316 : /// key/data slot if found. If unsuccessful it returns end().
317 99990 : iterator find(const key_type &key)
318 : {
319 99990 : return tree.find(key);
320 : }
321 :
322 : /// Tries to locate a key in the B+ tree and returns an constant iterator
323 : /// to the key/data slot if found. If unsuccessful it returns end().
324 0 : const_iterator find(const key_type &key) const
325 : {
326 0 : return tree.find(key);
327 : }
328 :
329 : /// Tries to locate a key in the B+ tree and returns the number of
330 : /// identical key entries found. Since this is a unique map, count()
331 : /// returns either 0 or 1.
332 0 : size_type count(const key_type &key) const
333 : {
334 0 : return tree.count(key);
335 : }
336 :
337 : /// Searches the B+ tree and returns an iterator to the first key less or
338 : /// equal to the parameter. If unsuccessful it returns end().
339 0 : iterator lower_bound(const key_type& key)
340 : {
341 0 : return tree.lower_bound(key);
342 : }
343 :
344 : /// Searches the B+ tree and returns an constant iterator to the first key less or
345 : /// equal to the parameter. If unsuccessful it returns end().
346 0 : const_iterator lower_bound(const key_type& key) const
347 : {
348 0 : return tree.lower_bound(key);
349 : }
350 :
351 : /// Searches the B+ tree and returns an iterator to the first key greater
352 : /// than the parameter. If unsuccessful it returns end().
353 0 : iterator upper_bound(const key_type& key)
354 : {
355 0 : return tree.upper_bound(key);
356 : }
357 :
358 : /// Searches the B+ tree and returns an constant iterator to the first key
359 : /// greater than the parameter. If unsuccessful it returns end().
360 0 : const_iterator upper_bound(const key_type& key) const
361 : {
362 0 : return tree.upper_bound(key);
363 : }
364 :
365 : /// Searches the B+ tree and returns both lower_bound() and upper_bound().
366 0 : inline std::pair<iterator, iterator> equal_range(const key_type& key)
367 : {
368 0 : return tree.equal_range(key);
369 : }
370 :
371 : /// Searches the B+ tree and returns both lower_bound() and upper_bound().
372 0 : inline std::pair<const_iterator, const_iterator> equal_range(const key_type& key) const
373 : {
374 0 : return tree.equal_range(key);
375 : }
376 :
377 : public:
378 : // *** B+ Tree Object Comparison Functions
379 :
380 : /// Equality relation of B+ trees of the same type. B+ trees of the same
381 : /// size and equal elements (both key and data) are considered
382 : /// equal.
383 0 : inline bool operator==(const self &other) const
384 : {
385 0 : return (tree == other.tree);
386 : }
387 :
388 : /// Inequality relation. Based on operator==.
389 0 : inline bool operator!=(const self &other) const
390 : {
391 0 : return (tree != other.tree);
392 : }
393 :
394 : /// Total ordering relation of B+ trees of the same type. It uses
395 : /// std::lexicographical_compare() for the actual comparison of elements.
396 0 : inline bool operator<(const self &other) const
397 : {
398 0 : return (tree < other.tree);
399 : }
400 :
401 : /// Greater relation. Based on operator<.
402 0 : inline bool operator>(const self &other) const
403 : {
404 0 : return (tree > other.tree);
405 : }
406 :
407 : /// Less-equal relation. Based on operator<.
408 0 : inline bool operator<=(const self &other) const
409 : {
410 0 : return (tree <= other.tree);
411 : }
412 :
413 : /// Greater-equal relation. Based on operator<.
414 0 : inline bool operator>=(const self &other) const
415 : {
416 0 : return (tree >= other.tree);
417 : }
418 :
419 : public:
420 : /// *** Fast Copy: Assign Operator and Copy Constructors
421 :
422 : /// Assignment operator. All the key/data pairs are copied
423 0 : inline self& operator= (const self &other)
424 : {
425 0 : if (this != &other)
426 : {
427 0 : tree = other.tree;
428 : }
429 0 : return *this;
430 : }
431 :
432 : /// Copy constructor. The newly initialized B+ tree object will contain a
433 : /// copy of all key/data pairs.
434 0 : inline btree_map(const self &other)
435 0 : : tree(other.tree)
436 0 : {
437 : }
438 :
439 : public:
440 : // *** Public Insertion Functions
441 :
442 : /// Attempt to insert a key/data pair into the B+ tree. Fails if the pair
443 : /// is already present.
444 2000 : inline std::pair<iterator, bool> insert(const value_type& x)
445 : {
446 2000 : return tree.insert2(x.first, x.second);
447 : }
448 :
449 : /// Attempt to insert a key/data pair into the B+ tree. Beware that if
450 : /// key_type == data_type, then the template iterator insert() is called
451 : /// instead. Fails if the inserted pair is already present.
452 0 : inline std::pair<iterator, bool> insert(const key_type& key, const data_type& data)
453 : {
454 0 : return tree.insert2(key, data);
455 : }
456 :
457 : /// Attempt to insert a key/data pair into the B+ tree. This function is the
458 : /// same as the other insert, however if key_type == data_type then the
459 : /// non-template function cannot be called. Fails if the inserted pair is
460 : /// already present.
461 0 : inline std::pair<iterator, bool> insert2(const key_type& key, const data_type& data)
462 : {
463 0 : return tree.insert2(key, data);
464 : }
465 :
466 : /// Attempt to insert a key/data pair into the B+ tree. The iterator hint
467 : /// is currently ignored by the B+ tree insertion routine.
468 0 : inline iterator insert(iterator hint, const value_type &x)
469 : {
470 0 : return tree.insert2(hint, x.first, x.second);
471 : }
472 :
473 : /// Attempt to insert a key/data pair into the B+ tree. The iterator hint is
474 : /// currently ignored by the B+ tree insertion routine.
475 0 : inline iterator insert2(iterator hint, const key_type& key, const data_type& data)
476 : {
477 0 : return tree.insert2(hint, key, data);
478 : }
479 :
480 : /// Returns a reference to the object that is associated with a particular
481 : /// key. If the map does not already contain such an object, operator[]
482 : /// inserts the default object data_type().
483 0 : inline data_type& operator[](const key_type& key)
484 : {
485 0 : iterator i = insert( value_type(key, data_type()) ).first;
486 0 : return i.data();
487 : }
488 :
489 : /// Attempt to insert the range [first,last) of value_type pairs into the B+
490 : /// tree. Each key/data pair is inserted individually.
491 : template <typename InputIterator>
492 : inline void insert(InputIterator first, InputIterator last)
493 : {
494 : return tree.insert(first, last);
495 : }
496 :
497 : public:
498 : // *** Public Erase Functions
499 :
500 : /// Erases the key/data pairs associated with the given key. For this
501 : /// unique-associative map there is no difference to erase().
502 0 : bool erase_one(const key_type &key)
503 : {
504 0 : return tree.erase_one(key);
505 : }
506 :
507 : /// Erases all the key/data pairs associated with the given key. This is
508 : /// implemented using erase_one().
509 0 : size_type erase(const key_type &key)
510 : {
511 0 : return tree.erase(key);
512 : }
513 :
514 : #ifdef BTREE_TODO
515 : /// Erase the key/data pair referenced by the iterator.
516 : void erase(iterator iter)
517 : {
518 :
519 : }
520 : #endif
521 :
522 : #ifdef BTREE_TODO
523 : /// Erase all key/data pairs in the range [first,last). This function is
524 : /// currently not implemented by the B+ Tree.
525 : void erase(iterator /* first */, iterator /* last */)
526 : {
527 : abort();
528 : }
529 : #endif
530 :
531 : #ifdef BTREE_DEBUG
532 : public:
533 : // *** Debug Printing
534 :
535 : /// Print out the B+ tree structure with keys onto the given ostream. This function
536 : /// requires that the header is compiled with BTREE_DEBUG and that key_type
537 : /// is printable via std::ostream.
538 0 : void print(std::ostream &os) const
539 : {
540 0 : tree.print(os);
541 : }
542 :
543 : /// Print out only the leaves via the double linked list.
544 0 : void print_leaves(std::ostream &os) const
545 : {
546 0 : tree.print_leaves(os);
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 : }
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 and data_type must be
565 : /// integral types and contain no pointers or references.
566 0 : void dump(std::ostream &os) const
567 : {
568 0 : tree.dump(os);
569 : }
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 and data_type must be integral types and contain no
574 : /// pointers or 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_MAP_H_
|
