Provide a main program. Your main program should do the following: (a) Create a

Question

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 <fstream>
#include <iostream>
#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 << "File open error!" << endl;
dictionary.close();
exit(EXIT_FAILURE);
}

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

dictionary.close();
cout << " The Hash Table size of " << ht.getCapacity()
<< " contains " << ht.getCurrentSize()<< " words. ";
  
// 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.
  
ht.printStats();
  
// d. Read the words from the document and output each word that is NOT in the dictionary.
fstream document;
document.open("document.txt", ios::in);

  
// start checking if words are in dictionary.txt or not
vector<string>check;
  

dictionary.close();
cout << " Words that are NOT in the dictionary:";

  
cout << " program completed!";
}

SeperateChaining.h

#ifndef SEPARATE_CHAINING_H
#define SEPARATE_CHAINING_H

#include <vector>
#include <list>
#include <string>
#include <algorithm>
#include <functional>
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 <typename HashedObj>
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<int> & stats ) {
for( auto & thisList : theLists ) {
int count = thisList.size();
if ( count ) stats.push_back( count );
}
}
  
void printStats() {
vector<int> stats;
getStats( stats );
  
int min_id=0, max_id=0;
double mean, sum=0;
for( int i=0; i<stats.size(); i++ ) {
if( stats[i] < stats[min_id]) min_id = i;
if( stats[i] > stats[max_id]) max_id = i;
sum += stats[i];
}
mean = sum / double(stats.size());
  
cout << " minimum chain size is " << stats[min_id]
<< " maximum chain size is " << stats[max_id]
<< " The average collision is " << mean << endl;
}

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

void rehash( ) {
vector<list<HashedObj>> 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<HashedObj> 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 <= n; i += 2 )
if( n % i == 0 )
return false;
return true;
}

// 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!

Explanation / Answer

ANSWER:

FILE: dictionary.txt

20
ape
apple
ali
bowl
bad
cotton
door
from
floor
from
good
hand
sonu
vivo
yellow
yard
zoo
ali
door
EOF

FILE: document.txt

door
hello
ape
god
hen

JAVA CODE:

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Hashtable;
import java.util.Scanner;
import java.util.Set;

public class HashTableMain {

public static void printStats(Hashtable<String, String> dictTable,
           int numberOfWords) {

       int min = dictTable.size();
       int max = numberOfWords;
       double mean = (min + max) / 2.f;
       System.out.println("minimum maximum mean");
       System.out.println(" "+min+" "+max+" "+mean);
   }

   @SuppressWarnings("resource")
   public static void main(String[] args) throws FileNotFoundException {

       int numberOfWords = 0;
       int count = 1;
       Hashtable<String, String> dictionaryTable = null;
       Hashtable<String, String> wordsNotFound = new Hashtable<String, String>();

       Scanner scan = new Scanner(new File("files/dictionary.txt"));
       if (scan.hasNextLine()) {
           numberOfWords = Integer.parseInt(scan.nextLine());
           dictionaryTable = new Hashtable<String, String>(numberOfWords);
       }
       while (scan.hasNextLine()) {
           String word = scan.nextLine();
           dictionaryTable.put(word, word);
       }

       //System.out.println(dictionaryTable);

       scan = new Scanner(new File("files/document.txt"));
       while (scan.hasNextLine()) {
           String docWord = scan.nextLine();

           String fromDic = dictionaryTable.get(docWord);

           if (fromDic == null) {
               wordsNotFound.put(docWord, docWord);
           }
       }
       System.out.println("Words not found in dictionary: ");
       Set<String> keys = wordsNotFound.keySet();
       for(String key: keys){
           System.out.println(count+++": "+wordsNotFound.get(key));
       }

  printStats(dictionaryTable, numberOfWords);

   }

}

Output for above program:

Words not found in dictionary:
1: hello
2: hen
3: god
minimum maximum mean
17 20 18.5

______________________________________________________

Working fine. Let me know any concerns. Thank you

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.