Assignment 9: The Associative Array (Collaborative)

Assigned: 11/30/2017
Due: 23:59 12/8/2017


In this lab you will be implementing an associative array class with a custom binary search tree. In your associative array class we will be separating the value that the array stores, from the key (index) over which the array is sorted. In order to consider separating the array's key from its data, consider the following tree example (we will use a string as the key value and store an integer value as data). A node for the tree will resemble the following:

class Node {
    Node *left, *right;
    std::string key;
    int data;
    Node(std::string key);
Remember to use proper access control--any methods that comprise your interface should be public. In general, helper methods should be private.

At the start, our tree is simply a null pointer. Now, suppose we wish to store the following (somewhat arbitrary) values in order:

After insertion, we would have the following BST:

What we have described here is essentially a custom-built tree implementation of an associative array/map/dictionary type (you can see the C++ example of the map container, however you aren't allowed to use this in your assignment). By overloading the bracket operator we will provide the user with array-like access to our structure (i.e., map["string"] = value;).

What you must implement

At minimum, you must implement a node class and an associative array class. Your associative array class must have (at minimum) the following public member functions:

tree["one_word"]++;             // Increment the value at position "one_word"
tree["another_word"] = 15;  // Set the value at position "another_word" to be 15	

Note that you will have to define two versions of operator[] for both accessing and mutating.

Driver/testing your program

Implemented as an associative array your binary search tree class would be immediately useful for doing simple analysis of bodies of text. In order to test your program you should create a menu-based interface that allows the user the ability to manually test all of the functionality of your data structure.

Your menu should also give the user the ability to read text data from an arbitrary file. When it does, your program should increment in the binary tree the value stored for each word every time it is seen. After the program is done, your tree should store the total number of times that each word of the file was seen. Your program should only store words without whitespace and should filter out punctuation and other symbols (I'm leaving the definition of a word up to you--it would be reasonable to consider "o'clock" a word). As a test for your program's reading functionality, you can find the text for Arthur Conan Doyle's The Adventures of Sherlock Holmes here.

I am leaving the driver implementation up to you, but I still expect good software development to occur (separation of functionality into functions or methods, organization by either a separate class or the main in your driver).

What you must turn in:

For this assignment you will be turning in by (i.e., committing regularly). When the assignment comes due, I will pull down the latest commit for your project. Note that if you have commits in after the due date but during the late period I will be pulling those, and you will incur a late penalty. Your project should include (at minimum) the following files: