Data Structures and Algorithms

Lab 5: Spell Checker

Due on Sunday, February 28th at 11:59 PM. This is a team lab. You and your assigned lab partner(s) will complete this lab together. Make sure that you are familiar with the Partner Etiquette guidelines. You may discuss the concepts of this lab with other classmates, but you may not share your code with anyone other than course staff and your lab partner(s). Do not look at solutions written by students other than your team. If your team needs help, please post on the Piazza forum or contact the instructor or ninjas. If you have any doubts about what is okay and what is not, it’s much safer to ask than to risk violating the Academic Integrity Policy.

Overview

In this lab, you will write a linked list data structure in C++. You will then write a program that uses the linked list to store a dictionary and spell-check the contents of a user’s file. Like the last team lab, your repository URL will be git@github.swarthmore.edu:cs35-s16/lab05-<team-name>. You can see a list of all of your repositories on the Swarthmore GitHub in the lower-right side of the main page; make sure to switch your view to the organization for this class to see them.

A significant part of the credit for this lab is assigned to the correctness of your linked list. For that reason, be sure to develop and test your linked list first before continuing to work on the main application.

Interface

This program will make use of both user input (from cin) as well as command-line arguments (from argc and argv). Initially, the user will launch the program like so:

./spellchecker dictionary.txt

When you do so, your program will open the dictionary and read each word it contains (line by line) into a list. Afterward, the program will present a main menu like the following:

Welcome to Spellchecker.
A) Add a word to the dictionary.
C) Check to see if a word is in the dictionary.
D) Delete a word from the dictionary.
S) Spellcheck a document.
W) Write the dictionary to its file.
X) Exit.
What do you want to do?

The following behavior is expected:

• The program will present this menu in a loop, continuing to ask the user for instructions and performing them.
• The user selects a menu option by typing the appropriate letter by itself in either upper or lower case. (Using >> to read a string is still your best move here.)
• For Add, Check, and Delete, the user simply types the word. The program should then take appropriate action:
  • For add, the word should be added to the list only if it’s not already in the list somewhere.
  • For check, the program should tell the user whether the word is in the list or not.
  • For delete, the program should remove the word from the list (or do nothing if it’s not there).
• For Write, the program will save the list of dictionary words to the originally-specified dictionary file, overwriting the original dictionary. The words should be stored one per line.
• If the user chooses Exit, then the program stops.
• For spellchecking, see below.

Spellchecking

When the user asks to spellcheck a document, your program must prompt the user for the name of a file, check each word in the file, and then save the corrected results to the same file. You should follow this algorithm:

1. Input the name of the file from the user.
2. Create a new, empty list to hold spellchecked words.
3. As long as there are words left in the input file 1. Read a word. 2. If it is correctly spelled, just add it to the list. 3. If it is not, prompt the user for an action to take. (See below.)
4. Write all of the words from your spellchecked word list back into the file that the user specified.

When you discover a word which is not in the dictionary, you should display a prompt that looks like this:

The word "broccolli" is not in the dictionary.
A) Add to the dictionary.
I) Ignore this word.
R) Replace this word with a different word.
What would you like to do?

As above, the user chooses one of these options by entering a letter in either upper or lower case.

If the user chooses to ignore the word, you should simply add it to your spellchecked words list. If the user chooses to add the word to the dictionary, you should add the word to the dictionary as well as your spellchecked words list. If the user chooses to replace the word, you should prompt for an appropriate replacement; then, add that replacement to your spellchecked words list instead of the original word.

Once you’ve spellchecked every word in the document, you will save those words back into the file; this will overwrite the original file with the corrected content. Afterwards, your program should return to the main menu. Note that the dictionary (as a list of words) may have been changed by the process of spellchecking. These changes should still be visible from the main menu.

Capitalization

We will assume for this assignment that capitalization is part of spelling. That is, if "birthday" is in your dictionary and "BiRtHdAy" is in the document, you should report this word as misspelled.

Reading Words

From previous labs, we’ve seen that ifstream skips spaces by default. If we do this, then we will be unable to preserve the spaces that are in the original document. If we use noskipws, then reading strings will not behave as we want. The process of reading words from a file while preserving whitespace is a bit tedious and tricky, so we’ve completed that portion for you. Some of your starter files (spellcheck.h and spellcheck.cpp) define a function read_word which accepts an ifstream and returns a string. The string it returns will be one of two things:

• A sequence of characters which is only comprised of upper- and lower-case ASCII letters.
• A sequence of characters which contains no upper- or lower-case ASCII letters.

For spellchecking purposes, we will treat a “word” which contains no letters as correctly spelled. This allows you to avoid thinking about symbols, numbers, and other non-alphabetic strings when spellchecking. To tell whether the string returned by read_word is an alphabetic word or not, just look at the first character. If it’s a letter (upper- or lower-case), then you should spellcheck it. Otherwise, pretend that it is correctly spelled and write it to the output file.

For instance, consider the following input:

I yelled, "Here!"

Multiple calls to the read_word function would return these strings in order:

• "I"
• " "
• "yelled"
• ", \""
• "Here"
• "!\""

