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

/magnus/back_end/Polynomial/include/PBTree.h

Go to the documentation of this file.
00001 /*
00002  *   $Id: PBTree.h,v 1.2 2000/02/10 00:00:15 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 _PBTREE_H_
00021 #define _PBTREE_H_
00022 
00023 
00024 #include "global.h"
00025 
00026 
00027 template <class Key, class Value> class PBTree;
00028 template <class Key, class Value> class PBTreeIterator;
00029 
00030 
00031 //------------------------------ PBTreePage ---------------------------------//
00032 
00033 
00034 // the class PBTreePage is not a public class and will be hidden
00035 
00036 template <class Key, class Value> class PBTreePage
00037 {
00038 
00039   friend class PBTree<Key,Value>;
00040   friend class PBTreeIterator<Key,Value>;
00041 
00042 public:
00043 
00044 
00045   /////////////////////////////////////////////////////////////////////////
00046   //                                                                     //
00047   // Constructors:                                                       //
00048   //                                                                     //
00049   /////////////////////////////////////////////////////////////////////////
00050 
00051   PBTreePage( 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 PBTree::PBTree( int ) : "
00057             "the order of PBTree must be 2 or more.");
00058   #endif  
00059     
00060     keys = new (Key*)[order-1];
00061     values = new (Value*)[order-1];
00062     links = new (PBTreePage<Key,Value>*)[order];
00063     for( int i = 0; i < order; ++i )
00064       links[i] = NULL;
00065   }
00066 
00067   ~PBTreePage( ) 
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   PBTreePage **links;
00089   PBTreePage *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 //--------------------------------- PBTree ----------------------------------//
00109 
00110 
00111 //@db 2.91
00112 
00113 template <class Key, class Value> class PBTree;
00114 
00115 template <class Key, class Value>
00116 ostream& operator < ( ostream& ostr, const PBTree<Key,Value>& T )
00117 {
00118   error("Operator ostr < PBTree not emplemeted yet");
00119 }
00120 
00121 template <class Key, class Value>
00122 istream& operator > ( istream& ostr, const PBTree<Key,Value>& T )
00123 {
00124   error("Operator istr > PBTree not emplemeted yet");
00125 }
00126 
00127 //@db end
00128 
00129 
00130 template <class Key, class Value> class PBTree
00131 {
00132 
00133   friend class PBTreeIterator<Key,Value>;
00134 
00135 public:
00136 
00137 
00138   /////////////////////////////////////////////////////////////////////////
00139   //                                                                     //
00140   // Constructors:                                                       //
00141   //                                                                     //
00142   /////////////////////////////////////////////////////////////////////////
00143 
00144   PBTree( int order = 6 ) : theOrder( order )
00145   {
00146     #if SAFETY > 0
00147       if( order < 3 )
00148         error("template <class Key, class Value> class PBTree::PBTree( int ) : "
00149               "the order of PBTree must be 3 or more.");
00150     #endif  
00151       
00152     root = new PBTreePage<Key,Value>(order);
00153   }
00154   // Constructs a PBTree with "order" keys and values in each node.
00155 
00156   PBTree( const PBTree& );
00157   PBTree& operator = ( const PBTree& ){
00158     error( "PBTree& operator = ( const PBTree& ) : not emplemented yet");
00159   }
00160   //copy constructor not emplemented yet
00161  
00162   ~PBTree( ) 
00163   { 
00164     deleteAll(); 
00165     delete root;
00166   }
00167 
00168 
00169   /////////////////////////////////////////////////////////////////////////
00170   //                                                                     //
00171   // Accessors:                                                          //
00172   //                                                                     //
00173   /////////////////////////////////////////////////////////////////////////
00174 
00175   bool remove( const Key& key );
00176 
00177   void insert( const Key& key, const Value& value );
00178 
00179   Value* search( const Key& key );
00180   // returns the corresponding value or NULL if there's no such key in
00181   // the tree.
00182  
00183 
00184   /////////////////////////////////////////////////////////////////////////
00185   //                                                                     //
00186   // I/O:                                                                //
00187   //                                                                     //
00188   /////////////////////////////////////////////////////////////////////////
00189   friend ostream& operator << ( ostream& ostr, const PBTree& T )
00190   {
00191      error("Operator ostr < PBTree not emplemeted yet");
00192   }
00193 
00194   friend ostream& operator < <Key,Value>( ostream& ostr, const PBTree& T );
00195 
00196   friend istream& operator > <Key,Value>( istream& ostr, const PBTree& T );
00197 
00198   friend bool operator == ( const PBTree& T,const PBTree& T1 )
00199    {
00200           error("Operator PBTree == PBTree not emplemeted yet");
00201    }
00202    void printAll();
00203 protected:
00204 
00205 
00206   /////////////////////////////////////////////////////////////////////////
00207   //                                                                     //
00208   // Protected functions:                                                //
00209   //                                                                     //
00210   /////////////////////////////////////////////////////////////////////////
00211 
00212   virtual void theKeyIsFound( const Key& key, Value& value ) { }
00213   /*
00214   { 
00215     //value += key;
00216     //error("PBTree::theKeyIsFound called.");
00217   }
00218   */
00219 
00220   bool search( const Key& key, const PBTreePage<Key,Value>& searchPage,
00221                PBTreePage<Key,Value> **keyPage, int& position );
00222   
00223   void deleteKey( PBTreePage<Key,Value> *page, int position );
00224 
00225   void deleteAll( ) { deleteAllPages(root); }
00226 
00227   void deleteAllPages( PBTreePage<Key,Value> *page );
00228 
00229 
00230 private:
00231 
00232 
00233   /////////////////////////////////////////////////////////////////////////
00234   //                                                                     //
00235   // Data Members:                                                       //
00236   //                                                                     //
00237   /////////////////////////////////////////////////////////////////////////
00238 
00239   int theOrder;
00240   PBTreePage<Key,Value> *root;
00241 
00242 
00243   /////////////////////////////////////////////////////////////////////////
00244   //                                                                     //
00245   // Private functions:                                                  //
00246   //                                                                     //
00247   /////////////////////////////////////////////////////////////////////////
00248 
00249 
00250 /*
00251   void printOn( ostream& ) const;
00252 */
00253 
00254   /////////////////////////////////////////////////////////////////////////
00255   //                                                                     //
00256   //  Debugging stuff:                                                   //
00257   //                                                                     //
00258   /////////////////////////////////////////////////////////////////////////
00259 
00260 #ifdef DEBUG
00261 
00262  // void printAll( );
00263 
00264   //friend int main(...);
00265 
00266 #endif
00267 
00268 };
00269 
00270 
00271 //----------------------------- PBTreeIterator -------------------------------//
00272 
00273 // Note: This iterator don't make a copy of PBTree. Be careful - don't 
00274 // delete keys in the tree when iterating over them.
00275 
00276 
00277 template <class Key, class Value> class PBTreeIterator 
00278 {
00279 
00280   friend class PBTree<Key,Value>; 
00281 
00282 public:
00283 
00284 
00285   /////////////////////////////////////////////////////////////////////////
00286   //                                                                     //
00287   // Constructors:                                                       //
00288   //                                                                     //
00289   /////////////////////////////////////////////////////////////////////////
00290   
00291   PBTreeIterator( const PBTree<Key,Value>& T ) : tree( T ) { reset( ); }
00292 
00293   // No default constructor
00294   // Copy constructor provided by compiler (does logical deep copy).
00295 
00296 
00297   /////////////////////////////////////////////////////////////////////////
00298   //                                                                     //
00299   // Status Queries:                                                     //
00300   //                                                                     //
00301   /////////////////////////////////////////////////////////////////////////
00302 
00303   bool done( ) { return bDone; }
00304 
00305 
00306   /////////////////////////////////////////////////////////////////////////
00307   //                                                                     //
00308   // Accessors:                                                          //
00309   //                                                                     //
00310   /////////////////////////////////////////////////////////////////////////
00311 
00312   void reset( );
00313 
00314   Value getValue( ) 
00315   { 
00316   #if SAFETY > 0
00317     if( bDone )
00318       error("Value PBTreeIterator<Key,Value>::value( ) : "
00319             "Tried to retrieve value from iterator which is done.");
00320   #endif  
00321     
00322     return *value; 
00323   }
00324 
00325   Key getKey( ) 
00326   { 
00327   #if SAFETY > 0
00328     if( bDone )
00329       error("Value PBTreeIterator<Key,Value>::value( ) : "
00330             "Tried to retrieve value from iterator which is done.");
00331   #endif  
00332     
00333     return *key; 
00334   }
00335 
00336   bool next( );
00337 
00338 
00339 private:
00340 
00341 
00342   /////////////////////////////////////////////////////////////////////////
00343   //                                                                     //
00344   // Data Members:                                                       //
00345   //                                                                     //
00346   /////////////////////////////////////////////////////////////////////////
00347 
00348   const PBTree<Key,Value>& tree; 
00349   PBTreePage<Key,Value> *page;  // current page in tree 
00350   int linkNumber;    // current link in tree
00351   bool bDone;
00352   Key *key;
00353   Value *value;
00354   
00355   /////////////////////////////////////////////////////////////////////////
00356   //                                                                     //
00357   // Private functions:                                                  //
00358   //                                                                     //
00359   /////////////////////////////////////////////////////////////////////////
00360   
00361 };
00362 
00363 #endif
00364 
00365 
00366 
00367 
00368 

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