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

/magnus/back_end/general/include/List.h

Go to the documentation of this file.
00001 /*
00002  *   $Id: List.h,v 1.6 2000/02/10 00:14:44 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 and implementation of ListOf, ListRep,
00009 //           ListIterator, and ListIteratorRep template classes.
00010 //
00011 // Principal Authors: Stephane Collart, Roger Needham
00012 //
00013 // Status: Useable.
00014 //
00015 // Revision History:
00016 //
00017 // Special Notes:
00018 //
00019 // * To instantiate ListOf<T>, class T must have
00020 //   1) An assignment operator
00021 //   2) A copy constructor
00022 //   3) An == operator
00023 //   4) A destructor
00024 //   and there must be an
00025 //     ostream& operator << ( ostream&, const Type& ),
00026 //   and a conversion of T to Type.
00027 //
00028 // * Some ListOf methods can safely ignore bad indices, but they post a
00029 //   warning if SAFETY > 0 on the assumption that the caller is 
00030 //   probably bugged.
00031 //
00032 // * 7/96 Dmitry B. made porting to gcc 2.7.2.
00033 //
00034 // 07/96 Aleksey M. implemented IPC tools
00035 
00036 
00037 #ifndef _LIST_H_
00038 #define _LIST_H_
00039 
00040 #include "RefCounter.h"
00041 #include "ObjectOf.h"
00042 #include "Cell.h"
00043 
00044 template <class T> class ListIteratorRep;
00045 // Forward declaration for friend declarations.
00046 
00047 
00048 //---------------------- class ListRep ----------------------------------
00049 
00050 template <class T> class ListRep : public RefCounter {
00051 
00052 public:
00053 
00054   ListRep( ) : root(NULL), last(NULL), len(0) { }
00055 
00056   ListRep( const T& t ) {
00057     root = last = new CellType(t);
00058     len = 1;
00059   }
00060 
00061   // copy constructor does deep copy
00062   ListRep( const ListRep& lr ) : len(lr.len) {
00063     
00064     if ( lr.root == NULL )
00065       root = last = NULL;
00066     else {
00067       CellType* to = root = new CellType( *lr.root );
00068       CellType* from = lr.root->nextCell;
00069       while ( from ) {
00070         to = to->nextCell = new CellType( *from );
00071         from = from->nextCell;
00072       }
00073       last = to;
00074       last->nextCell = NULL; // Better safe than sorry
00075     }
00076   }
00077 
00078   ~ListRep( ) {
00079     CellType* r;
00080     while ( root ) {
00081       r = root->nextCell;
00082       delete root;
00083       root = r;
00084     }
00085   }
00086 
00087   Bool operator == ( const ListRep& lr ) const {
00088     return ( len == lr.len && agreement(&lr, 0) == len );
00089   }
00090 
00091   ListRep* clone( ) { return new ListRep(*this); }
00092 
00093   void insert( const T& t, int i ) {
00094   #if SAFETY > 0
00095       if ( i < 0 || i > len )
00096         error("index argument to ListRep::insert out of bounds");
00097   #endif
00098     if ( i == 0 ) {
00099       if ( root )
00100         root = new CellType(t, root);
00101       else
00102         root = last = new CellType(t);
00103     }
00104     else if ( i == len ) {
00105       last = last->nextCell = new CellType(t);
00106     }
00107     else {
00108       CellType* scan = root;
00109       while ( --i ) {
00110        #if SAFETY > 0
00111           if ( scan == NULL )
00112             error("internal error, len and actual length differ in ListRep");
00113        #endif
00114         scan = scan->nextCell;
00115       }
00116       scan->nextCell = new CellType(t, scan->nextCell);
00117     }
00118     ++len;
00119   }
00120 
00121   void removeElement( const T& t ) {
00122     if ( root == NULL ) return;
00123     if ( root->getContents() == t ) removeElementOfIndex(0);
00124     else {
00125       CellType* prev = root;
00126       CellType* scan = root->nextCell;
00127       while ( scan != NULL ) {
00128         if ( scan->getContents() == t ) {
00129           if ( (prev->nextCell = scan->nextCell) == NULL ) last = prev;
00130           delete scan;
00131           --len;
00132           break;
00133         }
00134         prev = scan;
00135         scan = scan->nextCell;
00136       }
00137     }
00138   }
00139 
00140   void removeElementOfIndex( int i ) {
00141     if ( root == NULL ) return;
00142     #if SAFETY > 0
00143       if ( i < 0 ) {
00144         warn("ignoring negative index in ListRep::removeElementOfIndex");
00145         return;
00146       }
00147     #endif
00148     if ( i == 0 ) {
00149       CellType* tmp = root;
00150       root = root->nextCell;
00151       --len;
00152       delete tmp;
00153     }
00154     else {
00155       CellType* prev = root;
00156       CellType* scan = root->nextCell;
00157       while ( scan != NULL ) {
00158         if ( --i == 0 ) {
00159           if ( (prev->nextCell = scan->nextCell) == NULL ) last = prev;
00160           delete scan;
00161           --len;
00162           break;
00163         }
00164         prev = scan;
00165         scan = scan->nextCell;
00166       }
00167       #if SAFETY > 0
00168         if ( scan == NULL && i )
00169           warn("ignoring index > length in ListRep::removeElementOfIndex");
00170       #endif
00171     }
00172   }
00173 
00174   void splice( const ListRep* rp, int i, int j ) {
00175     #if SAFETY > 0
00176       if ( i < 0 || j < i || j > len )
00177         error("ListRep::splice indices out of bounds");
00178     #endif
00179     CellType* left = root;
00180     // When i > 0, set left to predecessor of cell with index i.
00181     for( int k = 1; k < i; k++ ) left = left->nextCell;
00182     // Remove sublist [i,j), setting up left & right for splicing.
00183     CellType* right;
00184     if ( i == 0 ) right = left;
00185     else right = left->nextCell;
00186     for( int k = i; k < j; k++ ) {
00187       CellType* tmp = right;
00188       right = right->nextCell;
00189       delete tmp;
00190     }
00191     // Attach rp between left and right
00192     CellType* copy = rp->root;
00193     if ( i == 0 ) {
00194       root = left = new CellType(copy->getContents());
00195       copy = copy->nextCell;
00196     }
00197     while ( copy != NULL ) {
00198       left = left->nextCell = new CellType(copy->getContents());
00199       copy = copy->nextCell;
00200     }
00201     left->nextCell = right;
00202     if ( right == NULL ) last = left;
00203     len += ( rp->len - (j - i) );
00204   }
00205 
00206   ListRep* sublist( int i, int j ) const {
00207     #if SAFETY > 0
00208       if ( i < 0 || j < i || j > len )
00209         error("ListRep::sublist indices out of bounds");
00210     #endif
00211     CellType* scan = root;
00212     for( int k = 0; k < i; k++ ) scan = scan->nextCell;
00213     ListRep* result = new ListRep;
00214     int result_len = 0;
00215     for( int k = i; k < j; k++ ) {
00216       result->insert(scan->getContents(), result_len++);
00217       scan = scan->nextCell;
00218     }
00219     return result;
00220   }
00221   
00222 
00223   ListRep* concatenate( const ListRep* rp ) const {
00224     ListRep* result = new ListRep;
00225     CellType* scan = root;
00226     int result_len = 0;
00227     while ( scan != NULL ) {
00228       result->insert(scan->getContents(), result_len++);
00229       scan = scan->nextCell;
00230     }
00231     scan = rp->root;
00232     while ( scan != NULL ) {
00233       result->insert(scan->getContents(), result_len++);
00234       scan = scan->nextCell;
00235     }
00236     return result;
00237   }
00238 
00239   ListRep* reverse( ) const {
00240     ListRep* result = new ListRep;
00241     CellType* scan = root;
00242     while ( scan != NULL ) {
00243       result->insert(scan->getContents(), 0);
00244       scan = scan->nextCell;
00245     }
00246     return result;
00247   }
00248 
00249   int length( ) const { return len; }
00250 
00251   T element( int i ) const {
00252     #if SAFETY > 0
00253       if ( i < 0 || i >= len )
00254         error("index argument to ListRep::element out of bounds");
00255     #endif
00256     CellType* scan = root;
00257     while ( i-- ) scan = scan->nextCell;
00258     return scan->getContents();
00259   }
00260 
00261   int indexOf( const T& t ) const {
00262     int result = 0;
00263     CellType* scan = root;
00264     while ( scan != NULL ) {
00265       if ( scan->getContents() == t ) return result;
00266       ++result;
00267       scan = scan->nextCell;
00268     }
00269     return -1;
00270   }
00271 
00272   int agreement( const ListRep* rp, int start ) const {
00273     CellType* scan1 = root;
00274     CellType* scan2 = rp->root;
00275     while ( start ) {
00276       --start;
00277       if ( scan2 == NULL ) {
00278         #if SAFETY > 0
00279           warn("ignoring start > length in ListRep::agreement");
00280         #endif
00281         return 0;
00282       }
00283       scan2 = scan2->nextCell;
00284     }
00285     int result = 0;
00286     while ( scan1 != NULL && scan2 != NULL &&
00287             scan1->getContents() == scan2->getContents() ) {
00288       ++result;
00289       scan1 = scan1->nextCell;
00290       scan2 = scan2->nextCell;
00291     }
00292     return result;
00293   }
00294 
00295   #ifdef DEBUG
00296     void debugPrint( ostream& ostr ) const { }
00297   #endif
00298 
00299   void printOn( ostream& ostr ) const {
00300     CellType* r = root;
00301     while ( r ) {
00302       ostr << " -> " << r->getContents();
00303       r = r->nextCell;
00304     }
00305   }
00306   //@rn imposes constraint on Associations Key type
00307 
00308   /////////////////////////////////////////////////////////////////////////
00309   //                                                                     //
00310   // IPC tools:                                                          //
00311   //                                                                     //
00312   /////////////////////////////////////////////////////////////////////////
00313 
00314   void  write( ostream& ostr ) const;
00315   void  read( istream& istr );
00316 
00317 private:
00318 
00319   ListRep& operator = ( const ListRep& ); // prohibit assignment
00320   //@rn be systematic about this?
00321 
00322   typedef Cell<T> CellType;
00323 
00324 friend class ListIteratorRep<T>;
00325 
00326   // Data members:
00327 
00328   CellType* root;
00329   CellType* last;
00330 
00331   int len;
00332 };
00333 
00334 
00335 //---------------------- class ListOf ----------------------------------
00336 
00337 template <class T> class ListOf : ObjectOf< ListRep<T> > {
00338 
00339 public:
00340 
00341   typedef T ListElementType; // Export the template parameter
00342 
00343   ListOf( ) : ObjectOf<Rep>( new Rep() ) { }
00344   // Default constructor makes empty list.
00345 
00346   ListOf( const T& t ) : ObjectOf<Rep>( new Rep(t) ) { }
00347   // Cast constructor T -> ListOf<T>.
00348 
00349   // Copy constructor, operator=, and destructor supplied by compiler.
00350 
00351   Bool operator == ( const ListOf& L ) const { return equalTo(L); }
00352 
00353   Bool operator != ( const ListOf& L ) const { return !equalTo(L); }
00354 
00355   T operator [ ] ( int i ) const { return element(i); }
00356   // For read access only. Zero-based indexing.
00357 
00358   Bool equalTo( const ListOf& L ) const {
00359     return ( *look() == *L.look() );
00360   }
00361   // TRUE iff L contains the same T's as this list, in the same order.
00362 
00363   T element( int i ) const { return look()->element(i); }
00364   // Return the element of index i in this list. Zero-based indexing.
00365   // It is a fatal error if i < 0 or i >= length().
00366 
00367   int length( ) const { return look()->length(); }
00368   // Return length of this List.
00369 
00370   Bool contains( const T& t ) const {
00371     return ( indexOf(t) != -1 );
00372   }
00373   // TRUE iff this list contains t according to T::operator==.
00374 
00375   int indexOf( const T& t ) const { return look()->indexOf(t); }
00376   // Returns the index of t in this list, or -1 if not here.
00377   // Uses T::operator== in search.
00378   // Zero-based indexing.
00379 
00380   Bool prefixOf( const ListOf& L ) const {
00381     return ( agreement(L) == length() );
00382   }
00383   // TRUE iff this list is a prefix of L.
00384 
00385   Bool properPrefixOf( const ListOf& L ) const {
00386     return ( length() < L.length() && prefixOf(L) );
00387   }
00388   // TRUE iff this list is a proper prefix of L.
00389 
00390   int agreement( const ListOf& L, int start = 0 ) const {
00391     return look()->agreement(L.look(), start);
00392   }
00393   // Returns the length of the maximal prefix of this list which matches
00394   // the suffix of L beginning at start. You get a warning if
00395   // start >= L.length(); the result is 0 in this case.
00396 
00397   ListOf sublist( int i, int j ) const {
00398     return ListOf( look()->sublist(i, j) );
00399   }
00400   // Returns a copy of the sublist [i,j) of this list.
00401   // It is a fatal error if i < 0, j < i, or j > length().
00402   // Note if i == j this returns an empty list.
00403 
00404   friend ListOf concatenate( const ListOf& L1, const ListOf& L2 ) {
00405     return ListOf( L1.look()->concatenate(L2.look()) );
00406   }
00407   // Returns the concatenatation of L1 and L2.
00408 
00409   ListOf reverse( ) const { return ListOf( look()->reverse() ); }
00410   // Returns a copy of this list in reverse order.
00411 
00412   void append( const T& t ) { change()->insert(t, length()); }
00413   // Appends t to this List.
00414 
00415   void prepend( const T& t ) { change()->insert(t, 0); }
00416   // Prepends t to this List.
00417 
00418   void insert( const T& t, int i ) { change()->insert(t, i); }
00419   // Make t the (i+1)th element of this List. Zero-based. The previous (i+1)th
00420   // element becomes the (i+2)th. It is a fatal error if i < 0 or i > length().
00421 
00422   void removeElement( const T& t ) { change()->removeElement(t); }
00423   // Remove t from this list. It is not an error if t is not in this list.
00424 
00425   void removeElementOfIndex( int i ) { change()->removeElementOfIndex(i); }
00426   // Remove the (i+1)th element of this list. Zero-based. You get a warning
00427   // if i < 0 or i >= length().
00428 
00429   void splice( const ListOf& L, int i, int j ) {
00430     change()->splice(L.look(), i, j);
00431   }
00432   // Replaces the sublist [i,j) of this list with L.
00433   // It is a fatal error if i < 0, j < i, or j > length().
00434   // Note if i == j this inserts L into this list by moving the suffix of
00435   // this list beginning at index i to the right.
00436 
00437   inline friend ostream& operator << ( ostream& ostr, const ListOf& l ) {
00438     l.look()->printOn(ostr);
00439     return ostr;
00440   }
00441 
00442   #ifdef DEBUG
00443     void debugPrint( ostream& ostr ) const {
00444       look()->debugPrint(ostr);
00445       ostr << endl;
00446       look()->printOn(ostr);
00447     }
00448   #endif
00449   /////////////////////////////////////////////////////////////////////////
00450   //                                                                     //
00451   // IPC tools:                                                          //
00452   //                                                                     //
00453   /////////////////////////////////////////////////////////////////////////
00454 
00455   friend ostream& operator < ( ostream& ostr, const ListOf& L )
00456   {
00457     L.look()->write(ostr);
00458     return ostr;
00459   }
00460   
00461   friend istream& operator > ( istream& istr, ListOf& L)
00462   {
00463     L.change()->read(istr);
00464     return istr;
00465   }
00466 
00467 
00468 private:
00469 
00470   typedef Cell<T> CellType;
00471   typedef ListRep<T> Rep;
00472 
00473   friend class ListIteratorRep<T>;
00474 
00475   typedef ObjectOf<Rep> R;
00476   ListOf( Rep* p ) : R(p) { }
00477 };
00478 
00479 
00480 //---------------------- class ListIteratorRep ----------------------------------
00481 
00482 template <class T> class ListIteratorRep : public RefCounter {
00483 
00484 public:
00485 
00486   ListIteratorRep( const ListOf<T>& L ) : theList(L) { reset(); }
00487 
00488   // Use compiler's copy constructor, operator=, and destructor.
00489 
00490   ListIteratorRep *clone() const { return new ListIteratorRep(*this); }
00491 
00492   Bool operator == ( const ListIteratorRep& LIR ) const {
00493     return ( ( current == LIR.current ) && 
00494              ( ( theList.look() == LIR.theList.look() ) ||
00495                ( *(theList.look()) == *(LIR.theList.look()) ) ));
00496   }
00497 
00498   T value( ) const {
00499     #if SAFETY > 0
00500       if ( current == NULL )
00501         error("tried to retrieve value from ListIterator which is done");
00502     #endif
00503     return current->getContents();
00504   }
00505 
00506   Bool next( ) {
00507     if ( current != NULL )
00508       current = current->nextCell;
00509     return current != NULL;
00510   }
00511 
00512   Bool done( ) const { return current == NULL; }
00513 
00514   void reset( ) { current = theList.look()->root; }
00515 
00516   /////////////////////////////////////////////////////////////////////////
00517   //                                                                     //
00518   // IPC tools:                                                          //
00519   //                                                                     //
00520   /////////////////////////////////////////////////////////////////////////
00521 
00522     void  write( ostream& ostr ) const;
00523 
00524     void  read( istream& istr );
00525 
00526 private:
00527 
00528   // Data members:
00529 
00530   const ListOf<T>& theList;
00531   Cell<T>* current;
00532 };
00533 
00534 
00535 //---------------------- class ListIterator ----------------------------------
00536 
00537 // Example of use:
00538 //
00539 //  ListOf<Word> wordList;
00540 //  Word w;
00541 //  ...
00542 //
00543 //  ListIterator< ListOf<Word> > I(wordList);
00544 //  
00545 //  // Stupidly check for w:
00546 //  while ( !I.done() ) {
00547 //    if ( I.value() == w ) /* w is in wordList */
00548 //    I.next();
00549 //  }
00550 
00551 template <class ListType>
00552 class ListIterator :
00553 public ObjectOf< ListIteratorRep<typename ListType::ListElementType> > {
00554 
00555 public:
00556 
00557   typedef typename ListType::ListElementType T;
00558 
00559   ListIterator(const ListOf<T>& L) : ObjectOf<LIR>( new LIR(L) ) { }
00560   // Initialize an iterator with the list over which to iterate.
00561 
00562   // Copy constructor, operator=, and destructor supplied by compiler.
00563 
00564   // Copying or assigning an iterator is guaranteed to produce an
00565   // iterator which visits the (rest of the) same elements in the
00566   // same order as the original.
00567 
00568   Bool operator == ( const ListIterator& I ) const {
00569     return ((look() == I.look()) || (*look() == *I.look()));
00570   }
00571 
00572   T value( ) const { return look()->value(); }
00573   // Returns the current value. Calling this is a fatal error if done().
00574 
00575   Bool next( ) { return change()->next(); }
00576   // Advances this iterator.
00577   // Returns TRUE iff the iteration has not finished.
00578   // This may be called after it returns FALSE with no side effect.
00579 
00580   Bool done( ) const { return look()->done(); }
00581   // Returns TRUE iff the iteration has finished. This may
00582   // be called after it returns TRUE with no side effect.
00583 
00584   void reset( ) { change()->reset(); }
00585   // Resets this iterator to the state it was in after construction.
00586 
00587   /////////////////////////////////////////////////////////////////////////
00588   //                                                                     //
00589   // IPC tools:                                                          //
00590   //                                                                     //
00591   /////////////////////////////////////////////////////////////////////////
00592 
00593   friend ostream& operator < ( ostream& ostr, const ListIterator& LI )
00594   {
00595     LI.look()->write(ostr);
00596     return ostr;
00597   }
00598   
00599   friend istream& operator > ( istream& istr, ListIterator& LI)
00600   {
00601     LI.change()->read(istr);
00602     return istr;
00603   }
00604 
00605 private:
00606 
00607   typedef ListIteratorRep<T> LIR;
00608 };
00609 
00610 
00611 #endif

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