stx/btree_multimap.h

Go to the documentation of this file.
00001 // $Id: btree_multimap.h 59 2007-05-13 11:08:30Z tb $
00006 /*
00007  * STX B+ Tree Template Classes v0.8
00008  * Copyright (C) 2007 Timo Bingmann
00009  *
00010  * This library is free software; you can redistribute it and/or modify it
00011  * under the terms of the GNU Lesser General Public License as published by the
00012  * Free Software Foundation; either version 2.1 of the License, or (at your
00013  * option) any later version.
00014  *
00015  * This library is distributed in the hope that it will be useful, but WITHOUT
00016  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
00017  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License
00018  * for more details.
00019  *
00020  * You should have received a copy of the GNU Lesser General Public License
00021  * along with this library; if not, write to the Free Software Foundation,
00022  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
00023  */
00024 
00025 #ifndef _STX_BTREE_MULTIMAP_H_
00026 #define _STX_BTREE_MULTIMAP_H_
00027 
00028 #include <stx/btree.h>
00029 
00030 namespace stx {
00031 
00046 template <typename _Key, typename _Data,
00047           typename _Compare = std::less<_Key>,
00048           typename _Traits = btree_default_map_traits<_Key, _Data> >
00049 class btree_multimap
00050 {
00051 public:
00052     // *** Template Parameter Types
00053 
00056     typedef _Key                        key_type;
00057 
00060     typedef _Data                       data_type;
00061 
00063     typedef _Compare                    key_compare;
00064 
00067     typedef _Traits                     traits;
00068 
00069     // The macro BTREE_FRIENDS can be used by outside class to access the B+
00070     // tree internals. This was added for wxBTreeDemo to be able to draw the
00071     // tree.
00072     BTREE_FRIENDS
00073 
00074 public:
00075     // *** Constructed Types
00076 
00078     typedef btree_multimap<key_type, data_type, key_compare, traits>    self;
00079 
00082     typedef std::pair<key_type, data_type>      value_type;
00083 
00085     typedef stx::btree<key_type, data_type, value_type, key_compare, traits, true> btree_impl;
00086 
00088     typedef typename btree_impl::value_compare  value_compare;
00089 
00091     typedef typename btree_impl::size_type      size_type;
00092 
00094     typedef typename btree_impl::tree_stats     tree_stats;
00095 
00096 public:
00097     // *** Static Constant Options and Values of the B+ Tree
00098 
00100     static const unsigned short         leafslotmax =  btree_impl::leafslotmax;
00101 
00104     static const unsigned short         innerslotmax =  btree_impl::innerslotmax;
00105 
00109     static const unsigned short         minleafslots = btree_impl::minleafslots;
00110 
00114     static const unsigned short         mininnerslots = btree_impl::mininnerslots;
00115 
00118     static const bool                   selfverify = btree_impl::selfverify;
00119 
00123     static const bool                   debug = btree_impl::debug;
00124 
00126     static const bool                   allow_duplicates = btree_impl::allow_duplicates;
00127 
00128 public:
00129     // *** Iterators and Reverse Iterators
00130 
00133     typedef typename btree_impl::iterator               iterator;
00134 
00137     typedef typename btree_impl::const_iterator         const_iterator;
00138 
00140     typedef typename btree_impl::reverse_iterator       reverse_iterator;
00141 
00143     typedef typename btree_impl::const_reverse_iterator const_reverse_iterator;
00144 
00145 private:
00146     // *** Tree Implementation Object
00147 
00149     btree_impl  tree;
00150 
00151 public:
00152     // *** Constructors and Destructor
00153 
00156     inline btree_multimap()
00157         : tree()
00158     {
00159     }
00160 
00163     inline btree_multimap(const key_compare &kcf)
00164         : tree(kcf)
00165     {
00166     }
00167 
00169     template <class InputIterator>
00170     inline btree_multimap(InputIterator first, InputIterator last)
00171         : tree(first, last)
00172     {
00173     }
00174 
00177     template <class InputIterator>
00178     inline btree_multimap(InputIterator first, InputIterator last, const key_compare &kcf)
00179         : tree(first, last, kcf)
00180     {
00181     }
00182 
00184     inline ~btree_multimap()
00185     {
00186     }
00187 
00189     void swap(self& from)
00190     {
00191         std::swap(tree, from.tree);
00192     }
00193 
00194 public:
00195     // *** Key and Value Comparison Function Objects
00196 
00198     inline key_compare key_comp() const
00199     {
00200         return tree.key_comp();
00201     }
00202 
00205     inline value_compare value_comp() const
00206     {
00207         return tree.value_comp();
00208     }
00209 
00210 public:
00211     // *** Fast Destruction of the B+ Tree
00212 
00214     void clear()
00215     {
00216         tree.clear();
00217     }
00218 
00219 public:
00220     // *** STL Iterator Construction Functions
00221 
00224     inline iterator begin()
00225     {
00226         return tree.begin();
00227     }
00228 
00231     inline iterator end()
00232     {
00233         return tree.end();
00234     }
00235 
00238     inline const_iterator begin() const
00239     {
00240         return tree.begin();
00241     }
00242 
00245     inline const_iterator end() const
00246     {
00247         return tree.end();
00248     }
00249 
00252     inline reverse_iterator rbegin()
00253     {
00254         return tree.rbegin();
00255     }
00256 
00259     inline reverse_iterator rend()
00260     {
00261         return tree.rend();
00262     }
00263 
00266     inline const_reverse_iterator rbegin() const
00267     {
00268         return tree.rbegin();
00269     }
00270 
00273     inline const_reverse_iterator rend() const
00274     {
00275         return tree.rend();
00276     }
00277 
00278 public:
00279     // *** Access Functions to the Item Count
00280 
00282     inline size_type size() const
00283     {
00284         return tree.size();
00285     }
00286 
00288     inline bool empty() const
00289     {
00290         return tree.empty();
00291     }
00292     
00295     inline size_type max_size() const
00296     {
00297         return tree.max_size();
00298     }
00299 
00301     inline const tree_stats& get_stats() const
00302     {
00303         return tree.get_stats();
00304     }
00305 
00306 public:
00307     // *** Standard Access Functions Querying the Tree by Descending to a Leaf
00308 
00311     bool exists(const key_type &key) const
00312     {
00313         return tree.exists(key);
00314     }
00315 
00318     iterator find(const key_type &key)
00319     {
00320         return tree.find(key);
00321     }
00322 
00325     const_iterator find(const key_type &key) const
00326     {
00327         return tree.find(key);
00328     }
00329 
00332     size_type count(const key_type &key) const
00333     {
00334         return tree.count(key);
00335     }
00336 
00339     iterator lower_bound(const key_type& key)
00340     {
00341         return tree.lower_bound(key);
00342     }
00343 
00346     const_iterator lower_bound(const key_type& key) const
00347     {
00348         return tree.lower_bound(key);
00349     }
00350 
00353     iterator upper_bound(const key_type& key)
00354     {
00355         return tree.upper_bound(key);
00356     }
00357 
00360     const_iterator upper_bound(const key_type& key) const
00361     {
00362         return tree.upper_bound(key);
00363     }
00364 
00366     inline std::pair<iterator, iterator> equal_range(const key_type& key)
00367     {
00368         return tree.equal_range(key);
00369     }
00370 
00372     inline std::pair<const_iterator, const_iterator> equal_range(const key_type& key) const
00373     {
00374         return tree.equal_range(key);
00375     }
00376 
00377 public:
00378     // *** B+ Tree Object Comparison Functions
00379 
00383     inline bool operator==(const self &other) const
00384     {
00385         return (tree == other.tree);
00386     }
00387 
00389     inline bool operator!=(const self &other) const
00390     {
00391         return (tree != other.tree);
00392     }
00393 
00396     inline bool operator<(const self &other) const
00397     {
00398         return (tree < other.tree);
00399     }
00400 
00402     inline bool operator>(const self &other) const
00403     {
00404         return (tree > other.tree);
00405     }
00406 
00408     inline bool operator<=(const self &other) const
00409     {
00410         return (tree <= other.tree);
00411     }
00412 
00414     inline bool operator>=(const self &other) const
00415     {
00416         return (tree >= other.tree);
00417     }
00418 
00419 public:
00421 
00423     inline self& operator= (const self &other)
00424     {
00425         if (this != &other)
00426         {
00427             tree = other.tree;
00428         }
00429         return *this;
00430     }
00431 
00434     inline btree_multimap(const self &other)
00435         : tree(other.tree)
00436     {
00437     }
00438     
00439 public:
00440     // *** Public Insertion Functions
00441 
00444     inline iterator insert(const value_type& x)
00445     {
00446         return tree.insert2(x.first, x.second).first;
00447     }
00448     
00452     inline iterator insert(const key_type& key, const data_type& data)
00453     {
00454         return tree.insert2(key, data).first;
00455     }
00456 
00461     inline iterator insert2(const key_type& key, const data_type& data)
00462     {
00463         return tree.insert2(key, data).first;
00464     }
00465 
00468     inline iterator insert(iterator hint, const value_type &x)
00469     {
00470         return tree.insert2(hint, x.first, x.second);
00471     }
00472 
00475     inline iterator insert2(iterator hint, const key_type& key, const data_type& data)
00476     {
00477         return tree.insert2(hint, key, data);
00478     }
00479 
00482     template <typename InputIterator>
00483     inline void insert(InputIterator first, InputIterator last)
00484     {
00485         return tree.insert(first, last);
00486     }
00487 
00488 public:
00489     // *** Public Erase Functions
00490 
00493     bool erase_one(const key_type &key)
00494     {
00495         return tree.erase_one(key);
00496     }
00497 
00500     size_type erase(const key_type &key)
00501     {
00502         return tree.erase(key);
00503     }
00504 
00505 #ifdef BTREE_TODO
00507     void erase(iterator iter)
00508     {
00509 
00510     }
00511 #endif
00512 
00513 #ifdef BTREE_TODO
00516     void erase(iterator /* first */, iterator /* last */)
00517     {
00518         abort();
00519     }
00520 #endif
00521 
00522 #ifdef BTREE_DEBUG
00523 public:
00524     // *** Debug Printing
00525 
00529     void print(std::ostream &os) const
00530     {
00531         tree.print(os);
00532     }
00533 
00535     void print_leaves(std::ostream &os) const
00536     {
00537         tree.print_leaves(os);
00538     }
00539 #endif
00540 
00541 public:
00542     // *** Verification of B+ Tree Invariants
00543 
00546     void verify() const
00547     {
00548         tree.verify();
00549     }
00550 
00551 public:
00552 
00557     void dump(std::ostream &os) const
00558     {
00559         tree.dump(os);
00560     }
00561 
00566     bool restore(std::istream &is)
00567     {
00568         return tree.restore(is);
00569     }
00570 };
00571 
00572 } // namespace stx
00573 
00574 #endif // _STX_BTREE_MULTIMAP_H_

Generated on Sun May 13 19:24:41 2007 for STX B+ Tree Template Classes by  doxygen 1.5.2