home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 7 / 07.iso / c / c081_11 / 11.ddi / CLASSSRC.ZIP / HASHTBL.CPP < prev    next >
Encoding:
C/C++ Source or Header  |  1991-02-13  |  10.3 KB  |  394 lines
  1. // Borland C++ - (C) Copyright 1991 by Borland International
  2.  
  3.  
  4. // Contents ----------------------------------------------------------------
  5. //
  6. //         HashTable::isA
  7. //         HashTable::nameOf
  8. //         HashTable::add
  9. //         HashTable::detach
  10. //         HashTable::hashValue
  11. //         HashTable::findMember
  12. //         HashTable::initIterator
  13. //
  14. //      HashTableIterator::HashTableIterator            constructor
  15. //      HashTableIterator::operator ++
  16. //      HashTableIteartor::preIterate
  17. //      HashTableIterator::operator int
  18. //      HashTableIterator::restart
  19. //
  20. // Description
  21. //
  22. //      Class HashTable member functions.
  23. //
  24. // End ---------------------------------------------------------------------
  25.  
  26. // Interface Dependencies ---------------------------------------------------
  27.  
  28. #ifndef __IOSTREAM_H
  29. #include <iostream.h>
  30. #define __IOSTREAM_H
  31. #endif
  32.  
  33. #ifndef __CLSTYPES_H
  34. #include <clstypes.h>
  35. #endif
  36.  
  37. #ifndef __OBJECT_H
  38. #include <object.h>
  39. #endif
  40.  
  41. #ifndef __CONTAIN_H
  42. #include <contain.h>
  43. #endif
  44.  
  45. #ifndef __HASHTBL_H
  46. #include <hashtbl.h>
  47. #endif
  48.  
  49. // End Interface Dependencies ------------------------------------------------
  50.  
  51.  
  52. // Interface Dependencies ---------------------------------------------------
  53.  
  54. #ifndef __LIST_H
  55. #include <list.h>
  56. #endif
  57.  
  58. // End Interface Dependencies ------------------------------------------------
  59.  
  60.  
  61. // Member Function //
  62.  
  63. HashTable::~HashTable()
  64.  
  65. // Summary -----------------------------------------------------------------
  66. //
  67. //      Destructor for a HashTable object.
  68. //
  69. //        We don't do anything here, because the destructor for Array
  70. //        will take care of destroying the contained objects.
  71. //
  72. // End ---------------------------------------------------------------------
  73. {
  74. }
  75. // End Destructor //
  76.  
  77.  
  78. // Member Function //
  79.  
  80. classType HashTable::isA() const
  81.  
  82. // Summary -----------------------------------------------------------------
  83. //
  84. //         Returns the class type of an hash table.
  85. //
  86. // End ---------------------------------------------------------------------
  87. {
  88.     return hashTableClass; 
  89. }
  90. // End Member Function HashTable::isA //
  91.  
  92.  
  93. // Member Function //
  94.  
  95. char *HashTable::nameOf() const
  96.  
  97. // Summary -----------------------------------------------------------------
  98. //
  99. //         Returns a pointer to the character string "HashTable."
  100. //
  101. // End ---------------------------------------------------------------------
  102. {
  103.     return "HashTable";
  104. }
  105. // End Member Function HashTable::nameOf //
  106.  
  107.  
  108. // Member Function //
  109.  
  110. void HashTable::add( Object& objectToAdd )
  111.  
  112. // Summary -----------------------------------------------------------------
  113. //
  114. //         Adds an element to a hash table.
  115. //
  116. // Parameters
  117. //
  118. //      objectToAdd
  119. //
  120. //         The object we are to put in the hash table.
  121. //
  122. // End ---------------------------------------------------------------------
  123. {
  124.  
  125.     hashValueType index = getHashValue( objectToAdd );
  126.  
  127. // Body Comment
  128. //
  129. //      Check to see if there is any List object at the given index.
  130. //      If there isn't an object already there, then we use the
  131. //      table's addAt() function to put a new List object there.
  132. //      If there is a List object already there, then we can use its member
  133. //      functions (note that it would be a run-time error to use the member
  134. //      functions of theErrorObject) to add our object to the list.
  135. //
  136. // EndComment
  137.  
  138.     if( table[ index ] == NOOBJECT )
  139.     {
  140.         table.addAt( *(new List), index );
  141.     }
  142.  
  143.     ((List&)table[ index ]).add( objectToAdd );
  144.  
  145. }
  146. // End Member Function HashTable::add //
  147.  
  148.  
  149. // Member Function //
  150.  
  151. void HashTable::detach( const Object& objectToDetach, int deleteObjectToo )
  152.  
  153. // Summary -----------------------------------------------------------------
  154. //
  155. //         Detaches an element in a hash table.
  156. //
  157. // Parameters
  158. //
  159. //         objectToDetach
  160. //
  161. //         The object we are to detach from the hash table.
  162. //
  163. //         deleteObjectToo
  164. //
  165. //         Indicates whether we are to call the object's destructor
  166. //
  167. // Functional Description
  168. //
  169. //         If there is a list of objects at the given hash table entry,
  170. //         detach our object in the list.
  171. //
  172. // End ---------------------------------------------------------------------
  173. {
  174.  
  175.     hashValueType index = getHashValue( objectToDetach );
  176.  
  177.     if( table[ index ] != NOOBJECT )
  178.     {
  179.         ((List&)table[ index ]).detach( objectToDetach, deleteObjectToo );
  180.     }
  181.  
  182. }
  183. // End Member Function HashTable::detach //
  184.  
  185.  
  186. // Member Function //
  187.  
  188. hashValueType HashTable::hashValue() const
  189.  
  190. // Summary -----------------------------------------------------------------
  191. //
  192. //      Returns the hash value of a list.
  193. //
  194. // End ---------------------------------------------------------------------
  195. {
  196.     return hashValueType(0);
  197. }
  198. // End Member Function HashTable::hashValue //
  199.  
  200.  
  201. // Member Function //
  202.  
  203. Object& HashTable::findMember( const Object& testObject ) const
  204.  
  205. // Summary -----------------------------------------------------------------
  206. //
  207. //      Looks up the given object in the hash table and returns a
  208. //         reference to the object in the hash table, if the hash table
  209. //         contains an object which is equal to the given object.
  210. //
  211. // Parameters
  212. //
  213. //         testObject
  214. //
  215. //         The object for which we will be searching in this
  216. //         hash table.
  217. //
  218. // Return Value
  219. //
  220. //         Returns NOOBJECT if this hash table does not have the given
  221. //         object.  Returns a reference to the object otherwise.
  222. //
  223. // Functional Description
  224. //
  225. //      Check to see if there is any List object at the given index.
  226. //      If there isn't an object already there, then we don't have
  227. //         the object in our hash table.
  228. //      If there is a List object already there, then we can use its member
  229. //      functions (note that it would be a run-time error to use the member
  230. //      functions of theErrorObject) to search for our object in the list.
  231. //
  232. // End ---------------------------------------------------------------------
  233. {
  234.  
  235.     hashValueType index = getHashValue( testObject );
  236.  
  237.     if( table[ index ] == NOOBJECT )
  238.     {
  239.         return NOOBJECT;
  240.     }
  241.  
  242.     return ((List&)table[ index ]).findMember( testObject );
  243. }
  244. // End Member Function HashTable::findMember //
  245.  
  246.  
  247. // Member Function //
  248.  
  249. ContainerIterator& HashTable::initIterator() const
  250.  
  251. // Summary -----------------------------------------------------------------
  252. //
  253. //      Initializes an iterator for a hash table.
  254. //
  255. // End ---------------------------------------------------------------------
  256. {
  257.     return *( (ContainerIterator *)new HashTableIterator( this->table ) );
  258. }
  259. // End Member Function HashTable::initIterator //
  260.  
  261.  
  262.  
  263. // Constructor //
  264.  
  265. HashTableIterator::HashTableIterator( const Array& toIterate ) :
  266.                                 beingIterated( toIterate )
  267.  
  268. // Summary -----------------------------------------------------------------
  269. //
  270. //      Constructor for a hash table iterator object.
  271. //
  272. // Functional Description
  273. //
  274. //      We initialize the list iterator to a dummy list's iterator, then
  275. //      initialize the array iterator.  Finally, we invoke operator ++()
  276. //      on the iterator to finish the initialization.
  277. //
  278. // End ---------------------------------------------------------------------
  279. {
  280.     List dummy;
  281.     listIterator = (ListIterator *)&dummy.initIterator();
  282.     indexIterator = (ArrayIterator *)&toIterate.initIterator();
  283.     (void)preIterate();
  284. }
  285. // End Constructor HashTableIterator::HashTableIterator //
  286.  
  287.  
  288. // Member Function //
  289.  
  290. Object& HashTableIterator::operator ++()
  291.  
  292. // Summary -----------------------------------------------------------------
  293. //
  294. //      Increments a hash table iterator.
  295. //
  296. // End ---------------------------------------------------------------------
  297. {
  298.     if ( preIterate() )
  299.        return (*listIterator)++;
  300.     else
  301.        return NOOBJECT;
  302. }
  303. // End Member Function HashTableIterator::operator ++ //
  304.  
  305.  
  306. // Member Function //
  307.  
  308. int HashTableIterator::preIterate()
  309.  
  310. // Summary -----------------------------------------------------------------
  311. //
  312. //      Prepares a hash table iterator for the next iteration step.
  313. //
  314. // Functional Description
  315. //
  316. //      If our current list iterator is finished, we bump the array
  317. //      iterator up.  If the element at that index is a valid list,
  318. //      we set up an iterator using that list.
  319. //
  320. //
  321. // End ---------------------------------------------------------------------
  322. {
  323.     while ( *listIterator == NOOBJECT )
  324.     {
  325.         delete listIterator;
  326.         while ( *indexIterator && *indexIterator == NOOBJECT )
  327.             (*indexIterator)++;
  328.         if ( *indexIterator == 0 )
  329.             return 0;
  330.         else // the array iteration isn't over.
  331.         {
  332.             Object& l = *indexIterator;
  333.             List& l1 = (List&)l;
  334.             listIterator = (ListIterator *)&l1.initIterator();
  335.             do {
  336.                 (*indexIterator)++;
  337.                 } while ( *indexIterator && *indexIterator == NOOBJECT );
  338.         }
  339.     }
  340.     return 1;
  341. }
  342. // End Member Function preIterate //
  343.  
  344.  
  345. // Member Function //
  346.  
  347. HashTableIterator::operator int()
  348.  
  349. // Summary -----------------------------------------------------------------
  350. //
  351. //      Implements a hash table iterator integer conversion operator.
  352. //      This is used to test for the end of iteration sequence.
  353. //
  354. // End ---------------------------------------------------------------------
  355. {
  356.     return  *indexIterator != 0;
  357. }
  358. // End Member Function HashTableIterator::operator int //
  359.  
  360.  
  361. // Member Function //
  362.  
  363. HashTableIterator::operator Object&()
  364.  
  365. // Summary -----------------------------------------------------------------
  366. //
  367. //      Conversion to Object operator.
  368. //
  369. // End ---------------------------------------------------------------------
  370. {
  371.     return  *listIterator;
  372. }
  373. // End Member Function HashTableIterator::operator Object& //
  374.  
  375.  
  376. // Member Function //
  377.  
  378. void    HashTableIterator::restart()
  379.  
  380. // Summary -----------------------------------------------------------------
  381. //
  382. //      Restarts the iteration process.
  383. //
  384. // End ---------------------------------------------------------------------
  385. {
  386.     delete indexIterator;
  387.     delete listIterator;
  388.     List dummy;
  389.     listIterator = (ListIterator *)&dummy.initIterator();
  390.     indexIterator = (ArrayIterator *)&beingIterated.initIterator();
  391.     operator ++();
  392. }
  393. // End Member Function HashTableIterator::restart //
  394.