CS 24, Fall 2016

Programming Assignment 4

Due: Sunday, November 6, 11:59pm
Worth: 100 points

PA4 can be done either in two-people teams or individually.

If you are working with a partner, be sure that both partners' names are in a comment at the top of the source code file, and that you properly form a group for this project in the submit.cs system.

Copies of all necessary files either can be downloaded from the links below, or you can access them from your CSIL account by copying all eight files in the directory named ~cs24/pa4/ of the class account.
  1. [10 points] Implement the function list_piece described in Self-Test Exercise 24 on page 258 of the text as specified below. This step is partly to get you started using the basic node class and the text's linked list toolkit, but it also will provide you a useful tool to use in the next step.
    • Complete listpiece.cxx by implementing the function specified in listpiece.h.
    • Test your implementation with piecetest.cxx. Make sure you have copies of all necessary files in your working directory: listpiece.h, listpiece.cxx, piecetest.cxx, node1.h and node1.cxx. Then compile and run as follows: 
      g++ -o piecetest piecetest.cxx listpiece.cxx node1.cxx
./piecetest
      Ensure your results exactly match these piecetest results before continuing to the next step.
  2. [90 points] Implement one more version of class sequence, this time using a linked list. Your implementation must be in a new file that you create named sequence3.cxx.
    • Type your name(s) and the date in a comment at the top of sequence3.cxx.
    • Implement each of the member functions (including both constructors, the destructor and the assignment operator) of class sequence, as they are defined in sequence3.h.
    • Be sure to #include "sequence3.h" (which already includes node1.h), and if you choose to use your list_piece function from Step 1, then #include "listpiece.h" too. Our solution also included <cassert> for asserting the preconditions of advance, current and remove_current, and <cstdlib> to use NULL where necessary.
    • Your implementation should be defined in (or at least use) namespace main_savitch_5.
    • We suggest you refer to both the textbook's implementation of the bag class using a linked list (bag3) in section 5.3, as well as the authors' discussion of this specific project in section 5.4.
  3. Compile and test your programs at CSIL. To test sequence3.cxx you can use the same interactive test program you used for PA2 and PA3. Here is a copy of sequence_test.cxx that already has the required changes. After you know your implementation can pass basic tests, run all six of the tests from the non-interactive test program that will be used by submit.cs to score your work: sequence_exam3.cxx. Run it by giving a test number between 1 and 6 as a command line argument. For example, the following commands demonstrate compiling this non-interactive program with all of its parts, and then running test5 with it: 
    g++ -o sequence_exam3 sequence3.cxx sequence_exam3.cxx node1.cxx listpiece.cxx
./sequence_exam3 5
    Alternatively, you can write a Makefile like the one from Lab05. That would conserve resources, including your time (assuming you will compile more than once or twice).
  4. Submit both listpiece.cxx and sequence3.cxx for project PA4 at https://submit.cs.ucsb.edu/, or use the following command from a CS terminal: 
    ~submit/submit -p 590 listpiece.cxx sequence3.cxx
    Be sure to wait for the results of the listpiece test and all six sequence3 tests. If you score 100/100 and you've followed all of the other rules, then you'll earn full credit.
Updated 10/27/2016, by C. Michael Costanzo.
Special thanks to Michael Main, University of Colorado, creator of most parts of this project.