Modify the given code as follows:

Augment the hash_table class with a private subclass called "key_line" which uses a string to hold a key (word) and a vector of integers to keep track of all the line numbers where the key is found in the input file. You will neither need to implement a constructor or a destructor (the defaults will do fine), but you must implement a key_line::inuse() member function that indicates whether the object holds a key or not. You will also need to overload the comparison operator, i.e., operator==(). That's it for key_line which should be based on a struct instead of a class to make it readily available to the hash_table member functions.

Remove all template references used by the hash_table class which should be modified to explicitly use the key_line subclass. This includes making member functions qprobe(), insert(), and resize() all use key_line::inuse() when checking to see if an entry exists.

Modify the hash_table::insert() function to add a key if not present in the hash table. Update each key_line object to have it maintain a sorted list of all unique line numbers for it (no That is, search the line number vector mentioned above and if not found, add the new line number at the end of the list. Use std::find() to carry out the search.

Add a public member function hash_table::find() that returns a constant reference to the vector of line numbers associated with the hash table entry for a given key. If the key is not found, a reference to an empty vector is returned. You deal with this in the main program.

#include <...>

using namespace std;

typedef unsigned int uint;

template

class hash_table {

public:

hash_table(int N=9999);

void insert(const Tkey &);

private:

int hash(const Tkey &);

vector table;

};

template

hash_table::hash_table(int N) {

table.assign(N, Tkey());

}

template

void hash_table::insert(const Tkey &key) {

int index = hash(key);

cout << setw(20) << left << key

<< "index "

<< setw(3) << right << index;

if (table[index] == key) {

cout << " -- key repeat (" << table[index] << ")";

} else if (table[index] == Tkey()) {

table[index] = key;

} else {

cout << " -- collision (" << table[index] << ")";

}

cout << " ";

}

Hint: Keys that hash to the index produces collisions. Above we detect and report them. Next handout provides

work arounds.

template<>

int hash_table::hash(const int &key) {

return (uint)key % table.size();

}

template<>

int hash_table::hash(const float &key) {

return *(uint *)&key % table.size();

}

template<>

int hash_table::hash(const string &key) {

uint index = 0;

const char *p = key.c_str();

while (*p)

index = ((index << 5) | (index >> 27)) + *p++;

return index % table.size();

}

int main(int argc, char *argv[]) {

hash_table H;

string key;

while (cin >> key)

H.insert(key);

}

Hint: The odd-looking type casting for hashing of floats serves to ensure full use of the underlying 32-bit data.

Hint: The binary logic used when hashing strings serves to implement cyclic shifting to prevent loss of bits as

more and more chars are added to the index. The 5 MSB bits become LSB bits. The remaining 27 bits are shifted

left to become the new MSB bits.