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

/magnus/back_end/general/include/QuickAssociations.h

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

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