In this lab, you will implement a C++ linked list. You will then write a program that will load a dictionary into a linked list and perform basic operations on the dictionary. Your program will also have a feature which allows users to use your dictionary to check and correct spelling of documents.

To get started, run update35 from a computer science lab computer. The program update35 will create a cs35/labs/04 directory in your CS home directory, and the program handin35 will subsequently submit files from that directory.

You may choose one partner for this lab. Both partners should be present and working on the code together. You will both be responsible for understanding all concepts, so dividing and conquering is not an option. The academic integrity policy applies to the entire pair; you cannot work or share code with anyone outside of your partner. Also, be sure to indicate who your partner is by including both names at the top of your files and by also selecting the 'p' option when using handin35 for the first time. Only one student in the pair should submit the lab.

You will earn reasonable partial credit for this lab if you complete and test your linked list implementation. So be sure to work in a modular fashion, testing and completing your linked list first before implementing the main program

Here, I list the requirements for each major component of the lab. See the IMPLEMENTATION STRATEGY section below for hints on how to begin attacking the problem.

You have been given the following files (blue indicates you will need to modify/implement in this file):

• stringList.h - the StringList interface. This file should not be modified
• linkedStringList.h, linkedStringList.cpp - the declaration and definition of the LinkedStringList class. You will need to implement both files.
• testStringList.cpp - a partially completed test file for the LinkedStringList class. You will need to implement your tests here. You should include tests for each aspect of your LinkedStringList class as you implement it.
• spellCheck.cppthe main program for loading/modifying a dictionary and doing the spell checking. This has been started for you; implement a main while loop here and handle any necessary cleanup after the loop finishes. Most of the functions you will call should be define in...
• spellCheckHelper.h, spellCheckHelper.cpp - where the majority of your functionality will be implemented. Note that this (like ppmHelper.h/.cpp from Lab 1) is not a class, but a file of function declarations and definitions.
• Makefile - use to compile your code. You will need to modify this once you want to test your LinkedStringList.
• input/ a directory containing a few sample documents to spell check.
• dict/ a directory containing a few simple dictionaries.

StringList

I have provided a StringList interface. It is very similar to the interface given in lecture, but adds two additional methods that will be needed for this lab. search takes a string value and returns the index of the first occurence in the list (or -1 if value is not in the list). deleteItem deletes the ith element of the list.

You must define and implement a LinkedStringList class that implements the StringList interface, without altering the StringList interface.

LinkedStringList (and its Requirements)

Begin by thinking about your methods in pseudocode, and then implement them one-by-one. Some requirements to note:

• You should not add any extra public methods to the LinkedStringList interface than what is already specified in the StringList interface.
• You may, however, add as many private methods as you desire.
• The class should only contain variables necessary for maintaining the linked list.
• Your methods should be safe. That means that it should not rely on a user of the class to avoid making mistakes, such as removing a non-existent item. In the case that the class-user attempts something illegal, you should throw a runtime_error with a descriptive message (see the ArrayStringList implementation from class---provided in cs35/class/04/stringList directory -- and the Tips and Hints section below).
• Your implementation must manage dynamic memory allocation properly. No memory leaks!

testStringList

You must modify your testStringList.cpp file to make sure your LinkedStringList implementation is working. The ninjas will ask you to show your test file to help you with errors.

Main SpellCheck Program (and its requirements)

Once you have thoroughly tested your LinkedStringList implementation, you should implement the main program. This program has been started for you. To keep the program clean, we divided the main program into three files, similar to what you had for Lab 1. spellCheck.cpp only contains the main loop. Modify this to get it working, but any large implementation details belong in the helper files. Those details should use good top-down design (e.g. one function per feature). Any functions should be declared and defined in spellCheckHelper.h/.cpp respectively. We provided getChoice() for you as an example. To complete the main program:

• Begin by finishing loadDictionary which loads the dictionary from a file. The dictionary should contain a series of words separated by white space. Each word in the file will be treated as a legal word in the dictionary.

