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