COMP15 Project #7: Dictionary ADT (binary search tree)

COMP 15 Project #7: Dictionary ADT (binary search tree)

COMP15 Spring 20XX
Due: Thursday, April 21, 11:00PM

Overview

The goal of this project is to implement, test and assess a dictionary abstract data type (ADT.) A dictionary stores key-value pairs. A key is used to identify and refer to a particular pair. A key is used to select a pair in order to retrieve the associated value, remove the pair from the dictionary, etc. Dictionaries are used in a large number of applications. Compilers use a form of dictionary called a "symbol table" to store information about programmer-defined classes, types, variables and functions. The PostScript language uses dictionaries to store variables, functions and even fonts.

In this project, we will use a binary search tree (BST) representation to implement a simple dictionary ADT. In Project #8, we will use hash tables to implement the same simple dictionary ADT. In both projects, we will measure the execution speed of insertion and lookup operations. These measurements will allow us to compare the efficiency of the two implementation methods.

Objectives

The objectives for this project are:

To implement a simple dictionary ADT using a binary search tree.
To learn to instrument an application to measure its execution speed.
To gain further experience with software reuse and testing.

What needs to be done

Several files are provided:

bst_node.h, which is the declaration and definition of the BSTNode class and its interface.
dictionary.h, which is the declaration of the Dictionary interface.
dictionary.cpp, which is the definition of the Dictionary class.
bst_search.cpp, a preliminary skeleton for testing and measuring the Dictionary class.
stats.h and stats.cpp, a class for collecting and displaying simple descriptive statistics.
timer.h and timer.cpp, a class for measuring elapsed wall-clock time and for displaying execution time measurements.
makefile, which is to be used for building the test programs.

All files are available in the directory /g/15/class/project7.

You will need to implement the dictionary ADT using the files dictionary.h and dictionary.cpp. The implementation must use a binary search tree (BST) to maintain the contents of the dictionary. Dictionary items are represented using BSTNode objects which must be allocated and deallocated dynamically. To simplify, a BSTNode elides the value part of a key-value pair and only stores the symbolic key in the form of a C-style string. The key symbol must be dynamically allocated and deallocated, too.

It is not necessary to implement a copy constructor or overloaded assignment operator for the Dictionary class.

You will need to implement a test and measurement driver, bst_search.cpp. The driver has three phases of operation:

Read dictionary word list and store into a temporary data structure (for example, using an array of char *, where each element points to a word.)
Insert the words into the dictionary.
Read and store words to be looked-up in the dictionary into a separate temporary data structure.
Look up the words in the dictionary (iterate through the temporary data structure and find each word.) Tally the number of comparisons performed per look-up (find) operation.
Display descriptive statistics for the number of symbol comparisons per look-up (find) operation.

At the end of each phase, the driver must display the elapsed time for the phase, the accumulated number of user-mode CPU seconds and the accumulated number of system-mode CPU seconds. Measurements should be taken using the provided statistics and timer modules. Sample output is shown below.

    Number of words in dictionary: 354984
    Measurements for reading dictionary word list
      Elapsed time: 0.344894 seconds
      User time:    0.330000 seconds
      System time:  0.020000 seconds
    Measurements for inserting words into dictionary
      Elapsed time: 1.595779 seconds
      User time:    1.870000 seconds
      System time:  0.050000 seconds
    Number of words to lookup: 30065
    Measurements for reading list of words to be found
      Elapsed time: 0.024342 seconds
      User time:    1.890000 seconds
      System time:  0.060000 seconds
    Starting lookups
    Lookups finished
    Measurements for finding words in dictionary
      Elapsed time: 0.077263 seconds
      User time:    1.960000 seconds
      System time:  0.060000 seconds
    Statistics for comparisons per find operation
      Samples:      30065
      Minimum:      4.000000
      Maximum:      45.000000
      Mean:         25.181074
      Variance:     668.901876
      Std dev:      25.863137
      Coeff of var: 1.027086

The command line

