This is an individual assignment. You must complete this lab on your own, although you may discuss lab concepts with other students. Please keep the Academic Integrity Policy in mind---do not show your code to anyone outside of the professors and ninjas, and do not look at anyone else's code for this lab. If you need help, please post a question on Piazza, or contact the professor.

The main goal of this lab is to gain practice using and implementing abstract data types (ADTs). To that end, you will complete a Singly Linked List with Tail 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:

• Linked Lists
• exceptions
• the pair class of the STL
• making the computer wait in a program

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 test all the methods thoroughly, I will be testing all methods even those not used by 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.

First, download the .zip file that contains the starter code for the forth programming assignment. It contains the code the files you will have to complete for this assignment. Unzip the folder it contains in your CLionProjects folder and turn it into a CLion Project by opening the folder in CLion, opening main.cpp and creating the CMakeList.txt file. If CLion automatically opens in your previous project, you may need to close that project (File->Close) Project to get back to the CLion welcome screen.

In the first phase of the assignment, you will write the part of the program that runs the movie. You will initially use the Array List implementation I provided in the starter code to store all the frames of the animation, but you will later move to a singly linked list with tail that you will implement yourself. Before I describe the ASCIImation program, I will talk about the pair class, which you will need for your implementation.

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 instance, a pair<int,string> is an object with a field first of type int and a field second of type string.

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
p2 = make_pair(2, "five");       // creates a pair and assigns it to p2
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

Programming ASCIImation

The first 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: smiley.asciimation
reverse list? no

You can play the movie in reverse simply by reversing the contents of your list before playing the video. Reversing the list should require $O(n)$ time, and you are allowed to destroy the original list in the process of creating the reversed list.

The ASCIImation Format

The file asciimation.zip contains several ASCIImation files with the file extension .asciimation. These files contain the text representing different scenes in the animation. Copy these files in the cmake-build-debug folder of your project.

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 function

this_thread::sleep_for(chrono::microseconds(usec));

where usec is the number of microseconds to sleep. To use this, you need to include the libraries thread and chrono. For instance, this_thread::sleep_for(chrono::microseconds(1000000/15)) will sleep for about $(\frac{1}{15})$ seconds. After sleeping, you can clear the screen using system("clear"); (which will do the same as typing the command "clear" in the terminal). Note that this will only work in an actual terminal window, I will show you in lab how to run the program properly.

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.

Read the comments about the two functions in asciimationFunctions.h. Your implementation should follow the behavior dictated in these comments exactly.

The function loadMovie takes a filename as input and returns a list of pairs, each pair consisting of an integer (the number of frames the picture should remain on screen) and a string (the picture itself). During Phase 1, this list will be an Array list, but that will be changed to a singly linked list with tail during Phase 2.

In the main loop that reads the file, I would recommend that you read an entire pair for each iteration of the loop. You may also want to write a function getPicture that takes an ifstream as input parameter and returns a string containing 13 lines (a picture). This way, each iteration of the main loop of loadMovie will read a pair by reading a line with the frame count and read a picture by making a call to getPicture.

The function playMovie takes a list of pairs as input and, well, plays the movie. For maximum points, the function should only use methods of the list that run in $O(1)$ time, but is allowed to destroy the list containing the movie while playing it.

The second (and most important) part of this assignment is to implement the SLLwT class (Singly Linked List with Tail); the declaration of that class appears in SLLwT.h. You will implement all of the methods in SLLwT.cpp.

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). And of course, you should do your best to ensure that as much of the dynamic memory you used is eventually reclaimed.

Your implementation of the SLLwT class must meet the following complexity requirements:

• copy constructor, operator= and destructor: $O(n)$
• 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
• at and operator[]: $O(n)$ time

In order to test your Singly Linked List with Tail methods, you may want to use this testing program. It contains a main function, so you will have to make sure that either test.cpp or main.cpp is part of CMakeLists.txt but not both.
Testing code always looks ugly so do not look at the code too closely, you can trust that all the "checks" do what their names states they should do. I will talk about how to use it briefly in lab, feel free to ask me questions about it on Piazza if you have trouble using the tests.

For this and future labs, I 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

  /**
   * Name: Martin Gagne
   * Project: PrgAsst6
   * File: SafeIntArray.cpp
   * Content: implementation of the methods for the class SafeIntArray declared in SafeIntArray.h
   */
  

• 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.

  void insertAtHead(int value) {
    // make sure that there is room in the array for the additional element
    if (this->size == this->capacity) {
      this->expandCapacity();
    }
    // shift all the current element one position to the right
    for (int i=size-1; i>=0; i--) {
      this->theArray[i+1] = this->theArray[i];
    }
    //place the new element
    this->theArray[0] = value;
  }
  

• Do write comments describing the purpose and signature of each function declaration. use @param to describe an input parameter and @return to describe what gets returned. An example lies below:

  /**
   * Performs the main quick sort algorithm to sort the provided array.
   * @param array The array to sort.
   * @param startIndex The leftmost index (inclusive) of the part of the array
   *                   to sort.
   * @param endIndex The rightmost index (inclusive) of the part of the array
   *                 to sort.
   */
  void quickSort(int* array, int startIndex, int endIndex);
  

Submit a .zip file containing the entire project folder for the programming assignment using the submission link on onCourse.

This lab write up is based off of the ASCIImation lab developped by the Computer Science Department of Swarthmore College.