Take a look at getChoice() to see what options the user has. You should implement each option appropriately in the main while loop. These include:

• (0) Exit
• (1) Add Word -- ask user for word to add to the dictionary
• (2) Remove Word -- ask user for word to remove from the dictionary
• (3) Check Word -- ask user for word; check to see if that word is in the dictionary
• (4) Spellcheck document -- ask user for document, then spell-check it, interacting with user when words are not in the dictionary. (see below for details)

When a user spell-checks a document, you should ask the user for a document, load that document into a List, and then check the spelling of the words one-by-one. When a word does not appear in the dictionary, you should tell the user, then present three options

• (1) add the word to the dictionary. For the rest of the document, treat this word as if it is in the dictionary.
• (2) ignore the word. Don't add the word to the dictionary, but also don't change the word.
• (3) correct spelling. If this option is selected, let the user manually type corrections.

By the end of the spell-check, the original file should now contain the same text, but with the spelling mistakes corrected. A couple pointers when implementing these methods:

• Do not try to read in your document and make corrections simultaneously. Writing to the same file you are reading from causes problems with the file streams. Instead, read the entire document in first. (if only there was some data structure that let you store all of the words in the document in an ordered fashion...) Then, iterate through the document, making corrections and writing words back to the file one-by-one.
• Handling cases and punctuation can be a bit tricky. Your program should be able to handle cases and some rudimentary punctuation. For cases you cannot handle, you should treat the string as a word not in the dictionary, and allow the user to ignore it or make corrections. For example, you should not expect isn't or cat's to be in the dictionary, but it is easy to see that these are legal words. You should let the user choose to ignore them. At a minimum, you should be able to handle the following punctuation:
  • periods and commas
  • quotations at the start or end of a word
  For example, if your document contains The quick brown fox jumped over the lazy toad. your spell-checker should read "toad." from the file as a word and be able to understand that toad is in the dictionary. See the hints below for handling punctuation.
• If (3) is selected, you should make the correction the user typed in, but still spell-check this new word.

You should always program incrementally such that you can test your work as you go. Here is one suggested strategy:

1. Begin by declaring the LinkedStringList class in linkedStringList.h. Remember that you must declare all data members and at least all methods specified in the StringList interface before proceeding.
2. Start implementing your class in linkedStringList.cpp I suggest stubbing all functions (that is, defining the function and giving a dummy return value). This will let you compile the class properly without having done any actual implementation. An example function stub is:

   /* getItem - returns the value for the ith item in the list
    * @param i, an int for the index of the string to return
    * @return a string containing a scene from the list
    */
   string LinkedStringList::getItem(int i) {
     //TODO: implement this
    
     return "EXAMPLE WORD";
   }
   

3. Check to see if your class compiles, fix any errors before proceeding. Now, begin implementing one method at a time. I suggest starting with insertAtHead or insertAtTail. Your procedure should be: implement one method, compile, and then test it in testLinkedList.cpp
4. Implement the destructor last. Carefully consider every possible way that your class might allocate memory on the heap, and be sure that there is a corresponding call to delete for each call to new.

At this point you should have a complete working LinkedStringList class, as well as a very thorough testStringList program.

You should not under any circumstances begin the spell check implementation until you have thoroughly verified the correctness of your LinkedStringList class. Any bugs in your LinkedStringList class will hinder progress on the main program. Begin working on spellCheck.cpp by implementing and testing one feature of the program at a time. Be sure that your solution follows good design/modularity guidelines.

Throwing and Handling Exceptions

Your linked list should handle invalid usage by throwing a runtime_error. There is an example in the ArrayStringList implementation from class. For example, if you may want to handle an attempt to get an invalid item:

throw std::runtime_error("Attempt to get out of bounds item");

Here is an example of handling a runtime_error (not required in this lab):