The test and measurement driver takes two command line arguments: the name of the file containing words to be place into the dictionary and the name of the file containing words to be looked-up. The usage synopsis for the driver is:

    Usage: bst_search wordfile lookupfile

The test and measurement driver must check for the correct number of command line arguments.

Test data files

Two test data files are provided:

moby.scrambled, a list of 350,000+ words to be loaded into the dictionary.
lookup, a list of 30,000+ words to be looked-up in the the dictionary.

Each file is organized in the following way. The first line in the file is the number of words in the file. The remaining lines in the file contain exactly one word.

Additional requirements

Here are some additional requirements to be satisfied:

You must use the supplied makefile to build your solution. This makefile produces four executable programs:
- bst_search, the program to test and measure the dictionary ADT.
- bsttest, a simple smoke test for the dictionary ADT.
- statstest, a simple smoke test for the statistics collection module.
- timertest, a simple smoke test for the execution timer module.
You must thoroughly and systematically test the dictionary ADT. You may extend the simple smoke test for the dictionary ADT.
Add comments to the source code to describe your approach and solution.

Don't forget to fill out any header comments with your name, section and e-mail address.

Submitting your work

Use the provide system to submit your finished program:

    /local/bin/provide comp15 p7 makefile bst_node.h ...

The files to be submitted are:

    bst_node.h        Declaration/definition of a BST node
    dictionary.h      Declaration of the dictionary ADT interface
    dictionary.cpp    Definition of the dictionary ADT
    bst_search.cpp    Test and measurement driver
    stats.h           Declaration of the statistics interface
    stats.cpp         Definition of the statistics module
    timer.h           Declaration of the timing interface
    timer.cpp         Definition of the timer module
    makefile          makefile to build everything

Do not submit the test files moby.scrambled and lookup.

Be sure you are completely satisfied with your work before submitting! Build and test your program on comp15.cs.tufts.edu before submitting your work. This system is the target build and test platform for all course projects. Projects which do not build correctly receive a score of zero.

Informal interface specification: Dictionary

Project #8 will use this same informal interface specification for the dictionary ADT. Since the dictionary interface will not change, you should be able to reuse your test and measurement driver for Project #8.

Function: Dictionary()
  Purpose: 
    Constructor for the Dictionary class. Initializes the
    dictionary to its empty state.
  Parameters:
    None
  Returns:
    Nothing
  Error conditions:
    None

Function: ~Dictionary()
  Purpose: 
    Deallocates (deletes) any items in the dictionary
  Parameters:
    None
  Returns:
    Nothing
  Error conditions:
    None

Function: insert(char *new_symbol)
  Purpose: 
    Inserts a new entry into the dictionary with the
    key specified by new_symbol
  Parameters:
    new_symbol: The key (a C-style string)
  Returns:
    Nothing
  Error conditions:
    Memory space exhausted

Function: find(char *target)
  Purpose: 
    Performs a look-up to find an item in the dictionary
    with the specified key
  Parameters:
    target: The key (a C-style string)
  Returns:
    True if the item was found, otherwise false
  Error conditions:
    None

Function: remove(char *target)
  Purpose: 
    Finds and removes the item with the specified key
    from the dictionary
  Parameters:
    target: The key (a C-style string)
  Returns:
    Nothing
  Error conditions:
    None

Function: print
  Purpose: 
    Prints (dumps) the contents of the dictionary. Only useful
    for debugging with *small* dictionaries!
  Parameters:
    None
  Returns:
    Nothing
  Error conditions:
    None

Function: clear_number_of_comparisons
  Purpose: 
    Resets the running count of symbol (string) comparisons
    to zero
  Parameters:
    None
  Returns:
    Nothing
  Error conditions:
    None

Function: inc_number_of_comparisons
  Purpose: 
    Increments the running count of symbol (string) comparisons
  Parameters:
    None
  Returns:
    Nothing
  Error conditions:
    None

Function: get_number_of_comparisons
  Purpose: 
    Retrieves the running count of symbol (string) comparisons
  Parameters:
    None
  Returns:
    Current running count of symbol comparisons
  Error conditions:
    None