stx/btree_multiset.h

Go to the documentation of this file.
00001 // $Id: btree_multiset.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_MULTISET_H_
00026 #define _STX_BTREE_MULTISET_H_
00027 
00028 #include <stx/btree.h>
00029 
00030 namespace stx {
00031 
00050 template <typename _Key,
00051           typename _Compare = std::less<_Key>,
00052           typename _Traits = btree_default_set_traits<_Key> >
00053 class btree_multiset
00054 {
00055 public:
00056     // *** Template Parameter Types
00057 
00060     typedef _Key                        key_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 private:
00075     // *** The Data_Type
00076 
00078     struct empty_struct
00079     {
00080     };
00081 
00082 public:
00083     // *** Constructed Types
00084 
00086     typedef struct empty_struct         data_type;
00087 
00089     typedef key_type                    value_type;
00090 
00092     typedef btree_multiset<key_type, key_compare, traits>       self;
00093 
00095     typedef stx::btree<key_type, data_type, value_type, key_compare, traits, true> btree_impl;
00096 
00098     typedef typename btree_impl::value_compare  value_compare;
00099 
00101     typedef typename btree_impl::size_type      size_type;
00102 
00104     typedef typename btree_impl::tree_stats     tree_stats;
00105 
00106 public:
00107     // *** Static Constant Options and Values of the B+ Tree
00108 
00110     static const unsigned short         leafslotmax =  btree_impl::leafslotmax;
00111 
00114     static const unsigned short         innerslotmax =  btree_impl::innerslotmax;
00115 
00119     static const unsigned short         minleafslots = btree_impl::minleafslots;
00120 
00124     static const unsigned short         mininnerslots = btree_impl::mininnerslots;
00125 
00128     static const bool                   selfverify = btree_impl::selfverify;
00129 
00133     static const bool                   debug = btree_impl::debug;
00134 
00136     static const bool                   allow_duplicates = btree_impl::allow_duplicates;
00137 
00138 public:
00139     // *** Iterators and Reverse Iterators
00140 
00143     typedef typename btree_impl::iterator               iterator;
00144 
00147     typedef typename btree_impl::const_iterator         const_iterator;
00148 
00150     typedef typename btree_impl::reverse_iterator       reverse_iterator;
00151 
00153     typedef typename btree_impl::const_reverse_iterator const_reverse_iterator;
00154 
00155 private:
00156     // *** Tree Implementation Object
00157 
00159     btree_impl  tree;
00160 
00161 public:
00162     // *** Constructors and Destructor
00163 
00166     inline btree_multiset()
00167         : tree()
00168     {
00169     }
00170 
00173     inline btree_multiset(const key_compare &kcf)
00174         : tree(kcf)
00175     {
00176     }
00177 
00179     template <class InputIterator>
00180     inline btree_multiset(InputIterator first, InputIterator last)
00181         : tree()
00182     {
00183         insert(first, last);
00184     }
00185 
00188     template <class InputIterator>
00189     inline btree_multiset(InputIterator first, InputIterator last, const key_compare &kcf)
00190         : tree(kcf)
00191     {
00192         insert(first, last);
00193     }
00194 
00196     inline ~btree_multiset()
00197     {
00198     }
00199 
00201     void swap(self& from)
00202     {
00203         std::swap(tree, from.tree);
00204     }
00205 
00206 public:
00207     // *** Key and Value Comparison Function Objects
00208 
00210     inline key_compare key_comp() const
00211     {
00212         return tree.key_comp();
00213     }
00214 
00217     inline value_compare value_comp() const
00218     {
00219         return tree.value_comp();
00220     }
00221 
00222 public:
00223     // *** Fast Destruction of the B+ Tree
00224 
00226     void clear()
00227     {
00228         tree.clear();
00229     }
00230 
00231 public:
00232     // *** STL Iterator Construction Functions
00233 
00236     inline iterator begin()
00237     {
00238         return tree.begin();
00239     }
00240 
00243     inline iterator end()
00244     {
00245         return tree.end();
00246     }
00247 
00250     inline const_iterator begin() const
00251     {
00252         return tree.begin();
00253     }
00254 
00257     inline const_iterator end() const
00258     {
00259         return tree.end();
00260     }
00261 
00264     inline reverse_iterator rbegin()
00265     {
00266         return tree.rbegin();
00267     }
00268 
00271     inline reverse_iterator rend()
00272     {
00273         return tree.rend();
00274     }
00275 
00278     inline const_reverse_iterator rbegin() const
00279     {
00280         return tree.rbegin();
00281     }
00282 
00285     inline const_reverse_iterator rend() const
00286     {
00287         return tree.rend();
00288     }
00289 
00290 public:
00291     // *** Access Functions to the Item Count
00292 
00294     inline size_type size() const
00295     {
00296         return tree.size();
00297     }
00298 
00300     inline bool empty() const
00301     {
00302         return tree.empty();
00303     }
00304     
00307     inline size_type max_size() const
00308     {
00309         return tree.max_size();
00310     }
00311 
00313     inline const tree_stats& get_stats() const
00314     {
00315         return tree.get_stats();
00316     }
00317 
00318 public:
00319     // *** Standard Access Functions Querying the Tree by Descending to a Leaf
00320 
00323     bool exists(const key_type &key) const
00324     {
00325         return tree.exists(key);
00326     }
00327 
00330     iterator find(const key_type &key)
00331     {
00332         return tree.find(key);
00333     }
00334 
00337     const_iterator find(const key_type &key) const
00338     {
00339         return tree.find(key);
00340     }
00341 
00344     size_type count(const key_type &key) const
00345     {
00346         return tree.count(key);
00347     }
00348 
00351     iterator lower_bound(const key_type& key)
00352     {
00353         return tree.lower_bound(key);
00354     }
00355 
00358     const_iterator lower_bound(const key_type& key) const
00359     {
00360         return tree.lower_bound(key);
00361     }
00362 
00365     iterator upper_bound(const key_type& key)
00366     {
00367         return tree.upper_bound(key);
00368     }
00369 
00372     const_iterator upper_bound(const key_type& key) const
00373     {
00374         return tree.upper_bound(key);
00375     }
00376 
00378     inline std::pair<iterator, iterator> equal_range(const key_type& key)
00379     {
00380         return tree.equal_range(key);
00381     }
00382 
00384     inline std::pair<const_iterator, const_iterator> equal_range(const key_type& key) const
00385     {
00386         return tree.equal_range(key);
00387     }
00388 
00389 public:
00390     // *** B+ Tree Object Comparison Functions
00391 
00394     inline bool operator==(const self &other) const
00395     {
00396         return (tree == other.tree);
00397     }
00398 
00400     inline bool operator!=(const self &other) const
00401     {
00402         return (tree != other.tree);
00403     }
00404 
00407     inline bool operator<(const self &other) const
00408     {
00409         return (tree < other.tree);
00410     }
00411 
00413     inline bool operator>(const self &other) const
00414     {
00415         return (tree > other.tree);
00416     }
00417 
00419     inline bool operator<=(const self &other) const
00420     {
00421         return (tree <= other.tree);
00422     }
00423 
00425     inline bool operator>=(const self &other) const
00426     {
00427         return (tree >= other.tree);
00428     }
00429 
00430 public:
00432 
00434     inline self& operator= (const self &other)
00435     {
00436         if (this != &other)
00437         {
00438             tree = other.tree;
00439         }
00440         return *this;
00441     }
00442 
00445     inline btree_multiset(const self &other)
00446         : tree(other.tree)
00447     {
00448     }
00449     
00450 public:
00451     // *** Public Insertion Functions
00452 
00455     inline iterator insert(const key_type& x)
00456     {
00457         return tree.insert2(x, data_type()).first;
00458     }
00459     
00462     inline iterator insert(iterator hint, const key_type &x)
00463     {
00464         return tree.insert2(hint, x, data_type());
00465     }
00466 
00469     template <typename InputIterator>
00470     inline void insert(InputIterator first, InputIterator last)
00471     {
00472         InputIterator iter = first;
00473         while(iter != last)
00474         {
00475             insert(*iter);
00476             ++iter;
00477         }
00478     }
00479 
00480 public:
00481     // *** Public Erase Functions
00482 
00484     bool erase_one(const key_type &key)
00485     {
00486         return tree.erase_one(key);
00487     }
00488 
00491     size_type erase(const key_type &key)
00492     {
00493         return tree.erase(key);
00494     }
00495 
00496 #ifdef BTREE_TODO
00498     void erase(iterator iter)
00499     {
00500 
00501     }
00502 #endif
00503 
00504 #ifdef BTREE_TODO
00507     void erase(iterator /* first */, iterator /* last */)
00508     {
00509         abort();
00510     }
00511 #endif
00512 
00513 #ifdef BTREE_DEBUG
00514 public:
00515     // *** Debug Printing
00516 
00520     void print(std::ostream &os) const
00521     {
00522         tree.print(os);
00523     }
00524 
00526     void print_leaves(std::ostream &os) const
00527     {
00528         tree.print_leaves(os);
00529     }
00530 #endif
00531 
00532 public:
00533     // *** Verification of B+ Tree Invariants
00534 
00537     void verify() const
00538     {
00539         tree.verify();
00540     }
00541 
00542 public:
00543 
00548     void dump(std::ostream &os) const
00549     {
00550         tree.dump(os);
00551     }
00552 
00557     bool restore(std::istream &is)
00558     {
00559         return tree.restore(is);
00560     }
00561 };
00562 
00563 } // namespace stx
00564 
00565 #endif // _STX_BTREE_MULTISET_H_

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