1 : // $Id: btree_multimap.h 35 2007-04-27 11:26:33Z tb $
2 : /** \file btree_multimap.h
3 : * Contains the specialized B+ tree template class btree_multimap
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_MULTIMAP_H_
26 : #define _STX_BTREE_MULTIMAP_H_
27 :
28 : #include <stx/btree.h>
29 :
30 : namespace stx {
31 :
32 : /** @brief Specialized B+ tree template class implementing STL's multimap
33 : * container.
34 : *
35 : * Implements the STL multimap using a B+ tree. It can be used as a drop-in
36 : * replacement for std::multimap. Not all asymptotic time requirements are met in
37 : * theory. There is no allocator template parameter, instead the class has a
38 : * traits class defining B+ tree properties like slots and self-verification.
39 : *
40 : * Most noteworthy difference to the default red-black implementation of
41 : * std::multimap is that the B+ tree does not hold key and data pair together
42 : * in memory. Instead each B+ tree node has two arrays of keys and data
43 : * values. This design directly generates many problems in implementing the
44 : * iterator's operator's which return value_type composition pairs.
45 : */
46 : template <typename _Key, typename _Data,
47 : typename _Compare = std::less<_Key>,
48 : typename _Traits = btree_default_map_traits<_Key, _Data> >
49 : class btree_multimap
50 : {
51 : public:
52 : // *** Template Parameter Types
53 :
54 : /// First template parameter: The key type of the btree. This is stored in
55 : /// inner nodes and leaves
56 : typedef _Key key_type;
57 :
58 : /// Second template parameter: The data type associated with each
59 : /// key. Stored in the B+ tree's leaves
60 : typedef _Data data_type;
61 :
62 : /// Third template parameter: Key comparison function object
63 : typedef _Compare key_compare;
64 :
65 : /// Fourth template parameter: Traits object used to define more parameters
66 : /// of the B+ tree
67 : typedef _Traits traits;
68 :
69 : public:
70 : // *** Constructed Types
71 :
72 : /// Typedef of our own type
73 : typedef btree_multimap<key_type, data_type, key_compare, traits> self;
74 :
75 : /// Construct the STL-required value_type as a composition pair of key and
76 : /// data types
77 : typedef std::pair<key_type, data_type> value_type;
78 :
79 : /// Implementation type of the btree_base
80 : typedef stx::btree<key_type, data_type, value_type, key_compare, traits, true> btree_impl;
81 :
82 : /// Function class comparing two value_type pairs.
83 : typedef typename btree_impl::value_compare value_compare;
84 :
85 : /// Size type used to count keys
86 : typedef typename btree_impl::size_type size_type;
87 :
88 : /// Small structure containing statistics about the tree
89 : typedef typename btree_impl::tree_stats tree_stats;
90 :
91 : public:
92 : // *** Static Constant Options and Values of the B+ Tree
93 :
94 : /// Base B+ tree parameter: The number of key/data slots in each leaf
95 : static const unsigned short leafslotmax = btree_impl::leafslotmax;
96 :
97 : /// Base B+ tree parameter: The number of key slots in each inner node,
98 : /// this can differ from slots in each leaf.
99 : static const unsigned short innerslotmax = btree_impl::innerslotmax;
100 :
101 : /// Computed B+ tree parameter: The minimum number of key/data slots used
102 : /// in a leaf. If fewer slots are used, the leaf will be merged or slots
103 : /// shifted from it's siblings.
104 : static const unsigned short minleafslots = btree_impl::minleafslots;
105 :
106 : /// Computed B+ tree parameter: The minimum number of key slots used
107 : /// in an inner node. If fewer slots are used, the inner node will be
108 : /// merged or slots shifted from it's siblings.
109 : static const unsigned short mininnerslots = btree_impl::mininnerslots;
110 :
111 : /// Debug parameter: Enables expensive and thorough checking of the B+ tree
112 : /// invariants after each insert/erase operation.
113 : static const bool selfverify = btree_impl::selfverify;
114 :
115 : /// Debug parameter: Prints out lots of debug information about how the
116 : /// algorithms change the tree. Requires the header file to be compiled
117 : /// with BTREE_PRINT and the key type must be std::ostream printable.
118 : static const bool debug = btree_impl::debug;
119 :
120 : /// Operational parameter: Allow duplicate keys in the btree.
121 : static const bool allow_duplicates = btree_impl::allow_duplicates;
122 :
123 : public:
124 : // *** Iterators and Reverse Iterators
125 :
126 : /// STL-like iterator object for B+ tree items. The iterator points to a
127 : /// specific slot number in a leaf.
128 : typedef typename btree_impl::iterator iterator;
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::const_iterator const_iterator;
133 :
134 : /// create mutable reverse iterator by using STL magic
135 : typedef typename btree_impl::reverse_iterator reverse_iterator;
136 :
137 : /// create constant reverse iterator by using STL magic
138 : typedef typename btree_impl::const_reverse_iterator const_reverse_iterator;
139 :
140 : private:
141 : // *** Tree Implementation Object
142 :
143 : /// The contained implementation object
144 : btree_impl tree;
145 :
146 : public:
147 : // *** Constructors and Destructor
148 :
149 : /// Default constructor initializing an empty B+ tree with the standard key
150 : /// comparison function
151 2 : inline btree_multimap()
152 2 : : tree()
153 2 : {
154 : }
155 :
156 : /// Constructor initializing an empty B+ tree with a special key
157 : /// comparison object
158 0 : inline btree_multimap(const key_compare &kcf)
159 0 : : tree(kcf)
160 0 : {
161 : }
162 :
163 : /// Constructor initializing a B+ tree with the range [first,last)
164 : template <class InputIterator>
165 : inline btree_multimap(InputIterator first, InputIterator last)
166 : : tree(first, last)
167 : {
168 : }
169 :
170 : /// Constructor initializing a B+ tree with the range [first,last) and a
171 : /// special key comparison object
172 : template <class InputIterator>
173 : inline btree_multimap(InputIterator first, InputIterator last, const key_compare &kcf)
174 : : tree(first, last, kcf)
175 : {
176 : }
177 :
178 : /// Frees up all used B+ tree memory pages
179 2 : inline ~btree_multimap()
180 2 : {
181 : }
182 :
183 : /// Fast swapping of two identical B+ tree objects.
184 0 : void swap(self& from)
185 : {
186 0 : std::swap(tree, from.tree);
187 : }
188 :
189 : public:
190 : // *** Key and Value Comparison Function Objects
191 :
192 : /// Constant access to the key comparison object sorting the B+ tree
193 0 : inline key_compare key_comp() const
194 : {
195 0 : return tree.key_comp();
196 : }
197 :
198 : /// Constant access to a constructed value_type comparison object. required
199 : /// by the STL
200 0 : inline value_compare value_comp() const
201 : {
202 0 : return tree.value_comp();
203 : }
204 :
205 : public:
206 : // *** Fast Destruction of the B+ Tree
207 :
208 : /// Frees all key/data pairs and all nodes of the tree
209 0 : void clear()
210 : {
211 0 : tree.clear();
212 : }
213 :
214 : public:
215 : // *** STL Iterator Construction Functions
216 :
217 : /// Constructs a read/data-write iterator that points to the first slot in
218 : /// the first leaf of the B+ tree.
219 2 : inline iterator begin()
220 : {
221 2 : return tree.begin();
222 : }
223 :
224 : /// Constructs a read/data-write iterator that points to the first invalid
225 : /// slot in the last leaf of the B+ tree.
226 8364 : inline iterator end()
227 : {
228 8364 : return tree.end();
229 : }
230 :
231 : /// Constructs a read-only constant iterator that points to the first slot
232 : /// in the first leaf of the B+ tree.
233 0 : inline const_iterator begin() const
234 : {
235 0 : return tree.begin();
236 : }
237 :
238 : /// Constructs a read-only constant iterator that points to the first
239 : /// invalid slot in the last leaf of the B+ tree.
240 0 : inline const_iterator end() const
241 : {
242 0 : return tree.end();
243 : }
244 :
245 : /// Constructs a read/data-write reverse iterator that points to the first
246 : /// invalid slot in the last leaf of the B+ tree. Uses STL magic.
247 0 : inline reverse_iterator rbegin()
248 : {
249 0 : return tree.rbegin();
250 : }
251 :
252 : /// Constructs a read/data-write reverse iterator that points to the first
253 : /// slot in the first leaf of the B+ tree. Uses STL magic.
254 0 : inline reverse_iterator rend()
255 : {
256 0 : return tree.rend();
257 : }
258 :
259 : /// Constructs a read-only reverse iterator that points to the first
260 : /// invalid slot in the last leaf of the B+ tree. Uses STL magic.
261 0 : inline const_reverse_iterator rbegin() const
262 : {
263 0 : return tree.rbegin();
264 : }
265 :
266 : /// Constructs a read-only reverse iterator that points to the first slot
267 : /// in the first leaf of the B+ tree. Uses STL magic.
268 0 : inline const_reverse_iterator rend() const
269 : {
270 0 : return tree.rend();
271 : }
272 :
273 : public:
274 : // *** Access Functions to the Item Count
275 :
276 : /// Return the number of key/data pairs in the B+ tree
277 14082 : inline size_type size() const
278 : {
279 14082 : return tree.size();
280 : }
281 :
282 : /// Returns true if there is at least one key/data pair in the B+ tree
283 2 : inline bool empty() const
284 : {
285 2 : return tree.empty();
286 : }
287 :
288 : /// Returns the largest possible size of the B+ Tree. This is just a
289 : /// function required by the STL standard, the B+ Tree can hold more items.
290 0 : inline size_type max_size() const
291 : {
292 0 : return tree.max_size();
293 : }
294 :
295 : /// Return a const reference to the current statistics.
296 0 : inline const tree_stats& get_stats() const
297 : {
298 0 : return tree.get_stats();
299 : }
300 :
301 : public:
302 : // *** Standard Access Functions Querying the Tree by Descending to a Leaf
303 :
304 : /// Non-STL function checking whether a key is in the B+ tree. The same as
305 : /// (find(k) != end()) or (count() != 0).
306 7040 : bool exists(const key_type &key) const
307 : {
308 7040 : return tree.exists(key);
309 : }
310 :
311 : /// Tries to locate a key in the B+ tree and returns an iterator to the
312 : /// key/data slot if found. If unsuccessful it returns end().
313 0 : iterator find(const key_type &key)
314 : {
315 0 : return tree.find(key);
316 : }
317 :
318 : /// Tries to locate a key in the B+ tree and returns an constant iterator
319 : /// to the key/data slot if found. If unsuccessful it returns end().
320 0 : const_iterator find(const key_type &key) const
321 : {
322 0 : return tree.find(key);
323 : }
324 :
325 : /// Tries to locate a key in the B+ tree and returns the number of
326 : /// identical key entries found.
327 7040 : size_type count(const key_type &key) const
328 : {
329 7040 : 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 1210 : iterator lower_bound(const key_type& key)
335 : {
336 1210 : 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 1210 : iterator upper_bound(const key_type& key)
349 : {
350 1210 : 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 1210 : inline std::pair<iterator, iterator> equal_range(const key_type& key)
362 : {
363 1210 : 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. Beware of the random ordering of duplicate keys.
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 or all key/data pairs.
429 0 : inline btree_multimap(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. As this tree allows
438 : /// duplicates insertion never fails.
439 0 : inline iterator insert(const value_type& x)
440 : {
441 0 : return tree.insert2(x.first, x.second).first;
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. As this tree allows duplicates insertion never fails.
447 0 : inline iterator insert(const key_type& key, const data_type& data)
448 : {
449 0 : return tree.insert2(key, data).first;
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. As this tree allows duplicates
455 : /// insertion never fails.
456 3520 : inline iterator insert2(const key_type& key, const data_type& data)
457 : {
458 3520 : return tree.insert2(key, data).first;
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 : /// Attempt to insert the range [first,last) of value_type pairs into the B+
476 : /// tree. Each key/data pair is inserted individually.
477 : template <typename InputIterator>
478 : inline void insert(InputIterator first, InputIterator last)
479 : {
480 : return tree.insert(first, last);
481 : }
482 :
483 : public:
484 : // *** Public Erase Functions
485 :
486 : /// Erases one (the first) of the key/data pairs associated with the given
487 : /// key.
488 3520 : bool erase_one(const key_type &key)
489 : {
490 3520 : return tree.erase_one(key);
491 : }
492 :
493 : /// Erases all the key/data pairs associated with the given key. This is
494 : /// implemented using erase_one() and thus not very efficient.
495 0 : size_type erase(const key_type &key)
496 : {
497 0 : return tree.erase(key);
498 : }
499 :
500 : #ifdef BTREE_TODO
501 : /// Erase the key/data pair referenced by the iterator.
502 : void erase(iterator iter)
503 : {
504 :
505 : }
506 : #endif
507 :
508 : #ifdef BTREE_TODO
509 : /// Erase all key/data pairs in the range [first,last). This function is
510 : /// currently not implemented by the B+ Tree.
511 : void erase(iterator /* first */, iterator /* last */)
512 : {
513 : abort();
514 : }
515 : #endif
516 :
517 : public:
518 : // *** Debug Printing
519 :
520 : /// Print out the B+ tree structure with keys onto std::cout. This function
521 : /// requires that the header is compiled with BTREE_PRINT and that key_type
522 : /// is printable via std::ostream.
523 0 : void print() const
524 : {
525 0 : tree.print();
526 : }
527 :
528 : /// Print out only the leaves via the double linked list.
529 0 : void print_leaves() const
530 : {
531 0 : tree.print_leaves();
532 : }
533 :
534 : public:
535 : // *** Verification of B+ Tree Invariants
536 :
537 : /// Run a thorough verification of all B+ tree invariants. The program
538 : /// aborts via BTREE_ASSERT() if something is wrong.
539 0 : void verify() const
540 : {
541 0 : tree.verify();
542 : }
543 :
544 : public:
545 :
546 : /// Dump the contents of the B+ tree out onto an ostream as a binary
547 : /// image. The image contains memory pointers which will be fixed when the
548 : /// image is restored. For this to work your key_type and data_type must be
549 : /// integral types and contain no pointers or references.
550 0 : void dump(std::ostream &os) const
551 : {
552 0 : tree.dump(os);
553 : }
554 :
555 : /// Restore a binary image of a dumped B+ tree from an istream. The B+ tree
556 : /// pointers are fixed using the dump order. For dump and restore to work
557 : /// your key_type and data_type must be integral types and contain no
558 : /// pointers or references. Returns true if the restore was successful.
559 0 : bool restore(std::istream &is)
560 : {
561 0 : return tree.restore(is);
562 : }
563 : };
564 :
565 : } // namespace stx
566 :
567 : #endif // _STX_BTREE_MULTIMAP_H_
|
