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