The main goal of this lab is to gain practice using and implementing abstract data types (ADTs). To that end, you will complete and test a Linked List implementation of the List ADT. You will then use these to create and play animated movies using a format called ASCIImation. Concepts you will be familiar with after this lab include:

• Abstract Data Types
• Linked Lists
• exceptions
• templates
• unit tests

As with most assignments for the rest of the semester, you will be working with a partner. 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 your partner.

You and your lab partner will share the same git repository, which is named lab04-<user1>-<user2>.git. Please access your lab by cloning the appropriate git repository, e.g.:

$ cd ~/cs35/
$ git clone git@github.swarthmore.edu:CS35-S18/lab04-lmeeden1-mgagne1.git ./lab04

You can also get the ssh git url from CS35 github org.

For this lab, we also are hosting several test files. Instead of giving everyone identical copies of the somewhat large files, you will create a symbolic link to the folder containing the files.

$ cd ~/cs35/lab04
$ ln -s /usr/local/doc/lab04-data/  ./test_data

Note: A significant portion of the credit for this lab is assigned to the correctness of your linked list. For that reason, be sure to develop your linked list and ensure it passes all tests before working on the main application.

ASCII, ASCII art, ASCII animation

ASCII is an abbreviation for the American Standard Code for Information Interchange. In brief, the ASCII table picks a numeric representation for each of a set of characters; for instance, the letter 'A' is given the code 65, 'B' is 66, and '^' is 94. Text is stored in a computer as a sequence of numbers and then, when displayed, is translated from these numbers into visual representations of characters by tables like the ASCII table. Until recently, most text stored on computers was encoded in ASCII.

