Project 1 - Sound Blaster! Solution

Outline
Introduction
The Assignment
Questions
Above and Beyond
Logistics
How Digital Sound Works
Sox, a program for converting sound file formats
The .dat File Format
Java Reminder

Introduction
The purpose of this project is to implement a Stack ADT in the two most common ways, an array and a linked list.

Your Stack implementation 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.
Click here for a history of this (sometime constroversial!) practice. "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.


The Assignment
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 provide you with a class Reverse whose main method 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.

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 these implementations, 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. You may assume that the array won't fill completely (although we'll discuss what happens in that case in the writeup questions). 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 Reverse program takes 3 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 the following.

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.

Writeup Questions
Who/What did you find helpful for this project?
How did you test that the final program is correct?
The file secret.wav is a backwards recording of a word or short phrase. Use sox (or another converter) and your program to reverse it, and write that as the answer to this question.
Did you use any classes from the Java framework or other class library? (Remember, as stated in the programming guidelines, if the answer to this question is anything other than "no", you may get a low score on this project if you use the library to implement your stacks!)
(Addendum: it's OK to use java.util.EmptyStackException!)
What happens if you exceed the maximum size of the array implementation of DStack? Can you think of other ways to handle this case, if you were allowed to change DStack.java and Reverse.java? Be specific: refer to particular lines of code that would change, list any exceptions you would add and who would throw them, describe who catches any such exceptions and how they are handled, etc. Referring to comments you have inserted in your code is the best way to do this. Give one good point of your current implementation and one good point of the alternative implementation you describe.
Let's pretend that, instead of a DStack interface, you were given a fully-functional FIFO Queue class. How might you implement this project (ie, simulate a Stack) with one or more instances of a FIFO Queue?
Write pseudocode for your push and pop operations. Refer to the Written Homework Guidelines for instructions on writing pseudocode.
(Addendum: Assume your Queue class provides the operations enqueue, dequeue, isEmpty and size).
In the previous question, what trade-offs did you notice between a Queue implementation of a Stack and your original array-based implementation? Which implementation would you choose, and why?
Include a description of how your project goes "above and beyond" the basic requirements (if it does).
What did you enjoy about this assignment? What did you hate? What could you have done better?
Any other information you would like to include.
Going Above and Beyond
The following list of suggestions are meant for you to try if you finish the requirements early. Recall that any extra-credit points you earn for these are kept separate from your assignment score and will be used to adjust your grade at the end of the quarter, as detailed in the course grading policy.

(1 point) Change the array implementation to grow when it becomes full.
(2 points) Try implementing the Karplus-Strong algorithm (to generate "reverb" sounds). A description of this algorithm is available here.
(5 points) Assuming that your .dat input file contained a single note, try writing a program which will output a single-octave scale beginning at that note. Would the notes of an "evenly spaced" scale grow logarithmically, linearly, polynomially, or according to some other function? For more information about the evenly-spaced scale, refer tothis article. To earn full credit, you must start from an actual recorded note (not a synthetic one) and generate the single-octave scale.

Logistics for Project 1
The files we have provided for you:
Source code: DStack.java, Reverse.java
Sound files: bot.wav, bot.dat.
It may be useful for you to create some short .dat files by hand to aid testing.

Each file you turn in should have your name at the beginning. All text files should have your name on the first line; your name should appear in the javadoc comment at the beginning of each source code file you turn in.
You must implement the list and array stacks by hand - you may not use any classes from the Java libraries to do the work. You should not use any import statements, except for java.util.EmptyStackException.
Electronic Turnin: You should turn in the following files, named as follows:
ArrayStack.java. Your array should hold around a million elements.
ListStack.java
README.txt, your writeup, containing the answers to each assignment question.
Any extra credit, in a zip file named extracredit.zip. Please make sure that this zip file decompresses its contents into a folder called extracredit and not into a bunch of individual files.
Electronic turnin should be done via the online dropbox linked at the top of this page. Note that you should 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 may not receive credit for it.

You may discuss the assignment with others in the class, but your solution must be entirely your own work!

How Digital Sound Works
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 CSE326.

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

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

There is a windows version of sox available, and the source archive is known to compile and work on OS X 10.4. The program is also installed on the lab machines. You can download versions from the project page at SourceForge. The windows version is also a command-line program and works in the same way as the UNIX version described below. Follow this link for some hints on using it.

The general strategy for using sox is as follows.

Take a .wav sound file of your choosing (e.g. secret.wav). This sound shouldn't be longer than a couple seconds, or your program will run out of memory.
Convert it to a .dat file: sox secret.wav secret.dat
Manipulate it with the program you will write: java Reverse secret.dat secret-revealed.dat
Convert it back to a .wav file: sox secret-revealed.dat secret-revealed.wav
Listen to it! (Use your favorite sound player.)
That's all there is to it!

The .dat File Format
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 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 explaining the format because it will be helpful for you if you want to write a short file by hand to run, to verify if your program works.


Java Reminder
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);

double pop();

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:


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. You should include appropriate comments as needed. In particular, each file should begin with a JavaDoc comment that describes the class in the file, and includes your name and other identifying information.