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