CSCI 2275 – Data Structures and Algorithms Assignment 5

$30.00

Category: You will Instantly receive a download link for .zip solution file upon Payment

Description

5/5 - (4 votes)

Buffered communication between towers

In the Lord of the Rings trilogy, there is a scene where the first beacon is lit in the
towers of Minas Tirith. The second beacon then sees the fire, and knows to light its
fire to send a signal to the third beacon, and so forth. This was a means of
communicating in the days before telegraphs were invented as it was much faster
than sending a human rider to deliver a message. Communication towers were
equipped with signaling mechanisms, such as mirrors, that could spell out messages
using the positions of the mirrors.

In many current communications networks, data buffers are used to temporarily
store data as it is read in from an input device before being transferred to an output
device. For example, videos downloaded from the Internet can be buffered before
they are displayed onscreen to improve the quality of the picture you see. Buffers
are implemented by storing the incoming data in a First In First Out queue to
maintain the integrity of the order in which the data was received. We discussed
queues in lecture and looked at a few examples of how to implement one using an
array or a linked list.

Build your own (buffered) communications network

In this assignment, you’re going to build on the cities network you implemented in
Assignment 4 by adding a queue to serve as an input buffer for the message being
read in. You will read data in from a text file and store it in a queue, and then
transmit it through the network of cities and back again. You will use a circular
array queue for temporary storage, and then send the queue when the user selects
“Dequeue” or “Send Entire Message” from the menu. In this assignment, you don’t
need to implement the add city and remove city features, but if they already exist in
your code, you will not be marked down for having them.

Include the following cities in your network:
Los Angeles
Phoenix
Denver
Dallas
St. Louis
Chicago
Atlanta
Washington, D.C.
New York
Boston

Structuring your program

Your communications network, including the network nodes and the queue, should
all be included in one class. You are provided with a header file, called
CommunicationNetwork.h on Canvas. You will need to create a file called
CommunicationNetwork.cpp that implements the class defined in the .h file. Your
class does not need to look exactly like the one provided, you are welcome to modify
it to structure your implementation differently. In the header provided, the cities are
implemented with a struct, and the array queue is a dynamically allocated array.
The cities and the queue are private within the class. Your class needs to include
public methods to enqueue and dequeue the data, print the queue, and build and
print the network of cities.

A more-sophisticated implementation would be to have separate classes for the
queue and linked list. If you choose to approach the problem this way, I will give you
5 extra points on your grade.

Each of the menu options presented to the user needs to be handled in a separate
function. You are welcome to write additional helper functions to support those
functions. Included below are suggested, but not required, function prototypes.

First, do some system setup

There is a file on Canvas called messageQueue.txt that contains the message you will
use for this assignment. When your program starts, you should read the text out of
that file and store it locally in your code so that don’t need to open and close that file
multiple times throughout your program. Storing the file data will also make it
easier to track which words have been sent to the queue. You can use any data
structure you like to store the data.

Create an instance of your Communication Network with a queue size of 10. Your
CommunicationNetwork constructor should include the following settings:
CommunicationNetwork::CommunicationNetwork(int qs) {
queueSize = qs;
arrayQueue = new string[queueSize];
queueHead = 0;
queueTail = 0;
}

You may also need to initialize your linked list network in the constructor.
Next, display a menu
When your program starts, you should display a menu that presents the user with
options for how to run your program. The first two menu items were implemented
in the previous assignment. The expected menu is shown here:

The user will select the number for the menu option and your program should
respond accordingly to that number. Your menu options need to have the following
functionality.

1. Build Network: This option builds the linked list using the cities listed above
in the order they are listed. Each city needs to have a name, a pointer to the
next city, a pointer to the previous city, and a message value, which will
initially be an empty string. This option should be selected first to build the
network. Once the network is built, you should print the name of each city in
the network in the following format:
Los Angeles -> Phoenix -> Denver -> Dallas -> St. Louis -> Chicago -> Atlanta ->
Washington, D.C. -> New York -> Boston -> NULL

2. Print Network Path: This option prints out the linked list in order from
beginning to end by following the next pointer for each city. It could be very
useful to you when debugging your code. The format should be the same as
the format in Build Network.

