Data Structures and Algorithms

Lab 4: ASCIImation

Due on Sunday, October 2nd 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 play a video using text. You can get started by cloning your repository from the URL git@github.swarthmore.edu:cs35-f16/lab04-<team-name>.

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 your linked list and ensure it passes all tests before working on the main application.

ASCII, ASCII Art, and ASCIImation

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.

ASCII art is a term for the practice of using text to create images. For instance, the following text may be (generously) viewed as a picture of a flower:

/\/^/^\_^ /\
| \ |   \/ |
|  '    /  |
 \     '  /
. \  .   / ,
 -~`~ `~'~-
     ||
     ||
     ||
     ||

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.

Starting Code

Your starting repository will contain the following files. Bolded filenames indicate files you will need to change:

• adts/list.h: The C++ declaration for the List ADT.
• linkedList.h/linkedList__definitions.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 for you to use while you develop your program.
• tests.cpp: Unit tests for your data structure. These tests have already been written. You will not have to write your own tests for this assignment, but you should definitely run the ones you’ve been given!
• Makefile: The build instructions for your project.
• test_data/: A directory containing several ASCIImation files. The format is described below.

Linked List

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__definitions.h. This implementation requires you to do some things a bit differently from how you’ve written previous labs:

1. 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.
2. 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.
3. 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 clean all of the nodes up. (You can run valgrind to find out if you’re leaking any memory.) Your grade is not heavily affected by 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
• insertAtHead: \(O(1)\) time
• removeHead: \(O(1)\) 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 may be run in one of two ways. If there is a single command line argument, the program will load and play the video in that file. For instance, this command plays the smiley video:

./asciimation test_data/smiley.asciimation

If the user provides an additional command-line argument, then the first argument must be --reverse and the second argument must be the name of an ASCIImation file. This plays the movie in reverse (which you can accomplish simply by reversing the contents of your list before you play the video). For instance, the following command plays the smiley video in reverse:

./asciimation --reverse test_data/smiley.asciimation

Any other combination of command-line arguments should produce an error.

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.

Implementation Strategy

You may try approaching this lab in the following way:

1. Begin by running make tests and ./tests. All of the tests will, of course, fail. Keep track of how many tests failed (e.g. by keeping that window separate from the windows you’ll work in).

2. Implement the constructor of LinkedList as well as the insertAtHead and peekHead methods. Then, run the tests again. If you have had at least some success in implementing these methods, some tests will begin to pass.

3. Continue implementing methods on LinkedList a little at a time. If you need help figuring out which methods to implement, try looking at a test that’s failing. After each small amount of progress, run your tests to see if your new code works (and to see if your old code still works).

4. Once your LinkedList methods are implemented, begin implementing the asciimation program. Begin by writing the loadMovie function; use the manualTests program to experiment with it and see if it works correctly.

5. Next, implement the playMovie function. Then, write your main function to put everything together. Don’t deal with the --reverse option yet; just assume that the user provides a single command-line argument and wants to play the movie normally. See if your playMovie works correctly.

6. Finally, add the behavior for --reverse to main.

It’s good practice for you to commit and push your code each time you get something new to work. After you get the constructor and first two LinkedList methods to work, for instance, you can git commit and git push your work before you move on to the next part. If something goes wrong when making changes later, you’ll have your old version to fall back on. Please let us know if you need help recovering older, pushed versions of your code.

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 the image represented by this object to a file.
       * @param filename The name of the file to save.
       * @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(std::string filename);
  
  // Bad
  public:
      int save(std::string filename);
  

  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 participation grade points. Please don’t forget!

Summary of Requirements

For this lab, you must

• Write an implementation of a linked list
  • This implementation should manage its memory properly
• Read the .asciimation format videos and play them at 15fps
  • The user should be allowed to play the video from end to beginning with the --reverse argument.
• Ensure your code complies with the style requirements above
• Complete the lab peer review