Provide a main program. Your main program should do the following:

(a) Create a hash table whose size is equal to the number of words in the dictionary.

(b) Read the words from the dictionary and store each one in the hash table.

(c) Output the statistics (i.e. minimum, maximum, and mean chain length) of the hash table after all words in the dictionary has been stored in the hash table.

(d) Read the words from the document and output each word that is NOT in the dictionary.

Example Test Run

as11_starter.cpp

#include #include #include "SeparateChaining.h"

using namespace std;

int main() {

// a. Create a hash table whose size is equal to the number of words in the dictionary. fstream dictionary; dictionary.open("dictionary.txt", ios::in); if ( dictionary.fail() ) { cout

// b. Read the words from the dictionary and store each one in the hash table. HashTable ht; int word_count = 0; string word;

dictionary.close(); cout

// start checking if words are in dictionary.txt or not vectorcheck;

dictionary.close(); cout

cout

SeperateChaining.h

#ifndef SEPARATE_CHAINING_H #define SEPARATE_CHAINING_H

#include #include #include #include #include using namespace std;

int nextPrime( int n );

// SeparateChaining Hash table class // // CONSTRUCTION: an approximate initial size or default of 101 // // ******************PUBLIC OPERATIONS********************* // bool insert( x ) --> Insert x // bool remove( x ) --> Remove x // bool contains( x ) --> Return true if x is present // int getCapacity( ) --> Return theLists.size() // int getCurrentSize( ) --> Return currentSize; // void makeEmpty( ) --> Remove all items

template class HashTable { public: explicit HashTable( int size = 101 ) : currentSize{ 0 } { theLists.resize( 101 ); } int getCapacity() { return theLists.size(); } int getCurrentSize() { return currentSize; } bool contains( const HashedObj & x ) const { auto & whichList = theLists[ myhash( x ) ]; return find( begin( whichList ), end( whichList ), x ) != end( whichList ); }

void makeEmpty( ) { for( auto & thisList : theLists ) thisList.clear( ); }

bool insert( const HashedObj & x ) { auto & whichList = theLists[ myhash( x ) ]; if( find( begin( whichList ), end( whichList ), x ) != end( whichList) ) return false; whichList.push_back( x );

// Rehash; see Section 5.5 if( ++currentSize > theLists.size( ) ) rehash( );

return true; } bool insert( HashedObj && x ) { auto & whichList = theLists[ myhash( x ) ]; if( find( begin( whichList ), end( whichList ), x ) != end( whichList ) ) return false; whichList.push_back( std::move( x ) );

// Rehash; see Section 5.5 if( ++currentSize > theLists.size( ) ) rehash( );

return true; }

bool remove( const HashedObj & x ) { auto & whichList = theLists[ myhash( x ) ]; auto itr = find( begin( whichList ), end( whichList ), x );

if( itr == end( whichList ) ) return false;

whichList.erase( itr ); --currentSize; return true; } void getStats( vector & stats ) { for( auto & thisList : theLists ) { int count = thisList.size(); if ( count ) stats.push_back( count ); } } void printStats() { vector stats; getStats( stats ); int min_id=0, max_id=0; double mean, sum=0; for( int i=0; i stats[max_id]) max_id = i; sum += stats[i]; } mean = sum / double(stats.size()); cout

private: vector> theLists; // The array of Lists int currentSize;

void rehash( ) { vector> oldLists = theLists;

// Create new double-sized, empty table theLists.resize( nextPrime( 2 * theLists.size( ) ) ); for( auto & thisList : theLists ) thisList.clear( );

// Copy table over currentSize = 0; for( auto & thisList : oldLists ) for( auto & x : thisList ) insert( std::move( x ) ); // rvalue, no copy }

size_t myhash( const HashedObj & x ) const { static hash hf; return hf( x ) % theLists.size( ); } };

/** * Internal method to test if a positive number is prime. * Not an efficient algorithm. */ bool isPrime( int n ) { if( n == 2 || n == 3 ) return true; if( n == 1 || n % 2 == 0 ) return false; for( int i = 3; i * i

// To return a prime number at least as large as n, assumes n > 0. int nextPrime( int n ) { if( n % 2 == 0 ) ++n; for( ; !isPrime( n ); n += 2 ); return n; }

// A hash routine for string objects. size_t hash( const string & key ) { size_t hashVal = 0; for( char ch : key ) hashVal = 37 * hashVal + ch; return hashVal; }

// A hash routine for ints. size_t hash( int key ) { return key; }

#endif

Running /home/ubuntu/workspace/comsc210/dictionary/testSeparateChaining.cpp The Hash Table size of 222461 contains 113811 words. minimum chain size is 1 maximum chain size is 6 The average collision is 1.27754 Correctly spelled words are: handsome clever and rich with a comfortable home and happy disposition seemed to unite some of the best blessings of existence and had lived nearly twenty one years in the world with very little to distress or vex her she was the youngest of the two daughters of a most affectionate indulgent father and had in consequence of her marriage been mistress of his house from a very early period her mother had died too long ago for her to have more than an indistinct of her caresses and her place had been supplied by an excellent woman as governess who had fallen little short of a mother in affection the wedding was very much like other weddings where the parties have no taste for finery or parade and from the particulars detailed by her husband thought it all extremely shabby and very inferior to her own very little white satin very few lace veils a most pitiful business would stare when she heard of it but in spite of these deficiencies the wishes the hopes the confidence the predictions of the small band of true friends who witnessed the ceremony were fully answered in the perfect happiness of the union Incorrectly spelled words are: emma woodhouse sister's remembrance mrs elton selina program completed