ASCII art is a term for the practice of using text to create images.

  31
                 -===                    `"',
                ""o o                    O O|)   Going somewhere,
                _\ -/_                  _\o/ _        Solo?
               /| || |\                /|\ / |\
              //| || |\\              //| |  |\\
             || | || | \\            // | |  | ||
             || |/  \|  \\        -==#  | |  | ||
             |! |====|   ')         '\  |====| /#
             =] |/|| |                  | || | ''
              I ( )( )                  | || |
                |-||-|                  | || |
                | || |                  | || |
________________[_][__\________________/__)(_)_____________________

The use of printed text to form pictures is older than the ASCII standard. The term “ASCII art” gained popularity as the practice found its way onto computerized devices which used the ASCII table to standardize text representation. ASCIImation is the practice of using a repeated sequence of these textual images to create an animation using ASCII art. For this lab, you will be writing an ASCIImation player.

Below is an overview of the files required for submitting this lab. Those highlighted in blue will require implementation on your part. Those highlighted in black are complete and should not be modified except for comments.

• linkedList.h, linkedList-inl.h: the LinkedList class that you will define.
• asciimationFunctions.h, asciimationFunctions.cpp: The functions for loading and playing ASCIImation videos.
• main.cpp: the main asciimation program.
• manualTests.cpp: a "sandbox" test program that you can use while you develop your program.
• tests.cpp: Unit tests for your data structure. This week, we've given you all the unit tests you'll need. You won't have to write new unit tests, but you should definitely run the ones we've given you, and run them often!
• Makefile: The build instructions for your lab.
• test_data: a directory containing several ASCIImation files. The format is described below.

The list ADT is located on the CS system under the include path #include <cs35/list.h>, or the path /usr/local/include/cs35/list.h. You can browse a copy of list.h in your browser.

LinkedLists

The first (and most important) part of this assignment is to implement the LinkedList class; the declaration of that class appears in linkedList.h. You will implement all of the templated linked list methods in linkedList-inl.h. This implementation requires you to do some things a bit differently from how you’ve written previous labs:

You’ll need to implement a constructor for the LinkedList class that does more than just copy constructor arguments into the object’s fields. Your LinkedList constructor must set up the fields of its own object in a coherent way. You’ll need to use the LinkedListNode class in the operation of the LinkedList. As elements are added and removed, you’ll need to create and destroy the nodes. You’ll need to do a lot of your own memory management. That is, your program must use new and delete correctly. You should delete nodes as you remove them from your list and your LinkedList destructor should remove all of the remaining nodes.

Note: For this lab, you will not be penalized for memory leaks, but your code must be completely free of memory errors (e.g. using uninitialized pointers or pointers to memory you have deleted). Your implementation of the LinkedList class must meet the following complexity requirements:

• peekHead: $O(1)$ time
• peekTail: $O(1)$ time
• insertAtHead: $O(1)$ time
• insertAtTail: $O(1)$ time
• removeHead: $O(1)$ time
• removeTail: $O(n)$ time
• getSize and isEmpty: $O(1)$ time

Programming ASCIImation

The second part of your lab is to implement the asciimation program, which will read ASCIImation videos from a file and play them. Your program should first ask the user for the name of the animation file. Then, it should ask if the user wants to play the movie in reverse. Then, your program should load the appropriate movie file and play it, either as normal or in reverse. For instance, this command plays the smiley video:

$ ./asciimation
animation file: test_data/smiley.asciimation
reverse list? no

You can play the movie in reverse simply by reversing the contents of your list before playing the video.

The ASCIImation Format

Your test_data directory contains several ASCIImation files with the file extension .asciimation. These files contain the text representing different scenes in the animation. Our animations will run at 15 frames per second; that is, your program will need to display a frame, wait for \(\frac{1}{15}\) of a second, and then clear the screen and display the next frame.

One way to accomplish this is to use the usleep function from the library unistd.h (that is, #include <unistd.h>). The usleep function takes a single argument: the number of microseconds to sleep. For instance, usleep(1000000/15) will sleep for about \(\frac{1}{15}\) seconds. After sleeping, you can clear the screen using system("clear"); (which is a call to the system function mentioned in the previous lab).

The .asciimation files themselves contain groups of 14 lines each. The first line of each group indicates a frame count while the remaining lines are the contents of the frame. (That is, each frame is 13 lines tall.) The frame count exists to reduce the size of the file, since we often want frames which do not change for a second or more. For instance, the following .asciimation file would display a smiley face for two seconds (30 frames). The smiley would then close its eyes for the next second (15 frames).

30
    ~~~~~~~~~~~~~~
   /              \
  /   ~_~    ~_~   \
 /    / \    / \    \
|    | * |  | * |    |
|     \_/    \_/     |
|                    |
|         ~~         |
|    \          /    |
 \    \________/    /
  \                /
   \              /
    --------------
15
    ~~~~~~~~~~~~~~
   /              \
  /   ~~~    ~~~   \
 /                  \
|    -===-  -===-    |
|                    |
|                    |
|         ~~         |
|    \          /    |
 \    \________/    /
  \                /
   \              /
    --------------

When you read the file, you should read it into a list of pairs. pair is discussed below. Your list will have type List<pair<int,string>>, where the first element of the pair is an int and the second element is a string containing all 13 lines of the frame.

The pair Class

The pair class is part of the C++ standard template library (STL). It is defined in the the utility library and acts as a simple container of two values. We write pair<T1,T2> to create an object of two values. The first value has type T1; the second has type T2. For isntance, a pair<int,string> is an object with a field first of type int and a field second of type string.

Unlike the classes we have been writing, the pair class knows how to make copies of itself by assignment; that is, you can use = assignment with a pair just like you would with an int. Consider the following code:

pair<int,string> p1(4, "apple"); // create an int*string pair
pair<int,string> p2 = p1;        // copy the values from p1 into p2
p1.first = 5;                    // change p1's integer to 5
cout << p2.first << endl;        // prints 4, since p2's int is a different variable
pair<int,string>* ptr1 = new pair<int,string>(8,"orange"); // dynamically allocate a pair
pair<int,string>* ptr2 = ptr1;   // this copies the *pointer*, not the pair
ptr1->first = 10;                // change the dynamically-allocated object's integer to 10
cout << ptr2->first << endl;     // prints 10, since both pointers point to the same pair object

In the above, p1 and p2 are statically-allocated objects. Although none of the statically allocated objects we have used so far have been copyable (other than string objects), pair objects can be copied. Note how copying a pair object is different from copying a pair pointer. In this lab, you won’t need any pair pointers, so you don’t really need to worry about that case.

Unit Tests

As with Lab 03, you will use unit tests to test your linked list implementation. For this lab, we're giving you all of the unit tests. You won't have to write your own unit tests, but it will be important to run the ones we give you, and run them often.

$ make
clang++ -g -std=c++11 -Werror -c -o asciimationFunctions.o asciimationFunctions.cpp
clang++ -g -std=c++11 -Werror -c -o main.o main.cpp
clang++ -g -std=c++11 -Werror -o asciimation main.o asciimationFunctions.o
clang++ -g -std=c++11 -Werror -c -o tests.o tests.cpp
clang++ -g -std=c++11 -Werror -o tests tests.o asciimationFunctions.o -lUnitTest++
clang++ -g -std=c++11 -Werror -c -o manualTests.o manualTests.cpp
clang++ -g -std=c++11 -Werror -o manualTests manualTests.o asciimationFunctions.o

Then execute your tests. Initially, you should have many failed tests since you haven't completed your LL implementation!

$ ./tests
tests.cpp:29:1: error: Failure in createList: Unhandled exception: Not yet implemented:
      LinkedList::LinkedList
tests.cpp:33:1: error: Failure in addHeadAndRetrieve: Unhandled exception: Not yet implemented:
      LinkedList::LinkedList
tests.cpp:39:1: error: Failure in addHeadTwiceAndRetrieve: Unhandled exception: Not yet implemented:
      LinkedList::LinkedList
...
tests.cpp:223:1: error: Failure in performanceTestInsertAtHeadAndGetSize: Unhandled exception:
      Not yet implemented: LinkedList::LinkedList
FAILURE: 19 out of 19 tests failed (19 failures).
Test time: 0.00 seconds.

As you develop your LL implementation method by method, recompile and rerun the tests. The number of failures should decrease as you go along.

Commenting and Coding Style Requirements

For this and future labs, graders will assign minor penalties for poor commenting and coding style. Here are some style tips for this lab:

• You should pick meaningful variable names.

  // good
  int *array = new int[size];
  // bad
  int *a = new int[size];
  

• You should use correct and consistent indentation. Lines of code within a block should be indented two spaces further than lines surrounding them.*

    //good
    if(condition) {
      cout << "Test" << endl;
    }
  
    //bad
    if(condition) {
  cout << "Test" << endl;
       }
  

  *if your text editor's default indenting is four spaces instead of two, don't stress about it. Just be consistent when indenting.
  
• You should use a code block whenever possible, even if it's not necessary. This will help you avoid subtle/messy errors in the future.

  //good
  if(condition) {
    cout << "Something" << endl;
  }
  
  //legal but bad
  if(condition)
    cout << "Something" << endl;
  			 

• Do write comments at the top of each file, indicating your name and the purpose of the code file
• You don't have to write a comment for each line of code, but do write comments about meaningful chunks of code such as a loop, if/else statement, etc.
• Do write comments describing the purpose and signature of each function declaration. use @param to describe an input parameter, @return to describe what gets returned, and @throws to describe exceptions that should be thrown. An example lies below:

    /**
     * Retrieves the first element of the list.
     * @return The element at index 0 of this list.
     * @throws runtime_error If the list is empty.
     */
    virtual T peekHead() = 0;
  

The ASCIImation player you will design for this lab plays movies, but its functionality is limited. For example, you might want to edit the movie, or play only a portion of the movie. As an extra challenge, build a menu that offers the user some extra features. Some suggestions lie below:

• Allow the user to delete portions of the movie.
• Allow the user to start playing the movie from the middle.
• Allow the user to edit frames in the movie.

These additional features are optional -- we'll look at them, but they won't be for credit. Make sure you complete and push the main lab before starting any extra challenge, and note in your README file that you've done extra challenges so the graders know which version of your lab to grade. (There's a chance your added features will break our grading scripts; we'll grade the base version of your lab to ensure you don't get penalized in the off-chance your extra features break our grading scripts)

When you have completed your lab, answer a few short survey questions in the file README.md.

To summarize the requirements of this lab:

• Write an implementation of a linked list.
  • Incrementally test your implementation using the unit tests we provided.
  • This implementation should manage its memory properly.
• Read the .asciimation videos and play them at 15 frames per second.
  • The user also should be allowed to play the video in reverse
• Ensure your code complies with the style requirements above.
• You must complete the survey in the file README.md.

Once you are satisfied with your code, hand it in using git. Remember the add, commit, push development cycle. You can push as many times as you like, but only the most recent submission will be graded. You may want to run git status to confirm all modifications have been pushed.