代写CS2201留学生作业、代做C++ queue ADT作业

- 首页 >> C/C++编程


Fall 2019

Assignment No. 6

Purpose:

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

assignment.

The Assignment:

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.

Functional Specifications:

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

class.

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:

#include <chrono>

#include <random>

...

// 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

std::default_random_engine generator(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

“clipping”.

Sox can be downloaded from: http://prdownloads.sourceforge.net/sox/sox12181.zip?download

Other details:

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

simultaneously.

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).

Logistics:

• Electronic Turn-in: You should turn in the following files, named as follows:

o GuitarHero.cpp

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

question below.

• 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.

Write-up Questions:

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

complete it.

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.

Sample Execution:

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

..............................Done.

<Note: the number of “progress” dots produced will depend on how many you print per progress milestone, and how you define such

milestone.>

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

GuitarHero.cpp”

Additional information: More information on musical sounds and instruments can be found here.

Acknowledgments:

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.