The purpose of this project is to implement a Stack ADT in the two most common ways, a static array and a linked list.
Your Stack implementation will be used to do sound manipulation, namely reversing a sound clip. This tool was used by musicians including the Beatles, Jimi Hendrix and Ozzy Ozbourne, although it seems to have fallen out of favor in recent years. "But wait," you say, "CSE 143 never taught me how to work with music..." Don't worry! Most of the hard work has already been done.
You will write a program that will take a sound file in the .dat format (explained below), and output another .dat sound file which is the reverse of the first. We provide you with a class Reverse which reads in a .dat sound file, puts the sounds values on a stack, pops them off in reverse order, and puts these reversed values in a new .dat sound file. We've also provided you with a DStack interface, which defines a stack that holds double values. Your first job is to look over these files and become familiar with them.
Now for the work! You need to provide two stack implementations, one using an array and the other using a linked list. They should be called ArrayStack and ListStack, respectively. They should implement the interface DStack, which we provide to you. Once you provide this implementation, Reverse should work and create backwards sound files. It shouldn't take more than a page or two of code to provide the implementation. Your array implementation should hold around a million elements. The Reverse program takes 3 arguments. The first is either array or list, and specifies which implementation to use. The next two are the input and output .dat files (you need to provide the .dat extension). Running the program will depend on your system; from the command line it will look something like the following.
You should implement both versions of the stack interface without using any of the Java container library classes. In other words, no ArrayList or LinkedList.
java Reverse list in.dat out.dat
In an IDE there is usually a dialog for setting program parameters which contains a field for the program arguments.
Read the section on Digital Sound to learn how to create a .dat file. To get you started, we've created a .dat file here.
For details on what to turn in for this assignment and how, read the section on Logistics. For a quick reminder of how interfaces work in Java, see Java Reminder.
In addition, answer the following questions and provide the answer in your writeup.
The following list of suggestions are meant for you to try if you finish the requirements early. A small amount of extra credit will be awarded to assignments that go beyond the basic requirements.
It may be useful for you to create some short .dat files by hand to aid testing.
Details on electronic turnin will be announced later. Note that you do not turn in either Reverse.java or DStack.java. This means you shouldn't change them, either---your code must work with the original, unmodified versions.
Your extra credit may include a modifed Reverse.java, but because you've included it in a separate directory we'll be able to compile & grade your regular assignment without touching your extra credit. If you don't segregate your extra credit you probably won't receive credit for it!
You can turn in a printed copy of the receipt page you get when you submit your files online, or you can print the files separately.
Please make sure you have printed these files in a legible manner. If it's difficult to read or grade them, you will lose points.
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. Wait a minute! Is this the right class? I thought this was CSE373.
Yes, this is 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're giving you the code that reads and writes that format. In order to play sounds you produce, you need a way to convert the .dat file into a format that common media players (Windows Media Player, winamp, RealPlayer, etc.) understand. We'll describe one way to do it below; however, you're free to use any converter you can find.
There is a windows version of sox available at SourceForge. It seems to work well, but download and run at your own risk. It is also a command-line program and works in the same way as the UNIX version described below.
sox is a UNIX command-line utility whose name stands for "SOund eXchange". It allows you to 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 cool because they are human-readable, text-based, sound files. Note that you will need to perform this conversion to answer one of the writeup questions.
The general strategy is as follows.
That's all there is to it! But before we get too excited, let's first explain...
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. Here 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.0001814059 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.2270068 -0.011566162
0.22702948 -0.014556885
0.22705215 -0.014541626
0.22707483 -0.012191772
0.22709751 -0.012390137
0.22712018 -0.014541626
0.22714286 -0.01449585
0.22716553 -0.014770508
0.22718821 -0.015701294
0.22721088 -0.012954712
0.22723356 -0.012710571
0.22725624 -0.018157959
0.22727891 -0.01914978
0.22730159 -0.014572144
0.22732426 -0.012237549
0.22734694 -0.012435913
0.22736961 -0.010818481
Note that for this assignment, you shouldn't have to deal much with the .dat file yourself, as the provided Reverse.java does all the lifting for you. All you have to do is implement the stacks. We are telling you the format because it will be helpful for you to write a short file by hand to run, to verify if your program works.
For this assignment you will need to instantiate an interface, DStack, in two different ways. The DStack interface defines a simple stack:
interface DStack {
boolean isEmpty();
void push(double d);
void pop();
double top();
} To implement this interface, write a class as follows.
class ArrayStack implements DStack {
public ArrayStack() {
// Your constructor
}
public boolean isEmpty() {
// Your isEmpty()
}
public void push(double d) {
// Your push()
}
// continue with the rest of the functions,
// along with any member variables, etc.
}
The ListStack class should be defined similarly.
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, and Adrien Treuille and his Data Structures professor, Timothy Snyder.