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

/magnus/back_end/general/include/Associations.h

Go to the documentation of this file.
00001 /*
00002  *   $Id: Associations.h,v 1.3 2000/03/03 04:11:08 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
00009 //           template <class Key, class Val> class AssociationsOf
00010 //
00011 // AssociationsOf implements an associative array, currently with O(n)
00012 // access time.
00013 //
00014 // Principal Authors: Stephane Collart, Roger Needham
00015 //
00016 // Status: Useable.
00017 //
00018 // Revision History:
00019 //
00020 // Special remarks:
00021 //
00022 // * Requirements: Key and Val must have copy constructors and destructors,
00023 //   Val must have operator=, and Key must have operator==.
00024 //   Because an AssociationsOf method returns a ListOf<Key>, and ListOf wants to
00025 //   output its elements using <<, there must also be an
00026 //   ostream& operator << ( ostream&, const Type& ),
00027 //   and a conversion of Key to Type.
00028 //   @rn `inherited' requirements like this bear further consideration.
00029 //
00030 // * This copies Keys and Vals around, so non-user classes are less efficent.
00031 //
00032 // * The iterator template is parameterized by Key and Val, rather than
00033 //   container class type, so g++ 2.5.8 will buy it. We'll switch to the
00034 //   latter someday. Code which uses iterators will then break, but will be
00035 //   easy to fix.
00036 //
00037 // * Val AssociationsOf<Key,Val>::operator [ ] ( const Key& ) const
00038 //   may be enhanced later to act as an lvalue. No code will break.
00039 //
00040 // * I left out the possibly handy method
00041 //     Key AssociationsOf<Key,Val>::keyOf( const Val& ) const
00042 //   so as not to require Val to have operator==.
00043 //
00044 // * The return values of, e.g., valueOf would be more efficient as
00045 //   references, but that seems to make the reference count go bad.
00046 //   07/96 Aleksey M. implemented IPC tools
00047 
00048 #ifndef _ASSOCIATIONS_H_
00049 #define _ASSOCIATIONS_H_
00050 
00051 
00052 #include "RefCounter.h"
00053 #include "ObjectOf.h"
00054 #include "List.h"
00055 #include "Cell.h"
00056 
00057 #include <iostream.h>
00058 
00059 
00060 //---------------------- class Association ----------------------------------
00061 
00062 template <class Key, class Val> class Association {
00063 public:
00064   Association(Key k, Val v) : key(k), val(v) { }
00065   Key key;
00066   Val val;
00067  
00068  /////////////////////////////////////////////////////////////////////////
00069   //                                                                     //
00070   // IPC tools:                                                          //
00071   //                                                                     //
00072   /////////////////////////////////////////////////////////////////////////
00073 
00074   friend ostream& operator < ( ostream& ostr, const Association& A )
00075   {
00076     ostr < A.key;
00077     ostr < A.val;
00078     return ostr;
00079   }
00080   
00081   friend istream& operator > ( istream& istr, Association& A )
00082   {
00083     istr > A.key;
00084     istr > A.val;
00085     return istr;
00086   }
00087 
00088 };
00089 
00090 //---------------------- class AssociationsRep -----------------------------
00091 
00092 
00093 template <class Key, class Val> class AssociationsIteratorRep;
00094 // Forward declaration for friend declarations.
00095 
00096 template <class Key, class Val> class AssociationsRep : public RefCounter {
00097 
00098 public:
00099 
00100   AssociationsRep( ) : theList(NULL), theCardinality(0) {}
00101 
00102   AssociationsRep( const AssociationsRep& ar ) {  // Usual deep copy.
00103     theCardinality = ar.theCardinality;
00104     theList = NULL;
00105     CellType* tmpList = NULL;
00106     CellType* oldList = ar.theList;
00107     while ( oldList ) {
00108       if ( theList == NULL ) {
00109         theList = new CellType(*oldList);
00110         tmpList = theList;
00111       } // @stc are you relying on the compiler to move this out of
00112       // the loop?
00113       else {
00114         tmpList->nextCell = new CellType(*oldList);
00115         tmpList = tmpList->nextCell;
00116       }
00117       oldList = oldList->nextCell;
00118     }
00119     if( tmpList )
00120       tmpList->nextCell = NULL; // Better safe than sorry
00121   }
00122 
00123   ~AssociationsRep( ) {
00124          while ( theList ) {
00125                 CellType* tmpList = theList;
00126                 theList = theList->nextCell;
00127                 delete tmpList;
00128          }
00129   }
00130   
00131   AssociationsRep* clone( ) const { return new AssociationsRep(*this); }
00132 
00133   void unbind( const Key& k ) {
00134          if ( theList->getContents().key == k ) {
00135                 CellType* tmp = theList;
00136                 theList = theList->nextCell;
00137                 delete tmp;
00138                 --theCardinality;
00139          } else {
00140                 CellType* pred = theList;
00141                 CellType* scan = theList->nextCell;
00142                 while ( scan ) {
00143                   if ( scan->getContents().key == k ) {
00144                          pred->nextCell = scan->nextCell;
00145                          delete scan;
00146                          --theCardinality;
00147                          break;
00148                   }
00149                   scan = scan->nextCell;
00150                 }
00151          }
00152   }
00153 
00154   void bind( const Key& k, const Val& v ) {
00155          CellType* where = seek(k);
00156          if ( where )
00157                 where->getContents().val = v;
00158          else {
00159                 //@rn g++2.5.8 can get confused by:
00160                 // theList = new CellType(Association<Key,Val>(k, v), theList);
00161 
00162                 CellType* tmp = new CellType(Association<Key,Val>(k, v));
00163                 tmp->nextCell = theList;
00164                 theList = tmp;
00165                 ++theCardinality;
00166          }
00167   }
00168 
00169   Val val( const Key& k ) const {
00170          CellType* where = seek(k);
00171     #if SAFETY > 0
00172            if ( where == NULL )
00173         error("called AssociationsOf<Key,Val>::operator [ ] with unbound Key");
00174     #endif
00175          return where->getContents().val;
00176   }
00177 
00178   Bool bound( const Key& k ) const { return (seek(k) != NULL); }
00179 
00180   int cardinality() const { 
00181     return theCardinality;
00182   }
00183 
00184   /////////////////////////////////////////////////////////////////////////
00185   //                                                                     //
00186   // IPC tools:                                                          //
00187   //                                                                     //
00188   /////////////////////////////////////////////////////////////////////////
00189 
00190   void  write( ostream& ostr ) const;
00191   void  read( istream& istr );
00192 
00193 
00194 private:
00195 
00196   typedef Cell< Association<Key,Val> > CellType;
00197 
00198   friend class AssociationsIteratorRep<Key,Val>;
00199 
00200   AssociationsRep(CellType* L) { theList = L; }
00201 
00202   CellType* seek( const Key& k ) const {
00203          CellType* scan = theList;
00204          while ( scan ) {
00205                 if ( scan->getContents().key == k ) return scan;
00206                 scan = scan->nextCell;
00207          }
00208          return NULL;
00209   }
00210 
00211   // Data members:
00212 
00213   CellType* theList;
00214   int theCardinality;
00215 };
00216 
00217 
00218 //------------------- class AssociationsOf --------------------------//
00219 
00220 
00221 template <class Key, class Val> struct AssocRef;
00222 
00223 template <class Key, class Val>
00224 class AssociationsOf : public ObjectOf< AssociationsRep<Key,Val> > {
00225 
00226 public:
00227 
00228   AssociationsOf( ) : ObjectOf<Rep>(new Rep()) { }
00229   // Default constructor makes an empty set of associations.
00230 
00231   // Copy constructor, operator=, and destructor supplied by compiler.
00232 
00233   Val operator [ ] ( const Key& k ) const { return valueOf(k); }
00234   // Operator synonym for valueOf.
00235 
00236   AssocRef<Key,Val> operator [ ] ( const Key& k );
00237 
00238   Val valueOf( const Key& k ) const { return look()->val(k); }
00239   // Retrieves the Val associated with k. It is a fatal error if k is not
00240   // bound to any Val.
00241 
00242   void bind( const Key& k, const Val& v ) { change()->bind(k, v); }
00243   // Associates k with v. Overwrites any existing association.
00244 
00245   void unbind( const Key& k ) { change()->unbind(k); }
00246   // Breaks any association k has; not an error if none.
00247 
00248   Bool bound( const Key& k ) const { return look()->bound(k); }
00249   // Says whether k is associated with anything.
00250 
00251   ListOf<Key> keys( ) const;
00252   // Returns a list of all keys in this association list.
00253   // A similar function returning all values would require Val to
00254   // have an operator==.
00255 
00256   int cardinality() const { return look()->cardinality(); }
00257 
00258   /////////////////////////////////////////////////////////////////////////
00259   //                                                                     //
00260   // IPC tools:                                                          //
00261   //                                                                     //
00262   /////////////////////////////////////////////////////////////////////////
00263 
00264   friend ostream& operator < ( ostream& ostr, const AssociationsOf& A )
00265   {
00266     A.look()->write(ostr);
00267     return ostr;
00268   }
00269   
00270   friend istream& operator > ( istream& istr, AssociationsOf& A)
00271   {
00272     A.change()->read(istr);
00273     return istr;
00274   }
00275 
00276 private:
00277 
00278   typedef AssociationsRep<Key,Val> Rep;
00279 
00280   friend class AssociationsIteratorRep<Key,Val>;
00281 };
00282 
00283 
00284 //------------------------ struct AssocRef ---------------------------//
00285 
00286 
00287 template <class Key, class Val> struct AssocRef {
00288         AssociationsOf<Key,Val>& asref;
00289         const Key key;
00290         AssocRef( AssociationsOf<Key,Val>& a, const Key& k ) : asref(a), key(k) { }
00291    const Val& operator = ( const Val& val )
00292                 { asref.bind(key,val); return val; }
00293         operator Val ( ) { return asref.valueOf(key); }
00294         operator void* ( ) { return (void*)asref.bound(key); }
00295 };
00296 
00297 
00298 //------------------------ AssociationsOf ---------------------------//
00299 //---------------------- inline functions ---------------------------//
00300 
00301 template <class Key, class Val>
00302 inline AssocRef<Key,Val> AssociationsOf<Key,Val>::operator [ ] ( const Key& k )
00303         { return AssocRef<Key,Val>(*this,k); }
00304 
00305 
00306 //-------------- class AssociationsIteratorRep ----------------------//
00307 
00308 template <class Key, class Val>
00309 class AssociationsIteratorRep : public RefCounter {
00310 
00311 public:
00312 
00313   AssociationsIteratorRep( const AssociationsOf<Key,Val>& A ) :
00314     theAssociations(A) {
00315          current = theAssociations.look()->theList;
00316   }
00317 
00318   // Use compiler's copy constructor, operator=, and destructor.
00319 
00320   AssociationsIteratorRep *clone() const {
00321          return new AssociationsIteratorRep(*this);
00322   }
00323 
00324   Bool operator == ( const AssociationsIteratorRep& AIR ) const {
00325          return ( ( current == AIR.current ) && 
00326                                  ( theAssociations.look() == AIR.theAssociations.look() ) );
00327   }
00328   // @rn compare theAssociations cell-by-cell?
00329   // We do not want logical == of theAssociations, since iteration order
00330   // would be different.
00331 
00332   Key key( ) const {
00333          #if SAFETY > 0
00334            if ( current == NULL )
00335                   error("tried to retrieve key from AssociationsIterator which is done");
00336     #endif
00337          return current->getContents().key;
00338   }
00339 
00340   Val value( ) const {
00341          #if SAFETY > 0
00342            if ( current == NULL )
00343         error("tried to retrieve value from AssociationsIterator which is done");
00344     #endif
00345          return current->getContents().val;
00346   }
00347 
00348   Bool next( ) {
00349          if ( current != NULL )
00350                 current = current->nextCell;
00351          return (current != NULL);
00352   }
00353 
00354   Bool done( ) const { return (current == NULL); }
00355 
00356   void reset( ) { current = theAssociations.look()->theList; }
00357 
00358  /////////////////////////////////////////////////////////////////////////
00359   //                                                                     //
00360   // IPC tools:                                                          //
00361   //                                                                     //
00362   /////////////////////////////////////////////////////////////////////////
00363 
00364   void  write( ostream& ostr ) const;
00365   void  read( istream& istr );
00366 
00367 private:
00368 
00369   // Data members:
00370 
00371   const AssociationsOf<Key,Val>& theAssociations;
00372 
00373   AssociationsRep<Key,Val>::CellType* current;
00374 };
00375 
00376 
00377 //---------------------- class AssociationsIterator ---------------------------
00378 
00379 
00380 // Example of use:
00381 //
00382 //  AssociationsOf<Chars,Word> wordTable;
00383 //  Word w;
00384 //  ...
00385 //
00386 //  // Remove all associations with w from wordTable:
00387 //  
00388 //  AssociationsIterator<Chars,Word> I(wordTable);
00389 //  
00390 //  while ( !I.done() ) {
00391 //    if ( I.value() == G ) wordTable.unbind( I.key() );
00392 //    I.next();
00393 //  }
00394 
00395 // Note: You may alter the AssociationsOf over which you are iterating,
00396 //       but the iterator uses the `old' copy.
00397 
00398 template <class Key, class Val>
00399 class AssociationsIterator :
00400 public ObjectOf< AssociationsIteratorRep<Key,Val> > {
00401 
00402 public:
00403 
00404   AssociationsIterator(const AssociationsOf<Key,Val>& A) :
00405     ObjectOf<AIR>( new AIR(A) ) { }
00406   // Initialize an iterator with the Associations over which to iterate.
00407 
00408   // Copy constructor, operator=, and destructor supplied by compiler.
00409 
00410   // Copying or assigning an iterator is guaranteed to produce an
00411   // iterator which visits the (rest of the) same elements in the
00412   // same order as the original.
00413 
00414   Bool operator == ( const AssociationsIterator& I ) const {
00415          return ((look() == I.look()) || (*look() == *I.look()));
00416   }
00417 
00418   Key key( ) const { return look()->key(); }
00419   // Returns key of current association. Calling this is a fatal error
00420   // if done().
00421 
00422   Val value( ) const { return look()->value(); }
00423   // Returns value of current association. Calling this is a fatal error
00424   // if done().
00425 
00426   Bool next( ) { return change()->next(); }
00427   // Advances this iterator.
00428   // Returns TRUE iff the iteration has not finished.
00429   // This may be called after it returns FALSE with no side effect.
00430 
00431   Bool done( ) const { return look()->done(); }
00432   // Returns TRUE iff the iteration has finished. This may
00433   // be called after it returns TRUE with no side effect.
00434 
00435   void reset( ) { change()->reset(); }
00436   // Resets this iterator to the state it was in after construction.
00437 
00438   // @stc the following are added as a tentative supplementary
00439   // convenience
00440     AssociationsIterator& operator ++ ( ) { next(); return *this; }
00441     AssociationsIterator operator ++ ( int ) {
00442         AssociationsIterator old = *this;
00443         next( );
00444         return old;
00445     } // @stc need to check whether the semantics of this one are consistent
00446     // ie. does cloning preserve iterator semantics?
00447     operator void* ( ) { return (void*)!done(); }
00448 
00449   /////////////////////////////////////////////////////////////////////////
00450   //                                                                     //
00451   // IPC tools:                                                          //
00452   //                                                                     //
00453   /////////////////////////////////////////////////////////////////////////
00454 
00455   friend ostream& operator < ( ostream& ostr, const AssociationsIterator& AI )
00456   {
00457     AI.look()->write(ostr);
00458     return ostr;
00459   }
00460   
00461   friend istream& operator > ( istream& istr, AssociationsIterator& AI)
00462   {
00463     AI.change()->read(istr);
00464     return istr;
00465   }
00466 
00467 private:
00468 
00469   typedef AssociationsIteratorRep<Key,Val> AIR;
00470 };
00471 
00472 
00473 //-------------------------- Associations -----------------------------//
00474 //----------------------- associated functions ------------------------//
00475  
00476 template <class Key, class Val> inline ostream& operator <<
00477         ( ostream& o, const AssociationsOf<Key,Val>& a ) {
00478  
00479     AssociationsIterator<Key,Val> iter(a);
00480     o << "-";
00481     while (iter) {
00482         o << "[" << iter.key() << ":" << iter.value() << "]" << "-";
00483         ++iter;
00484     }
00485     return o;
00486 }
00487 // @stc inlined here (instead of defintion in .C) to circumvent g++
00488 // template problems
00489  
00490 
00491 //---------------------- methods which iterate -----------------------------
00492 
00493 template <class Key, class Val>
00494 inline ListOf<Key> AssociationsOf<Key,Val>::keys( ) const
00495 
00496 {
00497   ListOf<Key> result;
00498   AssociationsIterator<Key,Val> I(*this);
00499   while ( !I.done() ) {
00500          result.append( I.key() );
00501          I.next();
00502   }
00503   return result;
00504 }
00505 
00506 #endif

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