handout #4

CSE143—Computer Programming II

Programming Assignment #2

due: Thursday, 1/21/16, 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:


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.

ampling from Karplus-Strong

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.

hite noise

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.

he Karplus-Strong update

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.



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

iano keyboard

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.

The Guitar interface is defined as follows:

public interface Guitar {

    public void playNote(int pitch);

          public boolean hasString(char key);

    public void pluck(char key);

    public double sample();

    public void tic();

    public int time();


You can specify exactly which note to play (playNote) or you can specify a character that indicates which note to play (pluck).  Different guitar objects will have different mappings from characters to notes.  There is a hasString method paired with pluck that lets you verify that a particular character has a corresponding string for this guitar.  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.  The Guitar interface also has methods for getting the current sound sample (the sum of all samples from the strings of the guitar), to advance the time forward one "tic," and an optional method for determining the current time (the number of times tic has been called).  If the time method is not implemented, it returns -1.

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.

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 TestGuitar37.  This testing code should be stored in a separate directory from your solution because it includes a custom version of the GuitarString class and you don’t want to accidentally overwrite your version of the class.  You should copy your Guitar37 class to this folder, run it, and then compare against the sample output produced 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:


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.