Overview

This lab asks you to implement a dictionary library via a dynamically allocated linked list of strings. But the program surrounding it is more rudimentary than last week. Instead, it should be tested via a shell script -- which is also to be turned in for grading.

The Dictionaries

The "dictionary" that serves as this lab's main data structure is conceptually the same as last week -- but this time implemented using a linked list. As a result, there should be no periodic grow().

Please use the following type for the dictionary:

  typedef struct {
    linkedlist *wordList;
    unsigned long count;
  } dictionary;
  

The dictionary should be implemented as a library and, as such, should make use of appropriately named and configured .c and .h files.

The dictionary should support the following operations:

• initDict(...) -- Create and initialize an empty dictionary. Think carefully about what the single argument to this method should be. This method should allocate the entire dictionary -- including the struct. Be careful here.

  This method should return a 0 on success and non-0 on failure.
  
  

• destroyDict(...) -- Frees all of the dictionary's dynamically allocated memory -- the linked list, the individual words -- and the dictionary struct, itself.

  This method should return a 0 on success and non-0 on failure.
  
  

• addWordDict(...) -- Accepts a word, represented as a char * and add it to the dictionary, which should be passed by reference.

  Your initial implementation should probably be via adding new words at the head. But, for your final version, you should maintain the list in sorted order using an insertion sort.

  This method should return a 0 on success and non-0 on failure.
  
  

• removeWordDict(...) -- Accepts a word, represented as a char * and removes it from the dictionary, which should be passed by reference.

  This method should return a 0 on success and non-0 on failure.
  
  

• verifyWordDict(...) -- Accepts a word, represented as a char * and searches the dictionary, passed by reference, for it. If found, this method returns 0. If not found, this method returns 1.
  
  
• getWordDict(...) -- Accepts an integer representing the index of the word in the dictionary, from the 0th word - the (N - 1)th word. The requested word is communicated to the caller via an argument. Returns 0 upon success and non-0 if the index is out of bounds.
  
  

The Linked List

You should implement a linked list data structure similar to the one we began in class. You may not use anyone else's source or library code here. And, yes, it should be generic. Really, why not?

Main Program

Your main program should be very rudimentary. It should provide the user with a prompt, dictionary> and accept the following commands add, remove, query, dump, reset, and quit:

• dictionary>add word
  Adds the specified word to the dictionary. Reports "success" upon success and "unable", if the word is already there.
  
  
• dictionary>remove word
  Removes the specified word from the dictionary. Reports "success" upon success and "unable", otherwise.
  
  
• dictionary>query word
  Verifies that the specified word is present within the dictionary. Reports "success" upon success and "unable", otherwise.
  
  
• dictionary>dump outputFile
  Dumps the contents of the dictionary, one word per line, into the prescribed file. Reports "success" upon success and "unable", if the file cannot be opened with the correct mode or if any write fails.
  
  
• dictionary>reset
  Deallocates all space associated with the dictionary, including the underlying linked list and then reinitializes it. Reports "success" upon success and "unable", otherwise.
  
  
• dictionary>quit
  The dictionary's main program is normally an endless loop. It displays the prompt, takes action, and redisplays the prompt. "quit" causes all allocated storage assocaited wtih the dictionary to be freed and the program to exit.
  
  

The Shell Script Test Driver

You should write a shell script to exercise your dictionary. It should, at the very least, do the following:

• Add every word from a supplied input dictionary file to the in-memory dictionary. Verify the success by dumping the in-memory dictionary and comparing it to the original input file. Report the success or failure of the test to the console.

  The input dictionary file should be supplied as the first command line argument to this script. The dump file should be temporary and "cleaned up".
  
  

• Verify every word from a supplied input query file against the in-memory dictionary. Verify the success by checking the messages reported by the main program. Report the success or failure of the test to the console.

  The query file should be supplied as the second command line argument to this script.
  
  

• Remove every word from a supplied input file from the in-memory dictionary. Verify the success, in part, by dumping the in-memory dictionary and comparing it to the original input file.

  Also verify success, by checking to make sure that those words from your original query file that are present can still be found and those that were removed cannot be found. Yes, this does imply that you should remove some, but not all, of the entries from your query file.

  Report the success or failure of the test to the console.
  
  

• Reset the dictionary and verify that it works, in part, by dumping the dictionary to a tempory file. Don't forget to clean up this file.

  And, in part, verify that it works by recreating and retesting the dictionary, this time with special-case tests of your design. You may accept input via files specified by additional command line arguments -- but the script should not become interactive. In other words, don't accept input directly from the user.
  
  

• Verify that quit works by exiting the dictionary and checking that the return code is 0.
  
  

The output of the test driver should print, before a test begins, a very short description of the test, followed by a :-colon, followed by one space, followed by "success" or "fail". Each test should be reported on a separate line. For example:

  Add words:    success
  Verify words: success
  Remove words: failure
  

Code organization and Coding Practices

All aspects of the program, including the script, should satisfy the various code organization and coding practices that we've developed within class.

We're Here To Help!

As always -- remember, we're here to help!