home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 7 / 07.iso / c / c221 / 6.ddi / MWHC.006 / O2 < prev    next >
Encoding:
Text File  |  1992-06-07  |  8.5 KB  |  309 lines
  1. #ifndef __RWTVHDICT_H__
  2. #define __RWTVHDICT_H__
  3. pragma push_align_members(64);
  4.  
  5. /*
  6.  * RWTValHashDictionary: A parameterized hashing dictionary of keys K and values V.
  7.  *
  8.  * $Header:   E:/vcs/rw/tvhdict.h_v   1.1   04 Mar 1992 10:16:46   KEFFER  $
  9.  *
  10.  ****************************************************************************
  11.  *
  12.  * Rogue Wave Software, Inc.
  13.  * P.O. Box 2328
  14.  * Corvallis, OR 97339
  15.  *
  16.  * Copyright (C) 1992. This software is subject to copyright 
  17.  * protection under the laws of the United States and other countries.
  18.  *
  19.  ***************************************************************************
  20.  *
  21.  * $Log:   E:/vcs/rw/tvhdict.h_v  $
  22.  * 
  23.  *    Rev 1.1   04 Mar 1992 10:16:46   KEFFER
  24.  *  
  25.  * 
  26.  *    Rev 1.0   02 Mar 1992 16:10:54   KEFFER
  27.  * Initial revision.
  28.  */
  29.  
  30. //$DECLARE_TEMPLATE
  31.  
  32. #include "rw/tvsldict.h"
  33. #include "rw/tvvector.h"
  34.  
  35. template <class K, class V> class RWTValHashDictionary {
  36.  
  37.   typedef RWTValSlistDictionary<K,V>        CHAINDICT;
  38.   typedef RWTValSlistDictionaryIterator<K,V>    CHAINDICTITERATOR;
  39.   typedef RWTValVector<CHAINDICT*>        CHAINVEC;
  40.   friend class RWTValHashDictionaryIterator<K,V>;
  41.  
  42. protected:
  43.  
  44.   CHAINVEC        _table;
  45.   unsigned        _nitems;
  46.   unsigned        (*_hashFun)(const K&);    // User-supplied hashing function
  47.  
  48.   int            hashIndex(const K& val) const {return (int)((*_hashFun)(val) % _table.length());}
  49.  
  50. public:
  51.  
  52.   // Constructors:
  53.   RWTValHashDictionary(unsigned (*hashKey)(const K&), unsigned size = RWDEFAULT_CAPACITY);
  54.   RWTValHashDictionary(const RWTValHashDictionary<K,V>&);
  55.   ~RWTValHashDictionary()        {clear();}
  56.  
  57.   // Operators:
  58.   RWTValHashDictionary&        operator=(const RWTValHashDictionary<K,V>&);
  59.   // Look up key, add if not there:
  60.   V&            operator[](K key);
  61.  
  62.   // Member functions:
  63.   void            applyToKeyAndValue(void (*applyFun)(K,V&,void*), void*);
  64.   void            clear();
  65.   RWBoolean        contains(K) const;    // Contain key?
  66.   unsigned        entries() const        {return _nitems;}
  67.   RWBoolean        isEmpty() const        {return _nitems==0;}
  68.   RWBoolean        find(K key, K& retKey) const;        // Returns key in "retKey" if found
  69.   RWBoolean        findValue(K key, V& retVal) const;    // Returns value in "retVal" if found
  70.   RWBoolean        findKeyAndValue(K key, K& retKey, V& retVal) const;
  71.   void            insertKeyAndValue(K key, V value)
  72.                   {(*this)[key] = value;}
  73.   RWBoolean        remove(K);
  74.   void            resize(unsigned);
  75. };
  76.  
  77.  
  78.  
  79. /****************************************************************
  80.  *                                *
  81.  *    Declarations for RWTValHashDictionaryIterator<K,V>    *
  82.  *                                *
  83.  ****************************************************************/
  84.  
  85. template <class K, class V>
  86. class RWTValHashDictionaryIterator {
  87.  
  88.   // For convenience in what follows:
  89.   typedef RWTValHashDictionary<K,V>        HASHDICT;
  90.   typedef RWTValSlistDictionary<K,V>        CHAINDICT;
  91.   typedef RWTValSlistDictionaryIterator<K,V>    CHAINDICTITERATOR;
  92.  
  93.   HASHDICT*        _myHash;
  94.   int            _idx;
  95.   CHAINDICTITERATOR*    _iterator;
  96.  
  97.   void            nextChain();        // Advance to the next chain
  98.  
  99.   // Disallow postfix increment.  Unless we hide it, some compilers will
  100.   // substitute the prefix increment operator in its place.
  101.   RWBoolean        operator++(int);
  102.  
  103. public:
  104.  
  105.   RWTValHashDictionaryIterator(HASHDICT& s);
  106.  
  107.   RWBoolean        operator++();        // Advance and test
  108.   HASHDICT*        container() const    {return _myHash;}
  109.   K            key() const        {return _iterator->key();}
  110.   void            reset();
  111.   void            reset(HASHDICT& s);
  112.   V            value() const        {return _iterator->value();}
  113. };
  114.  
  115. //$IMPLEMENT_TEMPLATE
  116.  
  117. /****************************************************************
  118.  *                                *
  119.  *        Definitions for RWTValHashDictionary<T>        *
  120.  *                                *
  121.  ****************************************************************/
  122.  
  123. template <class K, class V>
  124. RWTValHashDictionary<K,V>::RWTValHashDictionary(unsigned (*hashFun)(const K&), unsigned size) :
  125.   _table(size, rwnil),
  126.   _nitems(0),
  127.   _hashFun(hashFun)
  128. {
  129. }
  130.  
  131. template <class K, class V>
  132. RWTValHashDictionary<K,V>::RWTValHashDictionary(const RWTValHashDictionary<K,V>& v) :
  133.   _table(v._table.length(), rwnil),
  134.   _nitems(v._nitems),
  135.   _hashFun(v._hashFun)
  136. {
  137.   int N = _table.length();
  138.   for (int i=0; i<N; i++){
  139.     if (v._table(i)) _table(i) = new CHAINDICT(*v._table(i));
  140.   }
  141. }
  142.  
  143. template <class K, class V> RWTValHashDictionary<K,V>&
  144. RWTValHashDictionary<K,V>::operator=(const RWTValHashDictionary<K,V>& v)
  145. {
  146.   int N;
  147.   clear();
  148.   _table.reshape(N=v._table.length());
  149.   _hashFun = v._hashFun;
  150.   for (int i=0; i<N; i++){
  151.     if (v._table(i)) _table(i) = new CHAINDICT(*v._table(i));
  152.   }
  153.   _nitems = v._nitems;
  154.   return *this;
  155. }
  156.  
  157. template <class K, class V> V&
  158. RWTValHashDictionary<K,V>::operator[](K key)
  159. {
  160.   int idx = hashIndex(key);
  161.   CHAINDICT* chain = _table(idx);
  162.   if (chain==rwnil) _table(idx) = chain = new CHAINDICT;
  163.   unsigned N = chain->entries();
  164.   V& val = chain->operator[](key);
  165.   if (N!=chain->entries()) _nitems++;    // Ugly, I know.
  166.   return val;
  167. }
  168.  
  169. template <class K, class V> void
  170. RWTValHashDictionary<K,V>::applyToKeyAndValue(void (*applyFun)(K,V&,void*), void* a)
  171. {
  172.   int N = (int)_table.length();
  173.   for (int i=0; i<N; i++) {
  174.     if (_table(i)) _table(i)->applyToKeyAndValue(applyFun, a);
  175.   }
  176. }
  177.  
  178. template <class K, class V> void
  179. RWTValHashDictionary<K,V>::clear()
  180. {
  181.   int i = _table.length();
  182.   while (i--) { delete _table(i); _table(i) = rwnil; }
  183.  
  184.   _nitems = 0;
  185. }
  186.  
  187. template <class K, class V> RWBoolean
  188. RWTValHashDictionary<K,V>::contains(K key) const
  189. {
  190.   CHAINDICT* chain = _table(hashIndex(key));
  191.   return chain ? chain->contains(key) : FALSE;
  192. }
  193.  
  194. // Returns TRUE if the key is in the collection.  Puts the found
  195. // key in retKey.
  196. template <class K, class V> RWBoolean
  197. RWTValHashDictionary<K,V>::find(K key, K& retKey) const
  198. {
  199.   CHAINDICT* chain = _table(hashIndex(key));
  200.   return chain ? chain->find(key, retKey) : FALSE;
  201. }
  202.  
  203. template <class K, class V> RWBoolean
  204. RWTValHashDictionary<K,V>::findValue(K key, V& retVal) const
  205. {
  206.   CHAINDICT* chain = _table(hashIndex(key));
  207.   return chain ? chain->findValue(key, retVal) : FALSE;
  208. }
  209.  
  210. template <class K, class V> RWBoolean
  211. RWTValHashDictionary<K,V>::findKeyAndValue(K key, K& retKey, V& retVal) const
  212. {
  213.   CHAINDICT* chain = _table(hashIndex(key));
  214.   return chain ? chain->findKeyAndValue(key, retKey, retVal) : FALSE;
  215. }
  216.  
  217. template <class K, class V> RWBoolean
  218. RWTValHashDictionary<K,V>::remove(K key)
  219. {
  220.   CHAINDICT* chain = _table(hashIndex(key));
  221.   if (chain) {
  222.     if (chain->remove(key)) {_nitems--; return TRUE;}
  223.   }
  224.   return FALSE;
  225. }
  226.  
  227. template <class K, class V> void
  228. RWTValHashDictionary<K,V>::resize(unsigned N)
  229. {
  230. #ifdef RWDEBUG
  231.   unsigned oldNitems = _nitems;
  232. #endif
  233.   CHAINVEC tempTable =_table;    // Save old values
  234.   _table.reshape(N);        // Resize internal table
  235.   _table  = rwnil;        // Zero it
  236.   _nitems = 0;
  237.  
  238.   // Now iterate through the old collection, inserting each item
  239.   for (int i=0; i<tempTable.length(); i++){
  240.     if (tempTable(i)) {
  241.       CHAINDICTITERATOR next(*tempTable(i));
  242.       while ( ++next ) insertKeyAndValue(next.key(), next.value());
  243.       delete tempTable(i);
  244.     }
  245.   }
  246. #ifdef RWDEBUG
  247.   assert(_nitems==oldNitems);    // Make sure we got 'em all.
  248. #endif
  249. }
  250.  
  251.  
  252.  
  253. /****************************************************************
  254.  *                                *
  255.  *    Definitions for RWTValHashDictionaryIterator<T>        *
  256.  *                                *
  257.  ****************************************************************/
  258.  
  259. template <class K, class V>
  260. RWTValHashDictionaryIterator<K,V>::RWTValHashDictionaryIterator(RWTValHashDictionary<K,V>& d) :
  261.   _myHash(&d),
  262.   _idx(-1),
  263.   _iterator(rwnil)
  264. {
  265.   nextChain();    // Advance to the first chain
  266. }
  267.  
  268. template <class K, class V> RWBoolean
  269. RWTValHashDictionaryIterator<K,V>::operator++()
  270. {
  271.   while (_iterator && ++(*_iterator)==FALSE){
  272.     nextChain();
  273.   }
  274.   return _iterator!=rwnil;
  275. }
  276.  
  277. template <class K, class V> void
  278. RWTValHashDictionaryIterator<K,V>::reset()
  279. {
  280.   _idx = -1;
  281.   nextChain();
  282. }
  283.  
  284. template <class K, class V> void
  285. RWTValHashDictionaryIterator<K,V>::reset(RWTValHashDictionary<K,V>& t)
  286. {
  287.   _myHash = &t;
  288.   _idx = -1;
  289.   nextChain();
  290. }
  291.  
  292. // Advance the iterator to work on the next chain.
  293. template <class K, class V> void
  294. RWTValHashDictionaryIterator<K,V>::nextChain()
  295. {
  296.   while (++_idx < _myHash->_table.length()) {
  297.     if (_myHash->_table(_idx)) {
  298.       if (_iterator) _iterator->reset(*_myHash->_table(_idx));
  299.       else           _iterator = new CHAINDICTITERATOR(*_myHash->_table(_idx));
  300.       return;
  301.     }
  302.   }
  303.   delete _iterator;
  304.   _iterator = rwnil;
  305. }
  306.  
  307. pragma pop_align_members();
  308. #endif    /* __RWTVDICT_H__ */
  309.