Data Structures

Assignment - To measure the student`s ability to implement and/or use complex data structures (e.g., hash tables and binary search trees) to solve an underlying
problem in C++.

Overview
This assignment will test your ability to implement a hash table and binary search tree, then use their functionality to implement a basic spell-checking program. The program will use a hash table with binary search tree chaining as a dictionary, which will be populated with a list of ≈3000 words (see here for the basis of the word list: Oxford 3000). Your spell-checker will then have basic functionality to determine if a word is spelled correctly (i.e., if it exists in the hash table) and suggest potential corrections if spelled incorrectly. For the purposes of this assignment, the potential corrections will be limited to single-character substitutions and swapping of adjacent characters.

The Tasks

The first task is to implement templated BTNode, BinarySearchTree, and HashTable classes. For each class, you are provided with the header file and must adhere to its definitions. These headers will be substantially similar to those discussed in class and in lab but differ in a few minor ways. In particular, the binary search tree has been modified to work with keys rather than data objects, much the same as the hash table. Furthermore, the hash table uses a binary search tree in each cell for collision avoidance.

Next, you will implement the SpellChecker class. As mentioned previously, your spell- checker will have only basic functionality to determine if a word is spelled correctly (i.e., if it exists in the hash table), suggest potential corrections if spelled incorrectly, and to insert and remove words.

Firstly, you will use a hash table of Word objects to represent a dictionary of words. A word can be assumed to be spelled correctly if it exists in the dictionary (i.e., hash table). Conversely, a word that does not exist in the dictionary can be assumed to be spelled incorrectly.

If a word is spelled incorrectly (i.e., it is not in the hash table), the program will present the user with some suggested corrections. In particular, it will present correctly spelled words that are either single-character substitutions (e.g., "analyze" should result in the suggestion of "analyse" by swapping "z" for "s") or can be formed by swapping of adjacent characters (e.g., "tets" should result in the suggestion of "test" by swapping "ts" for "st"). Notably, both suggestions can produce multiple words and all words from both sets of suggestions should be presented to the user. For example, "etst" should suggest both "test" (using adjacent swap) and "east" (using single substitution).

Furthermore, the user can manually insert words to the dictionary, as well as remove words.

BTNode

The BTNode class is a templated version of a node in a binary tree and should be implemented as discussed in lecture. For a full list of methods required and some important details, you should examine the bt_node.h file and its associated documentation.

BSTree

The BSTree class is a templated version of a binary search tree and should be implemented recursively as discussed in lecture. Do note, the signatures of some methods have been modified slightly, particularly to use keys rather than data objects. For a full list of methods required and some important details, you should examine the bs_tree.h file and its associated documentation.

By default, your binary search tree should print an inorder traversal, but should provide functionality to print according to the three traversals discussed in lecture (preorder, postorder, and inorder).

HashTable

The HashTable class is a templated version of a hash table that uses a binary search tree for chaining and should be implemented as discussed in lecture. For a full list of methods required and some important details, you should examine the hash_table.h file and its associated documentation.

You are to use the built-in std::hash as the hash function and should simply copy the hash function definition from Figure 1 to your HashTable class.

SpellChecker

The SpellChecker class contains the main logic of the spell-checking process and uses your HashTable class to support the dictionary functionality. That is, this class must use the public interface provided by your HashTable class to support its operations, as further detailed in the header file. Your hash table should be initialised with 101 cells, as is the default size in the header file, but should work for any provided capacity. For a full list of methods required and some important details, you should examine the spell_checker.h file and its associated documentation.

The spell_check method will accept a std::string and determine whether it is spelled correctly. If the word is spelled correctly, a message indicating it is spelled correctly should be displayed to the console: " is spelled correctly.". If the word is not spelled correctly, the user should then be presented with one of two messages. If there are no potential suggestions, the user should be presented with the message " is not spelled correctly. There are no suggestions." Alternatively, if there are potential corrections, the user should be presented with the message: " is not spelled correctly. Here is a list of suggestions: " followed by a list of suggested corrections, one per line. An example of the program execution is shown in Figure 2.

Figure 3 shows a skeleton for the similar_words method, which demonstrates how to perform each of the modifications that are used to generate potential suggestions. However, it does not validate whether the suggestions are valid and does not include any suggestions in the vector. You must complete the implementation to ensure only correct suggestions (i.e., existing words) are added to the vector.