import java.io.BufferedReader;

import java.io.BufferedWriter;

import java.io.FileReader;

import java.io.FileWriter;

import java.io.IOException;

import java.io.PrintWriter;

import java.util.StringTokenizer;

/**

* Read a .dat file and reverse it.

*/

public class Reverse {

public static void main(String[]args) {

if (args.length != 3) {

System.err.println(" Incorrect number of arguments");

System.err.println(" Usage: ");

System.err.

println("\tjava Reverse <stack type> <input file> <output file>");

System.exit(1);

}

boolean useList = true;

if (args[0].compareTo("list")==0)

useList = true;

else if (args[0].compareTo("array")==0)

useList = false;

else {

System.err.println("\tSaw "+args[0]+" instead of list or array as first argument");

System.exit(1);

}

try {

//

// Set up the input file to read, and the output file to write to

//

BufferedReader fileIn =

new BufferedReader(new FileReader(args[1]));

PrintWriter fileOut =

new PrintWriter(new

BufferedWriter(new FileWriter(args[2])));

//

// Read the first line of the .dat file to get sample rate.

// We want to store the sample rate value in a variable,

// but we can ignore the "; Sample Rate" part of the line.

// Step through the first line one token (word) at a time

// using the StringTokenizer. The fourth token is the one

// we want (the sample rate).

//

StringTokenizer str;

String oneLine;

int sampleRate;

String strJunk;

oneLine = fileIn.readLine();

str = new StringTokenizer(oneLine);

strJunk = str.nextToken(); // Read in semicolon

strJunk = str.nextToken(); // Read in "Sample"

strJunk = str.nextToken(); // Read in "Rate"

// Read in sample rate

sampleRate = Integer.parseInt(str.nextToken());

//

// Read in the remainder of the file on line at a time.

// The values in the first column are thrown away.

// Place values from the second column on the stack.

// Stop reading if we reach the end of the file.

//

DStack s;

if (useList)

s = new ListStack();

else

s = new ArrayStack();

String timestep;

double data;

int count = 0;

while ((oneLine = fileIn.readLine()) != null) {

if (oneLine.charAt(0) == ';') {

continue;

}

str = new StringTokenizer(oneLine);

// Read in time step value from first column

timestep = str.nextToken();

// Read in data value from second column

data = Double.parseDouble(str.nextToken());

s.push(data);

count++;

}

System.out.println(count+" samples in file");

//

// Print the data values to output .dat file.

// First, output the header line:

// "; Sample Rate <sample rate>"

//

fileOut.println("; Sample Rate " + sampleRate);

// Since the first column consists of numbers which start

// at 0 and increase by 1/sampleRate every time slice, we'll

// just use numSteps to recalculate these numbers.

int numSteps = 0;

// Finally, we print the values in reverse order (by popping

// them off the stack). The first column consists of numbers

// which start at 0 and increase by 1/sampleRate per row, so

// we'll use numSteps/sampleRate to recalculate the appropriate

// values. Print a tab for uniform spacing.

while (!s.isEmpty()) {

fileOut.println((double) numSteps / sampleRate + "\t" +

s.pop());

numSteps++;

}

//

// Close the files

//

fileIn.close();

fileOut.close();

} catch(IOException ioe) {

System.err.

println

("Error opening/reading/writing input or output file.");

System.exit(1);

} catch(NumberFormatException nfe) {

System.err.println(nfe.toString());

System.err.println("Error in file format");

System.exit(1);

}

}

}

/**

* Interface for a stack of primitive doubles.

*

* NOTE: The comments for this interface are horrible! You will

* need to write something better for your implementations.

*/

public interface DStack {

/**

* is empty?

*/

public boolean isEmpty();

/**

* push

*/

public void push(double d);

/**

* pop

* @return the deleted value

* @throws EmptyStackException if stack is empty

*/

public double pop();

/**

* peek

* @throws EmptyStackException if stack is empty

*/

public double peek();

}

1. Purpose

The purpose of this assignment 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.

2. Description

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. You will write a program that reads a sound file in

the .dat format and writes another .dat sound file which is the reverse of the first. The sample

code has 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. The

sample code has also provided an interface DStack, which defines a stack that holds double

values. Your first job is to familiarize yourself with these files.

2.1. Implementing the Stack ADT (70 points)

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. Reverse should work and create backward sound files once

you complete these two 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.

2.2. Running Reverse (10 points)

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 Netbeans select Build->Run Arguments and a bar

will appear at the top of the screen that allows you to type in the arguments. Read more about

setting command line parameters in Netbeans.)

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.

Note that Reverse.java just uses your stacks in one particular way: pushing a bunch of

elements onto the stack and then popping them all off.

2.3. Questions (20 points)

Sumbit a report (in word or pdf), answering the questions below.

1. How did you test that your stack implementations were correct?

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

3. Your array stacks start with a small array and double in size if they become full. For

a .dat file with 1 million lines, how many times would this resizing occur? What about

with 1 billion lines or 1 trillion lines (assuming the computer had enough memory)?

Explain your answer.

4. Include a description of how your project goes "bonus components" the basic

requirements (if it does).

5. What did you enjoy about this assignment? What did you not enjoy? What could you

have done better?

6. What else, if anything, would you would like to include related to this homework?

2.4. Bonus Components (3 points)

The following suggestion is meant for you to try if you finish the requirements early.

• Modify your array implementations so that when the array is 3/4 empty, the stack resizes

to use an array of half the size.

2.5. Java Help

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.

Turn in ：ArrayStack.java

• ListStack.java

• ListStackNode.java, the linked-list node for use with your ListStack class. However,

you are also free to use an inner class inside ListStack in which case you will not have a

separate file.

Write answers for 2.3) Questions in a word file. Print the word file and submit it in

class