CS 112 Project 5: List Operations

Objectives:

  1. Build more List operations.
  2. Practice using pointers.
  3. Practice using the debugger (if necessary).

Introduction

This week's project is a team project to add more functionality to the List class we built in this week's lab. To illustrate, suppose that list1, list2, and list3 are List objects containing the following values:

   list1 == {11, 22, 33}
   list2 == {11, 22, 33}
   list3 == {}        // the empty list
  1. Equality. An expression like:
       list1 == list2
    should return true; an expression like:
       list1 == list3
    should return false.
  2. Inequality. An expression like:
       list1 != list2
    should return false; an expression like:
       list1 != list3
    should return true.
  3. Stream Input. The expressions:
  4.   list3.readFrom(cin);
    or
      list3.readFrom(fin);
    should erase any items currently in list3, and then read an arbitrary number of values from cin or fin, appending each value to list3. If there are no items on the line, then list3 should be an empty list when the method is finished. This method should read the character that follows each value, and halt when that character is the newline ('\n') character. In other words, this method should assume that all values to be read into the list are on the same line. You may find the basic_istream class's peek() method to be useful for determining when the next character is a newline character.
  5. Stream Output. The expressions:
      list1.writeTo(cout, " ");
    or
      list1.writeTo(fout, "\t");
    should write the values of list1 to cout with the items preceded by spaces, or fout with the items preceded by tabs. Your method should allow the user to pass whatever separator-string they wish to use.

  6. File Input. The expression:
      list3.readFrom(fileName);
    should empty list3 of any items it currently contains, and then fill list3 with values stored in fileName. This method should assume that fileName contains only values; it should continue reading and appending values to the List until end-of-file is reached.
  7. File Output. The expression:
       list1.writeTo(fileName, "\n");
    should write all of the values in list1 to the file named by fileName, with each item on a separate line of the file. Your method should let the user pass whatever separator-string they wish to use.
  8. Prepend. The expression:
       list2.prepend(-1);
    should change list2 as follows:
       list2 == {-1, 11, 22, 33}
    The operation aList.prepend(it) thus inserts it at the beginning of aList.
  9. Searching. The statement:
       int index = list1.getIndexOf(22);
    should set index to 1, because if our List were an array, 1 is the index at which 22 would reside. More generally, the operation aList.findIndexOf(it); should start at the beginning of the list, and return the index of the first occurrence of it. If it is not present in aList, this operation should return -1.
  10. Insertion. If list2 is as we just left it, the expression:
    list2.insert(0, 1);
    should insert the value 0 into list2 at index 1:
    list2 == {-1, 0, 11, 22, 33}
    More generally, the operation aList.insert(it, index) should insert item it into aList at index index. If index is negative or zero, insertion should occur at the front of the list; if index is greater than or equal to the size of the list, insertion should occur at the end of the list.
  11. Deletion. If list2 is as we just left it, the expression
    Item it = list2.remove(0);
    should remove the node at index 0 and return its Item (-1 in this case):
    list2 == {0, 11, 22, 33}
    More generally, the operation aList.remove(index) should remove the item at index index in aList, reclaiming its Node's dynamic storage, and returning the Item at that index. If index is negative or zero, the first Node in the list should be removed and its Item returned; if index is greater than or equal to the size of the list, the last Node in the list should be removed and its Item returned.

As indicated on the grade sheet, different members of your team are responsible for different operations. See me for the teams for this project. The person responsible for a given operation is also responsible for building a test-method for that operation. (Alternatively, you may if you wish write the test-cases for your team-mate's operations (and vice versa); just indicate in your test-classes who did what.) A part of your grade will be based on the thoroughness of your tests; you may want to use model your tests after those provided for you in previous projects.

I strongly encourage you to "design" your operations by drawing a diagram of what you want to have happen, showing the data structure before your operation is performed and then showing how it has changed after your operation has been performed. Once you have a diagram of what you want to happen, you are more likely to write code that actually does the right thing. (Lists and pointers are not something you can get right by trial and error.) Be careful to watch out for "special cases" (like empty vs. non-empty Lists).

If you get to the point where you cannot figure out what is wrong, use the debugger! The debugger is your friend when it comes to finding bugs in Lists and pointers.

Template. When you have "finished" your List class, convert it to a List<Item> template and modify the tests in ListTester to test your new template.

Preparing to Submit

Create a script file in which you use ls to list all your project's files, use cat to display the contents of each file, and build+run your project to demonstrate that it works correctly. Make certain that your script file is located in your project folder.

Our grader will grade your submission based on the categories given in this grade sheet, so you should make certain all of those categories are covered.

Submit


CS > 112 > Projects > 05


This page maintained by Joel Adams.