Build Dictionary ADT using Binary Search Tree in C.

The Dictionary ADT The Dictionary ADT maintains a set of pairs whose members are called key and value, respectively. A state of this ADT is a set (possibly empty) of such pairs. In general, key and value can be of any type. You will build a flexible version of the Dictionary in which these types are defined as macros in the header the file Dictionary.h. Think of the key as being some kind of identifying information, such as an account number, and the value as being data associated with that account. With this model in mind, a Dictionary usually enforces the constraint that no two distinct pairs may have the same key. There are other situations however (like the Lex module in this project) in which it is useful to relax this constraint. Your Dictionary constructor will contain a switch that determines whether or not it will accept duplicate keys. The main Dictionary ADT operations are lookup(k): If a pair with key exists in the Dictionary, return the associated value. Otherwise return nil. insert(k, v): Add a new pair to the Dictionary. Pre: (depending on switch) No pair with key exists. delete(k): Remove a pair with key from the Dictionary. Pre: A pair with key exists.

Also build Lex.c. The top level client in this project will be called Lex.c, and its operation will be exactly as described in pa1. Most of the code you wrote for Lex.c in pa1 can be re-used. In particular, the code for reading lines from the input file, and storing those lines in a string array can go through unchanged. It will be up to you to figure out how to use the Dictionary ADT to accomplish the task of printing out the unsorted array in sorted order. (Hint: study the example DictionaryClient.c which is posted on the webpage.)

Here is Lex.c from previous program for a doubley linked list:

//-----------------------------------------------------------------------------------------------------------------------

#include

#include

#include

#include "List.h"

#define MAX_LEN 250

typedef char *string;

int main(int argc, char *argv[])