The next call to the read_word function would set eof on the ifstream.

Getting Started

You will start with the following files in this lab:

• string_list.h: The header file for the StringList interface. Do not modify this file.
• linked_string_list.h/linked_string_list.cpp: The declaration/definition of the LinkedStringList class. You will need to implement both files.
• tests.cpp: The source file where you will put your tests for your linked list.
• spellcheck.h/spellcheck.cpp: The source file where you will write several functions pertaining to spellchecking. The read_word function is already implemented for you.
• program.cpp: The file containing the main function for the spellchecker.
• Makefile: The usual Makefile for compiling your code. There are two important targets: make (which builds the spellchecker) and make tests (which builds your tests).
• test_data/: A directory containing some data to use to test your spellchecker.

Testing

For this lab, you will only be required to test your LinkedStringList class. You should make sure to do so thoroughly. While it is possible to test a program that uses an interactive interface like this spellchecker does, such tests are a little more difficult to write.

Since your spellchecker will overwrite your test data when you run it, you need to be able to undo those changes to the test data files. You can do this by running the following command:

git checkout test_data/

Please be careful with that command, since running checkout on other files (like your source code) could likewise destroy all of the changes that you’ve made. To protect yourself, git commit and git push your changes every time you feel like you’ve made progress; that way, there’s a version on the Swarthmore GitHub that we can retrieve in case something goes wrong.

Requirements for LinkedStringList

To receive full credit for your LinkedStringList implementation, you must meet these requirements:

• Do not add any public methods to the LinkedStringList class which are not already given by the StringList interface. (You may add private methods to LinkedStringList if you want.)
• The LinkedStringList class should have only those fields which are necessary to make the class work.
• Your methods should be safe. That is, your list should be able to handle any sequence of calls in any order after it has been constructed. If the caller tries to do something illegal (like remove an item that isn’t there), your list should throw an exception like runtime_error.
• Your implementation must manage memory properly. We will run valgrind on your program and it should report no illegal accesses, no use of uninitialized memory, and no memory leaks.

Catching Exceptions

Your LinkedStringList methods like getItem or find should throw an exception if e.g. an item is requested which does not exist. In order to handle this, you may wish to catch that exception like so:

try {
    int position = my_list->find("please");
    cout << "The magic word was at position " << position << "." << endl;
} catch (std::exception& e) {
    cout << "Politeness error: magic word not found." << endl;
}
cout << "Finished!" << endl;

If a line in the try block throws an exception, then execution of the try block immediately stops. If the catch block catches the kind of exception that was thrown, then execution will start again inside of that catch block. (The catch keyword is much like the except keyword in Python.)

Testing Exceptions

To write a test that expects an exception to occur, you can give an expression to the CHECK_THROW macro of UnitTest++, our unit testing framework:

CHECK_THROW(my_list->get_item(8), std::exception);

The above check will fail if the method doesn’t throw an exception.

Coding Style Requirements

You are required to observe some good coding practices:

• You should pick meaningful variable names.

  // Good
  int* pixels = new int[size];
  // Bad
  int* p = new int[size];
  

• You should use correct and consistent indentation. Lines of code within a block (that is, surrounded by { and }) should be indented four spaces further than the lines surrounding them.

  // Good
  if (condition) {
      cout << "Test" << endl;
  }
  // Bad
  if (condition) {
  cout << "Test" << endl;
      }
  

• You should use a block whenever possible, even if it’s not necessary. This helps you avoid subtle or messy bugs in the future.

  // Good
  if (condition) {
      cout << "Something" << endl;
  }
  // Bad
  if (condition)
      cout << "Something" << endl;
  

• Any new methods or fields in your header files should have comments explaining their purpose and behavior. You are permitted to omit documentation for methods that are inherited from other classes; that is, if your class has a foo method because its superclass has a foo method, you don’t need to document that method.

  // Good
  public:
      /**
       * Saves this image object to a file.
       * @param file The already-open stream into which this image should be written.
       * @return The number of pixels in the saved image.
       * @throws runtime_error If the image could not be saved due to an I/O error.
       */
      int save(ofstream& file);
  
  // Bad
  public:
      int save(ofstream& file);
  

  Your method/field documentation does not have to be in the format above, but you must describe the method’s behavior, its parameters, its return value, and any exceptions that it may throw. (If you’re indifferent, the above syntax is a good one to know; it’s a de facto standard used by Javadoc, Doxygen, and other tools that automatically process source code comments into other formats like searchable webpages.)

Peer Review

As this is a team assignment, you are required to complete a peer review of your lab partner or partners. You must do this even if everything is fine. You should complete this peer review after you have turned in your assignment. The peer review comes in the form of a simple Google Form and can be accessed here; in most cases, it will likely take less than a minute to complete. If you have trouble accessing this peer review, please make sure that you are logged into Google using your Swarthmore credentials.

Your peer review will be kept private; only course staff will have access to this information. You can also update your peer review after you have submitted it. However, if you do not submit a peer review, you will lose points on your lab. Please don’t forget!

Summary of Requirements

When you are finished, you should have

