Lab5 Dictionary Tests

The deadline for lab4/lab5 has been extended to April 1st, 2010 at 11:59. However, you will need to make sure that the following tests are incorporated into your lab5-src and you are able to run them with your implemented data structures.

Step 1. Make a backup copy of your lab5 directory

Go one directory above lab5-src and type
cp -r lab5-src lab5-src-bkp1

Step 2. Untar lab5-test

Download lab5-test.tar.Z and then untar it into the lab5-src/ directory.
cd lab5-src
gtar -xvzf lab5-test.tar.Z

You will get the files:
avl-dictionary2.cpp test-avl.cpp test-dict.cpp testall

Step 3. Prevent the file dictionary.h to be included multiple times.

In the file dictionary.h add the following at the top:

#ifndef DICTIONARY_H
#define DICTIONARY_H

and at the end of the file add

#endif

Step 4. Do the same for the other dictionary header files.

Do the same for the header files array-dictionary.h, bsearch-dictionary.h, hash-dictionary.h and avl-dictionary.h. Make sure that the defined identifiers change. For example, for array-dictionary.h use ARRAY_DICTIONARY_H and so on. This will eliminate the errors for multiple defined classes.

Step 5. Add new functions to the dictionary.h header file.

In the file dictionary.h add the following nes functions that will be used in testing:

      // Removes one element from the table
    virtual bool removeElement(KeyType key) = 0;

    // Returns all the elements in the table as an array of strings.
    // *n is the size of the table and it is returned by reference
    virtual KeyType * keys(int * n)=0;

Step 6. Also add these functions to the other dictionary header files

In the header files array-dictionary.h, bsearch-dictionary.h, hash-dictionary.h and avl-dictionary.h add the following defintions:

    // Removes one element from the table
    bool removeElement(KeyType key);

    // Returns all the elements in the table as an array of strings.
    // *n is the size of the table and it is returned by reference
    KeyType * keys(int * n);

Step 7. Add these functions to the dictionary .cpp files

In the file hash-dictionary.cpp add the following defintions.

// Removes one element from the table. Returns true if the key was found or false otherwise
bool
HashDictionary::removeElement(KeyType key)
{
    return false;
}

// Returns all the elements in the table as an array of strings.
// *n is the size of the table and it is returned by reference
KeyType *
HashDictionary::keys(int * n)
{-
    *n = 0;
    return NULL;
}

Also copy this code to array-dictionary.cpp, avl-dictionary.cpp, bsearch-dictionary.cpp. Remember to change HashDictionary to ArrayDictionary or to the name of the class defined in that file.

Step 8. Modify your Makefile to compile and run the tests

In the Makefile add the following marked in red:

all: search-engine test-dict test-avl

...

search-engine: search-engine.o minihttpd.o array-dictionary.o \
    hash-dictionary.o avl-dictionary.o avl-dictionary2.o bsearch-dictionary.o
    g++ -g -o search-engine search-engine.o minihttpd.o \
        array-dictionary.o hash-dictionary.o avl-dictionary.o avl-dictionary2.o\
        bsearch-dictionary.o -lnsl -lsocket

test-dict: test-dict.cpp array-dictionary.o \
    hash-dictionary.o avl-dictionary.o avl-dictionary2.o bsearch-dictionary.o
    g++ -g -o test-dict test-dict.cpp \
        array-dictionary.o hash-dictionary.o avl-dictionary.o avl-dictionary2.o \
        bsearch-dictionary.o

test-avl: test-avl.cpp avl-dictionary.o avl-dictionary2.o
    g++ -g -o test-avl test-avl.cpp avl-dictionary.o avl-dictionary2.o

avl-dictionary2.o: avl-dictionary.h avl-dictionary2.cpp
    g++ -g -c avl-dictionary2.cpp

...

clean:
    rm -f *.o minihttpd search-engine test-avl test-dict core

Step 9. Now type "make"

The search engine and the tests programs should be built. Fix any errors that you may still have to have a clean build.

Step 10. To run the tests only.

If you want to run all tests, you can type

testall

Also, you can run independent tests like:

test-dict array test1

that runs test1 using the array dictionary.

You can use "array" , "bsearch", "hash" or "avl. The tests are test1 to test6.

Also you can run "test-avl".

To pass all tests, you will need to implement the functions removeElement(..) and keys(..) in each dictionary.

Step 11. New functions in AVLDictionary are provided

We have provided two new functions in your AVLDictionary that can help you debugging:

AVLDictionary::print() that print the AVL tree and AVLDictionary::check() that checks the AVL tree and exits if there is an error.