Assignment No. 6
This project is meant to give you experience in creating and using a queue ADT. In particular, you will implement a queue
ADT that will hold doubles. Your queue implementation will then be used to simulate the plucking of a guitar string
using the Karplus-Strong algorithm. This algorithm played a seminal role in the emergence of physically
modeled sound synthesis (where a physical description of a musical instrument is used to synthesize sound
electronically). This assignment will build upon our knowledge of sound files that we learned in the previous
You will create a program that reads a text file containing information on what notes are to be generated and when they
are to be generated, and from that create a sound file in the .dat format (the same .dat format as the previous assignment).
You have been provided with a starter file for the main program, GuitarHero.cpp that does some initial file
processing for you. Your task will be to define a queue that holds double values (DblQueue.h & DblQueue.cpp),
and to define a class that represents a guitar string (GuitarString.h & GuitarString.cpp) which uses the
queue. Finally you will complete the main program to generate a correct .dat file.
You will be provided starter files for DblQueue.h & GuitarString.h, which define the public interfaces of the
classes. You need to complete DblQueue.h and create DblQueue.cpp to implement an unbounded queue. Your
code should use a singly linked list as the basis for your implementation. You should test your queue implementation fully
before proceeding (use DblQueueTest.cpp). Once you complete the queue implementation, you will use it to
complete GuitarString.h and create GuitarString.cpp, a class that represents a guitar string. You should test
your GuitarString implementation fully before proceeding (use GuitarStringTest.cpp). The full API for both
classes is specified below.
After completing & testing the DblQueue and GuitarString classes, you will complete the code in
GuitarHero.cpp. The program reads data from a file which indicates which strings are to be plucked and when, and it
generates a data file for the sox program.
Simulating the Plucking of a Guitar String:
[Note: This is background information, so don’t get bogged down in it. Implementation details begin in the next section
titled “Functional Specifications”.] When a guitar string is plucked, the string vibrates to create 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 -½ and +½) at N equally spaced points (in time), where N equals the sampling rate (44,100 times per
second) divided by the fundamental frequency (rounded to the nearest integer).
• Plucking the string. The excitation of the string can contain energy at any frequency. We simulate the excitation by
filling a buffer (a queue in our case) with white noise: set each of the N sample displacements to a random real
number between -½ and +½.
• 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 buffer and adds to the end of the 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 an actual plucked string sounds.
DblQueue class: This class will provide support for an unbounded queue abstraction which holds double values. The
class should use a linked list as its underlying representation. It must support the following operations:
DblQueue() The default constructor that creates an empty queue.
DblQueue(const DblQueue& rhs) The copy constructor.
~DblQueue() The destructor.
const DblQueue& operator= (const DblQueue& rhs) The assignment operator.
bool isEmpty( ) const Tests whether the queue is empty.
void enqueue(const ItemType& item) Add an item to the end of the queue.
void dequeue( ) Remove the item at the front of the queue. If a dequeue( ) is attempted on an
empty queue then throw a std::underflow_error exception.
ItemType front( ) const Return the item at the front of the queue without removing it. If a front( ) is
attempted on an empty queue then throw a std::underflow_error exception.
size_t size( ) const Return the number of items on the queue.
Note 1: Be sure to name your files, classes, and methods exactly as specified; in particular, the files are named
DblQueue.h & DblQueue.cpp, with capital 'D' and 'Q', and the class is named DblQueue.
Note 2: The DblQueue.h file should use a typedef to define the new type ItemType. You should use this data type
whenever you specify the type of data that your queue will be holding. If you ever want to change the type of data that the
queue holds, you will only need to change one line of code.
Note 3: Your implementation is to be based on a singly linked list.
Note 4: The five methods of the stack class (enqueue, dequeue, front, isEmpty, & size) should all operate in O(1) time.
Note 5: To throw an underflow exception, you would write code such as:
throw std::underflow_error("The queue is empty");
Note that there is no “new” operation as needed when throwing exceptions in Java.
Other details: Here are a few notes that might be helpful:
1. Continue to use type size_t when appropriate.
2. Use the base initialization list for your constructors whenever possible.
3. You are free to add private helper methods to the class. You are not allowed to change the public interface of the
4. It is true that for representing a guitar string it would be sufficient to use a bounded queue, since the frequency of a
guitar string does not change once it has been created. However, you are required to implement an unbounded queue,
as you will need it for the next assignment.
GuitarString class: This class will model/simulate a vibrating guitar string of a given frequency. Implement a class
named GuitarString with the following API:
GuitarString(double frequency) The constructor for a string of the given frequency. Throw a std::invalid_argument
exception if the frequency is not positive.
void pluck() Fill the string’s buffer with white noise.
void tic() Advance the simulation one time step.
double sample() const Return the current sample.
size_t getTime() const Return number of tics.
double getFrequency() const Return the frequency of the string.
Each GuitarString object will need an internal queue (use a DblQueue) to act as its ring buffer feedback mechanism.
Constructor: create a ring buffer of the desired capacity N (sampling rate divided by frequency, rounded to the nearest
integer) by initializing a queue and filling the queue to represent a guitar string at rest by enqueueing N zeros.
pluck: Replace the N elements in the ring buffer (queue) with N random values between -0.5 and +0.5 (code to generate
random values is given below).
tic: Apply the Karplus-Strong update: delete the sample at the front of the buffer and add to the end of the buffer the
average of the deleted sample & the next sample, multiplied by the energy decay factor. A tic represents that our string
has been told to advance one time increment in its simulation.
sample: Return the value of the item at the front of the buffer.
getTime: Return the total number of times tic() was called since the object was created. This provides information on
how long the simulation of the current string has been running.
getFrequency: Return the frequency that was specified in the constructor.
Note 1: Be sure to name your files, classes, and methods exactly as specified; in particular, the files are named
GuitarString.h & GuitarString.cpp, with capital 'G' and 'S', and the class is named GuitarString.
Note 2: There is no default constructor for this class.
Note 3: If your GuitarString class performs any dynamic memory allocation, be sure to include the Big 3.
Note 4: You can add private data members to the class as you see fit. You are free to add private helper methods to the
class, but you are not allowed to change the public interface of the class.
Note 5: To generate a random number in the range -0.5 to +0.5 you can use the random number generation facilities
provided by C++ (this is new in C++11). These facilities are defined in <random>, so you will need to perform the
appropriate #include. You will need to create a generator object. This object will be capable of generating pseudo-
random numbers for you (they are pseudo-random since you get the same sequence of random numbers when started with
the same seed). Thus it is standard practice to seed the random number generator with a value based on time (which
requires #include <chrono>). After creating the generator object, you will need to create a distribution object. This
object directs what kind of random numbers will be generated. In our case we want double values in the range -0.5 to
+0.5. Once we have these two objects, we can get the desired random numbers by invoking the distribution object and
passing it the generator object. Here is the code you can use:
// then later in your code where you want to generate random numbers, do:
// create the seed
unsigned seed = (unsigned) std::chrono::system_clock::now().time_since_epoch().count();
// create the generator using the seed
// create the appropriate distribution
std::uniform_real_distribution<double> distribution(-0.5, 0.5);
// create random numbers as needed (the following will likely be in a loop)
double num = distribution(generator);
You should create the seed, generator, and distribution object only once per pluck or once per program execution. You
can then use the distribution object as many times as needed to create random numbers. You can see an example of using
these functions on this page: http://www.cplusplus.com/reference/random/uniform_real_distribution/.
Main: The main method in GuitarHero.cpp currently performs the following actions: (1) It creates an array of 3
octaves worth of GuitarString pointers, and dynamically creates a GuitarString object for each array element. These guitar
strings represent a total of 37 notes on the chromatic scale from 110Hz to 880Hz. See the diagram below for a mapping of
array index to note. (2) The program then prompts the user for the name of the input & output files. It opens the files and
primes the output file with the first two required comment lines of a .dat file used by sox. (3) The program then closes all
files and frees all the created guitar strings. Between steps 2 & 3 is where you will need to do your work of reading the
input file and generating data for the output file.
The input file is an ASCII text file. Each line of the file contains two numeric values. The first value of each line is a
double value indicating a time (in seconds) when the corresponding guitar string is to be plucked. The lines of the file
must be in chronological order of this time value. The second value of each line is an integer value in the range -1 to 36.
The values 0-36 are indices into the array of guitar strings, indicating which string is to be plucked. The value -1 is a
special “end song” value which indicates that the song should end at the specified time (this allows you to specify a fadeout
period for your last note played). Here is sample data file that plays a concert C scale (C-E-G-C). The first C note
(index 3) is played at a half second, the E note is played at 1 second, the G is played at 1.5 seconds, and the final C note is
played at 2 seconds. These notes die out over the next second until we hit the “end song” flag at the 3 second mark.
Your task is to read the input file and generate the desired .dat output file. Recall from the last assignment that digitized
sound is sampled at 44100 samples per second. That implies that your output file should contain 44100 lines of output for
each second of sound generated. You will need to write some type of loop nest that simulates the passing of time (e.g.,
increments a clock counter (type double) in steps of size 1/44100), and also reads all the data in the input file (you process
the line of data when the clock counter reaches the specified time). If the time for the next note has not been reached, you
need to sample & tic all guitar strings, and produce a single line of output in the output file. As you sample all the strings,
you need to sum up all the samples to produce a single cumulative sample which is the sound value you write to the
output file for that time step. When the time for the next note has been reached, you pluck the specified string (unless you
reach the “end song” value in which case you stop generating any more sounds). You continue this process until the time
for the “end song” value is encountered or the input data file is exhausted.
Once you have a .dat file generated, use the sox program to create a corresponding .wav file (just like the last assignment)
and listen to it with your computer’s media player. You can ignore messages from sox about clipped samples. As we
generate sounds, those sounds represent the culmination of all the strings, and thus some sound values may be outside the
range -1.0 to +1.0. When sox encounters such values it must cut them down into the range -1.0 to +1.0 – this is called
Sox can be downloaded from: http://prdownloads.sourceforge.net/sox/sox12181.zip?download
Here are a few notes that you need to keep in mind:
1. The array of strings contains GuitarString pointers. You need to dereference the pointers to access the GuitarString
objects. This is accomplished most easily with arrow notation; e.g., strings[i]->tic();
2. You should verify all data read from the input file. The time values need to be in chronological order and the note
values must be in the range -1 to 36 (inclusive). If an input value is not valid, generate a std::out_of_range
exception. Note that it is valid for adjacent lines to have the same time value, indicating that those strings are plucked
3. The .dat output file has the same format as the previous assignment. Please review the spec and your code for that
assignment. The data you generate in the .dat file should start at time zero (which may not be the first time specified
in the input file), increase by the time step value (1/44100), and finally stop at the time of the last note (or the special
“end song” indicator).
4. You may assume the input file always has pairs of values. That is, if you are able to extract a time value then there
will always be an associated note value. You may also assume the input file has at least one pair of values.
5. You should write helper functions to isolate complex logic and to make your program easier to read/understand. Each
function should be a reasonable length (less than 40 lines of code).
6. The DblQueue class is needed for the GuitarString class. You do not need to use the DblQueue class for any other
processing in this assignment; in particular you should not use queues as temporary storage as you read data from the
input file or as you generate data for the output file – rather you should read data only as it is needed and you should
write data to the output file as it is generated.
7. You may want your program to give some indication that it is making progress since generating a large .dat file will
be time consuming. Do this in a way so as to not overwhelm the user. I.e., generate a dot or two for each pluck of a
string or for each full/partial second of music generated, but not for each time step that is computed (since there are
44.1k steps per second of music generated).
• Electronic Turn-in: You should turn in the following files, named as follows:
o DblQueue.h, DblQueue.cpp, and DblQueueTest.cpp
o GuitarString.h, GuitarString.cpp and GuitarStringTest.cpp
o a README document (a .txt text file or a .doc Word document), containing the answers to each writeup
• Each file you turn in should have the standard block comments at the top of the file, including an honor statement.
Be sure to use good programming style.
• You must implement the linked-list queue by writing your own queue code - you may not use any classes from
the C++ standard template library to do the work.
Electronic turn-in should be done via the assignment page in Brightspace. Be sure to attach all the required files prior to
hitting the "Submit" button. Please do not zip up your entire project directory for submission, as the file would be
extremely large – just submit the six required files.
Answer the following questions in the README text file you are to submit for grading.
1. State your name and email address.
2. After reviewing this spec and the provided files, please estimate/report how long you think it will take you to
3. How many hours did you actually spend total on this assignment?
4. Who/What did you find helpful for this project?
5. How did you test that the final program is correct?
6. How did you test that your queue implementation is correct?
7. What did you enjoy about this assignment? What did you hate?
8. Do you have any suggestions for improving this assignment?
Please contact me if you find errors in this document or you feel something is missing or unnecessarily confusing.
Feel free to share any input files you create that generate interesting music by posting them to Piazza.
Enter the name of the input file: song.txt
Enter the name of the output file: song.dat
Reading the input file and generating a .dat file for sox
<Note: the number of “progress” dots produced will depend on how many you print per progress milestone, and how you define such
Sharing song files:
Past students have had a great deal of fun creating songs for their GuitarHero program. I even gave extra credit to the two
songs that received the most votes in a poll. Unfortunately, with the increase enrollment of the class, it is difficult for me
to manage all song submissions and so there is no longer an extra credit option. But you are free to share your songs with
the rest of the class. Please post your songs to Piazza (post it as a Note rather than a Question). You can post as many song
files as you wish. Please limit songs to 30 seconds or less in playing time. Please only post the .txt files -- do not post the
.dat or the .wav files. You can post anonymously if you want.
Let your inner Guitar Hero go wild!!
Past student feedback from README file:
“I do agree with Professor Roth emphasizing for us to read the spec file many times, because it is essential to implement
Additional information: More information on musical sounds and instruments can be found here.
This assignment is a modification of a submission made by Kevin Wayne to the Nifty Assignments collection. It was originally designed at Princeton
University by Andrew Appel, Jeff Bernstein, Maia Ginsburg, Ken Steiglitz, Ge Wang, and Kevin Wayne.