home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 7 / 07.iso / c / c221 / 6.ddi / MWHC.006 / N2 < prev    next >
Encoding:
Text File  |  1992-06-07  |  8.1 KB  |  321 lines
  1. #ifndef __RWTVHASHT_H__
  2. #define __RWTVHASHT_H__
  3. pragma push_align_members(64);
  4.  
  5. /*
  6.  * RWTValHashTable<T>:  A Bag of values T, implemented using a hashed lookup
  7.  *
  8.  * $Header:   E:/vcs/rw/tvhasht.h_v   1.2   17 Mar 1992 11:31:38   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.  * This class implements a parameterized hash table of types T.
  22.  * It uses chaining to resolve hash collisions.
  23.  *
  24.  * Example use of this class:
  25.  *
  26.  *   #include <rw/cstring.h>
  27.  *   #include <rw/tvhasht.h>
  28.  *   
  29.  *   unsigned myHash(const RWCString& s){ return s.hash(); }
  30.  *   
  31.  *   RWTValHashTable<RWCString> bag(myHash);    // A bag of RWCStrings
  32.  *   
  33.  *   bag.insert("a string");    // Type conversion: char* to RWCString happens
  34.  *   bag.insert("another string");
  35.  *   bag.contains("a string");    // Returns true.
  36.  *
  37.  *
  38.  * Note that the constructor for RWTValHashTable<T> takes a function with
  39.  * prototype
  40.  *
  41.  *   unsigned hashFun(const T&);
  42.  *
  43.  * It should return a suitable hashing value for an instance of class T.
  44.  * Usually, the definition for such a function is trivial because hashing
  45.  * functions have been defined for all Rogue Wave supplied classes.
  46.  *
  47.  ***************************************************************************
  48.  *
  49.  * $Log:   E:/vcs/rw/tvhasht.h_v  $
  50.  * 
  51.  *    Rev 1.2   17 Mar 1992 11:31:38   KEFFER
  52.  * 
  53.  *    Rev 1.1   04 Mar 1992 10:22:04   KEFFER
  54.  * 
  55.  *    Rev 1.0   02 Mar 1992 16:10:52   KEFFER
  56.  * Initial revision.
  57.  */
  58.  
  59. //$DECLARE_TEMPLATE
  60.  
  61. #include "rw/tvslist.h"
  62. #include "rw/tvvector.h"
  63.  
  64. /****************************************************************
  65.  *                                *
  66.  *        Declarations for RWTValHashTable<T>        *
  67.  *                                *
  68.  ****************************************************************/
  69.  
  70. template <class T> class RWTValHashTable {
  71.  
  72. protected:
  73.  
  74.   typedef RWTValSlist<T>        CHAIN;
  75.   typedef RWTValVector<CHAIN*>        CHAINVEC;
  76.   typedef RWTValSlistIterator<T>    CHAINITERATOR;
  77.   friend class RWTValHashTableIterator<T>;
  78.  
  79.   CHAINVEC        _table;
  80.   unsigned        _nitems;
  81.   unsigned        (*_hashFun)(const T&);    // User-supplied hashing function
  82.  
  83.   int            hashIndex(const T& val) const {return (int)((*_hashFun)(val) % _table.length());}
  84.  
  85. public:
  86.  
  87.   RWTValHashTable(unsigned (*hashFun)(const T&), unsigned size = RWDEFAULT_CAPACITY);
  88.   RWTValHashTable(const RWTValHashTable<T>&);
  89.   ~RWTValHashTable()        {clear();}
  90.  
  91.   RWTValHashTable&        operator=(const RWTValHashTable<T>&);
  92.  
  93.   // Member functions:
  94.   void            apply(void (*applyFun)(T, void*), void*);
  95.   void            clear();
  96.   RWBoolean        contains(T val) const;
  97.   unsigned        entries() const        {return _nitems;}
  98.   RWBoolean        find(T a, T& k) const;    // Find first occurrence
  99.   void            insert(T val);
  100.   RWBoolean        isEmpty() const        {return _nitems==0;}
  101.   unsigned        occurrencesOf(T val) const;
  102.   RWBoolean        remove(T val);
  103.   unsigned        removeAll(T val);
  104.   void            resize(unsigned);
  105.  
  106. };
  107.  
  108.  
  109. /****************************************************************
  110.  *                                *
  111.  *        Declarations for RWTValHashTableIterator<T>    *
  112.  *                                *
  113.  ****************************************************************/
  114.  
  115. template <class T> class RWTValHashTableIterator {
  116.  
  117.   typedef RWTValSlist<T>        CHAIN;
  118.   typedef RWTValSlistIterator<T>    CHAINITERATOR;
  119.   typedef RWTValHashTable<T>        HASHTABLE;
  120.  
  121.   HASHTABLE*        _myHash;
  122.   int            _idx;
  123.   CHAINITERATOR*    _iterator;
  124.  
  125.   void            nextIterator();
  126.  
  127. public:
  128.  
  129.   RWTValHashTableIterator(HASHTABLE& t);
  130.  
  131.   RWBoolean        operator++();        // Advance and test
  132.   HASHTABLE*        container() const    {return _myHash;}
  133.   T            key() const        {return _iterator->key();}
  134.   void            reset();
  135.   void            reset(HASHTABLE& t);
  136. };
  137.  
  138.  
  139.  
  140. //$IMPLEMENT_TEMPLATE
  141.  
  142. /****************************************************************
  143.  *                                *
  144.  *        Definitions for RWTValHashTable<T>        *
  145.  *                                *
  146.  ****************************************************************/
  147.  
  148. template <class T>
  149. RWTValHashTable<T>::RWTValHashTable(unsigned (*hashFun)(const T&), unsigned size) :
  150.   _table(size, rwnil),
  151.   _nitems(0),
  152.   _hashFun(hashFun)
  153. {
  154. }
  155.  
  156. template <class T>
  157. RWTValHashTable<T>::RWTValHashTable(const RWTValHashTable<T>& v) :
  158.   _table(v._table.length(), rwnil),
  159.   _nitems(v._nitems),
  160.   _hashFun(v._hashFun)
  161. {
  162.   int N = _table.length();
  163.   for (int i=0; i<N; i++){
  164.     if (v._table(i)) _table(i) = new CHAIN(*v._table(i));
  165.   }
  166. }
  167.  
  168. template <class T> RWTValHashTable<T>&
  169. RWTValHashTable<T>::operator=(const RWTValHashTable<T>& v)
  170. {
  171.   int N;
  172.   clear();
  173.   _table.reshape(N=v._table.length());
  174.   _hashFun = v._hashFun;
  175.   for (int i=0; i<N; i++){
  176.     _table(i) = v._table(i) ? new CHAIN(*v._table(i)) : rwnil;
  177.   }
  178.   _nitems = v._nitems;
  179.   return *this;
  180. }
  181.  
  182. template <class T> void
  183. RWTValHashTable<T>::apply(void (*applyFun)(T, void*), void* a)
  184. {
  185.   int N = _table.length();
  186.   for (int i=0; i<N; i++) {
  187.     if (_table(i)) _table(i)->apply(applyFun,a);
  188.   }
  189. }
  190.  
  191. template <class T> void
  192. RWTValHashTable<T>::clear()
  193. {
  194.   int i = _table.length();
  195.   while (i--) { delete _table(i); _table(i) = rwnil; }
  196.  
  197.   _nitems = 0;
  198. }
  199.  
  200. template <class T> RWBoolean
  201. RWTValHashTable<T>::contains(T val) const
  202. {
  203.   CHAIN* p = _table(hashIndex(val));
  204.   return p ? p->contains(val) : FALSE;
  205. }
  206.  
  207. template <class T> RWBoolean
  208. RWTValHashTable<T>::find(T val, T& retVal) const
  209. {
  210.   CHAIN* p = _table(hashIndex(val));
  211.   return  p ? p->find(val, retVal) : FALSE;
  212. }
  213.  
  214. template <class T> void
  215. RWTValHashTable<T>::insert(T val)
  216. {
  217.   int idx = (int)hashIndex(val);
  218.   if (_table(idx)==rwnil) _table(idx) = new CHAIN;
  219.   _table(idx)->insert(val);
  220.   _nitems++;
  221. }
  222.  
  223. template <class T> unsigned
  224. RWTValHashTable<T>::occurrencesOf(T val) const
  225. {
  226.   CHAIN* p = _table(hashIndex(val));
  227.   return  p ? p->occurrencesOf(val) : 0;
  228. }
  229.  
  230. template <class T> RWBoolean
  231. RWTValHashTable<T>::remove(T val)
  232. {
  233.   CHAIN* p = _table(hashIndex(val));
  234.   RWBoolean ret = p ? p->remove(val) : FALSE;
  235.   if (ret) _nitems--;
  236.   return ret;
  237. }
  238.  
  239. template <class T> unsigned
  240. RWTValHashTable<T>::removeAll(T val)
  241. {
  242.   CHAIN* p = _table(hashIndex(val));
  243.   unsigned count = p ? p->removeAll(val) : 0;
  244.   _nitems -= count;
  245.   return count;
  246. }
  247.  
  248. template <class T> void
  249. RWTValHashTable<T>::resize(unsigned N)
  250. {
  251.   CHAINVEC tempTable =_table;    // Save old values
  252.   _table.reshape(N);        // Resize internal table
  253.   _table  = rwnil;        // Zero it
  254.   _nitems = 0;
  255.  
  256.   // Now iterate through the old collection, inserting each item
  257.   for (int i=0; i<tempTable.length(); i++){
  258.     if (tempTable(i)) {
  259.       CHAINITERATOR next(*tempTable(i));
  260.       while ( ++next ) insert(next.key());
  261.       delete tempTable(i);
  262.     }
  263.   }
  264. }
  265.  
  266. /****************************************************************
  267.  *                                *
  268.  *        Definitions for RWTValHashTableIterator<T>    *
  269.  *                                *
  270.  ****************************************************************/
  271.  
  272. template <class T>
  273. RWTValHashTableIterator<T>::RWTValHashTableIterator(RWTValHashTable<T>& t) :
  274.   _myHash(&t),
  275.   _idx(-1),
  276.   _iterator(rwnil)
  277. {
  278.   nextIterator();    // Advance to the next iterator
  279. }
  280.  
  281. template <class T> RWBoolean
  282. RWTValHashTableIterator<T>::operator++()
  283. {
  284.   while ( _iterator && ++(*_iterator)==FALSE ) {
  285.     nextIterator();
  286.   }
  287.   return _iterator!=rwnil;
  288. }
  289.  
  290. template <class T> void
  291. RWTValHashTableIterator<T>::reset()
  292. {
  293.   _idx = -1;
  294.   nextIterator();
  295. }
  296.  
  297. template <class T> void
  298. RWTValHashTableIterator<T>::reset(RWTValHashTable<T>& t)
  299. {
  300.   _myHash = &t;
  301.   _idx = -1;
  302.   nextIterator();
  303. }
  304.  
  305. template <class T> void
  306. RWTValHashTableIterator<T>::nextIterator()
  307. {
  308.   while (++_idx < _myHash->_table.length()) {
  309.     if (_myHash->_table(_idx)) {
  310.       if (_iterator) _iterator->reset(*_myHash->_table(_idx));
  311.       else           _iterator = new CHAINITERATOR(*_myHash->_table(_idx));
  312.       return;
  313.     }
  314.   }
  315.   delete _iterator;
  316.   _iterator = rwnil;
  317. }
  318.  
  319. pragma pop_align_members();
  320. #endif    /* __RWTVHASHT_H__ */
  321.