Posted By

DrPepper on 11/11/11


Tagged


Versions (?)

[CISP 430] HASH TABLE FROM TEXT BOOK EXAMPLE (table1.template)


 / Published in: C++
 

  1. // FILE: table1.template
  2. // TEMPLATE CLASS IMPLEMENTED: table (see table1.h for documentation)
  3. // INVARIANT for the table ADT:
  4. // 1. The number of records in the table is in the member variable used.
  5. // 2. The actual records of the table are stored in the array data, with
  6. // a maximum of CAPACITY entries. Each used spot in the array has a
  7. // non-negative key. Any unused record in the array has a key field of
  8. // NEVER_USED (if it has never been used) or PREVIOUSLY_USED (if it once
  9. // was used, but is now vacant).
  10.  
  11. #include <cassert> // Provides assert
  12. #include <cstdlib> // Provides size_t
  13.  
  14. namespace main_savitch_12A
  15. {
  16. template <class RecordType>
  17. const std::size_t table<RecordType>::CAPACITY;
  18.  
  19. template <class RecordType>
  20. const int table<RecordType>::NEVER_USED;
  21.  
  22. template <class RecordType>
  23. const int table<RecordType>::PREVIOUSLY_USED;
  24.  
  25. template <class RecordType>
  26. table<RecordType>::table( )
  27. {
  28. std::size_t i;
  29.  
  30. used = 0;
  31. for (i = 0; i < CAPACITY; ++i)
  32. data[i].key = NEVER_USED; // Indicates a spot that's never been used.
  33. }
  34.  
  35. template <class RecordType>
  36. void table<RecordType>::insert(const RecordType& entry)
  37. // Library facilities used: cassert
  38. {
  39. bool already_present; // True if entry.key is already in the table
  40. std::size_t index; // data[index] is location for the new entry
  41.  
  42. assert(entry.key >= 0);
  43.  
  44. // Set index so that data[index] is the spot to place the new entry.
  45. find_index(entry.key, already_present, index);
  46.  
  47. // If the key wasn't already there, then find the location for the new entry.
  48. if (!already_present)
  49. {
  50. assert(size( ) < CAPACITY);
  51. index = hash(entry.key);
  52. while (!is_vacant(index))
  53. index = next_index(index);
  54. ++used;
  55. }
  56.  
  57. data[index] = entry;
  58. }
  59.  
  60. template <class RecordType>
  61. void table<RecordType>::remove(int key)
  62. // Library facilities used: cassert
  63. {
  64. bool found; // True if key occurs somewhere in the table
  65. std::size_t index; // Spot where data[index].key == key
  66.  
  67. assert(key >= 0);
  68.  
  69. find_index(key, found, index);
  70. if (found)
  71. { // The key was found, so remove this record and reduce used by 1.
  72. data[index].key = PREVIOUSLY_USED; // Indicates a spot that's no longer in use.
  73. --used;
  74. }
  75. }
  76.  
  77. template <class RecordType>
  78. bool table<RecordType>::is_present(int key) const
  79. // Library facilities used: assert.h
  80. {
  81. bool found;
  82. std::size_t index;
  83.  
  84. assert(key >= 0);
  85.  
  86. find_index(key, found, index);
  87. return found;
  88. }
  89.  
  90. template <class RecordType>
  91. void table<RecordType>::find(int key, bool& found, RecordType& result) const
  92. // Library facilities used: cassert.h
  93. {
  94. std::size_t index;
  95.  
  96. assert(key >= 0);
  97.  
  98. find_index(key, found, index);
  99. if (found)
  100. result = data[index];
  101. }
  102.  
  103. template <class RecordType>
  104. inline std::size_t table<RecordType>::hash(int key) const
  105. {
  106. return (key % CAPACITY);
  107. }
  108.  
  109. template <class RecordType>
  110. inline std::size_t table<RecordType>::next_index(std::size_t index) const
  111. // Library facilities used: cstdlib
  112. {
  113. return ((index+1) % CAPACITY);
  114. }
  115.  
  116. template <class RecordType>
  117. void table<RecordType>::find_index(int key, bool& found, std::size_t& i) const
  118. // Library facilities used: cstdlib
  119. {
  120. std::size_t count; // Number of entries that have been examined
  121.  
  122. count = 0;
  123. i = hash(key);
  124. while((count < CAPACITY) && (data[i].key != NEVER_USED) && (data[i].key != key))
  125. {
  126. ++count;
  127. i = next_index(i);
  128. }
  129. found = (data[i].key == key);
  130. }
  131.  
  132. template <class RecordType>
  133. inline bool table<RecordType>::never_used(std::size_t index) const
  134. {
  135. return (data[index].key == NEVER_USED);
  136. }
  137.  
  138. template <class RecordType>
  139. inline bool table<RecordType>::is_vacant(std::size_t index) const
  140. {
  141. return (data[index].key == NEVER_USED) || (data[index].key == PREVIOUSLY_USED);
  142. }
  143. }

Report this snippet  

You need to login to post a comment.