home *** CD-ROM | disk | FTP | other *** search
/ Piper's Pit BBS/FTP: ibm 0040 - 0049 / ibm0040-0049 / ibm0040.tar / ibm0040 / BCPPOWL1.ZIP / CLINC.ZIP / HASHTBL.H < prev    next >
Encoding:
C/C++ Source or Header  |  1991-08-28  |  7.1 KB  |  317 lines
  1. // Borland C++ - (C) Copyright 1991 by Borland International
  2.  
  3. // Contents ----------------------------------------------------------------
  4. //
  5. //      HashTable
  6. //      HashTable::HashTable
  7. //      HashTable::getHashValue
  8. //
  9. // Description
  10. //
  11. //      Defines the abstract class HashTable and associated inline
  12. //         functions.  A hash table is a "container-container," that is,
  13. //         it contains a number of container objects.
  14. //
  15. // End ---------------------------------------------------------------------
  16.  
  17. // Interface Dependencies ---------------------------------------------------
  18.  
  19. #ifndef __HASHTBL_H
  20. #define __HASHTBL_H
  21.  
  22. #ifndef __IOSTREAM_H
  23. #include <iostream.h>
  24. #define __IOSTREAM_H
  25. #endif
  26.  
  27. #ifndef __CLSTYPES_H
  28. #include <clstypes.h>
  29. #endif
  30.  
  31. #ifndef __RESOURCE_H
  32. #include <resource.h>
  33. #endif
  34.  
  35. #ifndef __OBJECT_H
  36. #include <object.h>
  37. #endif
  38.  
  39. #ifndef __CONTAIN_H
  40. #include <contain.h>
  41. #endif
  42.  
  43. #ifndef __COLLECT_H
  44. #include <collect.h>
  45. #endif
  46.  
  47. #ifndef __LIST_H
  48. #include <list.h>
  49. #endif
  50.  
  51. #ifndef __ARRAY_H
  52. #include <array.h>
  53. #endif
  54.  
  55. // End Interface Dependencies ------------------------------------------------
  56.  
  57. _CLASSDEF(HashTable)
  58. _CLASSDEF(HashTableIterator)
  59.  
  60. // Class //
  61.  
  62. class _CLASSTYPE HashTable:  public Collection
  63. {
  64. public:
  65.             HashTable( sizeType = DEFAULT_HASH_TABLE_SIZE );
  66.     virtual ~HashTable();
  67.  
  68.     virtual void        add( RObject );
  69.     virtual void            detach( RCObject, int = 0 );
  70.  
  71.     virtual RContainerIterator initIterator() const;
  72.     virtual RObject   findMember( RCObject ) const;
  73.  
  74.     virtual classType       isA() const;
  75.     virtual Pchar nameOf() const;
  76.     virtual hashValueType   hashValue() const;
  77.  
  78. private:
  79.     hashValueType   getHashValue( RCObject ) const;
  80.             sizeType        size;
  81.             Array           table;
  82. };
  83.  
  84. // Description -------------------------------------------------------------
  85. //
  86. //         Defines the class HashTable. 
  87. //      
  88. // Constructors
  89. //
  90. //      HashTable( sizeType )
  91. //
  92. //      Constructs a hash table of the given size.
  93. //
  94. // Destructors
  95. //
  96. //      ~HashTable()
  97. //
  98. //      We provide the destructor for the sole purpose of forcing a call
  99. //      to the destructor for the private member objects of the class.
  100. //
  101. // Public Members
  102. //
  103. //
  104. //         initIterator
  105. //
  106. //         Initializes an iterator for a hash table.
  107. //
  108. //      add
  109. //
  110. //      Adds an object to the hash table.
  111. //
  112. //      destroy
  113. //
  114. //      Removes an object reference from the hash table and
  115. //      destroys the object.
  116. //
  117. //         detach
  118. //
  119. //         Removes all references to the object in the hash table.
  120. //      Does not delete the object.  Use this function when the hash table
  121. //      elements are not owned by the hash table.
  122. //
  123. //         findMember
  124. //
  125. //         Returns a reference to the object which is associated with the
  126. //         given key.
  127. //
  128. //         hashValue
  129. //
  130. //         Returns a pre-defined value for a hash table.
  131. //
  132. //         isA
  133. //
  134. //         Returns the class type of class HashTable.
  135. //
  136. //         nameOf
  137. //
  138. //         Returns a pointer to the character string "HashTable."
  139. //     
  140. // Inherited Members
  141. //
  142. //      hasMember
  143. //
  144. //         Inherited from Collection.
  145. //
  146. //         isEmpty
  147. //
  148. //         Inherited from Container.
  149. //
  150. //      firstThat
  151. //
  152. //         Inherited from Container.
  153. //
  154. //      lastThat
  155. //
  156. //         Inherited from Container.
  157. //
  158. //         printOn
  159. //
  160. //         Inherited from Container.
  161. //
  162. // Protected Members
  163. //
  164. //         itemsInCollection
  165. //
  166. //         Inherited from Container.
  167. //
  168. // Private Members
  169. //
  170. //      getHashValue
  171. //
  172. //      Private member function to return the hash value of an object.
  173. //
  174. //      size
  175. //
  176. //      Container for the size of the hash table.
  177. //
  178. //      table
  179. //
  180. //      An array of lists which implements the hash table.
  181. //
  182. // End ---------------------------------------------------------------------
  183.  
  184.  
  185. // Constructor //
  186.  
  187. inline HashTable::HashTable( sizeType aPrime ) : size( aPrime ), table( aPrime )
  188.  
  189. // Summary -----------------------------------------------------------------
  190. //
  191. //      Construct a hash table of the given size.
  192. //
  193. // Parameters
  194. //
  195. //      aPrime
  196. //
  197. //      The size of the hash table.  To make the hashing algorithm work
  198. //      efficiently, you should make this a prime number.
  199. //
  200. // Functional Description
  201. //
  202. //      We store the passed size and create an array object of that size.
  203. //
  204. // End ---------------------------------------------------------------------
  205. {
  206. }
  207. // End Constructor //
  208.  
  209.  
  210. // Member Function //
  211.  
  212. inline sizeType HashTable::getHashValue( RCObject ofObject ) const
  213.  
  214. // Summary -----------------------------------------------------------------
  215. //
  216. //      Returns the hash value of the given object.
  217. //
  218. // Parameters
  219. //
  220. //      ofObject
  221. //
  222. //      The object we are to hash.
  223. //
  224. // Functional Description
  225. //
  226. //      We ask the object to hash itself, then modulo that value by the
  227. //      size of our hash table.
  228. //
  229. // End ---------------------------------------------------------------------
  230. {
  231.     return ofObject.hashValue() % size;
  232. }
  233. // End Member Function //
  234.  
  235.  
  236. // Class //
  237.  
  238. class _CLASSTYPE HashTableIterator:  public ContainerIterator
  239. {
  240. public:
  241.     HashTableIterator( RCArray );
  242.     virtual ~HashTableIterator();
  243.     
  244.     virtual            operator int();
  245.     virtual    RObject    operator ++();
  246.     virtual             operator RObject();
  247.     virtual    void        restart();
  248.  
  249. private:
  250.     int         preIterate();
  251.     PArrayIterator indexIterator;
  252.     PListIterator listIterator;
  253.     RCArray beingIterated;
  254. };
  255.  
  256. // Description -------------------------------------------------------------
  257. //
  258. //         Defines the hash table iterator class.  Upon initialization, we set up
  259. //         an internal pointer to our current position in the hash table.  As
  260. //      the increment operator is called, we update this current position.
  261. //
  262. // Constructor
  263. //
  264. //      HashTableIterator( RCArray )
  265. //
  266. //         Constructor for an iterator.  Note that this isn't a copy
  267. //         constructor, since it takes an object from a different class.
  268. //
  269. // Destructor
  270. //
  271. //         ~HashTableIterator
  272. //
  273. // Public Members
  274. //
  275. //         operator int
  276. //
  277. //         We are allowed one cast operator to a predefined type.  This
  278. //         operator defines an explicit or an implicit cast from a
  279. //         HashTableIterator to an integer.
  280. //
  281. //      operator Object&
  282. //
  283. //      Conversion operator from HashTableIterator to Object.
  284. //
  285. //         operator ++
  286. //
  287. //      The increment operator.
  288. //
  289. //         restart
  290. //
  291. //         Restarts an hash table iterator.
  292. //
  293. // Private Members
  294. //
  295. //      preIterate
  296. //
  297. //      Begins a step in the iteration.
  298. //
  299. //         indexIterator
  300. //
  301. //         Maintains the position information in the array for this iterator.
  302. //
  303. //         listIterator
  304. //
  305. //         Maintains the position information in the lists of the array 
  306. //      for this iterator.
  307. //
  308. //      beingIterated
  309. //
  310. //      A reference to the array hash table which is being iterated.  Used
  311. //      when restarting the iteration.
  312. //
  313. // End ---------------------------------------------------------------------
  314.  
  315.  
  316. #endif // ifndef __HASHTBL_H //
  317.