Use double hashing to reimplement the hash table .

Please write in c++

// FILE: table1.template

// TEMPLATE CLASS IMPLEMENTED: table (see table1.h for documentation)

// INVARIANT for the table ADT:

// 1. The number of records in the table is in the member variable used.

// 2. The actual records of the table are stored in the array data, with

// a maximum of CAPACITY entries. Each used spot in the array has a

// non-negative key. Any unused record in the array has a key field of

// NEVER_USED (if it has never been used) or PREVIOUSLY_USED (if it once

// was used, but is now vacant).

#include // Provides assert

#include // Provides size_t

namespace main_savitch_12A

{

template

const std::size_t table::CAPACITY;

template

const int table::NEVER_USED;

template

const int table::PREVIOUSLY_USED;

template

table::table( )

{

std::size_t i;

used = 0;

for (i = 0; i < CAPACITY; ++i)

data[i].key = NEVER_USED; // Indicates a spot that's never been used.

}

template

void table::insert(const RecordType& entry)

// Library facilities used: cassert

{

bool already_present; // True if entry.key is already in the table

std::size_t index; // data[index] is location for the new entry

assert(entry.key >= 0);

// Set index so that data[index] is the spot to place the new entry.

find_index(entry.key, already_present, index);

// If the key wasn't already there, then find the location for the new entry.

if (!already_present)

{

assert(size( ) < CAPACITY);

index = hash(entry.key);

while (!is_vacant(index))

index = next_index(index);

++used;

}

data[index] = entry;

}

template

void table::remove(int key)

// Library facilities used: cassert

{

bool found; // True if key occurs somewhere in the table

std::size_t index; // Spot where data[index].key == key

assert(key >= 0);

find_index(key, found, index);

if (found)

{ // The key was found, so remove this record and reduce used by 1.

data[index].key = PREVIOUSLY_USED; // Indicates a spot that's no longer in use.

--used;

}

}

template

bool table::is_present(int key) const

// Library facilities used: assert.h

{

bool found;

std::size_t index;

assert(key >= 0);

find_index(key, found, index);

return found;

}

template

void table::find(int key, bool& found, RecordType& result) const

// Library facilities used: cassert.h

{

std::size_t index;

assert(key >= 0);

find_index(key, found, index);

if (found)

result = data[index];

}

template

inline std::size_t table::hash(int key) const

{

return (key % CAPACITY);

}

template

inline std::size_t table::next_index(std::size_t index) const

// Library facilities used: cstdlib

{ if(((index+5)%CAPACITY)>=CAPACITY){

return (((index+5) % CAPACITY) - CAPACITY);

}

return ((index+5) % CAPACITY);

}

template

void table::find_index(int key, bool& found, std::size_t& i) const

// Library facilities used: cstdlib

{

std::size_t count; // Number of entries that have been examined

count = 0;

i = hash(key);

while((count < CAPACITY) && (data[i].key != NEVER_USED) && (data[i].key != key))

{

++count;

i = next_index(i);

}

found = (data[i].key == key);

}

template

inline bool table::never_used(std::size_t index) const

{

return (data[index].key == NEVER_USED);

}

template

inline bool table::is_vacant(std::size_t index) const

{

return (data[index].key == NEVER_USED) || (data[index].key == PREVIOUSLY_USED);

}

}

// FILE: table1.h (part of the namespace main_savitch_12A)

// TEMPLATE CLASS PROVIDED: table (a table of records with keys).

// This class is a container template class for a table of records.

// The template parameter, RecordType, is the data type of the records in the

// table. It may be any of the bulit-in C++ types (int, char, etc.), or a

// class with a default constructor, an assignment operator, and an integer

// member variable called key.

//

// MEMBER CONSTANT for the table class:

// static const size_type CAPACITY = ________

// table::CAPACITY is the maximum number of records held by a table.

//

// CONSTRUCTOR for the table template class:

// table( )

// Postcondition: The table has been initialized as an empty table.

//

// MODIFICATION MEMBER FUNCTIONS for the table class:

// void insert(const RecordType& entry)

// Precondition: entry.key >= 0. Also if entry.key is not already a key in

// the table, then the table has space for another record

// (i.e., size( ) < CAPACITY).

// Postcondition: If the table already had a record with a key equal to

// entry.key, then that record is replaced by entry. Otherwise, entry has

// been added as a new record of the table.

//

// void remove(int key)

// Postcondition: If a record was in the table with the specified key, then

// that record has been removed; otherwise the table is unchanged.

//

// CONSTANT MEMBER FUNCTIONS for the table class:

// bool is_present(const Item& target) const

// Postcondition: The return value is true if there is a record in the

// table with the specified key. Otherwise, the return value is false.

//

// void find(int key, bool& found, RecordType& result) const

