Overview

Suppose we want to analyze an arbitrary✯ text file. We want to learn the following details:

❼ How many words are in the text file?

❼ What are the most frequent words in the text file?

❼ Of the most frequent words, how often do they occur?

Dan wants your help!  We want to use hashing to store an English Dictionary and another to store words from the text file based on their frequency (how often the words appear). Dan started getting the code together to address the above, but there is some missing code he is entrusting you to implement!

You will in C++:

❼ Implement a Dictionary using a Hash Table.

❼ Solve some basic string problems, and implement Quick Sort (specifically, partition; you are

provided all other elements of Quick Sort [we are just using the last element as the pivot here]).

❼ The hash table implemented uses separate chaining, given certain requirements.

The specifications of the assignment start on Page 2.  You are provided several classes and eventually a program for analyzing text files.  The functioning code (assuming the whole of your code compiles and is completed) will be used to partially grade your work.

Learning Objectives

❼ Implement a variant of a dictionary, using hashing (separate chaining).

❼ Making practical considerations for hashing (determining an appropriate size for a hash table).

❼ Implementing a hash function (polynomial hash code).

❼ Basic manipulation of the vector container, and sorting.

❼ Solving text-based analysis problems.

❼ Throwing an exception.

❼ Understanding code provided, where student code is part of a larger program.

Classes to Implement, Other Details

In this assignment you must implement two classes, HashWordDictionary and complete the partially                provided TextParser class, your code will be contained in files you will create called HashWordDictionary.cpp

and TextParser.cpp, respectively.  You will be provided header files for all classes, except for TextParser which will be entirely enclosed in a single .cpp file. You must write all remaining code yourself.  Our HashWordDictionary class is implementing WordDictionary (an interface for a dictionary (that only has get and put, along with some other operations) that consists of WordData pointers which will be used to keep track of data about words (string, frequency pairs)). When the TextParser class is being implemented, you will be asked to choose the size of the hash table for the English dictionary it will use, so that it has a specific load factor.

The program that uses all our classes is TextParsing.cpp, which has no code to be completed within it.

I will expect you to know how to compile C++ programs and understand C++. Please compile your code using g++. Presume input data being fed to the program indeed matches the parameters of methods.

Please study the WordNode and the WordData classes. Both play an integral role in this assign- ment. The former is used to form nodes for our hash table (using separate chaining) and the latter stores our data for each word we encounter in a text file (along with an English dictionary).  In cases, we will encounter the keyword null in this assignment, we will use nullptr.

The next three sections outline how to carry out the first three goals.

Class HashWordDictionary

This is a variant of a basic dictionary (it does not remove records), where it has as records WordData objects (the key is the std::string). Some of the dictionary ADT operations are modified to return the whole record.

The following are the instance variables of this class:

❼ WordNode** table: An array of linked lists, where each node is WordNode.  Each WordNode

has a WordData object as data that stores a string (its key) and a frequency (value).  To initialize the table, one may use table = new WordNode*[tableSize];.

❼  int numElem:  The number of records in the dictionary (not to be confused with the hash

table’s size).

❼  int tableSize: The table size, if not defined by the constructor it has a default value of 100

(as initialized/specified in the header file).

You must implement all the following private methods:

❼  int HashWordDictionary::hashFunction(std::string  input): Implement the polynomial

hash code function we seen in class (that uses a variant of Horner’s Method). You can pick any of the recommended values for x we discussed in class.  Note that our function in class presumes that the string is non-empty, add a conditional check at the beginning that returns 0 for an empty string.

Next, you must implement the following public methods:

1. HashWordDictionary::HashWordDictionary(): A constructor that creates a new array table of WordNode* of size tableSize (which is 100, by default, as provided by the header file [you  do not need to do anything with tableSize]). Make sure to go through each position in the  array table and assign each table[i] to nullptr. Finally set numElem = 0.

2. HashWordDictionary::HashWordDictionary(int M): The same as the above constructor, except begin by setting tableSize to M (the provided table size as input).

3. HashWordDictionary::∼HashWordDictionary(): The deconstructor.  Go through each po- sition in the table and scan its linked list, deleting each node (similar to the previous pro- gramming assignment).

4. void HashWordDictionary::put(WordData* word): Our put operation for separate chain- ing. The put operation will be slightly different here, where if there is an attempt to insert a record with a duplicate key, the frequency of that word will be incremented by one then the exception DuplicateKeyException will be thrown. Make sure to increment the variable counting the number of records in the dictionary appropriately.  Given WordData record word:

(a) Use the hash function to compute the position into the table,  get the WordNode*

pointer p that will be the head of some linked list (it may be null).

(b) If p equals null, then it is safe to insert at the head of the linked list a new WordNode

containing word as its data.

(c) Otherwise, we need to scan through the linked list beginning at the node p. While both p’s next node is not null and the WordData object’s key of node p does not equal word’s key, assign p to be its next node.

(d) If the node p’s WordData object has a key that equals words’s key, then we have a dupli- cate word (key). Get the frequency of p’s WordData object and increment that object’s word frequency by one (Hint: it is the value of the WordData object, use the appropriate getters and setters). Once this is completed, throw the DuplicateKeyException.

(e) Otherwise, set the next node of p to be a new WordNode whose data is word.

5. WordData* HashWordDictionary::get(std::string key): Return the WordData object that has the key. If there is no record of type WordData exists with the key, return null.

6.  std::vector HashWordDictionary::listRecords(): Build a std::vector that contains all the records of the dictionary. Follow the next steps:

(a) Create the vector, you can use std::vector recordList to initialize a

vector.

(b) For each position of the table, go through its linked list and use recordList.push back(...)

to insert the WordData* data at each node in the linked list.

(c) Return the vector recordList.

7.  int HashWordDictionary::size(): Return the number of records in the dictionary.

8.  int HashWordDictionary::M(): Return the tableSize.

9. bool HashWordDictionary::isEmpty():  Return true if the dictionary has no records, and false otherwise.

Ensure to #include all header files necessary for compilation, including HashWordDictionary.h and DuplicateKeyException.h.