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

/magnus/back_end/general/include/Vector.h

Go to the documentation of this file.
00001 /*
00002  *   $Id: Vector.h,v 1.14 2000/03/03 04:11:11 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 VectorOf<T> and VectorRep<T> class
00009 //
00010 // Principal Author: Stephane Collart, Roger Needham
00011 //
00012 // Status: Useable.
00013 //
00014 // Revision History:
00015 //
00016 // * 27.10.94 StC gave VectorItemRef::operator= a reference return type
00017 // * 11.11.94 Stc gave Vector a ctor to make a vector of specified length
00018 //                initialised from another vector
00019 // * 3/95 sr added
00020 //        int hash() const
00021 //        so that sets of vectors are (marginally) possible.
00022 // * 3/95 sr added
00023 //        VectorOf( int len, bool e )
00024 //        VectorOf( int len, bool e, const VectorOf& v )
00025 //
00026 // * 01/96 Dmitry B. implemented IPC tools.
00027 //
00028 // * 7/96 Dmitry B. made porting to gcc 2.7.2.
00029 //
00030 // * 2/97 EP added a method:
00031 //           const T& constref(int i) const;
00032 //        to enhance the i-th element of the vector.
00033 //
00034 //
00035 // * 02/97 dp fixed VectorRep::shrink(int start, int newlen).
00036 //
00037 // * 03/97 dp remove empty body from private member (hidden, not to be implemented)
00038 //            VectorRep& VectorRep::operator = ( const VectorRep& );
00039 //
00040 // Special Notes:
00041 //
00042 // * To instantiate VectorOf<T>, class T must have
00043 //   1) A default constructor
00044 //   2) A copy constructor
00045 //   3) An assignment operator
00046 //   4) An == operator
00047 //   5) A destructor
00048 //
00049 // Further implementation steps:
00050 //
00051 // * Analogs of the List methods would be nice.
00052 //
00053 // * Should negative indices count from the end of the vector?
00054 //
00055 // * VectorOf should also have cast constructors from SetOf, ListOf, etc,
00056 //   in order to be able to conveniently use the latter where a VectorOf
00057 //   is expected in a constructor etc.
00058 //
00059 // * Should some compatibility mechanism be installed between things
00060 //   like say VectorOf<Elt> and VectorOf<Word>?
00061 //
00062 // Bugs:
00063 //
00064 // * g++ 2.5.8 and less can't find templates of non-inlined functions
00065 //   so it is necessary to give explicit definitions in Vector.C of
00066 //   every instance.
00067 //
00068  
00069 #ifndef _VECTOR_H_
00070 #define _VECTOR_H_
00071  
00072 
00073 #include "global.h"
00074 #include "RefCounter.h"
00075 #include "ObjectOf.h"
00076 #include "Chars.h"
00077 #include "ExtendedIPC.h"
00078 
00079 template <class T> struct VectorRep : public RefCounter {
00080   
00081   public :
00082   
00083   // copy constructor does deep copy
00084   
00085   VectorRep( const VectorRep& vr ) {
00086          
00087          len = vr.last - vr.first;
00088          first = 0;
00089          last = len;
00090          vec = new T[len];
00091 #if ( SAFETY > 1 )
00092          if( !vec )
00093            error("Cannot allocate memory in VectorRep::VectorRep( const VectorRep& vr )");
00094 #endif
00095          for( int i = 0; i < len; i++ )
00096                 vec[i] = vr.vec[vr.first + i];
00097          fastExpansion = false;
00098   }
00099   
00100   VectorRep( int l ) {
00101          len = l;
00102          first = 0;
00103          last = len;
00104          vec = new T[len];
00105 #if ( SAFETY > 1 )
00106          if( !vec )
00107            error("Cannot allocate memory in VectorRep::VectorRep(int)");
00108 #endif
00109          fastExpansion = false;
00110   }
00111   // creates an uninitialized vector of length l
00112   
00113   VectorRep( int l, bool e ) {
00114          len = l;
00115          first = 0;
00116          last = len;
00117          vec = new T[len];
00118 #if ( SAFETY > 1 )
00119          if( !vec )
00120            error("Cannot allocate memory in VectorRep::VectorRep(int,bool)");
00121 #endif
00122          fastExpansion = e;
00123   }
00124   // creates an uninitialized vector of length l
00125 
00126   ~VectorRep( ) { delete [] vec; }
00127   
00128   // standard cloning operation for representations
00129   
00130   VectorRep* clone( ) { return new VectorRep( *this ); }
00131 
00132   int length() const { return last - first; }
00133 
00134   // for reference access
00135   T& ref(int i) {
00136     #if ( SAFETY > 0 )
00137            if ( i < 0 || i >= last - first ) error("VectorOf index out of bounds"
00138                         " in T& VectorRep::ref(int)");
00139          #endif
00140          return vec[first + i];
00141   }
00142   
00143   // for constant reference access
00144   const T& constref(int i) const {
00145     #if ( SAFETY > 0 )
00146            if ( i < 0 || i >= last - first ) error("VectorOf index out of bounds"
00147                         " in const T& VectorRep::constref(int)");
00148          #endif
00149          return vec[first + i];
00150   }
00151 
00152   // for value access
00153   T val(int i) const {
00154     #if ( SAFETY > 0 )
00155            if ( i < 0 || i >= last - first ) error("VectorOf index out of bounds"
00156                         " in T& VectorRep::val(int) const");
00157          #endif
00158          return vec[first + i];
00159   }
00160 
00161   void append( const T& t ) {
00162          if ( last < len ) {
00163                 vec[last++] = t;
00164          }
00165          else {
00166                 if (fastExpansion && len) len *= 2; else len++;
00167                 T* new_vec = new T[len];
00168 #if ( SAFETY > 1 )
00169                 if( !new_vec )
00170                   error("Cannot allocate memory in VectorRep::append()");
00171 #endif
00172                 int j = 0;
00173                 for( int i = first; i < last; i++ )
00174                   new_vec[j++] = vec[i];
00175                 delete [] vec;
00176                 vec = new_vec;
00177                 vec[j++] = t;
00178                 last = j;
00179                 first = 0;
00180          }
00181   }
00182 
00183   void prepend( const T& t ) {
00184          if ( first > 0 ) {
00185                 vec[--first] = t;
00186          }
00187          else {
00188                 if (fastExpansion && len) len *= 2; else len++;
00189                 T* new_vec = new T[len];
00190 #if ( SAFETY > 1 )
00191                 if( !new_vec )
00192                   error("Cannot allocate memory in VectorRep::prepend()");
00193 #endif
00194                 int j = 0;
00195                 new_vec[j++] = t;
00196                 for( int i = first; i < last; i++ )
00197                   new_vec[j++] = vec[i];
00198                 delete [] vec;
00199                 vec = new_vec;
00200                 last = j;
00201                 first = 0;
00202          }
00203   }
00204 
00205   void shrink( int start, int newlen ) {
00206     #if ( SAFETY > 0 )
00207       // if ( start < first || start >= last || newlen > last - first )
00208       //if ( start < 0 || first + start >= last || newlen > last - first )
00209       if ( start < 0 || newlen < 0 || newlen > last - first - start )
00210         error("argument to VectorRep::shrink out of bounds");
00211     #endif
00212     // The semantics are dangerous if we allow shrink to `expand' the VectorOf:
00213     // a copy construction may throw the `extra' stuff away in between
00214     // calls to shrink.
00215     first += start;
00216     last = first + newlen;
00217   }
00218 
00219   /////////////////////////////////////////////////////////////////////////
00220   //                                                                     //
00221   // IPC tools:                                                          //
00222   //                                                                     //
00223   /////////////////////////////////////////////////////////////////////////
00224 
00225   void write( ostream& ostr ) const
00226   {
00227 #ifdef DEBUG
00228     ostr < Chars("Vector<") < ' ';
00229 #endif    
00230 
00231     ostr < fastExpansion < first < last < len;
00232     for( int i = 0; i < len; ++i ) {
00233        ostr < vec[i];
00234        ostr < '\n'; //@dp temp
00235       // temporary cludge to avoid gcc 2.6.3 template bugs
00236 //      cludgeWrite(ostr, vec[i]);
00237     }
00238 #ifdef DEBUG
00239     ostr < ' ' < Chars(">Vector");
00240 #endif
00241   }
00242 
00243   void read( istream& istr )
00244   {
00245     delete [] vec;
00246 
00247 #ifdef DEBUG
00248     {
00249       Chars header;
00250       istr > header;
00251       if( header != Chars("Vector<") ) {
00252         error("Cannot load Vector<T>: bad header of the data section.");
00253       }
00254     }
00255 #endif
00256 
00257     istr > fastExpansion > first > last > len;
00258     vec = new T[len];
00259 #if ( SAFETY > 1 )
00260     if( !vec )
00261       error("Cannot allocate memory in VectorRep::read()");
00262 #endif
00263     for( int i = 0; i < len; ++i ) {
00264       istr > vec[i];
00265       // temporary cludge to avoid gcc 2.6.3 template bugs
00266 //      cludgeRead(istr, t);
00267     }
00268 
00269 #ifdef DEBUG
00270     {
00271       Chars footer;
00272       istr > footer;
00273       if( footer != Chars(">Vector") ) {
00274         error("Cannot load Vector<T>: bad footer of the data section.");
00275       }
00276     }
00277 #endif
00278   }
00279 
00280 
00281 //@@db
00282   
00283 /*  inline void cludgeWrite( ostream& ostr, const T& t ) const { ostr < t; }
00284 
00285   inline void cludgeRead( istream& istr, T& t ) { istr > t; }*/
00286 
00287    
00288 private :
00289   
00290   // assignment operator undesired : made private
00291   
00292   VectorRep& operator = ( const VectorRep& );//@dp { }//@rn
00293   // hidden, not to be implemented
00294 
00295   // data members
00296   
00297   bool fastExpansion; // true if expansion should be done by doubling space 
00298   unsigned int first; // index of first valid entry
00299   unsigned int last;  // index + 1 of last valid entry
00300   unsigned int len;   // actual length of storage, so last - first <= len
00301   
00302   T* vec;
00303 
00304 };
00305 
00306 /*
00307 //@db temporary cludges to avoid gcc template bugs
00308 
00309 inline void VectorRep<Chars>::cludgeWrite( ostream& ostr, const Chars& t )
00310        const { ostr < t; }
00311 
00312 inline void VectorRep<Chars>::cludgeRead( istream& istr, Chars& t )
00313        { istr > t; }
00314 
00315 inline void VectorRep<int>::cludgeWrite( ostream& ostr, const int& t ) const
00316        { ostr < t; }
00317 
00318 inline void VectorRep<int>::cludgeRead( istream& istr, int& t ) { istr > t; }
00319 
00320 //@db end of cludges
00321 */
00322 
00323 
00324 // ------------------------------- VectorOf -------------------------------- //
00325 
00326 
00327 //@db 2.91
00328 
00329 template <class T> class VectorOf;
00330 
00331 template<class T>
00332 ostream& operator < ( ostream& ostr, const VectorOf<T>& v )
00333 {
00334   v.look()->write(ostr);
00335   return ostr;
00336 }
00337 
00338 template<class T>
00339 istream& operator > ( istream& istr, VectorOf<T>& v )
00340 {
00341   v.change()->read(istr);
00342   return istr;
00343 }
00344 
00345 //@db end
00346 
00347 
00348 template <class T> class VectorOf : public ObjectOf< VectorRep<T> > {
00349   
00350   typedef VectorRep< T > Tvr;
00351   typedef ObjectOf< Tvr > Rep;
00352   
00353 public:
00354   
00355   // copy constructor, operator=, and destructor supplied by compiler.
00356   
00357   VectorOf( int len = 0 ) : Rep( new Tvr(len) ) { }
00358 
00359   VectorOf( int len, bool e ) : Rep( new Tvr(len,e) ) { }
00360   // When e is true, the vector length doubles when an append or prepend
00361   // needs more space (instead of increasing by 1).
00362 
00363   VectorOf( int len, const VectorOf& v ) : Rep( new Tvr(len) ) {
00364 
00365         for (int i = 0; i < min( len, v.length() ); i++)
00366                 enhance()->ref(i) = v[i];
00367   }
00368   // to make a vector of given length, (partly) initialized with
00369   // (part of) another vector
00370 
00371   VectorOf( int len, bool e, const VectorOf& v ) : Rep( new Tvr(len,e) ) {
00372         for (int i = 0; i < min( len, v.length() ); i++)
00373                 enhance()->ref(i) = v[i];
00374   }
00375   // See comment for VectorOf( int len, bool e ).
00376 
00377   int operator == ( const VectorOf& v ) const
00378   {
00379          if (look() == v.look()) return 1;
00380          if ( look()->length() != v.look()->length() ) return 0;
00381          int i = look()->length();
00382          while ( i-- ) if ( !(look()->val(i) == v.look()->val(i)) ) return 0;
00383          return 1;
00384   }
00385   
00386   int operator != ( const VectorOf& v ) const { return !(*this == v); }
00387 
00388   T operator [] ( int i ) const { return look()->val(i); }
00389 
00390   T& operator [] ( int i ) { return change()->ref(i); }
00391 
00392   //@rn Temporary (perhaps should be permanent) additions of Sergei:
00393 
00394   T val( int i ) const { return look()->val(i); }
00395   T& ref( int i ) { return change()->ref(i); }
00396   const T& constref( int i ) const { return look()->constref(i); }
00397 
00398   //@rn
00399   
00400   int length( ) const { return look()->length(); }
00401 
00402   int hash() const { return look()->length(); }
00403   //@rn Replace this in specific template instances if you want
00404   //    any semblance of efficiency.
00405   
00406   int indexOf( const T& t ) const {
00407          int i = length();
00408          while ( i-- ) if ( look()->val(i) == t ) return i;
00409          return -1;
00410   }
00411   // Returns the index of t in this VectorOf, or -1 if not here.
00412   
00413   void append( const T& t ) { change()->append(t); }
00414   // Appends t to this VectorOf.
00415   
00416   void prepend( const T& t ) { change()->prepend(t); }
00417   // Prepends t to this VectorOf.
00418 
00419   void shrink( int newLength ) { change()->shrink(0, newLength); }
00420   void shrink( int start, int newLength )
00421         { change()->shrink(start, newLength); }
00422 
00423 // I/O :
00424  
00425     // @stc these should not be inlined here but its easier than
00426     // fighting with g++'s template shortcomings
00427     inline friend ostream& operator << ( ostream& o, const VectorOf& v ) {
00428  
00429         o << "<";
00430         if ( v.length() == 0 )
00431             o << " ";
00432         else
00433             o << v[0];
00434         for ( int i = 1; i < v.length(); i++ ) o << "," << v[i];
00435         o << ">";
00436         return o;
00437     }
00438 
00439 
00440   /////////////////////////////////////////////////////////////////////////
00441   //                                                                     //
00442   // IPC tools:                                                          //
00443   //                                                                     //
00444   /////////////////////////////////////////////////////////////////////////
00445 
00446   friend ostream& operator < <T>( ostream& ostr, const VectorOf& v );
00447   
00448   friend istream& operator > <T>( istream& istr, VectorOf& v );
00449   
00450 private:
00451 
00452 
00453 };
00454 
00455 
00456 
00457 // concatenate the given vectors
00458 
00459 template <class T>
00460 inline VectorOf<T> concatenate(const VectorOf<T>& v1, const VectorOf<T>& v2)
00461 {
00462   VectorOf<T> res(v1.length()+v2.length());
00463   int pos = 0;
00464   for(int i = 0; i < v1.length(); i++)
00465     res[pos++] = v1[i];
00466   for(int j = 0; j < v2.length(); j++)
00467     res[pos++] = v2[j];
00468   return res;
00469 }
00470 
00471 
00472 #endif

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