CSC 321: Data Structures
Fall 2012

HW2: Queues & Music

This assignment is based on 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 methods:

public PianoWire(int rate, double frequency)
The class constructor takes two inputs, the sampling rate (which is usually 44,100) and the fundamental frequency of the wire. The constructor should initialize a queue containing N zeros, where N is the sampling rate divided by the fundamental frequency (rounded to the nearest integer).
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 number of values in 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 following classes:

The mapping from keyboard keys to piano keys used by the Piano class and thus supported by InteractivePiano is shown here:

Piano key mapping

Part 2: Modifying the piano model (15%)

Once you have your interactive piano working correctly, modify the Piano class so that it is more general-purpose. Instead of hard-coding the character mapping, add a second constructor that takes a string of characters as input. When called, this new constructor should map the characters in its input String to the piano keys (wires). For example, the statement Piano p = new Piano("12345678"); would create a piano with only 8 wires, labeled by the digits and ascending in frequency. There should still be a default constructor that results in the provided "q2we4r5..." mapping.

You should test your general-purpose class by constructing and playing several Piano objects with different keyboard mappings.

Part 3: Modeling a player piano (35%)

Finally, you are to implement an alternative interface for playing music with a piano. The PlayerPiano class should contain a main method that reads characters from a file and converts those characters to sounds (using a Piano object). The means of obtaining the file name is up to you - you may implement a GUI or just use a text prompt.

The first line of a music file will contain a series of characters that defines the character mapping assumed for that file. Your code will need to construct a Piano object using that mapping. The rest of the file will contain strings, one per line, that are to be played in sequence. For example, if a line contained the single character "e", then the wire corresponding to 'e' for that particular piano should be played. If a line contained the sequence "etu", then three wires (corresponding to the characters 'e', 't', and 'u') should be struck simultaneously. Each line of music should be played for a set period (equal to half the sampling rate) before moving on to the next line.

For example, the file chopsticks.txt contains one possible encoding of Chopsticks.