Main Page   Class Hierarchy   Compound List   File List   Compound Members   File Members  

/magnus/back_end/general/include/BTree.h

Go to the documentation of this file.
00001 /*
00002  *   $Id: BTree.h,v 1.5 1999/11/23 20:37:28 bormotov Exp $
00003  */
00004 
00005 // Copyright (C) 1997 The New York Group Theory Cooperative
00006 // See magnus/doc/COPYRIGHT for the full notice.
00007 //
00008 // Contents: Definitions of class BTree.
00009 //           
00010 // Principal Author: Dmitry Bormotov
00011 //
00012 // Status: Very first implementation (under development)
00013 //
00014 // Usage:
00015 //
00016 // Revision History:
00017 //
00018 
00019 
00020 #ifndef _BTREE_H_
00021 #define _BTREE_H_
00022 
00023 
00024 #include "global.h"
00025 
00026 //@db porting 
00027 template <class Key, class Value> class BTree;
00028 template <class Key, class Value> class BTreeIterator;
00029 
00030 
00031 //------------------------------- BTreePage ---------------------------------//
00032 
00033 
00034 // the class BTreePage is not a public class and will be hidden
00035 
00036 template <class Key, class Value> class BTreePage
00037 {
00038 
00039   friend class BTree<Key,Value>;
00040   friend class BTreeIterator<Key,Value>;
00041 
00042 public:
00043 
00044 
00045   /////////////////////////////////////////////////////////////////////////
00046   //                                                                     //
00047   // Constructors:                                                       //
00048   //                                                                     //
00049   /////////////////////////////////////////////////////////////////////////
00050 
00051   BTreePage( int order ) : theOrder( order ), numOfKeys( 0 ), 
00052       parentLink( NULL )
00053   {
00054   #if SAFETY > 0
00055     if( order < 2 )
00056       error("template <class Key, class Value> class BTree::BTree( int ) : "
00057             "the order of BTree must be 2 or more.");
00058   #endif  
00059     
00060     keys = new (Key*)[order-1];
00061     values = new (Value*)[order-1];
00062     links = new (BTreePage<Key,Value>*)[order];
00063     for( int i = 0; i < order; ++i )
00064       links[i] = NULL;
00065   }
00066 
00067   ~BTreePage( ) 
00068   { 
00069     delete [] links;
00070     delete [] keys;
00071     delete [] values;
00072   }
00073 
00074 
00075 private:
00076 
00077 
00078   /////////////////////////////////////////////////////////////////////////
00079   //                                                                     //
00080   // Data Members:                                                       //
00081   //                                                                     //
00082   /////////////////////////////////////////////////////////////////////////
00083 
00084   int theOrder;
00085   int numOfKeys;
00086   Key **keys;
00087   Value **values;
00088   BTreePage **links;
00089   BTreePage *parentLink;
00090   int numOfParentLink;
00091 
00092 
00093   /////////////////////////////////////////////////////////////////////////
00094   //                                                                     //
00095   //  Debugging stuff:                                                   //
00096   //                                                                     //
00097   /////////////////////////////////////////////////////////////////////////
00098 
00099 #ifdef DEBUG
00100 
00101   //friend int main( );
00102 
00103 #endif
00104 
00105 };
00106 
00107 
00108 //--------------------------------- BTree -----------------------------------//
00109 
00110 // Implements a BTree data structure
00111 template <class Key, class Value> class BTree
00112 {
00113 
00114   friend class BTreeIterator<Key,Value>;
00115 
00116 public:
00117 
00118 
00119   /////////////////////////////////////////////////////////////////////////
00120   //                                                                     //
00121   // Constructors:                                                       //
00122   //                                                                     //
00123   /////////////////////////////////////////////////////////////////////////
00124 
00125   BTree( int order = 6 ) : theOrder( order )
00126   {
00127     #if SAFETY > 0
00128       if( order < 3 )
00129         error("template <class Key, class Value> class BTree::BTree( int ) : "
00130               "the order of BTree must be 3 or more.");
00131     #endif  
00132       
00133     root = new BTreePage<Key,Value>(order);
00134   }
00135   //!< Constructs a BTree with "order" keys and values in each node.
00136 
00137   BTree( const BTree& );
00138   BTree& operator = ( const BTree& ){
00139     error( "BTree& operator = ( const BTree& ) : not emplemented yet");
00140   }
00141   //!< Copy constractor not emplemented yet
00142  
00143   ~BTree( ) 
00144   { 
00145     deleteAll(); 
00146     delete root;
00147   }
00148 
00149 
00150   /////////////////////////////////////////////////////////////////////////
00151   //                                                                     //
00152   // Accessors:                                                          //
00153   //                                                                     //
00154   /////////////////////////////////////////////////////////////////////////
00155 
00156   bool remove( const Key& key );
00157 
00158   void insert( const Key& key, const Value& value );
00159 
00160   Value* search( const Key& key );
00161   // returns the corresponding value or NULL if there's no such key in
00162   // the tree.
00163  
00164 
00165   /////////////////////////////////////////////////////////////////////////
00166   //                                                                     //
00167   // I/O:                                                                //
00168   //                                                                     //
00169   /////////////////////////////////////////////////////////////////////////
00170   friend ostream& operator << ( ostream& ostr, const BTree& T )
00171   {
00172      error("Operator ostr < BTree not emplemeted yet");
00173   }
00174 
00175   friend ostream& operator < ( ostream& ostr, const BTree& T )
00176    {
00177           error("Operator ostr < BTree not emplemeted yet");
00178    }
00179   friend istream& operator > ( istream& ostr, const BTree& T )
00180    {
00181           error("Operator istr > BTree not emplemeted yet");
00182    }
00183   friend bool operator == ( const BTree& T,const BTree& T1 )
00184    {
00185           error("Operator BTree == BTree not emplemeted yet");
00186    }
00187    void printAll();
00188 protected:
00189 
00190 
00191   /////////////////////////////////////////////////////////////////////////
00192   //                                                                     //
00193   // Protected functions:                                                //
00194   //                                                                     //
00195   /////////////////////////////////////////////////////////////////////////
00196 
00197   virtual void theKeyIsFound( BTreePage<Key,Value>& keyPage, int position ) { }
00198 
00199   bool search( const Key& key, const BTreePage<Key,Value>& searchPage,
00200                BTreePage<Key,Value> **keyPage, int& position );
00201   
00202   void deleteKey( BTreePage<Key,Value> *page, int position );
00203 
00204   void deleteAll( ) { deleteAllPages(root); }
00205 
00206   void deleteAllPages( BTreePage<Key,Value> *page );
00207 
00208 
00209 private:
00210 
00211 
00212   /////////////////////////////////////////////////////////////////////////
00213   //                                                                     //
00214   // Data Members:                                                       //
00215   //                                                                     //
00216   /////////////////////////////////////////////////////////////////////////
00217 
00218   int theOrder;
00219   BTreePage<Key,Value> *root;
00220 
00221 
00222   /////////////////////////////////////////////////////////////////////////
00223   //                                                                     //
00224   // Private functions:                                                  //
00225   //                                                                     //
00226   /////////////////////////////////////////////////////////////////////////
00227 
00228 
00229 /*
00230   void printOn( ostream& ) const;
00231 */
00232 
00233   /////////////////////////////////////////////////////////////////////////
00234   //                                                                     //
00235   //  Debugging stuff:                                                   //
00236   //                                                                     //
00237   /////////////////////////////////////////////////////////////////////////
00238 
00239 #ifdef DEBUG
00240 
00241   // void printAll( );
00242   
00243   //friend int main( );
00244 
00245 #endif
00246 
00247 };
00248 
00249 
00250 //----------------------------- BTreeIterator -------------------------------//
00251 
00252 // Note: This iterator don't make a copy of BTree. Be careful - don't 
00253 // delete keys in the tree when iterating over them.
00254 
00255 
00256 template <class Key, class Value> class BTreeIterator 
00257 {
00258 
00259   friend class BTree<Key,Value>; 
00260 
00261 public:
00262 
00263 
00264   /////////////////////////////////////////////////////////////////////////
00265   //                                                                     //
00266   // Constructors:                                                       //
00267   //                                                                     //
00268   /////////////////////////////////////////////////////////////////////////
00269   
00270   BTreeIterator( const BTree<Key,Value>& T ) : tree( T ) { reset( ); }
00271 
00272   // No default constructor
00273   // Copy constructor provided by compiler (does logical deep copy).
00274 
00275 
00276   /////////////////////////////////////////////////////////////////////////
00277   //                                                                     //
00278   // Status Queries:                                                     //
00279   //                                                                     //
00280   /////////////////////////////////////////////////////////////////////////
00281 
00282   bool done( ) { return bDone; }
00283 
00284 
00285   /////////////////////////////////////////////////////////////////////////
00286   //                                                                     //
00287   // Accessors:                                                          //
00288   //                                                                     //
00289   /////////////////////////////////////////////////////////////////////////
00290 
00291   void reset( );
00292 
00293   Value getValue( ) 
00294   { 
00295   #if SAFETY > 0
00296     if( bDone )
00297       error("Value BTreeIterator<Key,Value>::value( ) : "
00298             "Tried to retrieve value from iterator which is done.");
00299   #endif  
00300     
00301     return *value; 
00302   }
00303 
00304   Key getKey( ) 
00305   { 
00306   #if SAFETY > 0
00307     if( bDone )
00308       error("Value BTreeIterator<Key,Value>::value( ) : "
00309             "Tried to retrieve value from iterator which is done.");
00310   #endif  
00311     
00312     return *key; 
00313   }
00314 
00315   bool next( );
00316 
00317 
00318 private:
00319 
00320 
00321   /////////////////////////////////////////////////////////////////////////
00322   //                                                                     //
00323   // Data Members:                                                       //
00324   //                                                                     //
00325   /////////////////////////////////////////////////////////////////////////
00326 
00327   const BTree<Key,Value>& tree; 
00328   BTreePage<Key,Value> *page;  // current page in tree 
00329   int linkNumber;    // current link in tree
00330   bool bDone;
00331   Key *key;
00332   Value *value;
00333   
00334   /////////////////////////////////////////////////////////////////////////
00335   //                                                                     //
00336   // Private functions:                                                  //
00337   //                                                                     //
00338   /////////////////////////////////////////////////////////////////////////
00339   
00340 };
00341 
00342 #endif
00343 
00344 
00345 
00346 
00347 

Generated at Tue Jun 19 09:49:35 2001 for Magnus Classes by doxygen1.2.6 written by Dimitri van Heesch, © 1997-2001