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

/magnus/back_end/Equations/include/VectorPtr.h

Go to the documentation of this file.
00001 /*
00002  *   $Id: VectorPtr.h,v 1.8 1999/11/23 20:25:06 bormotov Exp $
00003  */
00004  
00005 //   Copyright (C) 1994 The New York Group Theory Cooperative
00006 //   See magnus/doc/COPYRIGHT for the full notice.
00007  
00008 // Contents: Definition of VectorPtrOf<T> and VectorPtrRep<T> class
00009 //
00010 // Principal Author: Dmitry Pechkin
00011 //
00012 // Status: under trial.
00013 //
00014 // Revision History:
00015 //
00016 // * 96/01/06 @dp Added functions in class VectorPtrOf<T>:
00017 //     T val( int i ) const;
00018 //     T& ref( int i );
00019 //
00020 // * 7/96 Dmitry B. made porting to gcc 2.7.2.
00021 //
00022 // * 3/99 Dmitry B. moved the following implementation to VectorPtr.C 
00023 //   to satisfy new C++ standard:
00024 //
00025 //   VectorItemRef<T> VectorPtrOf<T>::operator [] ( int i );
00026 //
00027 //
00028 // * 03/97 dp fixed VectorPtrRep::shrink(int start, int newlen);
00029 //                  VectorPtrRep( const VectorPtrRep& vr );
00030 //                  bool VectorPtrOf::operator == ( const VectorPtrOf& v ) const;
00031 //
00032 // * 04/97 dp added bool VectorPtrOf<T>::isValid(int) const.
00033 //
00034 // Special Notes:
00035 //
00036 // * These classes are remake of VectorOf<T> and VectorRep<T> classes
00037 //   for one purpose only: class T may not have default constructor.
00038 //   But new implementation is some slow.
00039 //
00040 // * Some problem exists: now on comparison of uninitialized element of
00041 //   VectorPtrOf<T> and element of T error will not occur 
00042 //   (VectorPtrItemRef::operator==() is optimized for this),
00043 //   but if there is global operator==(T,T) error could be occur
00044 //   because in cast operator VectorPtrItemRef::operator T() 
00045 //   method VectorPtr<T>::val(int) is called which caused error
00046 //   if the element is uninitialized. Should be behavoiur
00047 //
00048 // * They aren't derived from VectorOf<> and VectorRep<> because
00049 //   now the last ones require some repairs to fit to general scheme of 
00050 //   derived objects, e.g. like Group hierarchy.
00051 //
00052 // * To instantiate VectorPtrOf<T>, class T must have
00053 //   1) A copy constructor
00054 //   2) An assignment operator
00055 //   3) An == operator
00056 //   4) A destructor
00057 //
00058 // OTHER NOTES FROM Vector.h:
00059 //
00060 // Further implementation steps:
00061 //
00062 // * Analogs of the List methods would be nice.
00063 //
00064 // * Should negative indices count from the end of the vector?
00065 //
00066 // * VectorOf should also have cast constructors from SetOf, ListOf, etc,
00067 //   in order to be able to conveniently use the latter where a VectorOf
00068 //   is expected in a constructor etc.
00069 //
00070 // * Should some compatibility mechanism be installed between things
00071 //   like say VectorOf<Elt> and VectorOf<Word>?
00072 //
00073 // Bugs:
00074 //
00075 // * g++ 2.5.8 and less can't find templates of non-inlined functions
00076 //   so it is necessary to give explicit definitions in Vector.C of
00077 //   every instance.
00078 //
00079  
00080 #ifndef _VECTOR_PTR_H_
00081 #define _VECTOR_PTR_H_
00082  
00083 
00084 #include <iostream.h>
00085 
00086 #include "RefCounter.h"
00087 #include "ObjectOf.h"
00088 
00089 //@db porting
00090 template < class T > class VectorItemRef;
00091 
00092 
00093 template <class T> struct VectorPtrRep : public RefCounter {
00094   
00095   public :
00096   
00097   // copy constructor does deep copy
00098   
00099   VectorPtrRep( const VectorPtrRep& vr ) {
00100     len = vr.last - vr.first;
00101     first = 0;
00102     last = len;
00103     vec = new (T*)[len];
00104 #if ( SAFETY > 1 )
00105     if( !vec )
00106       error("Cannot allocate memory in VectorPtrRep::VectorPtrRep(const VectorPtrRep& vr)");
00107 #endif
00108     for( int i = 0; i < len; i++ ) {
00109       if( vr.vec[vr.first + i] ) {
00110         vec[i] = new T( *vr.vec[vr.first + i] );
00111 #if ( SAFETY > 1 )
00112         if( !vec[i] )
00113           error("Cannot allocate memory in VectorPtrRep::VectorPtrRep(const VectorPtrRep& vr)");
00114 #endif
00115       }
00116       else
00117         vec[i] = NULL;
00118     }
00119     fastExpansion = false;
00120   }
00121   
00122   VectorPtrRep( int l ) {
00123     len = l;
00124     first = 0;
00125     last = len;
00126     vec = new (T*)[len];
00127 #if ( SAFETY > 1 )
00128     if( !vec )
00129       error("Cannot allocate memory in VectorPtrRep::VectorPtrRep(int)");
00130 #endif
00131     for(int i = 0; i<len; i++) vec[i] = NULL;
00132     fastExpansion = false;
00133   }
00134   // creates an uninitialized vector of length l
00135   
00136   VectorPtrRep( int l, bool e ) {
00137     len = l;
00138     first = 0;
00139     last = len;
00140     vec = new (T*)[len];
00141 #if ( SAFETY > 1 )
00142     if( !vec )
00143       error("Cannot allocate memory in VectorPtrRep::VectorPtrRep(int, bool)");
00144 #endif
00145     for(int i = 0; i<len; i++) vec[i] = NULL;
00146     fastExpansion = e;
00147   }
00148   // creates an uninitialized vector of length l
00149 
00150   ~VectorPtrRep( ) { 
00151     for(int i = 0; i<len; i++)
00152       delete vec[i];
00153     delete [] vec;
00154   }
00155   
00156   // standard cloning operation for representations
00157   
00158   VectorPtrRep* clone( ) { return new VectorPtrRep( *this ); }
00159 
00160   int length() const { return last - first; }
00161 
00162   bool isValid(int i) const { 
00163 #if ( SAFETY > 0 )
00164     if ( i < 0 || i >= last - first ) 
00165       error("VectorPtrOf index out of bounds "
00166             "in VectorPtrRep::isValid(int)");
00167 #endif
00168     return ( vec[first+i] ? true : false );
00169   }
00170 
00171   void set(int i, const T& t) {
00172 #if ( SAFETY > 0 )
00173     if ( i < 0 || i >= last - first ) 
00174       error("VectorPtrOf index out of bounds "
00175             "in VectorPtrRep::set(int, const T&)");
00176 #endif
00177     if (!vec[first+i]){
00178       delete vec[first+i];
00179       vec[first+i] = new T(t);
00180 #if ( SAFETY > 1 )
00181       if( !vec[first+i] )
00182         error("Cannot allocate memory in VectorPtrRep::set(int,T)");
00183 #endif
00184     }
00185     else *vec[first+i] = t;
00186   }
00187 
00188   // for reference access
00189   T& ref(int i) {
00190 #if ( SAFETY > 0 )
00191     if ( i < 0 || i >= last - first ) 
00192       error("VectorPtrOf index out of bounds in T& VectorRep::ref(int) const");
00193     if( !isValid(i) )
00194       error("VectorPtrOf access denied to uninitialized element "
00195             "in T& VectorPtrRep::ref(int) const");
00196 #endif
00197     return *vec[first + i];
00198   }
00199 
00200   // for value access
00201   T val(int i) const {
00202 #if ( SAFETY > 0 )
00203     if ( i < 0 || i >= last - first ) 
00204       error("VectorPtrOf index out of bounds in T VectorRep::val(int) const");
00205     if( !isValid(i) )
00206       error("VectorPtrOf access denied to uninitialized element "
00207             "in T VectorPtrRep::val(int) const");
00208 #endif
00209     return *vec[first + i];
00210   }
00211 
00212   VectorItemRef<T> operator [] ( int i ) { 
00213 #if ( SAFETY > 0 )
00214     if ( i < 0 || i >= length() ) 
00215       error("VectorPtrOf index out of bounds in VectorRep::operator [](int)");
00216 #endif
00217     if( isValid(i) )
00218       return VectorItemRef<T>(vec[i]);
00219     else
00220       return VectorItemRef<T>(&vec[i], 0);
00221   }
00222 
00223   void append( const T& t ) {
00224     if ( last < len ) {
00225       vec[last++] = new T(t);
00226     }
00227     else {
00228       if( fastExpansion && len ) len *= 2; else len++;
00229       T** new_vec = new (T *)[len];
00230  #if ( SAFETY > 1 )
00231       if( !new_vec )
00232         error("Cannot allocate memory in VectorPtrRep::append(T)");
00233 #endif
00234      int j = 0;
00235       for( int i = first; i < last; i++ )
00236         new_vec[j++] = vec[i];
00237       delete [] vec;
00238       vec = new_vec;
00239       vec[j++] = new T(t);
00240 #if ( SAFETY > 1 )
00241       if( !vec[j-1] )
00242         error("Cannot allocate memory in VectorPtrRep::append(T)");
00243 #endif
00244       last = j;
00245       first = 0;
00246       for(int i = last; i<len; i++)
00247         vec[i] = NULL;
00248     }
00249   }
00250 
00251   void prepend( const T& t ) {
00252     if ( first > 0 ) {
00253       vec[--first] = new T(t);
00254     }
00255     else {
00256       if( fastExpansion && len ) len *= 2; else len++;
00257       T** new_vec = new (T *)[len];
00258 #if ( SAFETY > 1 )
00259     if( !new_vec )
00260       error("Cannot allocate memory in VectorPtrRep::prepend(T)");
00261 #endif
00262       int j = 0;
00263       new_vec[j++] = new T(t);
00264 #if ( SAFETY > 1 )
00265     if( !new_vec[0] )
00266       error("Cannot allocate memory in VectorPtrRep::prepend(int)");
00267 #endif
00268       for( int i = first; i < last; i++ )
00269         new_vec[j++] = vec[i];
00270       delete [] vec;
00271       vec = new_vec;
00272       last = j;
00273       first = 0;
00274       for(int i = last; i<len; i++)
00275         vec[i] = NULL;
00276     }
00277   }
00278 
00279   void shrink( int start, int newlen ) {
00280 #if ( SAFETY > 0 )
00281     if ( start < 0 || first + start >= last || newlen > last - first )
00282       error("argument to VectorRep::shrink out of bounds");
00283 #endif
00284     // The semantics are dangerous if we allow shrink to `expand' the VectorPtrOf:
00285     // a copy construction may throw the `extra' stuff away in between
00286     // calls to shrink.
00287 
00288     // free all elements of vector which are out of new bounds
00289 
00290     T** tmp;
00291 
00292     T** tmpStart = vec+first+start;
00293     for(tmp = vec+first; tmp<tmpStart; tmp++) {
00294       delete *tmp;
00295       *tmp = NULL;
00296     }
00297 
00298     T** tmpLast = vec+last;
00299     for(tmp = tmpStart+newlen; tmp<tmpLast; tmp++) {
00300       delete *tmp;
00301       *tmp = NULL;
00302     }
00303 
00304     first += start;
00305     last = first + newlen;
00306   }
00307 
00308   
00309   private :
00310   
00311   // assignment operator undesired : made inaccessible private
00312   VectorPtrRep& operator = ( const VectorPtrRep& );
00313   // { }//@rn
00314 
00315   // data members
00316   
00317   bool fastExpansion; // true if expansion should be done by doubling space 
00318   unsigned int first; // index of first valid entry
00319   unsigned int last;  // index + 1 of last valid entry
00320   unsigned int len;   // actual length of storage, so last - first <= len
00321   
00322   T** vec;
00323 };
00324 
00325 
00326 
00327 template <class T> class VectorPtrOf : public ObjectOf< VectorPtrRep<T> > {
00328   
00329   typedef VectorPtrRep< T > Rep;
00330   typedef ObjectOf< Rep > Base;
00331   
00332 public:
00333   
00334   // copy constructor, operator=, and destructor supplied by compiler.
00335   
00336   VectorPtrOf( int len = 0 ) : Base( new Rep(len) ) { }
00337 
00338   VectorPtrOf( int len, bool e ) : Base( new Rep(len,e) ) { }
00339   // When e is true, the vector length doubles when an append or prepend
00340   // needs more space (instead of increasing by 1).
00341 
00342   VectorPtrOf( int len, const VectorPtrOf& v ) : Base( new Rep(len) ) {
00343     for (int i = 0; i < min( len, v.length() ); i++)
00344       if( v.look()->isValid(i) )
00345         enhance()->set(i, v[i]);
00346   }
00347   // to make a vector of given length, (partly) initialized with
00348   // (part of) another vector
00349 
00350   VectorPtrOf( int len, bool e, const VectorPtrOf& v ) : Base( new Rep(len,e)){
00351     for (int i = 0; i < min( len, v.length() ); i++) 
00352       if( v.look()->isValid(i) )
00353         enhance()->set(i, v[i]);
00354   }
00355   // See comment for VectorPtrOf( int len, bool e ).
00356 
00357   bool operator == ( const VectorPtrOf& v ) const
00358   {
00359     if (look() == v.look()) return true;
00360     if ( look()->length() != v.look()->length() ) return false;
00361     int i = look()->length();
00362     while ( i-- ) 
00363       if( look()->isValid(i) != v.look()->isValid(i) ||
00364           look()->isValid(i) && !(look()->val(i) == v.look()->val(i)) ) 
00365         return false;
00366     return true;
00367   }
00368   
00369   bool operator != ( const VectorPtrOf& v ) const { return !(*this == v); }
00370 
00371   T operator [] ( int i ) const { return look()->val(i); }
00372 
00373   VectorItemRef<T> operator [] ( int i ) { return change()->operator [](i); }
00374 
00375   T val( int i ) const { return look()->val(i); }
00376 
00377   T& ref( int i ) { return change()->ref(i); }
00378 
00379   bool isValid( int i ) const { return look()->isValid(i); }
00380   
00381   int length( ) const { return look()->length(); }
00382 
00383   int hash() const { return look()->length(); }
00384   //@rn Replace this in specific template instances if you want
00385   //    any semblance of efficiency.
00386   
00387   int indexOf( const T& t ) const {
00388     int i = length();
00389     while ( i-- ) 
00390       if ( look()->isValid(i) && look()->val(i) == t ) return i;
00391     return -1;
00392   }
00393   // Returns the index of t in this VectorPtrOf, or -1 if not here.
00394   
00395   void append( const T& t ) { change()->append(t); }
00396   // Appends t to this VectorPtrOf.
00397   
00398   void prepend( const T& t ) { change()->prepend(t); }
00399   // Prepends t to this VectorPtrOf.
00400 
00401   void shrink( int newLength ) { change()->shrink(0, newLength); }
00402   void shrink( int start, int newLength )
00403   { change()->shrink(start, newLength); }
00404 
00405   // I/O :
00406  
00407   // @stc these should not be inlined here but its easier than
00408   // fighting with g++'s template shortcomings
00409   inline friend ostream& operator << ( ostream& o, const VectorPtrOf& v ) {
00410  
00411     o << "<";
00412     if ( v.length() == 0 )
00413       o << " ";
00414     else {
00415       if( v.isValid(0) )
00416         o << v[0];
00417       else
00418         o << "-?-";
00419     }
00420     for ( int i = 1; i < v.length(); i++ ) {
00421       o << ",";
00422       if( v.look()->isValid(i) )
00423         o << v[i];
00424       else
00425         o << "-?-"; 
00426     }
00427     o << ">";
00428     return o;
00429   }
00430  
00431 private:
00432 
00433 };
00434 
00435 
00436 template < class T > class VectorItemRef {
00437   
00438 public:
00439   
00440   // no default constructor because of reference members
00441   // destructor compiler-supplied
00442   
00443   T& operator = ( const T& t ) { 
00444     if (elPoint) 
00445       *elPoint = t;
00446     else {
00447       elPoint = *elAddr = new T(t);
00448 #if ( SAFETY > 1 )
00449       if( !elPoint )
00450         error("Cannot allocate memory in VectorItemRef::operator=(T&)");
00451 #endif
00452      
00453     }
00454     return *elPoint;
00455   }
00456 
00457   bool operator == ( const T& t ) { 
00458     if (elPoint)
00459       return *elPoint == t; 
00460     else
00461       return false;
00462   }
00463   // if a global operator == with two T arguments is defined, the above
00464   // is not necessary; if T only has a member operator == with one T
00465   // argument, then the above is necessary, since the ARM excludes
00466   // type conversion to apply a method.
00467  
00468   operator T( ) { 
00469     if (!elPoint)
00470       error("VectorPtrOf access denied to uninitialized element "
00471             "in  VectorItemRef::operator T()");
00472     return *elPoint;
00473   }
00474   
00475 private:
00476 
00477   friend class VectorPtrRep<T>; //@@rn only op[] when possible.
00478 
00479   VectorItemRef( T* p) : elPoint(p) { }
00480   // Hide this from unauthorized users.
00481 
00482   VectorItemRef( T** addr, T* p) : elPoint(0), elAddr(addr) { }
00483   // Hide this from unauthorized users.
00484 
00485   // data members
00486 
00487 
00488   T* elPoint;
00489   T** elAddr;
00490 
00491 private:
00492 
00493   //@dp old notes: no assignment operator generated by compiler because of ref member.
00494   //@dp Really, compiler (gcc 2.7.2) generates default operator=(const VectorItemRef&)
00495   //    like for the structures that is wrong. We need this operator in expressions 
00496   //    like this:  a[i] = b[i] where b[i] must be initialized.
00497   VectorItemRef& operator = ( const VectorItemRef& ref );
00498 
00499   // make copy constructor inaccessible
00500 
00501   // @db porting
00502 
00503 public: 
00504 
00505   VectorItemRef( const VectorItemRef& ref )
00506   {
00507     if( !ref.elPoint ) {
00508       error("VectorPtrOf<T>: access denied to uninitialized element t"
00509             "in  VectorItemRef::operator=(const VectorItemRef& t)");
00510       
00511     }
00512     if( this != &ref ) {
00513       if( elPoint )
00514         *elPoint = *ref.elPoint;
00515       else
00516         elPoint = *elAddr = new T( *ref.elPoint );
00517     }
00518   }
00519 
00520 };
00521 
00522 #endif

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