stx/btree_set.h

Go to the documentation of this file.
00001 // $Id: btree_set.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_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 
00071     BTREE_FRIENDS
00072 
00073 private:
00074     // *** The data_type
00075 
00077     struct empty_struct
00078     {
00079     };
00080 
00081 public:
00082     // *** Constructed Types
00083 
00085     typedef struct empty_struct         data_type;
00086 
00088     typedef key_type                    value_type;
00089 
00091     typedef btree_set<key_type, key_compare, traits>    self;
00092 
00094     typedef stx::btree<key_type, data_type, value_type, key_compare, traits, false> btree_impl;
00095 
00097     typedef typename btree_impl::value_compare  value_compare;
00098 
00100     typedef typename btree_impl::size_type      size_type;
00101 
00103     typedef typename btree_impl::tree_stats     tree_stats;
00104 
00105 public:
00106     // *** Static Constant Options and Values of the B+ Tree
00107 
00109     static const unsigned short         leafslotmax =  btree_impl::leafslotmax;
00110 
00113     static const unsigned short         innerslotmax =  btree_impl::innerslotmax;
00114 
00118     static const unsigned short         minleafslots = btree_impl::minleafslots;
00119 
00123     static const unsigned short         mininnerslots = btree_impl::mininnerslots;
00124 
00127     static const bool                   selfverify = btree_impl::selfverify;
00128 
00132     static const bool                   debug = btree_impl::debug;
00133 
00135     static const bool                   allow_duplicates = btree_impl::allow_duplicates;
00136 
00137 public:
00138     // *** Iterators and Reverse Iterators
00139 
00142     typedef typename btree_impl::iterator               iterator;
00143 
00146     typedef typename btree_impl::const_iterator         const_iterator;
00147 
00149     typedef typename btree_impl::reverse_iterator       reverse_iterator;
00150 
00152     typedef typename btree_impl::const_reverse_iterator const_reverse_iterator;
00153 
00154 private:
00155     // *** Tree Implementation Object
00156 
00158     btree_impl  tree;
00159 
00160 public:
00161     // *** Constructors and Destructor
00162 
00165     inline btree_set()
00166         : tree()
00167     {
00168     }
00169 
00172     inline btree_set(const key_compare &kcf)
00173         : tree(kcf)
00174     {
00175     }
00176 
00178     template <class InputIterator>
00179     inline btree_set(InputIterator first, InputIterator last)
00180         : tree()
00181     {
00182         insert(first, last);
00183     }
00184 
00187     template <class InputIterator>
00188     inline btree_set(InputIterator first, InputIterator last, const key_compare &kcf)
00189         : tree(kcf)
00190     {
00191         insert(first, last);
00192     }
00193 
00195     inline ~btree_set()
00196     {
00197     }
00198 
00200     void swap(self& from)
00201     {
00202         std::swap(tree, from.tree);
00203     }
00204 
00205 public:
00206     // *** Key and Value Comparison Function Objects
00207 
00209     inline key_compare key_comp() const
00210     {
00211         return tree.key_comp();
00212     }
00213 
00216     inline value_compare value_comp() const
00217     {
00218         return tree.value_comp();
00219     }
00220 
00221 public:
00222     // *** Fast Destruction of the B+ Tree
00223 
00225     void clear()
00226     {
00227         tree.clear();
00228     }
00229 
00230 public:
00231     // *** STL Iterator Construction Functions
00232 
00235     inline iterator begin()
00236     {
00237         return tree.begin();
00238     }
00239 
00242     inline iterator end()
00243     {
00244         return tree.end();
00245     }
00246 
00249     inline const_iterator begin() const
00250     {
00251         return tree.begin();
00252     }
00253 
00256     inline const_iterator end() const
00257     {
00258         return tree.end();
00259     }
00260 
00263     inline reverse_iterator rbegin()
00264     {
00265         return tree.rbegin();
00266     }
00267 
00270     inline reverse_iterator rend()
00271     {
00272         return tree.rend();
00273     }
00274 
00277     inline const_reverse_iterator rbegin() const
00278     {
00279         return tree.rbegin();
00280     }
00281 
00284     inline const_reverse_iterator rend() const
00285     {
00286         return tree.rend();
00287     }
00288 
00289 public:
00290     // *** Access Functions to the Item Count
00291 
00293     inline size_type size() const
00294     {
00295         return tree.size();
00296     }
00297 
00299     inline bool empty() const
00300     {
00301         return tree.empty();
00302     }
00303     
00306     inline size_type max_size() const
00307     {
00308         return tree.max_size();
00309     }
00310 
00312     inline const tree_stats& get_stats() const
00313     {
00314         return tree.get_stats();
00315     }
00316 
00317 public:
00318     // *** Standard Access Functions Querying the Tree by Descending to a Leaf
00319 
00322     bool exists(const key_type &key) const
00323     {
00324         return tree.exists(key);
00325     }
00326 
00329     iterator find(const key_type &key)
00330     {
00331         return tree.find(key);
00332     }
00333 
00336     const_iterator find(const key_type &key) const
00337     {
00338         return tree.find(key);
00339     }
00340 
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_set(const self &other)
00446         : tree(other.tree)
00447     {
00448     }
00449     
00450 public:
00451     // *** Public Insertion Functions
00452 
00455     inline std::pair<iterator, bool> insert(const key_type& x)
00456     {
00457         return tree.insert2(x, data_type());
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 
00485     bool erase_one(const key_type &key)
00486     {
00487         return tree.erase_one(key);
00488     }
00489 
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 
00531 #endif
00532 
00533 public:
00534     // *** Verification of B+ Tree Invariants
00535 
00538     void verify() const
00539     {
00540         tree.verify();
00541     }
00542 
00543 public:
00544 
00549     void dump(std::ostream &os) const
00550     {
00551         tree.dump(os);
00552     }
00553 
00558     bool restore(std::istream &is)
00559     {
00560         return tree.restore(is);
00561     }
00562 };
00563 
00564 } // namespace stx
00565 
00566 #endif // _STX_BTREE_SET_H_

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