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

/magnus/back_end/general/include/DList.h

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

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