3. Enqueue: This option should enqueue the next word. For example, in your
code to setup your setup described above, if you’ve read the file into an array
called fileData, and fileData contains “A liger its pretty much my favorite
animal”, then
Obj->enqueue(fileData[0]) would add “A” to the queue
Obj->enqueue(fileData[1]) would add “liger” to the queue

In your main function, you need to keep track of which words have been
added to the queue so that you can enqueue them in order. For example, if
you are using a variable called x to track the index of the word, then you
could increment x each time you call: Obj->enqueue(fileData[x]).
When you enqueue a word, your code should print the word and the head
and tail indices after the word has been added to the queue in the following
format:
E:

H:T: Here is the expected output after one Enqueue operation on the samplesentence “A liger is pretty much my favorite animal”.

4. Dequeue: This option does a dequeue operation on the queue and transmitsthe word through the network and back again. The word should start in LosAngeles and go to Boston, passing through each city along the way. When acity receives the message, you should printreceived where is the name of the city and is the word received.When a city receives a word, the word should be deleted from the sendercity. When the word is received at the other end, it should be sent backthrough the network to the starting city. Again, print that each city hasreceived the word using the same format, and delete the word from thesender city.After the message has been sent, output the head and tail indices for thequeue in the following format:H:T: Here is the expected output after three enqueue operations on the samplesentence and one dequeue operation:

5. Print Queue: This option will print all words in the queue, starting at thehead and stopping at the tail with the index of where the word occurs in thequeue. The queue should not be modified in any way. For example, if I do sixenqueue operations and two dequeue operations, then printing the queuewould display the following:

6. Send Entire Message: This option should send the entire message byrepeatedly filling up the queue and sending the words in the queue throughthe network forward and backward until there are no remaining words to besent. If there are already words in the queue from previous enqueueoperations, then the words enqueued here should be added to the queueuntil the queue is full, nothing already in the queue should be overwritten.Once all words have been read into the queue, the contents of the queueshould be sent through the network even if the queue isn’t full.

7. Quit: This option allows the user to exit the program. You should also free allmemory allocated at this time.For each of the options presented, after the user makes their choice and your coderuns for that option, you should re-display the menu to allow the user to selectanother option.Suggestions for completing this assignmentThere are several components to this assignment that can be treated independently.My advice is to tackle these components one by one, starting with updating themenu from the last assignment to include the requirements for this assignment.

There is also some setup to do, such as creating an instance of the class and readingthe text from the file. Next, work on the enqueue and dequeue functionality, testingthat you can enqueue and dequeue words using the pseudocode from lecture.

Thewrap-around functionality is going to require some thought, tackle that next.Also, start early.What to do if you have questionsThere are several ways to get help on assignments in 2275, and depending on yourquestion, some sources are better than others. There is a Piazza Forum on ourCanvas page that is a good place to post technical questions, such as how to iteratethrough a linked list. When you answer other students’ questions on the forum,please do not post entire assignment solutions.

The TA and instructor are also goodsources of technical information in office hours, especially questions about C++. If,after reading the assignment write-up, you need clarification on what you’re beingasked to do in the assignment, the TAs and the Instructor are better sources ofinformation than the Piazza forum.Appendix A – cout statementsEnqueuecout<<“E: “<<word<<endl;cout<<“H: “<<queueHead<<endl;cout<<“T: “<<queueTail<<endl;//if no more words to enqueue from the file read incout << “No more words to queue.” << endl;//if the queue is fullcout << “Queue is full.” << endl;Dequeuecout<<“H: “<<queueHead<<endl;cout<<“T: “<<queueTail<<endl;//dequeue before network builtcout<<“Build a network before attempting to transmit a message.” <<endl;//if the queue is emptycout << “Queue is empty.” << endl;Print pathcout << “===CURRENT PATH===” << endl;//for all nodes in the networkcout << tmp->name << ” -> “;cout << “NULL” << endl;cout << “==================” << endl;Transmit Messagecout<name<<” received “<message<<endl;//if network not built yetcout << “Build a network before attempting to transmit a message.” <<endl;Print Queuecout<<current<<“: “<<arrayQueue[current]<<endl;//where current is the index//if queue is emptycout << “Empty” << endl;Quitcout << “Goodbye!” << endl;