stx/btree_set.h

Go to the documentation of this file.
00001 // $Id: btree_set.h 35 2007-04-27 11:26:33Z tb $
00006 /*
00007  * STX B+ Tree Template Classes v0.7
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_SET_H_
00026 #define _STX_BTREE_SET_H_
00027 
00028 #include <stx/btree.h>
00029 
00030 namespace stx {
00031 
00049 template <typename _Key,
00050           typename _Compare = std::less<_Key>,
00051           typename _Traits = btree_default_set_traits<_Key> >
00052 class btree_set
00053 {
00054 public:
00055     // *** Template Parameter Types
00056 
00059     typedef _Key                        key_type;
00060 
00062     typedef _Compare                    key_compare;
00063 
00066     typedef _Traits                     traits;
00067 
00068 private:
00069     // *** The data_type
00070 
00072     struct empty_struct
00073     {
00074     };
00075 
00076 public:
00077     // *** Constructed Types
00078 
00080     typedef struct empty_struct         data_type;
00081 
00083     typedef key_type                    value_type;
00084 
00086     typedef btree_set<key_type, key_compare, traits>    self;
00087 
00089     typedef stx::btree<key_type, data_type, value_type, key_compare, traits, false> btree_impl;
00090 
00092     typedef typename btree_impl::value_compare  value_compare;
00093 
00095     typedef typename btree_impl::size_type      size_type;
00096 
00098     typedef typename btree_impl::tree_stats     tree_stats;
00099 
00100 public:
00101     // *** Static Constant Options and Values of the B+ Tree
00102 
00104     static const unsigned short         leafslotmax =  btree_impl::leafslotmax;
00105 
00108     static const unsigned short         innerslotmax =  btree_impl::innerslotmax;
00109 
00113     static const unsigned short         minleafslots = btree_impl::minleafslots;
00114 
00118     static const unsigned short         mininnerslots = btree_impl::mininnerslots;
00119 
00122     static const bool                   selfverify = btree_impl::selfverify;
00123 
00127     static const bool                   debug = btree_impl::debug;
00128 
00130     static const bool                   allow_duplicates = btree_impl::allow_duplicates;
00131 
00132 public:
00133     // *** Iterators and Reverse Iterators
00134 
00137     typedef typename btree_impl::iterator               iterator;
00138 
00141     typedef typename btree_impl::const_iterator         const_iterator;
00142 
00144     typedef typename btree_impl::reverse_iterator       reverse_iterator;
00145 
00147     typedef typename btree_impl::const_reverse_iterator const_reverse_iterator;
00148 
00149 private:
00150     // *** Tree Implementation Object
00151 
00153     btree_impl  tree;
00154 
00155 public:
00156     // *** Constructors and Destructor
00157 
00160     inline btree_set()
00161         : tree()
00162     {
00163     }
00164 
00167     inline btree_set(const key_compare &kcf)
00168         : tree(kcf)
00169     {
00170     }
00171 
00173     template <class InputIterator>
00174     inline btree_set(InputIterator first, InputIterator last)
00175         : tree()
00176     {
00177         insert(first, last);
00178     }
00179 
00182     template <class InputIterator>
00183     inline btree_set(InputIterator first, InputIterator last, const key_compare &kcf)
00184         : tree(kcf)
00185     {
00186         insert(first, last);
00187     }
00188 
00190     inline ~btree_set()
00191     {
00192     }
00193 
00195     void swap(self& from)
00196     {
00197         std::swap(tree, from.tree);
00198     }
00199 
00200 public:
00201     // *** Key and Value Comparison Function Objects
00202 
00204     inline key_compare key_comp() const
00205     {
00206         return tree.key_comp();
00207     }
00208 
00211     inline value_compare value_comp() const
00212     {
00213         return tree.value_comp();
00214     }
00215 
00216 public:
00217     // *** Fast Destruction of the B+ Tree
00218 
00220     void clear()
00221     {
00222         tree.clear();
00223     }
00224 
00225 public:
00226     // *** STL Iterator Construction Functions
00227 
00230     inline iterator begin()
00231     {
00232         return tree.begin();
00233     }
00234 
00237     inline iterator end()
00238     {
00239         return tree.end();
00240     }
00241 
00244     inline const_iterator begin() const
00245     {
00246         return tree.begin();
00247     }
00248 
00251     inline const_iterator end() const
00252     {
00253         return tree.end();
00254     }
00255 
00258     inline reverse_iterator rbegin()
00259     {
00260         return tree.rbegin();
00261     }
00262 
00265     inline reverse_iterator rend()
00266     {
00267         return tree.rend();
00268     }
00269 
00272     inline const_reverse_iterator rbegin() const
00273     {
00274         return tree.rbegin();
00275     }
00276 
00279     inline const_reverse_iterator rend() const
00280     {
00281         return tree.rend();
00282     }
00283 
00284 public:
00285     // *** Access Functions to the Item Count
00286 
00288     inline size_type size() const
00289     {
00290         return tree.size();
00291     }
00292 
00294     inline bool empty() const
00295     {
00296         return tree.empty();
00297     }
00298     
00301     inline size_type max_size() const
00302     {
00303         return tree.max_size();
00304     }
00305 
00307     inline const tree_stats& get_stats() const
00308     {
00309         return tree.get_stats();
00310     }
00311 
00312 public:
00313     // *** Standard Access Functions Querying the Tree by Descending to a Leaf
00314 
00317     bool exists(const key_type &key) const
00318     {
00319         return tree.exists(key);
00320     }
00321 
00324     iterator find(const key_type &key)
00325     {
00326         return tree.find(key);
00327     }
00328 
00331     const_iterator find(const key_type &key) const
00332     {
00333         return tree.find(key);
00334     }
00335 
00339     size_type count(const key_type &key) const
00340     {
00341         return tree.count(key);
00342     }
00343 
00346     iterator lower_bound(const key_type& key)
00347     {
00348         return tree.lower_bound(key);
00349     }
00350 
00353     const_iterator lower_bound(const key_type& key) const
00354     {
00355         return tree.lower_bound(key);
00356     }
00357 
00360     iterator upper_bound(const key_type& key)
00361     {
00362         return tree.upper_bound(key);
00363     }
00364 
00367     const_iterator upper_bound(const key_type& key) const
00368     {
00369         return tree.upper_bound(key);
00370     }
00371 
00373     inline std::pair<iterator, iterator> equal_range(const key_type& key)
00374     {
00375         return tree.equal_range(key);
00376     }
00377 
00379     inline std::pair<const_iterator, const_iterator> equal_range(const key_type& key) const
00380     {
00381         return tree.equal_range(key);
00382     }
00383 
00384 public:
00385     // *** B+ Tree Object Comparison Functions
00386 
00389     inline bool operator==(const self &other) const
00390     {
00391         return (tree == other.tree);
00392     }
00393 
00395     inline bool operator!=(const self &other) const
00396     {
00397         return (tree != other.tree);
00398     }
00399 
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 
00420     inline bool operator>=(const self &other) const
00421     {
00422         return (tree >= other.tree);
00423     }
00424 
00425 public:
00427 
00429     inline self& operator= (const self &other)
00430     {
00431         if (this != &other)
00432         {
00433             tree = other.tree;
00434         }
00435         return *this;
00436     }
00437 
00440     inline btree_set(const self &other)
00441         : tree(other.tree)
00442     {
00443     }
00444     
00445 public:
00446     // *** Public Insertion Functions
00447 
00450     inline std::pair<iterator, bool> insert(const key_type& x)
00451     {
00452         return tree.insert2(x, data_type());
00453     }
00454     
00457     inline iterator insert(iterator hint, const key_type &x)
00458     {
00459         return tree.insert2(hint, x, data_type());
00460     }
00461 
00464     template <typename InputIterator>
00465     inline void insert(InputIterator first, InputIterator last)
00466     {
00467         InputIterator iter = first;
00468         while(iter != last)
00469         {
00470             insert(*iter);
00471             ++iter;
00472         }
00473     }
00474 
00475 public:
00476     // *** Public Erase Functions
00477 
00480     bool erase_one(const key_type &key)
00481     {
00482         return tree.erase_one(key);
00483     }
00484 
00486     size_type erase(const key_type &key)
00487     {
00488         return tree.erase(key);
00489     }
00490 
00491 #ifdef BTREE_TODO
00493     void erase(iterator iter)
00494     {
00495 
00496     }
00497 #endif
00498 
00499 #ifdef BTREE_TODO
00502     void erase(iterator /* first */, iterator /* last */)
00503     {
00504         abort();
00505     }
00506 #endif
00507 
00508 public:
00509     // *** Debug Printing
00510 
00514     void print() const
00515     {
00516         tree.print();
00517     }
00518 
00520     void print_leaves() const
00521     {
00522         tree.print_leaves();
00523     }
00524 
00525 public:
00526     // *** Verification of B+ Tree Invariants
00527 
00530     void verify() const
00531     {
00532         tree.verify();
00533     }
00534 
00535 public:
00536 
00541     void dump(std::ostream &os) const
00542     {
00543         tree.dump(os);
00544     }
00545 
00550     bool restore(std::istream &is)
00551     {
00552         return tree.restore(is);
00553     }
00554 };
00555 
00556 } // namespace stx
00557 
00558 #endif // _STX_BTREE_SET_H_

Generated on Fri Apr 27 14:49:56 2007 for STX B+ Tree Template Classes by  doxygen 1.5.2