handout #5
CSE143—Computer Programming II
Programming Assignment #2
due: Thursday, 1/23/14, 9 pm
many thanks to Kevin Wayne for this nifty assignment
This programming assignment will give
you practice with queues, interfaces, objects, and arrays of objects. You are going to implement two classes that
allow us to simulate a guitar. We will
be using two utility classes known as StdAudio and StdDraw that are used in the
Princeton intro CS course. You don’t
have to understand the details of these utility classes, but if you are
interested, you can read about them at the following url:
http://introcs.cs.princeton.edu/java/stdlib/
When a guitar string is plucked, the
string vibrates and creates sound. The length of the string determines its
fundamental frequency of vibration. We model a guitar string by sampling its
displacement (a real number between -1/2 and +1/2) at N equally spaced points
(in time), where N equals the sampling rate (44,100) divided by the fundamental
frequency (rounded to the nearest integer).
We store these displacement values in a structure that we will refer to
as a ring buffer.
Plucking
the string
The
excitation of the string can contain energy at any frequency. We simulate the
excitation by filling the ring buffer with white noise: set each of the N
sample displacements to a random real number between -1/2 and +1/2.
The
resulting vibrations
After
the string is plucked, the string vibrates. The pluck causes a displacement
which spreads wave-like over time. The Karplus-Strong algorithm simulates this
vibration by maintaining a ring buffer of the N samples: the algorithm
repeatedly deletes the first sample from the ring buffer and adds to the end of
the ring buffer the average of the first two samples, scaled by an energy decay
factor of 0.996.
Why
it works
The
two primary components that make the Karplus-Strong algorithm work are the ring
buffer feedback mechanism and the averaging operation.
·
The
ring buffer feedback mechanism. The ring buffer models the medium (a string
tied down at both ends) in which the energy travels back and forth. The length
of the ring buffer determines the fundamental frequency of the resulting sound.
Sonically, the feedback mechanism reinforces only the fundamental frequency and
its harmonics (frequencies at integer multiples of the fundamental). The energy
decay factor (.996 in this case) models the slight dissipation in energy as the
wave makes a roundtrip through the string.
·
The
averaging operation. The averaging operation serves as a gentle low pass filter
(which removes higher frequencies while allowing lower frequencies to pass,
hence the name). Because it is in the path of the feedback, this has the effect
of gradually attenuating the higher harmonics while keeping the lower ones,
which corresponds closely with how actually plucked
strings sound.
Part
1: GuitarString Class
In the first part of the assignment, you
will implement a class called GuitarString that models a vibrating guitar
string of a given frequency. The
GuitarString object will need to keep track of a ring buffer. You are to implement the ring buffer as a
queue using the Queue<E> interface and the LinkedList<E>
implementation. You are not allowed to
use other data structures to solve this problem. You must solve it with a queue.
Your class should have the following
public methods.
Method |
Description |
GuitarString(double
frequency) |
Constructs
a guitar string of the given frequency.
It creates a ring buffer of the desired capacity N (sampling rate
divided by frequency, rounded to the nearest integer), and initializes it to
represent a guitar string at rest by enqueueing N zeros. The sampling rate is specified by the
constant StdAudio.SAMPLE_RATE. If the
frequency is less than or equal to 0 or if the resulting size of the ring
buffer would be less than 2, your method should throw an
IllegalArgumentException. |
GuitarString(double[]
init) |
Constructs
a guitar string and initializes the contents of the ring buffer to the values
in the array. If the array has fewer
than two elements, your constructor should throw an
IllegalArgumentException. This
constructor is used only for testing purposes. |
void
pluck() |
This
method should replace the N elements in the ring buffer with N random values between
-0.5 inclusive and +0.5 exclusive (i.e. -0.5 <= value < 0.5). |
void
tic() |
This
method should apply the Karplus-Strong update once. It should delete the sample at the front of
the ring buffer and add to the end of the ring buffer the average of the
first two samples, multiplied by the energy decay factor (0.996). Your class should include a public constant
for the energy decay factor. |
double
sample() |
This
method should return the current sample (the value at the front of the ring
buffer). |
You will be provided with a testing
program that you can use to verify that your class has the basic functionality
that is required. The testing program
will not check to make sure that you are using a queue and that you are
checking for appropriate exceptions to throw and that you are using the queue
efficiently.
It is difficult in commenting the GuitarString class to know what constitutes an
implementation detail and what is okay to discuss in client comments. Assume that a client of the GuitarString class is familiar with the concept of a ring
buffer. The fact that we are
implementing it as a queue is an implementation detail. So don’t mention how you implement the ring
buffer. But you can discuss the ring
buffer itself and the changes that your methods make to the state of the ring
buffer (e.g., moving values from the front to the back of the ring buffer).
Normally we would encourage you to write
a single constructor and to use the “this(…)” notation
to have one constructor call another.
That won’t be possible for the GuitarString
class because the two constructors are completely different.
Because you are using Java’s queue
structure to implement the GuitarString, you will
need to include this import declaration at the beginning of the class:
import java.util.*;
Part
1: Guitar37 Class
In
the second part of the assignment, you are going to build on the GuitarString
class to write a class that keeps track of a musical instrument with multiple
strings. There could be many possible
guitar objects with different kinds of strings.
As a result, we introduce an interface known as Guitar that each guitar object implements.
You are being provided with a sample
class called GuitarLite.java that implements the Guitar interface. Once you have verified that your GuitarString
class passes the testing program, you can play the GuitarLite instrument. It has only two strings: a
and c. Keep in mind that
GuitarLite does not have a main method.
There is a separate class called GuitarHero that has main (the initial
version constructs a GuitarLite object).
In this second part of the assignment,
your task is to make a variation of GuitarLite known as Guitar37. It will model a guitar with 37 different
strings. Because it has so many strings,
we will want to keep track of them in a data structure. Your Guiter37 objects should each keep track
of an array of 37 GuitarString objects.
The Guitar37 class has a total of 37
notes on the chromatic scale from 110Hz to 880Hz. We will use the following string to map keys
typed by the user to positions in your array of strings. The i-th character
of this string should correspond to the i-th character of your array:
"q2we4r5ty7u8i9op-[=zxdcfvgbnjmk,.;/' "
This "keyboard" arrangement
imitates a piano keyboard, making playing songs a little easier for people used
to a piano keyboard. The "white keys" are on the qwerty
and zxcv rows and the "black keys" on the 12345 and asdf rows of the
keyboard, as in the drawing below.
You are being provided a skeleton
version of the Guitar37 class that includes this string defined as a constant
called KEYBOARD. The i-th character of
the string corresponds to a frequency of 440 × 2(i - 24) / 12, so
that the character “q” is 110Hz, “i” is 220Hz, “v” is
440Hz, and “ ” (space) is 880Hz.
In working on this second part of the
assignment, you are generalizing the code that you will find in
GuitarLite. Because that instrument has
just two strings, it uses two separate fields.
Your instrument has 37 strings, so it uses an array of strings. Each of the operations defined in the
interface needs to be generalized from using two specific strings to using an
array of strings. For example, the sample
method returns the sum of the current samples.
GuitarLite does this by adding together two numbers. Your version will have to use a loop to find
the sum of all 37 samples.
A description of the Guitar interface methods
appears below.
public interface Guitar {
// plays the given note if possible by plucking an appropriate string;
// the pitch uses a chromatic scale where Concert-A has a pitch of 12
public void playNote(int pitch);
// returns whether there is a string that corresponds to this character
public boolean hasString(char key);
// plucks the string for this character
public void pluck(char key);
// returns the current sound (sum of all strings)
public double sample();
// advances the simulation by having each string tic forward
public void tic();
// optional method that returns the number of times tic has been called;
// returns -1 if not implemented
public int time();
}
The GuitarLite class is not well
documented and does not handle illegal keys.
Your Guitar37 class should include complete comments. The pluck method should throw an
IllegalArgumentException if the key is not one of the 37 keys it is designed to
play. Recall that strings have an indexOf method that you might find helpful. In some of the String documentation you will
see that some methods take a parameter of type CharSequence. You can think of this as being a parameter of
type String.
As noted in the interface, the method
called time is optional. It is not
implemented in the GuitarLite class, but you should
implement it in the Guitar37 class.
In writing the playNote
method for Guitar37, notice that concert-A is assumed to have a pitch of
12. As noted earlier, the character “v”
is concert-A, which has index 24 in the keyboard string. You can convert from a pitch value to an
index in your string by adding 12 to the pitch value. Remember that not every value of pitch can be
played by any given guitar. If it can’t
be played, it is ignored. It should not
cause your code to throw an exception.
In order to run the program, you will
have to have the files StdAudio.java and StdDraw.java in the same folder as
your other class files. Remember that
the main method runs indefinitely. As
demonstrated in lecture, you can select a quit option from the GuitarHero
window that pops up or you can use the End command in jGRASP.
As mentioned earlier, the ring buffer in
your GuitarString class should be implemented as a queue. You are allowed to use any of the methods
defined in the Queue interface. In
particular, you are allowed to use the peek method that allows you to examine
the value at the front of the queue without removing it. The GuitarString class would be inefficient
if you didn’t have the ability to peek at the front of the queue.
To generate random real numbers, you can
either call the Math.random method or you can construct a Random object and
call its nextDouble method. Both methods
return a random real value n such that 0 ≤ n <
1.
You will be given a testing program for
Guitar37 as well called DebugThatTune. You should run it on the sample input files
and then compare against the sample output files using the output comparison
tool.
In terms of correctness, your class must
provide all of the functionality described above and must satisfy all of the
constraints mentioned in this writeup.
In terms of style, we will be grading on your use of comments, good
variable names, consistent indentation, minimal fields and good coding style to
implement these operations.
It is likely that you will make a
mistake somewhere in specifying your generic structures. When you do so, the Java compiler will warn
you that you have “unchecked or unsafe operations” in your program. You will lose style points if you don’t fix
these warnings. You can have jGRASP show
you the exact line by going to: Settings/Compiler Settings/Workspace/Flags / Args and then uncheck the box next to "Compile"
and type in:
-Xlint:unchecked
You should name your files
GuitarString.java and Guitar37.java and you should turn them in electronically
from the “Homework” tab on the class web page.