home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 7 / 07.iso / c / c081_11 / 1.ddi / CLASSINC.ZIP / HASHTBL.H < prev    next >
Encoding:
C/C++ Source or Header  |  1991-02-13  |  7.1 KB  |  314 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.  
  58. // Class //
  59.  
  60. class HashTable:  public Collection
  61. {
  62. public:
  63.             HashTable( sizeType = DEFAULT_HASH_TABLE_SIZE );
  64.     virtual ~HashTable();
  65.  
  66.     virtual void            add( Object& );
  67.     virtual void            detach( const Object&, int = 0 );
  68.  
  69.     virtual ContainerIterator& initIterator() const;
  70.     virtual Object&         findMember( const Object& ) const;
  71.  
  72.     virtual classType       isA() const;
  73.     virtual char           *nameOf() const;
  74.     virtual hashValueType   hashValue() const;
  75.  
  76. private:
  77.             hashValueType   getHashValue( const Object& ) const;
  78.             sizeType        size;
  79.             Array           table;
  80. };
  81.  
  82. // Description -------------------------------------------------------------
  83. //
  84. //         Defines the class HashTable. 
  85. //      
  86. // Constructors
  87. //
  88. //      HashTable( sizeType )
  89. //
  90. //      Constructs a hash table of the given size.
  91. //
  92. // Destructors
  93. //
  94. //      ~HashTable()
  95. //
  96. //      We provide the destructor for the sole purpose of forcing a call
  97. //      to the destructor for the private member objects of the class.
  98. //
  99. // Public Members
  100. //
  101. //
  102. //         initIterator
  103. //
  104. //         Initializes an iterator for a hash table.
  105. //
  106. //      add
  107. //
  108. //      Adds an object to the hash table.
  109. //
  110. //      destroy
  111. //
  112. //      Removes an object reference from the hash table and
  113. //      destroys the object.
  114. //
  115. //         detach
  116. //
  117. //         Removes all references to the object in the hash table.
  118. //      Does not delete the object.  Use this function when the hash table
  119. //      elements are not owned by the hash table.
  120. //
  121. //         findMember
  122. //
  123. //         Returns a reference to the object which is associated with the
  124. //         given key.
  125. //
  126. //         hashValue
  127. //
  128. //         Returns a pre-defined value for a hash table.
  129. //
  130. //         isA
  131. //
  132. //         Returns the class type of class HashTable.
  133. //
  134. //         nameOf
  135. //
  136. //         Returns a pointer to the character string "HashTable."
  137. //     
  138. // Inherited Members
  139. //
  140. //      hasMember
  141. //
  142. //         Inherited from Collection.
  143. //
  144. //         isEmpty
  145. //
  146. //         Inherited from Container.
  147. //
  148. //      firstThat
  149. //
  150. //         Inherited from Container.
  151. //
  152. //      lastThat
  153. //
  154. //         Inherited from Container.
  155. //
  156. //         printOn
  157. //
  158. //         Inherited from Container.
  159. //
  160. // Protected Members
  161. //
  162. //         itemsInCollection
  163. //
  164. //         Inherited from Container.
  165. //
  166. // Private Members
  167. //
  168. //      getHashValue
  169. //
  170. //      Private member function to return the hash value of an object.
  171. //
  172. //      size
  173. //
  174. //      Container for the size of the hash table.
  175. //
  176. //      table
  177. //
  178. //      An array of lists which implements the hash table.
  179. //
  180. // End ---------------------------------------------------------------------
  181.  
  182.  
  183. // Constructor //
  184.  
  185. inline HashTable::HashTable( sizeType aPrime ) : size( aPrime ), table( aPrime )
  186.  
  187. // Summary -----------------------------------------------------------------
  188. //
  189. //      Construct a hash table of the given size.
  190. //
  191. // Parameters
  192. //
  193. //      aPrime
  194. //
  195. //      The size of the hash table.  To make the hashing algorithm work
  196. //      efficiently, you should make this a prime number.
  197. //
  198. // Functional Description
  199. //
  200. //      We store the passed size and create an array object of that size.
  201. //
  202. // End ---------------------------------------------------------------------
  203. {
  204. }
  205. // End Constructor //
  206.  
  207.  
  208. // Member Function //
  209.  
  210. inline sizeType HashTable::getHashValue( const Object& ofObject ) const
  211.  
  212. // Summary -----------------------------------------------------------------
  213. //
  214. //      Returns the hash value of the given object.
  215. //
  216. // Parameters
  217. //
  218. //      ofObject
  219. //
  220. //      The object we are to hash.
  221. //
  222. // Functional Description
  223. //
  224. //      We ask the object to hash itself, then modulo that value by the
  225. //      size of our hash table.
  226. //
  227. // End ---------------------------------------------------------------------
  228. {
  229.     return ofObject.hashValue() % size;
  230. }
  231. // End Member Function //
  232.  
  233.  
  234. // Class //
  235.  
  236. class HashTableIterator:  public ContainerIterator
  237. {
  238. public:
  239.             HashTableIterator( const Array& );
  240.  
  241.     virtual                operator int();
  242.     virtual    Object&        operator ++();
  243.     virtual             operator Object&();
  244.     virtual    void        restart();
  245.  
  246. private:
  247.             int         preIterate();
  248.             ArrayIterator *indexIterator;
  249.             ListIterator  *listIterator;
  250.     const   Array&      beingIterated;
  251. };
  252.  
  253. // Description -------------------------------------------------------------
  254. //
  255. //         Defines the hash table iterator class.  Upon initialization, we set up
  256. //         an internal pointer to our current position in the hash table.  As
  257. //      the increment operator is called, we update this current position.
  258. //
  259. // Constructor
  260. //
  261. //      HashTableIterator( const Array& )
  262. //
  263. //         Constructor for an iterator.  Note that this isn't a copy
  264. //         constructor, since it takes an object from a different class.
  265. //
  266. // Destructor
  267. //
  268. //         ~HashTableIterator
  269. //
  270. // Public Members
  271. //
  272. //         operator int
  273. //
  274. //         We are allowed one cast operator to a predefined type.  This
  275. //         operator defines an explicit or an implicit cast from a
  276. //         HashTableIterator to an integer.
  277. //
  278. //      operator Object&
  279. //
  280. //      Conversion operator from HashTableIterator to Object.
  281. //
  282. //         operator ++
  283. //
  284. //      The increment operator.
  285. //
  286. //         restart
  287. //
  288. //         Restarts an hash table iterator.
  289. //
  290. // Private Members
  291. //
  292. //      preIterate
  293. //
  294. //      Begins a step in the iteration.
  295. //
  296. //         indexIterator
  297. //
  298. //         Maintains the position information in the array for this iterator.
  299. //
  300. //         listIterator
  301. //
  302. //         Maintains the position information in the lists of the array 
  303. //      for this iterator.
  304. //
  305. //      beingIterated
  306. //
  307. //      A reference to the array hash table which is being iterated.  Used
  308. //      when restarting the iteration.
  309. //
  310. // End ---------------------------------------------------------------------
  311.  
  312.  
  313. #endif // ifndef __HASHTBL_H //
  314.