stx/btree_map.h

Go to the documentation of this file.
00001 // $Id: btree_map.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_MAP_H_
00026 #define _STX_BTREE_MAP_H_
00027 
00028 #include <stx/btree.h>
00029 
00030 namespace stx {
00031 
00045 template <typename _Key, typename _Data,
00046           typename _Compare = std::less<_Key>,
00047           typename _Traits = btree_default_map_traits<_Key, _Data> >
00048 class btree_map
00049 {
00050 public:
00051     // *** Template Parameter Types
00052 
00055     typedef _Key                        key_type;
00056 
00059     typedef _Data                       data_type;
00060 
00062     typedef _Compare                    key_compare;
00063 
00066     typedef _Traits                     traits;
00067 
00068     // The macro BTREE_FRIENDS can be used by outside class to access the B+
00069     // tree internals. This was added for wxBTreeDemo to be able to draw the
00070     // tree.
00071     BTREE_FRIENDS
00072 
00073 public:
00074     // *** Constructed Types
00075 
00077     typedef btree_map<key_type, data_type, key_compare, traits> self;
00078 
00081     typedef std::pair<key_type, data_type>      value_type;
00082 
00084     typedef stx::btree<key_type, data_type, value_type, key_compare, traits, false> btree_impl;
00085 
00087     typedef typename btree_impl::value_compare  value_compare;
00088 
00090     typedef typename btree_impl::size_type      size_type;
00091 
00093     typedef typename btree_impl::tree_stats     tree_stats;
00094 
00095 public:
00096     // *** Static Constant Options and Values of the B+ Tree
00097 
00099     static const unsigned short         leafslotmax =  btree_impl::leafslotmax;
00100 
00103     static const unsigned short         innerslotmax =  btree_impl::innerslotmax;
00104 
00108     static const unsigned short         minleafslots = btree_impl::minleafslots;
00109 
00113     static const unsigned short         mininnerslots = btree_impl::mininnerslots;
00114 
00117     static const bool                   selfverify = btree_impl::selfverify;
00118 
00122     static const bool                   debug = btree_impl::debug;
00123 
00125     static const bool                   allow_duplicates = btree_impl::allow_duplicates;
00126 
00127 public:
00128     // *** Iterators and Reverse Iterators
00129 
00132     typedef typename btree_impl::iterator               iterator;
00133 
00136     typedef typename btree_impl::const_iterator         const_iterator;
00137 
00139     typedef typename btree_impl::reverse_iterator       reverse_iterator;
00140 
00142     typedef typename btree_impl::const_reverse_iterator const_reverse_iterator;
00143 
00144 private:
00145     // *** Tree Implementation Object
00146 
00148     btree_impl  tree;
00149 
00150 public:
00151     // *** Constructors and Destructor
00152 
00155     inline btree_map()
00156         : tree()
00157     {
00158     }
00159 
00162     inline btree_map(const key_compare &kcf)
00163         : tree(kcf)
00164     {
00165     }
00166 
00168     template <class InputIterator>
00169     inline btree_map(InputIterator first, InputIterator last)
00170         : tree(first, last)
00171     {
00172     }
00173 
00176     template <class InputIterator>
00177     inline btree_map(InputIterator first, InputIterator last, const key_compare &kcf)
00178         : tree(first, last, kcf)
00179     {
00180     }
00181 
00183     inline ~btree_map()
00184     {
00185     }
00186 
00188     void swap(self& from)
00189     {
00190         std::swap(tree, from.tree);
00191     }
00192 
00193 public:
00194     // *** Key and Value Comparison Function Objects
00195 
00197     inline key_compare key_comp() const
00198     {
00199         return tree.key_comp();
00200     }
00201 
00204     inline value_compare value_comp() const
00205     {
00206         return tree.value_comp();
00207     }
00208 
00209 public:
00210     // *** Fast Destruction of the B+ Tree
00211 
00213     void clear()
00214     {
00215         tree.clear();
00216     }
00217 
00218 public:
00219     // *** STL Iterator Construction Functions
00220 
00223     inline iterator begin()
00224     {
00225         return tree.begin();
00226     }
00227 
00230     inline iterator end()
00231     {
00232         return tree.end();
00233     }
00234 
00237     inline const_iterator begin() const
00238     {
00239         return tree.begin();
00240     }
00241 
00244     inline const_iterator end() const
00245     {
00246         return tree.end();
00247     }
00248 
00251     inline reverse_iterator rbegin()
00252     {
00253         return tree.rbegin();
00254     }
00255 
00258     inline reverse_iterator rend()
00259     {
00260         return tree.rend();
00261     }
00262 
00265     inline const_reverse_iterator rbegin() const
00266     {
00267         return tree.rbegin();
00268     }
00269 
00272     inline const_reverse_iterator rend() const
00273     {
00274         return tree.rend();
00275     }
00276 
00277 public:
00278     // *** Access Functions to the Item Count
00279 
00281     inline size_type size() const
00282     {
00283         return tree.size();
00284     }
00285 
00287     inline bool empty() const
00288     {
00289         return tree.empty();
00290     }
00291     
00294     inline size_type max_size() const
00295     {
00296         return tree.max_size();
00297     }
00298 
00300     inline const tree_stats& get_stats() const
00301     {
00302         return tree.get_stats();
00303     }
00304 
00305 public:
00306     // *** Standard Access Functions Querying the Tree by Descending to a Leaf
00307 
00310     bool exists(const key_type &key) const
00311     {
00312         return tree.exists(key);
00313     }
00314 
00317     iterator find(const key_type &key)
00318     {
00319         return tree.find(key);
00320     }
00321 
00324     const_iterator find(const key_type &key) const
00325     {
00326         return tree.find(key);
00327     }
00328 
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_map(const self &other)
00435         : tree(other.tree)
00436     {
00437     }
00438     
00439 public:
00440     // *** Public Insertion Functions
00441 
00444     inline std::pair<iterator, bool> insert(const value_type& x)
00445     {
00446         return tree.insert2(x.first, x.second);
00447     }
00448     
00452     inline std::pair<iterator, bool> insert(const key_type& key, const data_type& data)
00453     {
00454         return tree.insert2(key, data);
00455     }
00456 
00461     inline std::pair<iterator, bool> insert2(const key_type& key, const data_type& data)
00462     {
00463         return tree.insert2(key, data);
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 
00483     inline data_type& operator[](const key_type& key)
00484     {
00485         iterator i = insert( value_type(key, data_type()) ).first;
00486         return i.data();
00487     }
00488 
00491     template <typename InputIterator>
00492     inline void insert(InputIterator first, InputIterator last)
00493     {
00494         return tree.insert(first, last);
00495     }
00496 
00497 public:
00498     // *** Public Erase Functions
00499 
00502     bool erase_one(const key_type &key)
00503     {
00504         return tree.erase_one(key);
00505     }
00506 
00509     size_type erase(const key_type &key)
00510     {
00511         return tree.erase(key);
00512     }
00513 
00514 #ifdef BTREE_TODO
00516     void erase(iterator iter)
00517     {
00518 
00519     }
00520 #endif
00521 
00522 #ifdef BTREE_TODO
00525     void erase(iterator /* first */, iterator /* last */)
00526     {
00527         abort();
00528     }
00529 #endif
00530 
00531 #ifdef BTREE_DEBUG
00532 public:
00533     // *** Debug Printing
00534 
00538     void print(std::ostream &os) const
00539     {
00540         tree.print(os);
00541     }
00542 
00544     void print_leaves(std::ostream &os) const
00545     {
00546         tree.print_leaves(os);
00547     }
00548 #endif
00549 
00550 public:
00551     // *** Verification of B+ Tree Invariants
00552 
00555     void verify() const
00556     {
00557         tree.verify();
00558     }
00559 
00560 public:
00561 
00566     void dump(std::ostream &os) const
00567     {
00568         tree.dump(os);
00569     }
00570 
00575     bool restore(std::istream &is)
00576     {
00577         return tree.restore(is);
00578     }
00579 };
00580 
00581 } // namespace stx
00582 
00583 #endif // _STX_BTREE_MAP_H_

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