{

if (argc != 3)

{

printf("Usage: %s

", argv[0]);

exit(1);

}

FILE *in, *in1, *out;

int count = 0;

int i, j, cp;

int lines = 0;

char line[MAX_LEN];

char tokenBuffer[MAX_LEN];

/*checking for correct number of args*/

/*open files for reading and writing*/

in1 = fopen(argv[1], "r");

out = fopen(argv[2], "w");

if (in1 == NULL)

{

printf("Unable to open file %s for reading ", argv[1]);

exit(1);

}

if (out == NULL)

{

printf("Unable to open file %s for writing ", argv[2]);

exit(1);

}

/*count number of input lines*/

while (fgets(tokenBuffer, MAX_LEN, in1) != NULL)

{

lines++;

//printf("%s ", tokenBuffer);

}

string lineArray[lines];

/*closes file buffer and reopens it*/

fclose(in1);

in = fopen(argv[1], "r");

if (in1 == NULL)

{

printf("Unable to open file for reading. ", argv[1]);

exit(EXIT_FAILURE);

}

/*fills the string array with lines from input file*/

while (fgets(line, MAX_LEN, in) != NULL)

{

i = strlen(line) + 1;

lineArray[count] = malloc(sizeof(char) * i);

strcpy(lineArray[count], line);

count++;

}

/*goes through array of the lines inserted above in lex order*/

List lineofList = newList();

append(lineofList, 0);

/*loop to go through array*/

for (j = 1; j < lines; j++)

{

set(lineofList, 0);

for (i = 0; i < length(lineofList); i++)

{

/*gets the appropriate place in list*/

set(lineofList, i);

string tmp = lineArray[get(lineofList)];

cp = strcmp(lineArray[j], tmp);

if (cp < 0)

{

insertBefore(lineofList, j);

break;

}

/*if reached the end of list append*/

else if (i == length(lineofList) - 1)

{

append(lineofList, j);

break;

}

}

}

/*prints from the list*/

for (set(lineofList, 0); index(lineofList) != -1; moveNext(lineofList))

{

fprintf(out, "%s", lineArray[get(lineofList)]);

}

/*frees the memory space for array*/

for (j = 0; j < lines; j++)

{

free(lineArray[j]);

}

freeList(&lineofList);

/*close files*/

fclose(in);

fclose(out);

return (0);

}

Here is the header file for Dictionary ADT below:

//----------------------------------------------------------------------------- // Dictionary.h // Header file for Dictionary ADT storing (key, value) pairs of types KEY_TYPE // and VAL_TYPE. //----------------------------------------------------------------------------- #include #include #include #ifndef DICTIONARY_H_INCLUDE_ #define DICTIONARY_H_INCLUDE_ #define KEY_TYPE char* #define VAL_TYPE int #define KEY_UNDEF NULL #define VAL_UNDEF -1 #define KEY_FORMAT "%s" #define VAL_FORMAT "%d" #define KEY_CMP(x,y) strcmp((x),(y)) // Exported type -------------------------------------------------------------- typedef struct DictionaryObj* Dictionary; // Constructors-Destructors --------------------------------------------------- // newDictionary() // Creates a new empty Dictionary. If unique==false (0), then the Dictionary // will accept duplicate keys, i.e. distinct pairs with identical keys. If // unique==true (1 or any non-zero value), then duplicate keys will not be // accepted. In this case, the operation insert(D, k) will enforce the // precondition: lookup(D, k)==VAL_UNDEF Dictionary newDictionary(int unique); // freeDictionary() // Frees heap memory associated with *pD, sets *pD to NULL. void freeDictionary(Dictionary* pD); // Access functions ----------------------------------------------------------- // size() // Returns the number of (key, value) pairs in Dictionary D. int size(Dictionary D); // getUnique() // Returns true (1) if D requires that all pairs have unique keys. Returns // false (0) if D accepts distinct pairs with identical keys. int getUnique(Dictionary D); // lookup() // If Dictionary D contains a (key, value) pair whose key matches k (i.e. if // KEY_CMP(key, k)==0), then returns value. If D contains no such pair, then // returns VAL_UNDEF. VAL_TYPE lookup(Dictionary D, KEY_TYPE k); // Manipulation procedures ---------------------------------------------------- // insert() // Insert the pair (k,v) into Dictionary D. // If getUnique(D) is false (0), then there are no preconditions. // If getUnique(D) is true (1), then the precondition lookup(D, k)==VAL_UNDEF // is enforced. void insert(Dictionary D, KEY_TYPE k, VAL_TYPE v); // delete() // Remove the pair whose key is k from Dictionary D. // Pre: lookup(D,k)!=VAL_UNDEF (i.e. D contains a pair whose key is k.) void delete(Dictionary D, KEY_TYPE k); // makeEmpty() // Reset Dictionary D to the empty state, containing no pairs. void makeEmpty(Dictionary D); // beginForward() // If D is non-empty, starts a forward iteration over D at the first key // (as defined by the order operator KEY_CMP()), then returns the first // value. If D is empty, returns VAL_UNDEF. VAL_TYPE beginForward(Dictionary D); // beginReverse() // If D is non-empty, starts a reverse iteration over D at the last key // (as defined by the order operator KEY_CMP()), then returns the last // value. If D is empty, returns VAL_UNDEF. VAL_TYPE beginReverse(Dictionary D); // currentKey() // If an iteration (forward or reverse) over D has started, returns the // the current key. If no iteration is underway, returns KEY_UNDEF. KEY_TYPE currentKey(Dictionary D); // currentVal() // If an iteration (forward or reverse) over D has started, returns the // value corresponding to the current key. If no iteration is underway, // returns VAL_UNDEF. VAL_TYPE currentVal(Dictionary D); // next() // If an iteration (forward or reverse) over D has started, and has not // reached the last pair, moves to the next key in D (as defined by the // order operator KEY_CMP()), and returns the value corresponding to the // new key. If an iteration has started, and has reached the last pair, // ends the iteration and returns VAL_UNDEF. If no iteration is underway, // returns VAL_UNDEF. VAL_TYPE next(Dictionary D); // prev() // If an iteration (forward or reverse) over D has started, and has not // reached the first pair, moves to the previous key in D (as defined by the // order operator KEY_CMP()), and returns the value corresponding to the // new key. If an iteration has started, and has reached the first pair, // ends the iteration and returns VAL_UNDEF. If no iteration is underway, // returns VAL_UNDEF. VAL_TYPE prev(Dictionary D); // Other operations ----------------------------------------------------------- // printDictionary() // Prints a text representation of D to the file pointed to by out. Each key- // value pair is printed on a single line, with the two items separated by a // single space. The pairs are printed in the order defined by the operator // KEY_CMP(). void printDictionary(FILE* out, Dictionary D); #endif