CSCI 2275 – Data Structures and Algorithms Assignment 5

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 sample
sentence “A liger is pretty much my favorite animal”.
4. Dequeue: This option does a dequeue operation on the queue and transmits
the word through the network and back again. The word should start in Los
Angeles and go to Boston, passing through each city along the way. When a
city receives the message, you should print
received
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 sender
city. When the word is received at the other end, it should be sent back
through the network to the starting city. Again, print that each city has
received the word using the same format, and delete the word from the
sender city.
After the message has been sent, output the head and tail indices for the
queue in the following format:
H:
T:
Here is the expected output after three enqueue operations on the sample
sentence and one dequeue operation:
5. Print Queue: This option will print all words in the queue, starting at the
head and stopping at the tail with the index of where the word occurs in the
queue. The queue should not be modified in any way. For example, if I do six
enqueue operations and two dequeue operations, then printing the queue
would display the following:
6. Send Entire Message: This option should send the entire message by
repeatedly filling up the queue and sending the words in the queue through
the network forward and backward until there are no remaining words to be
sent. If there are already words in the queue from previous enqueue
operations, then the words enqueued here should be added to the queue
until 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 queue
should 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 all
memory allocated at this time.
For each of the options presented, after the user makes their choice and your code
runs for that option, you should re-display the menu to allow the user to select
another option.
Suggestions for completing this assignment
There are several components to this assignment that can be treated independently.
My advice is to tackle these components one by one, starting with updating the
menu 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 reading
the text from the file. Next, work on the enqueue and dequeue functionality, testing
that you can enqueue and dequeue words using the pseudocode from lecture. The
wrap-around functionality is going to require some thought, tackle that next.
Also, start early.
What to do if you have questions
There are several ways to get help on assignments in 2275, and depending on your
question, some sources are better than others. There is a Piazza Forum on our
Canvas page that is a good place to post technical questions, such as how to iterate
through 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 good
sources of technical information in office hours, especially questions about C++. If,
after reading the assignment write-up, you need clarification on what you’re being
asked to do in the assignment, the TAs and the Instructor are better sources of
information than the Piazza forum.
Appendix A – cout statements
Enqueue
cout<<"E: "<name << " -> “;
cout << "NULL" << endl; cout << "==================" << endl; Transmit Message cout<name<<" received "<message<