• A completed implementation of LinkedStringList
• Tests for LinkedStringList
• A main function which allows the user to spellcheck documents and update dictionaries
• The ability to handle bad command-line arguments or user input
• No memory errors!
• Code which conforms to the style requirements above
• A completed peer review

Sample Run

The following is a sample run of a working implementation of this program. It illustrates many of the requirements described above, including error handling and robustness.

$ ./spellchecker
You must give one argument: a dictionary file.
$ ./spellchecker test_data/animal-dictionary.txt
Welcome to Spellchecker.

A) Add a word to the dictionary.
C) Check to see if a word is in the dictionary.
D) Delete a word from the dictionary.
S) Spellcheck a document.
W) Write the dictionary to its file.
X) Exit.
What do you want to do? c
Which word would you like to check? dog
That word is in the dictionary.

A) Add a word to the dictionary.
C) Check to see if a word is in the dictionary.
D) Delete a word from the dictionary.
S) Spellcheck a document.
W) Write the dictionary to its file.
X) Exit.
What do you want to do? c
Which word would you like to check? mouse
That word is not in the dictionary.

A) Add a word to the dictionary.
C) Check to see if a word is in the dictionary.
D) Delete a word from the dictionary.
S) Spellcheck a document.
W) Write the dictionary to its file.
X) Exit.
What do you want to do? a
Which word would you like to add? sheep
Added "sheep" to the dictionary.

A) Add a word to the dictionary.
C) Check to see if a word is in the dictionary.
D) Delete a word from the dictionary.
S) Spellcheck a document.
W) Write the dictionary to its file.
X) Exit.
What do you want to do? a
Which word would you like to add? cat
That word is already in the dictionary.

A) Add a word to the dictionary.
C) Check to see if a word is in the dictionary.
D) Delete a word from the dictionary.
S) Spellcheck a document.
W) Write the dictionary to its file.
X) Exit.
What do you want to do? d
Which word would you like to delete? hippo
Removed "hippo" from the dictionary.

A) Add a word to the dictionary.
C) Check to see if a word is in the dictionary.
D) Delete a word from the dictionary.
S) Spellcheck a document.
W) Write the dictionary to its file.
X) Exit.
What do you want to do? d
Which word would you like to delete? giraffe
That word was not in the dictionary.

A) Add a word to the dictionary.
C) Check to see if a word is in the dictionary.
D) Delete a word from the dictionary.
S) Spellcheck a document.
W) Write the dictionary to its file.
X) Exit.
What do you want to do? s
What file would you like to spellcheck? test_data/animal-document.txt
The word "Dog" is not in the dictionary.
A) Add to the dictionary.
I) Ignore this word.
R) Replace this word with a different word.
What would you like to do? a
Added "Dog" to the dictionary.
The word "Caat" is not in the dictionary.
A) Add to the dictionary.
I) Ignore this word.
R) Replace this word with a different word.
What would you like to do? r
What would you like to use instead? Cat
The word "Cat" is not in the dictionary.
A) Add to the dictionary.
I) Ignore this word.
R) Replace this word with a different word.
What would you like to do? a
Added "Cat" to the dictionary.
The word "dogg" is not in the dictionary.
A) Add to the dictionary.
I) Ignore this word.
R) Replace this word with a different word.
What would you like to do? r
What would you like to use instead? dog
The word "Capybara" is not in the dictionary.
A) Add to the dictionary.
I) Ignore this word.
R) Replace this word with a different word.
What would you like to do? i
Ignoring "Capybara".
The word "capibara" is not in the dictionary.
A) Add to the dictionary.
I) Ignore this word.
R) Replace this word with a different word.
What would you like to do? r
What would you like to use instead? capybara
The word "Pangolin" is not in the dictionary.
A) Add to the dictionary.
I) Ignore this word.
R) Replace this word with a different word.
What would you like to do? a
Added "Pangolin" to the dictionary.

A) Add a word to the dictionary.
C) Check to see if a word is in the dictionary.
D) Delete a word from the dictionary.
S) Spellcheck a document.
W) Write the dictionary to its file.
X) Exit.
What do you want to do? w
Wrote dictionary to test_data/animal-dictionary.txt.

A) Add a word to the dictionary.
C) Check to see if a word is in the dictionary.
D) Delete a word from the dictionary.
S) Spellcheck a document.
W) Write the dictionary to its file.
X) Exit.
What do you want to do? s
What file would you like to spellcheck? test_data/nonexistent-file.txt
Error while spellchecking the file test_data/nonexistent-file.txt

A) Add a word to the dictionary.
C) Check to see if a word is in the dictionary.
D) Delete a word from the dictionary.
S) Spellcheck a document.
W) Write the dictionary to its file.
X) Exit.
What do you want to do? x
Goodbye!
$ cat test_data/animal-dictionary.txt
Pangolin
Cat
Dog
sheep
capybara
pangolin
bear
fish
cow
dog
cat
$ cat test_data/animal-document.txt
Dog cat cat.  Cat dog.  Cat dog cow dog.  "Capybara", dog cow cow.  Dog cow dog dog cat capybara cat?

Pangolin
$