CMPT-225 Assignment3

Dictionary.

Due on Monday March 31st, at 23:59.

 

Problem Statement

 

You are required to implement a dictionary application. There are two options, either implement the dictionary  using a binary search tree ADT and receive up to 70% of the total mark or implement it using the 2-3-4 or 2-3 tree ADT and receive up to 120% (i.e 20% bonus).

 

Your program must provide its operations through the following menu (important: implement the menu exactly as below. It makes it easier for the TA to mark the assignments).

 

f) find the meaning of a word.

i) insert and entry.

d) delete an entry.

p) print all the entries.

s) save the contents of the dictionary in an output file.

l) load the dictionary from an input file.

Choose one of the following options please:

 

A dictionary entry is a pair of (word, meaning). Both word and its meaning are one-word strings. The dictionary must be implemented as case insensitive. This means that “word”, “WORD”, “Word”, “WoRd” must be treated as if they are all the same. The easiest way to get around this it to first convert any input string to lower case and then work with it. For instance when the user inserts an entry in the dictionary, fist convert the entered strings to lower case and the insert them in the tree.

 

Find option:

The user enters a word and the program searches the dictionary and if it exists, prints the meaning of the word, otherwise prints:

Word not found.

 

Inset option:

The user first enters a word and if the word does not exists in the dictionary, the programs asks the user the enter the meaning of the word and inserts the entry in the dictionary. If the word exists in the dictionary the program must print:

The word you entered already exists in the dictionary.

 

Delete option:

The user enters a word and the program searches the dictionary and if it exists, delete the corresponding entry, otherwise prints:

Word not found

 

Print all the entries:

Upon selecting this option the program must print all the entries in the dictionary sorted based on the word. The program will print each entry on a separate line (see below for an example):

 

absent missing

bake cook

fold bend

…

 

Save:

Upon selecting this option the program must write the entries in the dictionary according to the pre-order traversal of the tree into an output file called “dictionary.txt”. Each line of the file contains one entry of the dictionary.

 

Load:

Upon selecting this option the program reads the entries in the file “dictionary.txt” and insert them into the dictionary.

 

Implementation

 

The implementing of the tree ADT must be such that it can could hold any object that extends a KeyedItem class. The KeyedItem is a class that contains the search key as a data field.

 

public abstract class KeyedItem <KT extends Comparable <? super KT>>{

      private KT searchKey;

      public KeyedItem (KT key){

            searchKey = key;

      }

      public KT getKey(){

            return searchKey;

      }

}

 

You can declare a class for the dictionary items that extends the KeyedItem class as follows:

 

public class dictionaryItem extends KeyedItem<String>{

      private String meaning;

      public dictionarItem (String w, String m){

            super(w); //calling the constructor of KeyedItem;

            meaning = m;

      }

      public String getMeaning(){

            return meaning;

      }

}

 

Then the ADT TwoThreeFourTree ADT can be implemented as follows:

 

public TwoThreeFourTreeNode <T>{

       private T small, middle, large;

       private TwoThreeFourTreeNode<T> firstChild, secondChild, thirdChild, forthChild;

       ….

}

 

public TwoThreeFourTree <T extends KeyedItem <KT>, KT extends Comparable <? super KT>> {

       private TwoTreeNode <T> root;

       public void inset (T newItem){

              ….

       }

       public void delete (KT searchKey) throws TreeException {

              ….

       }

}

 

Specific Requirements

 

· For Java programmers: You must name your main class (the class with the main method) dictionary.java.

 

Important Remarks

 

It’s very important that you make sure your program compiles without any problem  (you may get 0 if your program didn't compile-see the submission section below).

Make sure that your input and output file format is exactly the same as the requirement stated previously (see the display information option).

 

Submission

 

Submit your source files only (for java users: *.java and for c++ users: *.cpp and *.hpp or *.h). You can use any compiler that you want but you need to make sure that your program will compile under the Linux. It’s easy, create a directory called src and copy all your source files in it then in a Linux shell type javac dictionary.java for compiling your program and java dictionary for running your program. For c++ user you need to run g++ *.cpp –o dictionary command to compile your program and then ./dictionary to run it. If you are writing in Java this should work without any problem however, your c++ source files from some compilers (for instance Visual C++) may not directly compile in Linux. Drop by my or your TA’s office hours if you have difficulty compiling in Linux. Zip all your source files in the src directory and submit it.