CSC 321: Data Structures
Fall 2013

HW2: Queues & Music

This assignment is inispired by a Nifty Assignment introduced by Kevin Wayne (Princeton University) and refined by Stuart Reges (University of Washington).


When a piano wire is struck, the wire vibrates and creates sound. The vibration can be measured by sampling the displacement of the wire at equally spaced points. These displacement measurements can be stored digitally, say in a list or queue structure, then used to recreate the sound wave over a speaker.

Sample Displacements

For this assignment, you will store the displacement values for a piano wire in a queue structure. When at rest, the wire can contain energy at any frequency. This is modeled by assigning the queue to contain random real numbers between -1/2 and +1/2. After the wire is struck, it vibrates causing a displacement that spreads wave-like over time. The Karplus-Strong algorithm simulates this vibration using a fairly simple update process: it repeatedly deletes the first sample from the queue and adds to the end of the queue the average of the first two samples, scaled by an energy decay factor of 0.996.

Karplus-Strong algorithm

This simple algorithm provides an effective model of the wire vibration due to two features: the queue feedback mechanism and the averaging operation.

  1. The queue feedback mechanism. The queue models the medium (a wire fixed at both ends) in which the energy travels back and forth. The length of the queue 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 wire.
  2. The averaging operation. The averaging operation serves as a gentle low pass filter (which removes higher frequencies while allowing lower frequencies to pass). 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 a struck wire actually sounds.

Part 1: Modeling a piano wire (50%)

For the first part of this assignment, you are to implement a class that models a single piano wire. Your PianoWire class should provide the following constructor and methods:

public PianoWire(int wireNum)
The class constructor takes a single input, a non-negative integer that specifies the wire number (relative to C). That is, a parameter of 0 will produce a C string, 1 will produce C#, 2 will produce D..., etc. The constructor should initialize a queue containing N zeros, where N is the nearest integer to:

        SAMPLE_RATE * 2(22 - wireNum)/12 / 440

Here, SAMPLE_RATE is a constant defined in the StdAudio class, which was developed at Princeton.

public void strike()
This method simulates striking the wire by replacing all of the values in the queue with random values from the range -0.5 to 0.5. The size of the queue should remain unchanged.

public double sample()
This method returns the value currently stored at the front of the queue. It also updates the contents of the queue so that a different sample is obtained each time the method is called. The update removes the value currently at the front and adds a new value to the rear, which is the average of the two front values multiplied by a decay factor of 0.996. See the previous diagram for an example of this update operation.

You should test your class thoroughly by creating an object with a short queue and displaying the results of each update. Once you are convinced that the class is behaving as desired, you may integrate it with the provided Piano class. This class implements a simple piano, with keyboard keys mapping to individual wires. The routines for rendering the vibrations using your computer's sound card are contained in the utility class StdAudio. The routines for processing keyboard events are contained in the utility class StdDraw, which was also developed at Princeton.

Part 2: Modeling a player piano (50%)

A player piano is a mechanical piano that uses some medium (often paper rolls with patterns of holes) to encode the notes and chords of a composition. The player piano mechanism interprets the pattern and automates the playing of that composition. You are to implement a PlayerPiano class that automates the playing of a composition on a Piano object. The main method of your class should prompt the user for the name of a text file, read in the contents of the file, and play the notes/chords.

Your class should utilize a piano with 3 octaves. The 12 notes in the middle octave are denoted:

    "C", "C#" or "Db", "D", "D#" or "Eb", "E", "F", "F#" or "Gb", "G", "G#" or "Ab", "A", "A#" or "Bb", "B"

Note that the black keys in an octave can be denoted in two ways, as a sharp (using "#") or a flat (using "b"). The notes in the lower octave are the same but with a "-" character at the end (e.g., "C-" is low-C). Similarly, the notes in the higher octave are the same but with a "+" character at the end (e.g., "Eb+" is high-E-flat). Notes that appear on the same line of the file should be played simultaneously. This is accomplished by striking all of the corresponding wires, then calling the Piano.play method in a loop to control the duration. Each note/chord should play for 0.5 seconds (i.e., repeatedly play the notes SAMPLE_RATE/2 times).

Files that encode Chopsticks and Mary had a Little Lamb are provided for you.