Fall 2019Assignment No. 6Purpose:This project is meant to give you experience in creating and using a queue ADT. In particular, you will implement a queueADT that will hold doubles. Your queue implementation will then be used to simulate the plucking of a guitar stringusing the Karplus-Strong algorithm. This algorithm played a seminal role in the emergence of physicallymodeled sound synthesis (where a physical description of a musical instrument is used to synthesize soundelectronically). This assignment will build upon our knowledge of sound files that we learned in the previousassignment.The Assignment:You will create a program that reads a text file containing information on what notes are to be generated and when theyare 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 fileprocessing 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 thequeue. 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 theclasses. You need to complete DblQueue.h and create DblQueue.cpp to implement an unbounded queue. Yourcode should use a singly linked list as the basis for your implementation. You should test your queue implementation fullybefore proceeding (use DblQueueTest.cpp). Once you complete the queue implementation, you will use it tocomplete GuitarString.h and create GuitarString.cpp, a class that represents a guitar string. You should testyour GuitarString implementation fully before proceeding (use GuitarStringTest.cpp). The full API for bothclasses is specified below.After completing & testing the DblQueue and GuitarString classes, you will complete the code inGuitarHero.cpp. The program reads data from a file which indicates which strings are to be plucked and when, and itgenerates 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 sectiontitled “Functional Specifications”.] When a guitar string is plucked, the string vibrates to create sound. The length of thestring determines its fundamental frequency of vibration. We model a guitar string by sampling its displacement (a realnumber between -½ and +½) at N equally spaced points (in time), where N equals the sampling rate (44,100 times persecond) 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 byfilling a buffer (a queue in our case) with white noise: set each of the N sample displacements to a random realnumber between -½ and +½.• The resulting vibrations. After the string is plucked, the string vibrates. The pluck causes a displacement whichspreads wave-like over time. The Karplus-Strong algorithm simulates this vibration by maintaining a ring buffer ofthe N samples: the algorithm repeatedly deletes the first sample from the buffer and adds to the end of the buffer theaverage 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 feedbackmechanism and the averaging operation.• The ring buffer feedback mechanism. The ring buffer models the medium (a string tied down at both ends) in whichthe energy travels back and forth. The length of the ring buffer determines the fundamental frequency of the resultingsound. Sonically, the feedback mechanism reinforces only the fundamental frequency and its harmonics (frequenciesat integer multiples of the fundamental). The energy decay factor (.996 in this case) models the slight dissipation inenergy as the wave makes a roundtrip through the string.• The averaging operation. The averaging operation serves as a gentle low pass filter (which removes higherfrequencies while allowing lower frequencies to pass, hence the name). Because it is in the path of the feedback, thishas the effect of gradually attenuating the higher harmonics while keeping the lower ones, which corresponds closelywith how an actual plucked string sounds.Functional Specifications:DblQueue class: This class will provide support for an unbounded queue abstraction which holds double values. Theclass 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 anempty 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( ) isattempted 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 namedDblQueue.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 typewhenever you specify the type of data that your queue will be holding. If you ever want to change the type of data that thequeue 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 theclass.4. It is true that for representing a guitar string it would be sufficient to use a bounded queue, since the frequency of aguitar 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 classnamed GuitarString with the following API:GuitarString(double frequency) The constructor for a string of the given frequency. Throw a std::invalid_argumentexception 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 nearestinteger) 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 generaterandom 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 theaverage of the deleted sample & the next sample, multiplied by the energy decay factor. A tic represents that our stringhas 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 onhow 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 namedGuitarString.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 theclass, 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 facilitiesprovided by C++ (this is new in C++11). These facilities are defined in , so you will need to perform theappropriate #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 withthe same seed). Thus it is standard practice to seed the random number generator with a value based on time (whichrequires #include ). After creating the generator object, you will need to create a distribution object. Thisobject 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 nu代写CS2201、代做queue ADT、代写C++编程设计mbers by invoking the distribution object andpassing it the generator object. Here is the code you can use:#include #include ...// then later in your code where you want to generate random numbers, do:// create the seedunsigned seed = (unsigned) std::chrono::system_clock::now().time_since_epoch().count();// create the generator using the seedstd::default_random_engine generator(seed);// create the appropriate distributionstd::uniform_real_distribution 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. Youcan then use the distribution object as many times as needed to create random numbers. You can see an example of usingthese 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 3octaves worth of GuitarString pointers, and dynamically creates a GuitarString object for each array element. These guitarstrings represent a total of 37 notes on the chromatic scale from 110Hz to 880Hz. See the diagram below for a mapping ofarray index to note. (2) The program then prompts the user for the name of the input & output files. It opens the files andprimes the output file with the first two required comment lines of a .dat file used by sox. (3) The program then closes allfiles and frees all the created guitar strings. Between steps 2 & 3 is where you will need to do your work of reading theinput 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 adouble value indicating a time (in seconds) when the corresponding guitar string is to be plucked. The lines of the filemust 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 aspecial “end song” value which indicates that the song should end at the specified time (this allows you to specify a fadeoutperiod 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 isplayed 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 digitizedsound is sampled at 44100 samples per second. That implies that your output file should contain 44100 lines of output foreach 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 processthe line of data when the clock counter reaches the specified time). If the time for the next note has not been reached, youneed 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 theoutput file for that time step. When the time for the next note has been reached, you pluck the specified string (unless youreach the “end song” value in which case you stop generating any more sounds). You continue this process until the timefor 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 wegenerate sounds, those sounds represent the culmination of all the strings, and thus some sound values may be outside therange -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?downloadOther 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 GuitarStringobjects. 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 notevalues must be in the range -1 to 36 (inclusive). If an input value is not valid, generate a std::out_of_rangeexception. Note that it is valid for adjacent lines to have the same time value, indicating that those strings are pluckedsimultaneously.3. The .dat output file has the same format as the previous assignment. Please review the spec and your code for thatassignment. The data you generate in the .dat file should start at time zero (which may not be the first time specifiedin 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 therewill 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. Eachfunction 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 otherprocessing in this assignment; in particular you should not use queues as temporary storage as you read data from theinput file or as you generate data for the output file – rather you should read data only as it is needed and you shouldwrite 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 willbe 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 astring or for each full/partial second of music generated, but not for each time step that is computed (since there are44.1k steps per second of music generated).Logistics:• Electronic Turn-in: You should turn in the following files, named as follows:o GuitarHero.cppo DblQueue.h, DblQueue.cpp, and DblQueueTest.cppo GuitarString.h, GuitarString.cpp and GuitarStringTest.cppo a README document (a .txt text file or a .doc Word document), containing the answers to each writeupquestion 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 fromthe 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 tohitting the Submit button. Please do not zip up your entire project directory for submission, as the file would beextremely 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 tocomplete 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.txtEnter the name of the output file: song.datReading the input file and generating a .dat file for sox..............................Done.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 twosongs that received the most votes in a poll. Unfortunately, with the increase enrollment of the class, it is difficult for meto manage all song submissions and so there is no longer an extra credit option. But you are free to share your songs withthe rest of the class. Please post your songs to Piazza (post it as a Note rather than a Question). You can post as many songfiles 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 implementGuitarHero.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 PrincetonUniversity by Andrew Appel, Jeff Bernstein, Maia Ginsburg, Ken Steiglitz, Ge Wang, and Kevin Wayne.转自：http://www.3daixie.com/contents/11/3444.html