Actual Tulips
Due Wednesday, October 11 at 22 11:59pm.
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.
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 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.
You can find a link to your repository on Teammaker, a web application we will use to form teams.
Your starting repository will contain the following files. Bolded filenames indicate files you will need to change. You should not change any .h files other than those bolded below.
adts/list.h: The C++ declaration for the List ADT.
linkedList.h: The LinkedList class declaration.
linkedList-inl.h: The LinkedList class definition using templates.
asciimationFunctions.h and asciimationFunctions.cpp: The functions for loading and playing ASCIImation videos.
asciimation.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.
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 clean all of the nodes up. 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). You can run valgrind to find out if your code has memory errors or if you’re leaking any memory.
Every data structure we build in this class will include a special method called checkInvariants(). When called, this method will ensure that fundamental aspects of the data structure are sound, and if not, it will throw a runtime_error indicating the problem. For example, in the case of a LinkedList, we expect that if we count the nodes we can reach by walking down the linked list from the head to the tail, it should match the current value in the size data member.
Your implementation of the LinkedList class must meet the following complexity requirements:
getFirst and getLast: \(O(1)\) time
insertFirst and insertLast: \(O(1)\) time
removeFirst: \(O(1)\) time
getSize and isEmpty: \(O(1)\) time
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 program implementation will be done in three files. The
helper functions for loading and playing the video are to be declared in
asciimationFunctions.h and defined in asciimationFunctions.cpp. The main program
will be implemented in asciimation.cpp.
Click on the image below to see the expected behavior when running ./asciimation test_data/scene3.asciimation:
Here’s an example of the same scene running in reverse (./asciimation --reverse test_data/scene3.asciimation):
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}\) of a second. After sleeping, you can clear the screen using system("clear"); The bulk of this work should be in your playMovie() function in asciimationFunctions.cpp.
Your loadMovie() function will parse the input file into a series of frames. 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
~~~~~~~~~~~~~~
/ \
/ ~~~ ~~~ \
/ \
| -===- -===- |
| |
| |
| ~~ |
| \ / |
\ \________/ /
\ /
\ /
--------------For this and future labs, you should throw a runtime error if the file fails to open e.g. because the file doesn’t exist. You can check this with the ifstream method is_open().
You should read the file in line by line. This can be accomplished with the getline function as demonstrated below. After each call to getline, the entire contents of the next line of the file (except the newline "\n") will be read into the data variable.
ifstream myFile;
string data;
myFile.open(filename);
if(!myFile.is_open()) {
throw runtime_error("file " + filename + " failed to open ");
}
getline(myFile, data);
while (!myFile.eof()) {
// process the data in the line here
getline(myFile, data);
}Note that the eof() method of ifstream has somewhat surprising behavior. It does not test to see if we have reached the end of the file. It tests to see if we have failed to read a line because of the end of the file. This is why we call getline before and at the end of the loop (rather than at the beginning of the loop). This initial call to getline is called a priming read and is common in C, C++, and similar languages when dealing with input and output.
As you read the file, you should build up a list of pairs. The pair class 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.
pair ClassThe 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.
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 a pair between an int and a string
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 objectIn 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.
Your implementation of the ASCIImation functions must meet the following complexity requirements:
playing a movie: \(O(n)\) time
playing a movie in reverse: \(O(n)\) time
We recommend approaching this lab by doing incremental implementation
and using the unit tests we’ve given you in tests.cpp. You should
also create your own tests within the file manualTests.cpp. This
allows you to test only those methods you’ve implemented so far.
Start by compiling and running ./tests. All of your tests should
fail.
Then, implement just the constructor of LinkedList as well as
checkInvariants. The checkInvariants method should walk the list
from the head to the tail, counting the number of nodes. This count
should match the size of the list. You should make liberal use of the
checkInvariants method while you are testing. If you have a bug,
calling checkInvariants can help you more quickly identify where
things went wrong. Once these methods are implemented, compile and run
your unit tests. If you correctly implemented the constructor and
checkInvariants, then two unit tests will pass. You’ll still have
18/20 failed unit tests, but you’ve made forward progress!
Fix any issues before moving on, and test them by
adding calls to these methods in the file manualTests.cpp.
Next implement the insertFirst and getFirst methods. Again,
before moving on, compile and run your unit tests. Fix any issues
that you find, and make sure they are fixed by adding calls to these
methods in manualTests.cpp. Once you correctly implement
insertFirst and getFirst, a few more unit tests should pass.
Continue implementing methods on LinkedList a little at a
time. After each small amount of progress, compile your code and run
your unit tests. If needed, add more tests to your manualTests.cpp
file and fix any issues before moving onto the next step.
Once your LinkedList methods are successfully 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.
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.
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.
As with previous labs, you will be required to observe some good coding practices:
Your C++ code must be properly and consistently indented to match the blocks ({…}) you write.
You must always use blocks for conditions (if and else) and loops (for, while, etc.).
Throw a runtime error if the movie file fails to open.
For this lab, you must
Write an implementation of a linked list
This implementation should manage its memory properly
Your linked list must meet the complexity requirements
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
Your program must meet the complexity requirements
Ensure your code complies with the style requirements above