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