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

/magnus/back_end/general/include/Set.h

Go to the documentation of this file.
00001 /*
00002  *   $Id: Set.h,v 1.5 1996/08/20 22:58:48 alex 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 classes:
00009 //           SetData, SetIteratorData, SetOf, SetIterator.
00010 //
00011 // Everything is globbed together for now to keep g++ 2.5.8 happy.
00012 //
00013 // Principal Author: Roger Needham
00014 //
00015 // Status: Useable.
00016 //
00017 // Revision History:
00018 //
00019 // * 2/95 sr added
00020 //      int hashElement(const T & t) const;
00021 //      to avoid calling t.hash() directly. This accommodates SetOf<int>
00022 //
00023 // * 01/96 Dmitry B. implemented IPC tools.
00024 //
00025 // * 7/96 Dmitry B. made porting to gcc 2.7.2.
00026 //
00027 // Special Notes:
00028 //
00029 // * To instantiate SetOf<T>, class T must have
00030 //   1) An assignment operator
00031 //   2) A copy constructor
00032 //   3) An == operator
00033 //   4) A destructor
00034 //   5) A method int hash() const  (need not return positive ints)
00035 //
00036 // * The iterator template is parameterized by element type rather than
00037 //   container class type, so g++ 2.5.8 will buy it. We'll switch to the
00038 //   latter someday. Code which uses iterators will then break, but will be
00039 //   easy to fix.
00040 //
00041 // * The set-theoretic operators are not global, because I'm paranoid about
00042 //   the following: since there is a conversion T -> SetOf<T>, T would aquire
00043 //   a host of confusing new operators. For example, if
00044 //     inline SetOf<T> operator & (const SetOf<T>& S1, const SetOf<T>& S2) {
00045 //       return setIntersection(S1, S2);
00046 //     }
00047 //   then
00048 //     T t1, t2; T t = t1 & t2;
00049 //   would be caught by the compiler, but
00050 //     T t1, t2, t3; if ( (t1 & t2) == t3 ) {...}
00051 //   would not (assuming T has a default constructor).
00052 //   Keeping the operators as members is not much of a burden; because of
00053 //   the symmetry of the operators, one can recast any desired expression
00054 //   so that a genuine SetOf<T> is the left operand.
00055 //   Also, this decision is reversible without breaking existing code.
00056 //
00057 // Things to Deal With:
00058 //
00059 // * Adopt a consistent policy on the return type of assignment-like
00060 //   operators (val vs. ref). This affects other classes as well.
00061 //   To bear in mind / investigate is the effect the choice has on
00062 //   generating supplementary constructor calls, and the fact that the
00063 //   decision cascades through to assignment-like operators and
00064 //   functions which call other ones.
00065 //
00066 // Implementation Notes:
00067 //
00068 // * SetOfs are implemented as open hash tables. They are rehashed (doubling
00069 //   or halving number of buckets) when the number of elements exceeds
00070 //   FULLNESS_FACTOR * (number of buckets) or falls below
00071 //   (number of buckets) / FULLNESS_FACTOR.
00072 //   The (cheap) decision whether to rehash is made during each insert and
00073 //   delete, except that if the user specifies an initial size, the new size
00074 //   will not go below the specified size until the user calls `rehash()'.
00075 //
00076 // * We could choose the number of buckets more cleverly, and keep track
00077 //   of whether any bucket is getting too big. In that case, we'd resize
00078 //   +/- a small number to spread things out.
00079 
00080 
00081 #ifndef _SET_H_
00082 #define _SET_H_
00083 
00084 #include "global.h"
00085 #include "RefCounter.h"
00086 #include "PureRep.h"
00087 #include "ObjectOf.h"
00088 #include "Cell.h"
00089 
00090 
00091 template <class T> class SetIteratorData;
00092 // Forward declaration for friend declarations.
00093 
00094 
00095 //---------------------- class SetData ----------------------------------
00096 
00097 
00098 #define FULLNESS_FACTOR 2
00099 // Must be >= 2.
00100 
00101 
00102 template<class T>
00103 class SetData : public RefCounter {
00104 
00105 public:
00106 
00107   SetData(int size)
00108   // size is suggestion (possibly very bad) of eventual set cardinality.
00109   // The result represents an empty set.
00110   {
00111          // Make sure size has form 2^n - 1.
00112          if ( size < 0 ) size = 0;
00113          userSize = ( size > 1 ) ? size : 0;
00114          unsigned int realSize = 1;
00115          while ( size >>= 1 ) realSize = (realSize << 1) + 1;
00116          
00117          numberOfBuckets = realSize;
00118          hashTable = new CellType*[realSize];
00119          
00120          for( int i = 0; i < realSize; i++ )
00121                 hashTable[i] = NULL;
00122          
00123          numberOfElements = 0;
00124   }
00125 
00126   SetData( const T& t )
00127   {
00128          userSize = 0;
00129          numberOfBuckets = 1;
00130          hashTable = new CellType*[1];
00131          hashTable[0] = new CellType(t);
00132          numberOfElements = 1;
00133   }
00134 
00135   SetData(const SetData& sd)
00136   // Copy constructor does deep copy.
00137   {
00138          userSize = sd.userSize;
00139          numberOfElements = sd.numberOfElements;
00140          numberOfBuckets = sd.numberOfBuckets;
00141          hashTable = new CellType*[numberOfBuckets];
00142          CellType *bucket;
00143          CellType **newBucket;
00144          
00145          for( int i = 0; i < numberOfBuckets; i++ ) {
00146                 hashTable[i] = NULL;
00147                 newBucket = &hashTable[i];
00148                 bucket = sd.hashTable[i];
00149                 while ( bucket != NULL ) {
00150                   *newBucket = new CellType(*bucket);
00151                   newBucket = &((*newBucket)->nextCell);
00152                   bucket = bucket->nextCell;
00153                 }
00154          }
00155   }
00156 
00157   ~SetData()
00158   // Delete everything associated with this SetData. Reference counting
00159   // spares the T's if necessary.
00160   {
00161          if ( hashTable ) {
00162                 removeAllElements();
00163                 delete [] hashTable;
00164                 hashTable = NULL;
00165          }
00166   }
00167 
00168   SetData* clone( ) const { return new SetData(*this); }
00169 
00170   Bool operator == ( const SetData& sd ) const
00171   {
00172          if ( numberOfElements != sd.numberOfElements ) return FALSE;
00173          for ( int i = 0; i < numberOfBuckets; i++ ) {
00174                 CellType* scan = hashTable[i];
00175                 while ( scan != NULL ) {
00176                   if ( !sd.contains(scan->getContents()) ) return FALSE;
00177                   scan = scan->nextCell;
00178                 }
00179          }
00180          return TRUE;
00181   }
00182 
00183   int hashElement(const T & t) const;
00184 
00185   void rehash( Bool calledByUser = FALSE )
00186   {
00187          if ( calledByUser ) userSize = 0;
00188 
00189          int newNumberOfBuckets;
00190 
00191          if ( numberOfElements > FULLNESS_FACTOR * numberOfBuckets )
00192                 newNumberOfBuckets = (numberOfBuckets << 1) + 1;
00193          else if ( numberOfElements < numberOfBuckets / FULLNESS_FACTOR ) {
00194                 // Assumes FULLNESS_FACTOR >= 2, so won't resize to 0.
00195                 if ( !userSize || (numberOfBuckets >> 1) >= userSize )
00196                   newNumberOfBuckets = numberOfBuckets >> 1;
00197                 else return;
00198          }
00199          else return;
00200 
00201          int i;
00202 
00203          CellType **newHashTable = new CellType*[newNumberOfBuckets];
00204          for ( i = 0; i < newNumberOfBuckets; i++ )
00205                 newHashTable[i] = NULL;
00206          
00207          // Now cycle through the old set, rehash its elements, detach them and
00208          // reinsert them in newHashTable.
00209          
00210          CellType *curCell, *tmp;
00211          int index;
00212          for( i = 0; i < numberOfBuckets; i++ ) {
00213                 curCell = hashTable[i];
00214                 while ( curCell != NULL ) {
00215                   tmp = curCell->nextCell;
00216                   
00217                   // Rehash and insert entire cell into newHashTable
00218                   index = abs(hashElement(curCell->getContents())) % newNumberOfBuckets;
00219                   curCell->nextCell = newHashTable[index];
00220                   newHashTable[index] = curCell;
00221                   
00222                   curCell = tmp;
00223                 }
00224                 hashTable[i] = NULL;
00225          }
00226          
00227          // Put all private variables back together and clean up.
00228          numberOfBuckets = newNumberOfBuckets;
00229          delete [] hashTable;
00230          hashTable = newHashTable;
00231   }
00232 
00233   void removeAllElements()
00234   // Make *this represent an empty set, possibly keeping, e.g., a large
00235   // but empty bucket table.
00236   {
00237          for( int i = 0; i < numberOfBuckets; i++ ) {
00238                 CellType *bucket = hashTable[i];
00239                 while ( bucket != NULL ) {
00240                   CellType *tmp = bucket;
00241                   bucket = bucket->nextCell;
00242                   delete tmp;
00243                 }
00244                 hashTable[i] = NULL;
00245          }
00246          numberOfElements = 0;
00247   }
00248 
00249   int cardinality() const { return numberOfElements; }
00250 
00251   Bool contains(const T& e) const
00252   {
00253          int index = abs(hashElement(e)) % numberOfBuckets;
00254          CellType* search = hashTable[index];
00255          while ( search != NULL ) {
00256                 if ( e == search->getContents() ) return TRUE;
00257                 search = search->nextCell;
00258          }
00259          return FALSE;
00260   }
00261 
00262   void adjoinElement(const T& e)
00263   {
00264          rehash();
00265          int index = abs(hashElement(e)) % numberOfBuckets;
00266          CellType* search = hashTable[index];
00267          while ( search != NULL ) {
00268                 if ( e == search->getContents() ) return;
00269                 search = search->nextCell;
00270          }
00271          search = new CellType(e);
00272          search->nextCell = hashTable[index];
00273          hashTable[index] = search;
00274          ++numberOfElements;
00275   }
00276 
00277   void removeElement(const T& e)
00278   {
00279          int index = abs(hashElement(e)) % numberOfBuckets;
00280          CellType* search = hashTable[index];
00281          if ( search != NULL )
00282                 if ( e == search->getContents() )
00283                   hashTable[index] = search->nextCell;
00284                 else {
00285                   CellType* prev = search;
00286                   while ( (search = search->nextCell) != NULL ) {
00287                          if ( e == search->getContents() ) {
00288                                 prev->nextCell = search->nextCell;
00289                                 break;
00290                          }
00291                          prev = search;
00292                   }
00293                 }
00294          if ( search != NULL ) {
00295                 delete search;
00296                 --numberOfElements;
00297                 rehash();
00298          }
00299   }
00300 
00301   void printOn(ostream& ostr) const {
00302          ostr << "\nSet of cardinality: " << numberOfElements << "\n{" << endl;
00303          for ( int i = 0; i < numberOfBuckets; i++ ) {
00304                 CellType* scan = hashTable[i];
00305                 while ( scan != NULL ) {
00306                   ostr << scan->getContents() << endl;
00307                   scan = scan->nextCell;
00308                 }
00309          }
00310          ostr << "\n}" << endl;
00311   }
00312 
00313 
00314   /////////////////////////////////////////////////////////////////////////
00315   //                                                                     //
00316   // IPC tools:                                                          //
00317   //                                                                     //
00318   /////////////////////////////////////////////////////////////////////////
00319 
00320   void write( ostream& ostr ) const;
00321  
00322   void read( istream& istr );
00323  
00324 
00325   #ifdef DEBUG
00326   void printStats() const
00327   // Print statistics for hash table (for testing efficiency).
00328   {
00329          cout << "\n\nHash table statistics:\n\n";
00330          cout << "User specified size = ";
00331          if ( userSize ) cout << userSize << endl;
00332          else cout << "(cleared by call to `rehash()')" << endl;
00333          cout << "Number of entries = " << numberOfElements << endl;
00334          cout << "Number of buckets = " << numberOfBuckets << endl;
00335          
00336          double sum = 0;
00337          double sumSquares = 0;
00338          long maxLen = 0;
00339          long minLen = 1000000;
00340          long numEmpties = 0;
00341          long len;
00342          CellType *cPtr;
00343          for( int i = 0; i < numberOfBuckets; i++ ) {
00344                 cPtr = hashTable[i];
00345                 if ( !cPtr ) ++numEmpties;
00346                 len = 0;
00347                 while ( cPtr ) { len++; cPtr = cPtr->nextCell; }
00348                 maxLen = max( len, maxLen );
00349                 minLen = min( len, minLen );
00350                 sum += len;
00351                 sumSquares += len*len;
00352          }
00353          long numNonEmpty = numberOfBuckets-numEmpties;
00354          double mean = sum / numNonEmpty;
00355          cout << "Largest bucket size = " << maxLen << endl;
00356          cout << "Smallest bucket size = " << minLen << endl;
00357          cout << "Average non-empty bucket size = " << mean << endl;
00358          cout << "Number of empty buckets = " << numEmpties;
00359          cout << ", or " << 100*numEmpties/numberOfBuckets << "%" << endl;
00360          cout << "Sample standard deviation in non-empty bucket size = sqrt(";
00361          cout << ((sumSquares - 2*mean*sum + numNonEmpty*mean*mean)/(numNonEmpty-1)) << ")\n" << endl;
00362   }
00363   #endif
00364 
00365   #ifdef DEBUG
00366   void printRep() const
00367   // Print a legible representation of the hash table.
00368   {
00369          cout << "\n\nHash table:\n-----------\n\n";
00370          CellType *cPtr;
00371          for( int i = 0; i < numberOfBuckets; i++ ) {
00372                 cout << i << ": ";
00373                 cPtr = hashTable[i];
00374                 while ( cPtr ) {
00375                   cout << ". ";
00376                   cPtr = cPtr->nextCell;
00377                 }
00378                 cout << endl;
00379          }
00380   }
00381   #endif
00382   
00383   
00384 //@db private: 
00385 protected:
00386 
00387   typedef Cell<T> CellType;
00388 
00389   friend SetIteratorData<T>;
00390 
00391 
00392   // Data members:
00393 
00394   int         userSize;         // Initial size > 1 given by the user,
00395                                 // or 0 if none specified. Reset to 0
00396                                 // only by rehash(TRUE).
00397   int         numberOfElements;
00398   int         numberOfBuckets;  // Equal to 2^n - 1 for some n.
00399   CellType**  hashTable;
00400 
00401 };
00402 
00403 
00404 //---------------------- class SetOf -----------------------------------
00405 
00406 
00407 template<class T>
00408 class SetOf : public ObjectOf< SetData<T> > {
00409 
00410 public:
00411 
00412   typedef T SetElementType; // Export this
00413 
00414   SetOf( int size = 1 ) : ObjectOf<Rep>( new Rep(size) ) { }
00415   // Give rough advice about eventual cardinality. The result is an empty set.
00416   // If you specify size > 1, the underlying hash table never shrinks
00417   // below that size until you call `rehash()'.
00418   // Note that because of hash table doubling, it costs only O(n) to build
00419   // up a set of cardinality n from the default.
00420 
00421   SetOf( const T& t ) : ObjectOf<Rep>( new Rep(t) ) { }
00422   // Cast constructor wraps element in a set.
00423 
00424   // Use compiler's copy constructor, operator=, and destructor.
00425 
00426   // Standard set-theoretic operators, defined in terms of member
00427   // functions:
00428 
00429   Bool operator == ( const SetOf& S ) const {
00430          return equalTo(S);
00431   }
00432 
00433   Bool operator != ( const SetOf& S ) const {
00434          return !equalTo(S);
00435   }
00436 
00437   Bool operator < ( const SetOf& S ) const {
00438          return S.properlyContains(*this);
00439   }
00440 
00441   Bool operator <= ( const SetOf& S ) const {
00442          return S.contains(*this);
00443   }
00444 
00445   Bool operator > ( const SetOf& S ) const {
00446          return properlyContains(S);
00447   }
00448 
00449   Bool operator >= ( const SetOf& S ) const {
00450          return contains(S);
00451   }
00452 
00453   Bool operator >= ( const T& e ) const {
00454          return contains(e);
00455   }
00456 
00457   SetOf operator & ( const SetOf& S ) const {
00458          return setIntersection(*this, S);
00459   }
00460 
00461   SetOf operator &= ( const SetOf& S ) {
00462          shrinkToIntersectionWith(S);
00463          return *this;
00464   }
00465 
00466   SetOf operator | ( const SetOf& S ) const {
00467          return setUnion(*this, S);
00468   }
00469 
00470   SetOf operator |= ( const SetOf& S ) {
00471          adjoinElements(S);
00472          return *this;
00473   }
00474 
00475   SetOf operator |= ( const T& e ) {
00476          adjoinElement(e);
00477          return *this;
00478   }
00479 
00480   SetOf operator - ( const SetOf& S ) const {
00481          return setMinus(*this, S);
00482   }
00483 
00484   SetOf operator -= ( const SetOf& S ) {
00485          removeElements(S);
00486          return *this;
00487   }
00488 
00489   SetOf operator -= ( const T& e ) {
00490          removeElement(e);
00491          return *this;
00492   }
00493 
00494   SetOf operator ^ ( const SetOf& S ) const {
00495          return setSymmetricDifference(*this, S);
00496   }
00497 
00498   // Member functions:
00499 
00500   int cardinality() const { return look()->cardinality(); }
00501 
00502   Bool equalTo(const SetOf& S) const {
00503          return ((look() == S.look()) || (*look() == *S.look()));
00504   }
00505   // TRUE iff S is equal as a set to *this.
00506 
00507   Bool contains(const T& e) const { return look()->contains(e); }
00508   // TRUE iff *this contains a T == to e.
00509 
00510   Bool contains(const SetOf& S) const;
00511   // TRUE iff S is a subset of *this.
00512 
00513   Bool properlyContains(const SetOf& S) const {
00514          return ( cardinality() > S.cardinality() && contains(S) );
00515   }
00516   // TRUE iff S is a proper subset of *this.
00517 
00518   void adjoinElement(const T& e) { change()->adjoinElement(e); }
00519   // Add e to *this. It is not an error if *this already contains e.
00520 
00521   void removeElement(const T& e) { change()->removeElement(e); }
00522   // Remove e from *this.
00523   // It is not an error if this set does not contain e.
00524 
00525   void shrinkToIntersectionWith(const SetOf& S);
00526   // Make *this the intersection of *this and S.
00527 
00528   void adjoinElements(const SetOf& S);
00529   // Adjoin each element of S to *this.
00530 
00531   void removeElements(const SetOf& S);
00532   // Remove each element of S from *this.
00533 
00534   void removeAllElements() { change()->removeAllElements(); }
00535   // Makes *this into an empty set.
00536 
00537   void rehash( ) { enhance()->rehash(TRUE); }
00538   // For tweaking performance. Calling this is never sematically wrong, and
00539   // in the worst case degrades performance by increasing the constant in O(n);
00540   // see the comment for the default constructor.
00541 
00542   friend ostream& operator << ( ostream& ostr, const SetOf& S ) {
00543          S.look()->printOn(ostr);
00544          return ostr;
00545   }
00546 
00547 
00548   /////////////////////////////////////////////////////////////////////////
00549   //                                                                     //
00550   // IPC tools:                                                          //
00551   //                                                                     //
00552   /////////////////////////////////////////////////////////////////////////
00553 
00554   friend ostream& operator < ( ostream& ostr, const SetOf& S )
00555   {
00556     S.look()->write(ostr);
00557     return ostr;
00558   }
00559   
00560   friend istream& operator > ( istream& istr, SetOf& S )
00561   {
00562     S.change()->read(istr);
00563     return istr;
00564   }
00565 
00566 
00567   #ifdef DEBUG
00568     void printStats() const { look()->printStats(); }
00569     void printRep() const { look()->printRep(); }
00570   #endif
00571 
00572 
00573 
00574 protected:
00575 
00576   typedef SetData<T> Rep;
00577 
00578   friend class SetIteratorData<T>;
00579 
00580 //@rn  SetOf( Rep* p ) : ObjectOf<Rep>(p) { }
00581 
00582 };
00583 
00584 
00585 // /*@rn g++ 2.5.8 gets confused when you prototype these
00586 
00587 template <class T>
00588 SetOf<T> setUnion(const SetOf<T>&, const SetOf<T>&);
00589 
00590 template <class T>
00591 SetOf<T> setIntersection(const SetOf<T>&, const SetOf<T>&);
00592 
00593 template <class T>
00594 SetOf<T> setMinus(const SetOf<T>&, const SetOf<T>&);
00595 
00596 template <class T>
00597 SetOf<T> setSymmetricDifference(const SetOf<T>&, const SetOf<T>&);
00598 
00599 // */
00600 
00601 
00602 
00603 //---------------------- class SetIteratorData ------------------------------
00604 
00605 template<class T>
00606 class SetContainer : public ObjectOf< SetData<T> > {
00607 public:
00608   friend class SetIteratorData<T>;
00609   SetContainer( const SetOf<T>& S ) : ObjectOf< SetData<T> >(S) { }
00610 };
00611 // A helper class which mimics a SetOf<T>, to get around the usual g++
00612 // template fuckup. See the theSet member below.
00613 
00614 
00615 template<class T>
00616 class SetIteratorData : public PureRep {
00617 
00618 public:
00619 
00620   SetIteratorData(const SetOf<T>& S) : theSet(S) { reset(); }
00621 
00622   // Use compiler's copy constructor, operator=, and destructor.
00623 
00624   PureRep *clone() const { return new SetIteratorData(*this); }
00625 
00626   Bool operator == ( const SetIteratorData& sid ) const {
00627          return ( current == sid.current && theSet.look() == sid.theSet.look() );
00628   }
00629 
00630   T value( ) const {
00631          #if SAFETY > 0
00632            if ( current == NULL )
00633                   error("tried to retrieve value from SetIterator which is done");
00634     #endif
00635          return current->getContents();
00636   }
00637 
00638   Bool next( ) {
00639          if ( current != NULL )
00640                 current = current->nextCell;
00641          if ( current == NULL ) {
00642                 int numberOfBuckets = theSet.look()->numberOfBuckets;
00643                 if ( bucketIndex >= numberOfBuckets ) return 0;
00644                 CellType** hashTable = theSet.look()->hashTable;
00645                 ++bucketIndex;
00646                 while ( bucketIndex < numberOfBuckets && hashTable[bucketIndex] == NULL )
00647                   ++bucketIndex;
00648                 if ( bucketIndex < numberOfBuckets )
00649                   current = hashTable[bucketIndex];
00650          }
00651          return (current != NULL);
00652   }
00653 
00654   Bool done( ) const { return (current == NULL); }
00655 
00656   void reset( ) {
00657          current = NULL;
00658          bucketIndex = -1;
00659          next();
00660   }
00661 
00662 
00663 private:
00664 
00665   typedef Cell<T> CellType;
00666 
00667   // Data members:
00668 
00669   CellType*      current;
00670   int            bucketIndex;
00671 
00672   const SetContainer<T> theSet;
00673 
00674   // If theSet is declared as SetOf<T>, g++ 2.5.8 & 2.6.0 claim that it
00675   // has incomplete type. Then why, prithee, is this ok?
00676   // The exact same scheme works in ListOf and AssociationsOf.
00677 };
00678 
00679 
00680 
00681 //---------------------- class SetIterator ------------------------------
00682 
00683 // To iterate over the elements of a SetOf<T> S, just do:
00684 //
00685 //  SetIterator<T> I(S);
00686 //  while ( !I.done() ) {
00687 //    /* Do something with I.value() */
00688 //    I.next();
00689 //  }
00690 //
00691 // You may assign one SetIterator to another, so the following works:
00692 //
00693 //  SetIterator<T> I(S);
00694 //  while( !I.done() ) {
00695 //    SetIterator<T> J = I;
00696 //    while( J.next() )
00697 //      if ( I.value() == J.value() ) error("Set contains duplicates!");
00698 //    I.next();
00699 //  }
00700 //  int count = 0;
00701 //  I.reset();
00702 //  while( !I.done() ) {
00703 //    SetIterator<T> J(I);
00704 //    do { if ( I.value() == J.value() ) ++count; } while( J.next() );
00705 //    I.next();
00706 //  }
00707 //  if ( count != S.cardinality() ) error("I give up");
00708 //
00709 // Since I was reset, the two excursions of I through S are guaranteed to
00710 // produce the same sequence of elements. In any case, J is guaranteed to look
00711 // at the rest of what I is.
00712 // You may alter S during the iteration, but I uses the old copy
00713 // of S (see shrinkToIntersectionWith). You may alter the object returned by
00714 // I.value(), but this will not effect S or I.
00715 
00716 
00717 /* @@rn Changing parameterization for g++ 2.6.0
00718 
00719 template <class SetOfType>
00720 class SetIterator :
00721 public ObjectOf< SetIteratorData<SetOfType::SetElementType> > {
00722 */
00723 
00724 template <class T>
00725 class SetIterator : public ObjectOf< SetIteratorData<T> > {
00726 
00727 public:
00728 
00729 //@@rn  typedef SetOfType::SetElementType T;
00730 
00731   SetIterator(const SetOf<T>& S) : ObjectOf<SID>( new SID(S) ) { }
00732   // Constructs iterator from set over which to iterate.
00733 
00734   // Copy constructor, operator=, and destructor supplied by compiler.
00735 
00736   Bool operator == ( const SetIterator& I ) const {
00737          return ((look() == I.look()) || (*look() == *I.look()));
00738   }
00739   // TRUE iff the iterators will look at the same elements of the (physically)
00740   // same set in the same order. Valid at any point of the iteration.
00741 
00742   T value( ) const { return look()->value(); }
00743   // Returns the current T. Calling this is a fatal error if done().
00744 
00745   Bool next( ) { return change()->next(); }
00746   // Advances this iterator.
00747   // Returns TRUE iff the iteration has not finished.
00748   // This may be called after it returns FALSE with no side effect.
00749 
00750   Bool done( ) const { return look()->done(); }
00751   // Returns TRUE iff the iteration has finished. This may
00752   // be called after it returns TRUE with no side effect.
00753 
00754   void reset( ) { change()->reset(); }
00755   // Resets this iterator to the state it was in after construction.
00756 
00757 protected:
00758 
00759   typedef SetIteratorData<T> ThisRep;
00760   typedef ObjectOf<ThisRep> Base;
00761  
00762   // Shadow representation accessors to get representations of the
00763   // right type in the members of this class:
00764  
00765   const ThisRep* look( ) const {
00766     return (const ThisRep*)Base::look();
00767   }
00768   ThisRep* enhance( ) const {
00769          return (ThisRep*)Base::enhance();
00770   }
00771   ThisRep* change( ) {
00772          return (ThisRep*)Base::change();
00773   }
00774 
00775   SetIterator( ThisRep* rep ) : Base(rep) { }
00776   // To wrap new representation
00777 
00778 private:
00779 
00780   typedef SetIteratorData<T> SID;
00781 
00782 };
00783 
00784 
00785 //------------ SetOf functions which depend on SetIterator --------------------
00786 
00787 /*
00788 template <class T>
00789 void SetOf<T>::shrinkToIntersectionWith(const SetOf<T>& S)
00790 {
00791 //@@rn  SetIterator< SetOf<T> > I(*this);
00792   SetIterator<T> I(*this);
00793   while ( !I.done() ) {
00794          if ( !S.contains( I.value() ) ) removeElement( I.value() );
00795          I.next();
00796   }
00797 }
00798 
00799 
00800 template <class T>
00801 void SetOf<T>::adjoinElements(const SetOf<T>& S)
00802 {
00803 //@@rn  SetIterator< SetOf<T> > I(S);
00804   SetIterator<T> I(S);
00805   while ( !I.done() ) {
00806          adjoinElement( I.value() );
00807          I.next();
00808   }
00809 }
00810 
00811 
00812 template <class T>
00813 void SetOf<T>::removeElements(const SetOf<T>& S)
00814 {
00815 //@@rn  SetIterator< SetOf<T> > I(S);
00816   SetIterator<T> I(S);
00817   while ( !I.done() ) {
00818          removeElement( I.value() );
00819          I.next();
00820   }
00821 }
00822 
00823 
00824 template <class T>
00825 Bool SetOf<T>::contains(const SetOf<T>& S) const
00826 {
00827 //@@rn  SetIterator< SetOf<T> > I(S);
00828   SetIterator<T> I(S);
00829   while ( !I.done() ) {
00830          if ( !contains( I.value() ) ) return 0;
00831          I.next();
00832   }
00833   return 1;
00834 }
00835 */
00836 
00837 template <class T>
00838 SetOf<T> setUnion(const SetOf<T>& S1, const SetOf<T>& S2)
00839 {
00840   if ( S1.cardinality() < S2.cardinality() ) {
00841          SetOf<T> result = S2;
00842 //@@rn   SetIterator< SetOf<T> > I(S1);
00843          SetIterator<T> I(S1);
00844          while ( !I.done() ) {
00845                 result.adjoinElement( I.value() );
00846                 I.next();
00847          }
00848          return result;
00849   } else {
00850          SetOf<T> result = S1;
00851 //@@rn   SetIterator< SetOf<T> > I(S2);
00852          SetIterator<T> I(S2);
00853          while ( !I.done() ) {
00854                 result.adjoinElement( I.value() );
00855                 I.next();
00856          }
00857          return result;
00858   }
00859 }
00860 
00861 
00862 template <class T>
00863 SetOf<T> setIntersection(const SetOf<T>& S1, const SetOf<T>& S2)
00864 {
00865   SetOf<T> result;
00866   if ( S1.cardinality() < S2.cardinality() ) {
00867 //@@rn   SetIterator< SetOf<T> > I(S1);
00868          SetIterator<T> I(S1);
00869          while ( !I.done() ) {
00870                 if ( S2.contains( I.value() ) )
00871                   result.adjoinElement( I.value() );
00872                 I.next();
00873          }
00874   } else {
00875 //@@rn   SetIterator< SetOf<T> > I(S2);
00876          SetIterator<T> I(S2);
00877          while ( !I.done() ) {
00878                 if ( S1.contains( I.value() ) )
00879                   result.adjoinElement( I.value() );
00880                 I.next();
00881          }
00882   }
00883   return result;
00884 }
00885 
00886 
00887 template <class T>
00888 SetOf<T> setMinus(const SetOf<T>& S1, const SetOf<T>& S2)
00889 {
00890   SetOf<T> result;
00891 //@@rn  SetIterator< SetOf<T> > I(S1);
00892   SetIterator<T> I(S1);
00893   while ( !I.done() ) {
00894          if ( !S2.contains( I.value() ) )
00895                   result.adjoinElement( I.value() );
00896          I.next();
00897   }
00898   return result;
00899 }
00900 
00901 
00902 template <class T>
00903 SetOf<T> setSymmetricDifference(const SetOf<T>& S1, const SetOf<T>& S2)
00904 {
00905   SetOf<T> result;
00906 //@@rn  SetIterator< SetOf<T> > I1(S1);
00907   SetIterator<T> I1(S1);
00908   while ( !I1.done() ) {
00909          if ( !S2.contains( I1.value() ) )
00910                   result.adjoinElement( I1.value() );
00911          I1.next();
00912   }
00913 //@@rn  SetIterator< SetOf<T> > I2(S2);
00914   SetIterator<T> I2(S2);
00915   while ( !I2.done() ) {
00916          if ( !S1.contains( I2.value() ) )
00917                   result.adjoinElement( I2.value() );
00918          I2.next();
00919   }
00920   return result;
00921 }
00922 
00923 
00924 
00925 #endif
00926 
00927 
00928 
00929 

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