Due 11:00PM Wednesday January 15, 2014
Read the logistics before you submit — poor submissions may lose points.
The purpose of this project is to implement a Stack ADT in the two most common ways, an array and a linked list. You will implement stacks for Java double numbers.
Your Stack implementations will be used to do sound manipulation, namely reversing a sound clip. This process, called "backmasking," was used by musicians including the Beatles, Jimi Hendrix, and Ozzy Ozbourne, although it seems to have fallen out of favor in recent years. Here is a history of this (sometimes controversial!) practice. "But wait," you say, "CSE143 never taught me how to work with music..." Don't worry! All the music-handling parts have been done for you.
You will write a program that reads a sound file in the .dat format (explained below) and writes another .dat sound file which is the reverse of the first. We have provided a class Reverse whose main method reads in a .dat sound file, pushes all the sound values on a stack, then pops them all off and writes them into a new .dat sound file. We have also provided an interface DStack, which defines a stack that holds double values. Your first job is to familiarize yourself with these files.
You need to provide two stack implementations, one using an array and one using a linked list. They should be called ArrayStack and ListStack, respectively. They should implement the DStack interface given to you. Once you provide these implementations, Reverse should work and create backward sound files. It should take no more than a page or two of code to provide the implementations. Your array implementation should start with a small array (say, 10 elements) and resize to use an array twice as large whenever the array becomes full, copying over the elements in the smaller array. While there are convenient Java library methods for copying arrays, for this assignment, use your own loop to copy array elements manually (so you can "see" the work involved in copying).
Both ArrayStack and ListStack should throw an EmptyStackException if pop() or peek() is called when the stack is empty. To use EmptyStackException, add the following line to your file:
import java.util.EmptyStackException;
The only Java class that you should use to complete the implementations of your stacks is java.util.EmptyStackException. You should also use the length field of an array.
The Reverse program takes 3 arguments (also known as "command-line arguments"). The first is the word array or list and specifies which implementation to use. The next two are the input and output .dat file names (you need to include the .dat extension). Running the program will depend on your system; from a command line it will look something like:
java Reverse list in.dat out.dat
In an IDE there is usually a dialog box for setting program parameters which contains a field for the program arguments. (For example, in jGRASP select Build->Run Arguments and a bar will appear at the top of the screen that allows you to type in the arguments. See Working with Eclipse below for information on setting command line parameters in Eclipse.)
To test your program, you will need a .dat file, which you can create from a .wav file as explained in the Digital Sound section. It is also useful to create short .dat files by hand to aid testing.
We have provided you a client program, Reverse.java, that uses the stack implementations you will write. Getting Reverse.java to run and correctly reverse a sound file is fun and indicates that your stack implementations will compile and run. It does not, however, imply that your stack implementations have been thoroughly tested. Reverse.java just uses your stacks in one particular way: pushing a bunch of elements onto the stack and then popping them all off. There are other ways that someone use your stack implementations and other cases that are not tested by just being able to successfully listen to sound files in reverse.
We will be testing your stack implementations more generally and you should too! We highly suggest creating another small client program of your own to help test other aspects of your code. You also might consider creating some short (e.g., 10 line) .dat files by hand to aid testing. (See the ".dat File Format" section of the write-up below for more information).
Turn in a file README.txt containing answers to the following questions.
The following list of suggestions are meant for you to try if you finish the requirements early. Recall that extra-credit points earned for "above and beyond" are kept separate and will be used to adjust your grade at the end of the quarter, as detailed in the course grading policy.
Turn-in: You should turn in the following files, named as follows:
Do not turn in DStack.java or Reverse.java. You must not change these files. Your stack implementations must work with the code as provided to you.
You may discuss the assignment with others in the class, but your solution must be entirely your own work.
We will view sound as a continuous function of time from the positive real numbers (time) to the interval [-1.0, 1.0] (amplitude). Since a computer can't "hold" a function defined on the reals, we have to approximate the function. We do this by measuring (or "sampling ") the sound several thousand times per second.
This process is called "Analog to Digital Conversion", or ADC. The number of times per second the sound is sampled is called the sample rate and is measured in Hertz. For example, CDs are recorded at 44100 samples per second, or 44.1kHz. But you don't need to understand ADC for CSE373.
The only sound file format you need to know about is the .dat format described below. You don't even have to know very much about that either, as we are giving you the code that reads and writes that format. In order to play sounds you produce, you need a way to convert between the .dat format and a format that common media players (Windows Media Player, winamp, RealPlayer, etc.) understand, such as .wav. We will describe one way to do it below; however, you are free to use another converter.
sox is a command-line utility whose name stands for "SOund eXchange". It lets you convert between many different sound formats including .wav, .au, etc. In particular, sox allows you to convert to and from .dat sound files. .dat files are useful because they are human-readable, text-based, sound files. Note that you will need to perform this conversion to answer one of the write-up questions.
Versions of sox are available for Windows, Mac, and
Linux. You can download the one you need from
here
by clicking on the folder for the most recent version (or, really,
any version) and then downloading the correct file for your
operating system.
The Windows version is also a command-line program and works in the same way as the UNIX version described below. See here for some pointers on using it.
The general strategy for using sox is as follows.
That's all there is to it!
The .dat file format starts with one line describing the sample rate of the sound file. This line is required. The rest of the file is composed of two columns of numbers. The first column consists of the time (measured in seconds) when the sample was recorded, and the second column contains the value of the sample, between -1.0 and 1.0. This is the beginning of a sample .dat file. Notice that the numbers in the first column increase by 1/44100 each step. This is because the sample rate is 44.1kHz.
; Sample Rate 44100 0 0 2.2675737e-05 0 4.5351474e-05 0 6.8027211e-05 0 9.0702948e-05 0 0.00011337868 0 0.00013605442 0 0.00015873016 0 0.00018140590 0 0.00020408163 0
Here is the same file, a little deeper on:
0.22693878 -0.0062561035 0.22696145 -0.0043945312 0.22698413 -0.0068664551 0.22700680 -0.0115661620 0.22702948 -0.0145568850 0.22705215 -0.0145416260 0.22707483 -0.0121917720 0.22709751 -0.0123901370 0.22712018 -0.0145416260 0.22714286 -0.0144958500 0.22716553 -0.0147705080 0.22718821 -0.0157012940 0.22721088 -0.0129547120 0.22723356 -0.0127105710 0.22725624 -0.0181579590 0.22727891 -0.0191497800 0.22730159 -0.0145721440 0.22732426 -0.0122375490 0.22734694 -0.0124359130 0.22736961 -0.0108184810
Note that you shouldn't have to deal much with the .dat file yourself, as the provided Reverse.java does all the work for you. All you have to do is implement the stacks. We are explaining the format because it will be helpful for writing short files by hand for testing purposes.
For this assignment you need to implement an interface, DStack, in two ways. The DStack interface defines a simple stack:
public interface DStack {
public boolean isEmpty();
public void push(double d);
public double pop();
public double peek();
}
An actual interface includes comments, including a description of how pop() and peek() should behave if they are called when the stack is empty. To implement this interface, write a class as follows:
public class ArrayStack implements DStack {
public ArrayStack() {
// Your constructor code
}
public boolean isEmpty() {
// Your isEmpty() code
}
public void push(double d) {
// Your push() code
}
// continue with the rest of the methods,
// along with any fields, etc.
}
The ListStack class should be defined similarly. You should include appropriate comments as needed. In particular, each file should begin with a comment that describes the class in the file, and includes your name and other identifying information.
Feeling rusty on Java? You may also find it useful to refer to lecture materials (Powerpoint slides) from a recent offering of CSE143. See in particular lectures on arrays, list nodes, and linked lists.
We encourage you to try working on your project in Eclipse, a powerful environment for Java and several other languages. Eclipse may seem like overkill for this assignment, probably because it is! But as the projects get larger, having an integrated development environment with lots of features can come in handy, so you should consider trying it out now.
You can use Eclipse in the lab, or download it to your own computer. The download site offers a number of different versions: you want 'Eclipse IDE for Java Developers' (not the similar sounding 'Eclipse IDE for Java EE Developers').
First, check out an Eclipse tutorial. There are several available on the web. Here is one by a CSE143 TA that describes downloading and "installing" Eclipse.
Next, write and run a simple "Hello World" program using Eclipse before starting on the project. This is just a program that does nothing more than print out "Hello World". Once you have mastered "Hello World", you might try something with multiple files, or re-doing one of your assignments from CSE143.
Some starter instructions for opening the project in Eclipse:
Some starter instructions for running your program from Eclipse:
When you are ready to use your stack code with the Reverse.java program, you will need to do a bit of work to pass command-line arguments to the program:
array data_files/bot.dat data_files/out.dat(That should all be on one line.) In this example, data_files is a directory in your project folder where your input and output files are located. You may create a subdirectory called data_files in your project folder and place your .dat files there or you may find it easiest to put your .dat input and output files directly in the same directory as your .class files so that all you need to give is the file names themselves.
When you have finished the project and want to turn in ArrayStack.java, ListStack.java, and (if you do not use an inner class) ListStackNode.java, an easy way to get the individual files is to click on each one in Eclipse's left-hand window and drag to the Desktop. This copies the file from the Eclipse workspace to your desktop.
Like many assignments, this has been passed down to us through the vaporous mists of time. Among all our fore-bearers, we would especially like to thank Ashish Sabharwal, Adrien Treuille, and Adrien's Data Structures professor, Timothy Snyder.
