Homework 11: queues,
turtles, and grids
Due: Friday, November 20th.
This homework has you build several C++ programs. The exercises are
reminiscent of ones of several past homework except you will be
inventing classes and methods. To help you complete the work I’ve
provided some sample code either showcasing other object-oriented C++
examples, or giving you solutions to that past homework.
The first two exercises have you work with a “container” class
Queue which behaves like the data structure you invented
for Homework 05. In that older homework, we hadn’t discussed classes
yet, and so we just built a library of functions that operated on a
pointer to a struct that held the queue’s data. The underlying
representation was a linked list. Here, we have you represent the queue
as an array.
I’ve included a folder named hw05-soln that contains the
code for my solution to that older homework exercise.
The second exercise has you invent operator methods and
functions that work for Queue. I’ve included my solution to
Lab 11 which defines a class Rational and also invents a
few operators for its objects.
In class I showed you the class definition and method implementation
of a stack container class named Stck. Since it has many
similarities to the Queue class you’re making, I’ve
included its source code as well.
You’ll be putting your code for Exercise 1 within the subfolder named
Queue, and then modifying that code for Exercise 2. For
exercises 3 and 4, you’ll be working within the subfolder
grid.
Exercise 1. a
circular buffer queue class
I’ve made a copy of my test program for Homework 05, putiing a copy
of it as Queue/test_queue.cc. Recall that this code
produced the following interaction:
$ ./test_queue
Your queue contains []
Enter a command: head
Your queue is empty and has no head.
Your queue contains []
Enter a command: enqueue 1
Your queue contains [(1)]
Enter a command: enqueue 2
Your queue contains [(1) 2]
Enter a command: enqueue 3
Your queue contains [(1) 2 3]
Enter a command: head
1 is at the head of your queue.
Enter a command: dequeue
1 was removed from the head of your queue.
Your queue contains [(2) 3]
Bye!
$
In this exercise, you’re going to change that code so that it is
instead a client of a class Queue, one that allocates its
Queue instance that it tests within the stack of
main.
Let’s instead invent a Queue class that holds a sequence
of integers with the following methods:
enqueue: puts a new item onto back of the queuedequeue: removes the item at the front of the
queuehead: returns (but does not remove) the item at the
front of the queueisEmpty: returns whether or not there are any items in
the queuetoString: gives back a string displaying the elements
held in the queue
The last three methods can be designated as const
methods (per what we’ll describe in Lecture 12-1) because they don’t
change the contents of the queue. They only read its information; they
don’t modify that information.
The isEmpty and toString methods are
already written for you. They are written assuming that the other
methods and the constructor do the right thing. You need to complete the
code for the ither three.
You also need to complete the code for the constructor for
Queue. It takes an integer capacity as its sole parameter.
(You’ll see how this parameter is used just below.)
For the underlying representation, I would like you to heap-allocate
an array of integers of the capacity specified. You’ll then interpret
that array as a circular buffer. This treats the array as if it
its front and end is connected. That is, we think of the last element in
the array as having the first element as its successor.
To make this clear, let’s work with an example. Imagine we have an
array of length 5 and we’ve enqueued 5, 6, and 6 onto its queue. Then
the queue’s array should have these contents:
0 1 2 3 4
+---+---+---+---+---+
| 5 | 6 | 7 | . | . |
+---+---+---+---+---+
(where the last values aren’t important so we mark them with
.). The queue has a capacity of five and a
size of three.
If we then call dequeue, the slot holding 5 becomes
unimportant and 5 is returned. We picture the queue array this way:
0 1 2 3 4
+---+---+---+---+---+
| . | 6 | 7 | . | . |
+---+---+---+---+---+
Note that we didn’t bother shifting elements to the left. Enqueuing
an 8, we get this array
0 1 2 3 4
+---+---+---+---+---+
| . | 6 | 7 | 8 | . |
+---+---+---+---+---+
Enqueuing a 5 we get this:
0 1 2 3 4
+---+---+---+---+---+
| . | 6 | 7 | 8 | 5 |
+---+---+---+---+---+
Dequeing again gives us this
0 1 2 3 4
+---+---+---+---+---+
| . | . | 7 | 8 | 5 |
+---+---+---+---+---+
What should happen when we perform another enqueue? It turns out
that, with this circular buffer implementation, we wrap things around,
and so enqueuing a 9 leads to this array:
0 1 2 3 4
+---+---+---+---+---+
| 9 | . | 7 | 8 | 5 |
+---+---+---+---+---+
A dequeue, followed by an enqueue of 6 gives us this
0 1 2 3 4
+---+---+---+---+---+
| 9 | 6 | . | 8 | 5 |
+---+---+---+---+---+
In the above, 8 is at the head, and then the consecutive elements
after it in line go to the end of the array and then continue at the
front.
Write the code for the methods of Queue using this
representation. Normally, the way this is done, the programmer keeps
track of two other pieces of information: a headIndex which
gives the index of the head value and a tailIndex which
gives the index in the array where the next enqueued item will be placed
into the array. So in the last array depicted, the Queue
would have a headIndex of 3 and a tailIndex of
2. In the second array depicted (marked with *) it the head
is at 2 and the next tail element will be placed at index 4.
We also track a size as items are enqueued and dequeued.
This should be the count of the number of items stored in the queue. You
can assume that a client will never use the queue (with a pattern of
enqueues and dequeues) so that the size exceeds the array capacity.
Finally, because this queue uses a heap-allocated array to hold its
data, there needs to be a destructor ~Queue that gives that
array back to the heap memory when the Queue is
deallocated. I’ve also written that code for you.
Complete the code for Queue.hh, Queue.cc,
and test_queue.cc using this circular buffer
representation. Put all of this code inside the repo subfolder named
Queue. Note that this means you’ll have to change the
test_queue.cc code to use a stack-allocated
Queue rather than use a heap-allocated struct like it did
for Homework 05.
Exercise 2. Queue operators
Make a copy of the queue testing code you just completed for Exercise
1, making a different version named test_opqueue.cc,
perhaps using this command:
cp test_queue.cc test_opqueue.cc
For this exercise I want you to define some C++ operators that act on
Queue objects and then modify the
test_opqueue.cc code so that it uses them. Here are the
operators I’d like you to add:
• void operator+=(int item); This should behave the same
as enqueue. It can be used like so:
q += v;
In the code above, the value v will be placed at the end
of the queue q.
• int operator--(void); This is the “pre-decrement”
operation. For Queue objects, it should behave the same as
dequeue. It can be used like so:
v = (--q);
The code above should behave exactly the same as the code below:
v = q.dequeue();
• int operator[](int position) const; This should give a
means for inspecting the items stored in the queue based on their
position from the head. The expression q[0] should return
the integer at the head of q, and without changing
q. The expression q[1] gives the item just
after the head (next in line to become the head), q[2]
would be the one after that, and so on. You can assume that the client
would never call it with a position larger than
capacity-1. This operator should not modify its queue,
hence the use of the const keyword.
• int operator()(void) const; This should give back the
integer that is at the head. That is, the operator does the same thing
as the head method. This operator should not modify its
queue either, so we use const here too.
• bool operator!(void) const; This should retuen whether
or not the queue is empty. That is, the operator does the same thing as
the isEmpty method. This operator is also
const.
Finally, you should rewrite the toString method so that
it uses these operators instead of any of the “named” methods. And you
should modify test_opqueue.cc so that it uses these
operators instead of the “named” methods.
Exercise 3. turtles on a
grid
In this exercise you write code for two object classes
Grid and Turtle. A turtle is an object that
lives on a 2-D world that is a finite rectangular grid of square cells.
A grid consists of a number of rows and a number of columns. For
example, the one depicted below has 6 columns and 4 rows:
+---+---+---+---+---+---+
| | | | | | |
+---+---+---+---+---+---+
| | | | | | |
+---+---+---+---+---+---+
| | | | | | |
+---+---+---+---+---+---+
| | | | | | |
+---+---+---+---+---+---+
This means that it has 24 cells. To represent this world, we invent a
class Grid with a constructor:
Grid(int rows, int columns;
There is not much information attached to this grid object. Just the
number of rows and the number of columns. It supports these “getter”
methods:
int getRows(void);
int getColumns(void);
A turtle lives in this kind of world, and walks from grid cell to
grid cell. At any moment, we can describe the location of a turtle
living on the grid at a cell by its coordinates: a certain row and a
certain column, as labelled below:
0 1 2 3 4 5
+---+---+---+---+---+---+
| | | | | | | 0
+---+---+---+---+---+---+
| | | | | | | 1
+---+---+---+---+---+---+
| | | | | | | 2
+---+---+---+---+---+---+
| | | @ | | | | 3
+---+---+---+---+---+---+
Thus the bottom right corner point of the grid shown is (3,5) because
it is in row number 3 and column number 5. The cell marked with an
@ is at (3,2)
When a turtle is created, it is placed at the top left corner of the
grid, looking south. It can do any of the following to move:
void forward(void); // move forward along one edge
void left(void); // turn 90 degrees clockwise
void right(void); // turn 90 degrees counterclockwise
So, if a newly constructed turtle moves forward, then turns left,
then moves forward twice, then turns right, and then moves forward
twice, it will end up at (3,2) facing south. If they try to move forward
again but are at the bottom, they would not change location.
A Grid should not keep track of the turtle that lives on
it. Instead, a turtle keeps track of the grid it lives on. So it should
be created with the constructor:
Turtle(Grid* grid, std::string name);
In its use, upon construction a turtle learns about the world on
which it lives. When it is asked to move forward, it can check the
limits of the grid to see whether that move forward is possible or
not.
Note that the turtle also gets given a name. After all,
turtles are individuals, and with an inner life that is richer and more
fanciful than the grid on which they live.
I’ve included some minimal code try_turtle to test and
see if your Turtle and Grid classes work. It
relies on a Turtle::to_string method that reports the
status of the turtle:
Alex the turtle is sitting at (0,0) facing south.
Complete the Turtle and Grid classes as
required by this test code.
Exercise 4. living on the
grid
Let’s now enhance the Turtle and Grid
classes in two ways:
We’ll work to support several additional methods. You’ll need to
write
void Grid::display(int row, int column) { ... }
which displays the grid using a text-based diagram like I’ve been
showing in this README and then, in particular, shows the
location of the turtle at row and column.
You’ll also need to add several Grid methods to be used by
the turtle to mark its trail. We’ll describe these more carefully
below.
The turtle can optionally leave a trail and this is controlled by the
method defined like so:
void Turtle::trail(bool on) { ... } // turn trail on/off
Let’s reimagine the example movement I described in Exercise 3. We
create the turtle. And it moves forward, left,
forward, forward, right,
forward, forward. If, before they moved, they
turned their trail on, then the contents of the grid would be:
+---+---+---+---+---+---+
| X | | | | | |
+-X-+---+---+---+---+---+
| XXXXXXXXX | | | |
+---+---+-X-+---+---+---+
| | | X | | | |
+---+---+-X-+---+---+---+
| | | @ | | | |
+---+---+---+---+---+---+
The turtle marks the grid as it moves, and so the grid needs to store
these marks. Both cells and cell borders are marked. The
Grid tracks this by managing three arrays of
information:
The marked cells. These can be identified by their
coordinate.
The marked east-west borders. These can be identified by their
west cell’s coordinate.
The marked north-south borders. These can be identified by their
north cell’s coordinate.
So you could have these three methods
void Grid::mark(int r,int c) ...
void Grid::markToEast(int r,int c) ...
void Grid::markToSouth(int r,int c) ...
which mark those items. To check for those marks (for the display)
you could have these three companion methods
bool Grid::hasMark(int r,int c) ...
vool Grid::hasMarkToEast(int r,int c) ...
void Grid::hasMarkToSouth(int r,int c) ...
telling you whether a cell, an east border, or a south border is
marked.
In summary, a turtle, when it is leaving a trail, marks the grid
cells and cell borders as it moves. And then the grid’s
display method displays the cells along with the trail
marks left by the turtle, It shows them with X marks. The
method Grid::display is also told where the turtle is so
that it can show its position too, marking it with @.
To test your classes, write a main test program in a
file called trail.cc that creates a grid and a turtle and
accepts commands to move that turtle around. It should be like
try_turtle but include the commands on and
off for turning on/off the turtle’s trail. And it should
display the grid before it accepts each turtle command.