In this lab you will implement a C++ linked list and then use that linked list to store a movie. Specifically, each node will represent one frame of the film as a string. You will then create a movie player program that will load a movie into a linked list and perform some basic operations for playing and editing the film. You will also be responsible for answering written questions in regards to the performance of certain algorithms in your lab, to be handed in in class on Thursday, October 4.

To get started, run update35 from a computer science lab computer. The program update35 will create a cs35/labs/04 directory in your CS home directory, and the program handin35 will subsequently submit files from that directory.

You may work with one partner for the programming portion of this lab. Only one of you should submit your solution, but it is important that both of your names appear at the top of your program. As always, you must follow the academic integrity rules for the course. In particular, sharing/dicussing code with other groups is strictly prohibited. In addition, it is also a violation of academic integrity if both students are not equal contributors in this lab. You should be working together and both partners are responsible for understanding/verifying all code. The written portion of the lab must be done individually.

You will earn reasonable partial credit for this lab if you complete and test your linked list implementation. So be sure to work in a modular fashion, testing and completing your linked list first before implementing the main program

This lab is inspired by a late-90s internet phenomenon known as ASCII-mation (head here to see Star Wars as you've never seen it before). Most of you are familiar with ASCII art, where basic characters and symbols are pieced together to represent an image. ASCII-mation takes this a step further by placing a series of ASCII images one after another until it looks like a movie. In this lab, you will create a movie player that will load an ASCII-mation movie and allow a user to perform some basic functionalities including playing/pausing/stopping the movie, deleting frames, and reversing the movie to play it backwards.

As mentioned above, you will represent a movie as linked list of frames. You will then use basic linked list operations to implement the basic functionalities listed above for a movie player/editor. Most of the file format/playing features have been provided for you. One frame of the image will look similar to the following:

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

We will represent the text for the frame as one large string. The value in the upper left-hand corner (e.g., 31) is to compress the file size. It represents how many frames in a row looked the same as this. The movie has been filmed at 15 frames a second, so a value of 31 means that this image appears on the screen for 31 frames, or just over 2 seconds.

Here, I list the requirements for each major component of the lab. See the IMPLEMENTATION STRATEGY section below for hints on how to begin attacking the problem.

You have been given the following files.

• movieList.h - the MovieList interface. This file should not be modified
• movieLinkedList.h, movieLinkedList.cpp - the declaration and definition of the MovieLinkedList class. You will need to implement both files.
• frameNode.h, frameNode.cpp - the declaration and definition of the FrameNode class. These files should not be modified.
• tester.cpp - a partially completed test file for the FrameNode class. You should start here by filling out more tests to understand how a FrameNode works. You should then use this file to test our your MovieLinkedList class as you implement it.
• moviePlayer.cpp - the main program for playing a movie. This has been started for you you should implement the rest of the functionality specified in the menu.
• scene1.ani, scene2.ani, scene3.ani - small scenes for testing your program. Made available by Andrew Horner
• kbhit.h - code to make some of your movie player features possible. Do not modify this, and I wouldn't look at it, it's ugly code.
• starwar.ani - Episode IV in all of its glory, I wouldn't test with this though. Think of it as a reward for all of your hard work
• Makefile - use to compile your code. If you want to use tester.cpp to test your MovieLinkedList, be sure to follow the instructions in the Makefile.

MovieList

I have provided a MovieList interface, very similar to the StringList interface given in lecture. A MovieList defines the normal list functionality, but adds deleteItem and a playFrom method specific to this task. Recall that the interface is not the implementation, so we could theoretically use arrays or linked lists to implement a MovieList.

You must define and implement a MovieLinkedList class that implements the MovieList interface, without altering the MovieList interface.

MovieLinkedList Requirements

Don't worry about the movie-specific aspects at first, this class will largely be the same as any other linked list implementation. Begin by thinking about your algorithms in pseudocode and then implement them one-by-one. HINT: you may want to start by copying and pasting the MovieList interface declaration into the MovieLinkedList header file. Some requirements to note:

• You should not add any extra public methods to the MovieLinkedList interface than what is already specified in the MovieList interface.
• You may add as many private methods as you desire.
• The class should only contain variables necessary for maintaining the linked list. Do not declare local variables in the class declaration.
• Your methods should be safe. That means that it should not rely on a user of the class to avoid making mistakes, such as removing a non-existent item. In the case that the user attempts something illegal, you should throw a runtime_error with a descriptive message (see the ArrayList implementation from class and the Tips Section below).
• Your implementation must manage dynamic memory allocation properly. That is, your linked list should only allocate memory essential to the linked list implementation and must de-allocate memory when it is no longer being used.
• You should modify your tester.cpp file to make sure your MovieLinkedList implementation is working. Again, this file will not be graded but the ninjas will ask you to show your test file to help you with errors.
• A few of your methods will require traversing the linked list. Think about using a loop to follow the links. When do you know you've reached your destination? Also, how do you keep track of the previous node in the linked list?
• playFrom has largely been implemented for you. You do not need handle the actual movie playing. Simply replace each TODO with one or two lines of code to finish up the function.

MoviePlayer Program Requirement

Once you have thoroughly tested your MovieLinkedList implementation, you should implement the main program. The program has been started for you. Some tips and requirements

• Begin by finishing loadFilm, which reads the sequence from a file. You do not need to add code for the file input portion, but you should add a few lines of code to create your list. Recall that a each frame has a repeat value (count in the code provided). You should add the frame to the linked list accordingly.

Take a look at getChoice() to see what options the user has. You should implement each option appropriately in the main while loop. These include:

• Get Movie Status - A user can play and pause the movie many times. They should, at any time, be able to get a message about the movie they are watching and the current frame number they are at. This data should be maintained in your main program, not in the MovieLinkedList class. Note that playFrom should return the current frame number every time a user pauses. You should convert this into real time (15 frames per second) An example response would be:

  You are watching starwar.ani.  You are currently at 0hr 0min 0sec
  

• Play Movie - this should begin playing the movie from the previous pause point. You should use the same data available for getting movie status to remember the last pause location.
• Stop Movie - this stops by reseting the pause counter to 0. Note that this can only be done after the movie has been paused This DOES NOT exit the program.
• Cut Trailers - your program should use available linked list methods to eliminate 1 second from the beginning of the movie (i.e., 15 frames).
• Cut Credits - your program should use available linked list methods to eliminate 1 second from the end of the movie (i.e., 15 frames).
• Delete Current Scene - your program should use available linked list methods to delete one second from the current pause point.
• Reverse Movie - this should take the existing movie reel and flip it backwards. This is permanent, so the original movie reel should be replaced by a backwards one. Be careful with memory management here. Be sure to change the current pause point to 0.
• Exit - add a message thanking the user for using your program and let your main function end normally.

A couple pointers when implementing these methods:

• Keeping track of the current pause point can be a bit tricky. Be sure to consider its status after each of the menu options above. In particular, the pause point may need to be adjusted when you delete frames.
• The pause point should never exceed the number of frames in the movie;
• The pause point should never go below 0.
• Whenever you delete frames, make sure that frame actually exists. This applies to all three delete methods.

You should always program incrementally such that you can test your work as you go. Here is one suggested strategy:

1. Start by testing the FrameNode class in tester.cpp. Can you create a few nodes? Link them together? Print all the items? I have provided the beginning of a program to do this.
2. Begin declaring the MovieLinkedList class in movieLinkedList.h. Remember that you must declare all data members and at least all methods specified in the MovieList interface
3. Begin implementing your class in movieLinkedList.cpp. I suggest stubbing all functions (that is, defining the function and giving a dummy return value). This will let you compile the class properly without having done any actual implementation. An example function stub is:

          /* getFrame - returns the value for the ith item in the list
             Input: i, an integer for the frame index that must be between
                   0 and size-1
             Return: a string value representing the ASCII art for the frame
          */
          string MovieLinkedList::getFrame(int i){
             
            //TODO: implement this
     
            return "EXAMPLE FRAME";
          }
          

4. Check to see if your class compiles, fix any errors before proceeding. Now, begin implementing one method at a time. I suggest starting with insertAtHead or insertAtTail. Your procedure should be implement one method, compile, and then test it in tester.cpp
5. Implement the destructor last. Carefully consider every possible way that your class might allocate memory on the heap, and be sure that there is a corresponding call to deleteItem for each call to new.

At this point you should have a complete working MovieLinkedList class.

You should not under any circumstances begin the movie player implementation until you have thoroughly verified the correctness of your MovieLinkedList class. Any bugs in your MovieLinkedList class will hinder progress on the main program. Begin working on moviePlayer.cpp by implementing and testing one feature of the program at a time. Be sure that your solution follows good design/modularity guidelines.

Individually, each of you are responsible for also handing in the answer to the following questions. Your submissions can be hand or type-written; please bring a hard copy to class on Thursday. Your answers should be brief.

1. In class, we discussed the advantages and disadvantages of array lists. After having implemented linked lists, please list which methods of the MovieLinkedList class are "fast" (i.e., O(1)) and which are not efficient (i.e., O(N) for a linked list of size N).


2. Draw a memory diagram for the movieReel variable immediately after returning from loadFilm in your program. You can ignore all other variables in your program, but your diagram should clearly show what parts of movieReel are in the heap and which are in the i main() stack frame. Instead of large ASCII art, assume you've read in the sequence a series of 3 strings "Scene 1" , "Scene 2", "Scene 3"


3. Think of the newly added methods deleteItem and playFrom. For each of these methods, is the Big-O performance the same if we used an array list? Practically speaking, are there scenarios where either array lists or linked lists perform better?


4. You have implemented a specific linked list called a singly-linked list. An alternative implementation, called a doubly-linked list, uses a node implementation that has a pointer to the previous node in addition to a pointer to the next node. Hypothesize which, if any, methods in the movieList.h interface would be more efficient with this alternate representation relative to a singly-linked list.

Throwing and Handling Exceptions

Your linked list should handle invalid usage by throwing a runtime_error. There is an example in the playFrom method in movieLinkedList.cpp as well is in the ArrayList implementation from class. For example, if you may want to handle at attempt to get an invalid item:

throw std::runtime_error("Attempt to getFrame out of bounds");

Here is an example of handling a runtime_error (not required in this lab:

try{
  //do something dangerous
} catch (runtime_error& exc){
  cerr << "Warning: " << exc.what() << endl;
  cerr << "Ignoring illegal behavior." << endl;
}

Don't forget to include the stdexcept library when handling or throwing exceptions.

Once you are satisfied with your program, hand it in by typing handin35 at the unix prompt.

You may run handin35 as many times as you like, and only the most recent submission will be recorded. This is useful if you realize after handing in some programs that you'd like to make a few more changes to them. Only one partner should hand in the code for the lab.

The written portion is due in class on Thursday and should be done individually

Home Page