try{
  //do something dangerous
} catch (runtime_error& exc){
  cerr << "Warning: " << exc.what() << endl;
  cerr << "Ignoring illegal behavior." << endl;
}

Don't forget to include the stdexcept library when handling or throwing exceptions.

Handling Upper Case Letters

All of the words in your dictionary will be lower case. It will be nice to be able to spell-check, say, the first word in a sentence without losing the case. One way to do this is to store the word from the document as is, but search for a lower-case version of the word in the dictionary. To do this, you'll need a function that converts a string to lower case. Here is one such implementation:

string lower(string word) {
  string toReturn = "";
  for(int i = 0; i < word.length(); i++){
    toReturn += tolower(word[i]);
  }
  return toReturn;
}

Handling Punctuation

I recommend handling punctuation in the same way. Store each "word" without removing punctuation, but strip this away when checking for the word in the dictionary. For example, the following code removes possible periods from the end of a word.

string stripPunctuation(string word) {
  string toReturn = word;

  if(toReturn[len-1] == '.')) {
    toReturn.erase(len-1);
  }

  return toReturn;
}

The following illustrates how your main program might operate:

$ more q.txt 
The quick broown fox jumps over the lazy dog.
$ ./spellCheck 
Enter dictionary name, or "sowpods" for scrabble dictionary: sowpods

Loading /usr/local/doc/sowpods.txt...
Dictionary Loading Complete
Dictionary contains 267752 words.

(0) Exit
(1) Add word
(2) Remove word
(3) Check word
(4) Spellcheck document

Enter Choice: 1

What word do you want to add? oogabooga

(0) Exit
(1) Add word
(2) Remove word
(3) Check word
(4) Spellcheck document

Enter Choice: 3

Enter the word you want to check: oogabooga
oogabooga is in the dictionary.

(0) Exit
(1) Add word
(2) Remove word
(3) Check word
(4) Spellcheck document

Enter Choice: 2

What word do you want to remove? oogabooga

(0) Exit
(1) Add word
(2) Remove word
(3) Check word
(4) Spellcheck document

Enter Choice: 3

Enter the word you want to check: oogabooga
oogabooga is NOT in the dictionary.

(0) Exit
(1) Add word
(2) Remove word
(3) Check word
(4) Spellcheck document

Enter Choice: 1

What word do you want to add? bear
Warning: bear is already in the dictionary!

(0) Exit
(1) Add word
(2) Remove word
(3) Check word
(4) Spellcheck document

Enter Choice: 4

Enter name of file to spell check: input/q.txt
[broown] is not in the dictionary.
What do you want to do?
  (1) add broown to dictionary.
  (2) ignore word
  (3) correct spelling
3
Enter correction now
brown

(0) Exit
(1) Add word
(2) Remove word
(3) Check word
(4) Spellcheck document

Enter Choice: 4

Enter name of file to spell check: input/gettysburg.txt
[battle-field] is not in the dictionary.
What do you want to do?
  (1) add battle-field to dictionary.
  (2) ignore word
  (3) correct spelling
1
[--] is not in the dictionary.
What do you want to do?
  (1) add -- to dictionary.
  (2) ignore word
  (3) correct spelling
2
[--] is not in the dictionary.
What do you want to do?
  (1) add -- to dictionary.
  (2) ignore word
  (3) correct spelling
2
[--] is not in the dictionary.
What do you want to do?
  (1) add -- to dictionary.
  (2) ignore word
  (3) correct spelling
1

(0) Exit
(1) Add word
(2) Remove word
(3) Check word
(4) Spellcheck document

Enter Choice: 0

Goodbye!
$ more input/q.txt
The quick brown fox jumps over the lazy dog. 

Note that the input file q.txt now has no spelling mistakes.

Once you are satisfied with your program, hand it in by typing handin35 at the unix prompt.

You may run handin35 as many times as you like, and only the most recent submission will be recorded. This is useful if you realize after handing in some programs that you'd like to make a few more changes to them. Only one partner should hand in the code for the lab.