// Postcondition: If a record is in the table with the specified key, then

// found is true and result is set to a copy of the record with that key.

// Otherwise found is false and the result contains garbage.

//

// size_type size( ) const

// Postcondition: Return value is the total number of records in the

// table.

//

// VALUE SEMANTICS for the table template class:

// Assignments and the copy constructor may be used with table objects.

#include // Provides size_t

namespace main_savitch_12A

{

template

class table

{

public:

// MEMBER CONSTANT -- See Appendix E if this fails to compile.

static const std::size_t CAPACITY = 811;

// CONSTRUCTOR

table( );

// MODIFICATION MEMBER FUNCTIONS

void insert(const RecordType& entry);

void remove(int key);

// CONSTANT MEMBER FUNCTIONS

bool is_present(int key) const;

void find(int key, bool& found, RecordType& result) const;

std::size_t size( ) const { return used; }

private:

// MEMBER CONSTANTS -- These are used in the key field of special records.

static const int NEVER_USED = -1;

static const int PREVIOUSLY_USED = -2;

// MEMBER VARIABLES

RecordType data[CAPACITY];

std::size_t used;

// HELPER FUNCTIONS

std::size_t hash(int key) const;

std::size_t next_index(std::size_t index) const;

void find_index(int key, bool& found, std::size_t& index) const;

bool never_used(std::size_t index) const;

bool is_vacant(std::size_t index) const;

};

}

#include "table1.cpp" // Include the implementation.

#endif // TABLE1_H

// FILE: testtab1.cxx

// An interactive test program for the first Table ADT.

#include // Provides toupper

#include // Provides EXIT_SUCCESS and size_t

#include // Provides cin, cout

#include "table1.h" // Provides the Table class

using namespace std;

using namespace main_savitch_12A;

// Struct definition for the test_record_type, which has a key and a double.

struct test_record_type

{

int key;

double data;

};

// PROTOTYPES for functions used by this test program:

void print_menu( );

// Postcondition: A menu of choices for this program has been written to cout.

char get_user_command( );

// Postcondition: The user has been prompted to enter a one character command.

// The next character has been read (skipping blanks and newline characters),

// and this character has been returned.

test_record_type get_record( );

// Postcondition: The user has been prompted to enter data for a record. The

// key has been read, echoed to the screen, and returned by the function.

int get_key( );

// Postcondition: The user has been prompted to enter a key for a record. The

// items have been read, echoed to the screen, and returned by the function.

int main( )

{

table test; // A table that we'll perform tests on

char choice; // A command character entered by the user

bool found; // Value returned by find function

test_record_type result; // Value returned by find function

cout << "I have initialized an empty table. Each record in the table ";

cout << "has an integer key and a real number as data." << endl;

do

{

print_menu( );

choice = toupper(get_user_command( ));

switch (choice)

{

case 'S': cout << "The table size is " << test.size( ) << endl;

break;

case 'I': test.insert(get_record( ));

cout << "The record has been inserted." << endl;

break;

case 'R': test.remove(get_key( ));

cout << "Remove has been called with that key." << endl;

break;

case '?': if (test.is_present(get_key( )))

cout << "That key is present." << endl;

else

cout << "That key is not present." << endl;

break;

case 'F': test.find(get_key( ), found, result);

if (found)

cout << "The key's data is: " << result.data << endl;

else

cout << "That key is not present." << endl;

break;

case 'Q': cout << "Ridicule is the best test of truth." << endl;

break;

default: cout << choice << " is invalid. Sorry." << endl;

}

}

while ((choice != 'Q'));

return EXIT_SUCCESS;

}

void print_menu( )

// Library facilities used: iostream.h

{

cout << endl; // Print blank line before the menu

cout << "The following choices are available: " << endl;

cout << " S Print the result from the size( ) function" << endl;

cout << " I Insert a new record with the insert(...) function" << endl;

cout << " R Remove a record with the remove(...) function" << endl;

cout << " ? Check whether a particular key is present" << endl;

cout << " F Find the data associated with a specified key" << endl;

cout << " Q Quit this test program" << endl;

}

char get_user_command( )

// Library facilities used: iostream.h

{

char command;

cout << "Enter choice: ";

cin >> command; // Input of characters skips blanks and newline character

return command;

}

test_record_type get_record( )

// Library facilities used: iostream.h

{

test_record_type result;

cout << "Please enter a real number for a record's data: ";

cin >> result.data;

cout << result.data << " has been read." << endl;

result.key = get_key( );

return result;

}

int get_key( )

// Library facilities used: iostream.h

{

int key;

do

{

cout << "Please enter a non-negative integer for a key: ";

cin >> key;

}

while (key < 0);

cout << key << " has been read." << endl;

return key;

}