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