►Fundamentals II
Introduction to Class-based Program Design
▼Lab Materials
►Lab 8: Stacks; Queues; More Iterators; Mutable worlds
On this page:
8.1 Stacks and Queues
8.1.1 Practice puzzle
8.2 Iterators and Iterables
8.2.1 Reminder
8.2.2 Iterating over a Deque
8.2.3 Two simple, short iterators
8.2.4 Testing iterators
8.2.5 Challenging iterators
8.3 The 15 Puzzle using impworld
8.12
    contents    up   

Lab 8: Stacks; Queues; More Iterators; Mutable worlds🔗

Goals: The goals of this lab is to get practice with related but distinct data types: stacks, queues, and iterators. Also, we will see mutable worlds and use the impworld library.

If you do not finish everything in lab today, you are strongly encouraged to continue working on it over break. It’s good practice.

8.1 Stacks and Queues🔗

Stacks and Queues are data structures that look much like mutable lists, where we restrict how we add and remove items to and from the list.

A stack is a mutable list where we are permitted only to access the head of the list: we can add an item to the head of the list, or we can remove an item from the head of the list, and we can determine if a stack is empty. The canonical example of stacks are piles of dishes: we can only access the topmost dish, and to access the bottom plates we have to remove the top ones first. Stacks are described as “last-in-first-out”: the last item that was added to the stack is the first one that gets removed.

In a separate file from your Deque implementation, implement the following class:

class Stack<T> {
Deque<T> contents;
void push(T item); // adds an item to the head of the list boolean isEmpty();
T pop(); // removes and returns the head of the list }

You are not to modify the implementation of Deque at all (except to fix bugs in your code, if you find any). In particular, you are not to rely on the particulars of Sentinels and Nodes and such; treat Deque as an opaque black box that you can only manipulate via its methods.

A queue is a mutable list where we are permitted only to add items to the tail of the list, remove items from the head of the list, and determine if the queue is empty. Queues are described as “first-in-first-out”: the first item that gets added to a queue is the first one that gets removed. The canonical example of a queue is waiting on line: people enter the line from the back, shuffle forward until they are at the front of the line, and exit the line at the front.

Implement the following class:
class Queue<T> {
Deque<T> contents;
void enqueue(T item); // adds an item to the tail of the list boolean isEmpty();
T dequeue(); // removes and returns the head of the list }

8.1.1 Practice puzzle🔗

Note: this is intended as a puzzle, to figure out how to use various tools at your disposal in possibly-unexpected ways. There are other ways to solve this particular task, which are not in the spirit of this puzzle.

Using two for-each loops and either a stack or a queue as a temporary storage space (only one of them will work), define the method that reverses an ArrayList:

class Utils {
<T> ArrayList<T> reverse(ArrayList<T> source) { ... }
}
Only use the 1-argument add method for ArrayLists; the two argument form could make this puzzle trivial. If you use a stack, then you can only use the methods push, pop and isEmpty; if you use a queue, you can only use the methods enqueue, dequeue and isEmpty.

8.2 Iterators and Iterables🔗
8.2.1 Reminder🔗

The Iterator<T> interface is responsible for producing a sequence of T values, and the interface is defined by Java as

interface Iterator<T> {
// returns true if there's at least one value left in this iterator boolean hasNext();
// returns the next value and advances the iterator T next();
}

The Iterable<T> interface asserts that a given object can be iterated to produce a sequence of T values. It is defined by Java as

interface Iterable<T> {
Iterator<T> iterator();
}

Classes that implement this interface must supply some Iterator object that can then be used to iterate over themselves.

8.2.2 Iterating over a Deque🔗

In your implementation of Deque, implement a class ForwardDequeIterator<T> that iterates through the Nodes and Sentinel of a Deque. It should contain a field curr that is a reference to an ANode.

Revise the definition of Deque to say it implements Iterable<T>. Implement the iterator() method to return a new ForwardDequeIterator.

If you’ve built your iterator correctly, then you should now be able to use a Deque in a for-each loop:

// In ExamplesDeque void testDequeIteration(Tester t) {
Deque<String> dq = new Deque<String>();
dq.addAtTail(", ");
dq.addAtHead("Hello");
dq.addAtTail("world!");
String msg = "";
for (String s : dq) {
msg = msg.concat(s);
}
t.checkExpect(msg, "Hello, world!");
}

Implement another class ReverseDequeIterator<T> that iterates backward through the Nodes and Sentinel of a Deque. (Hint: it should be just a tiny change from the forward iterator!) Add a method to Deque to return a reverse-iterator (since you already have a method that returns a forward-iterator).

Write a while loop that tests using a reverse iterator on a Deque.

8.2.3 Two simple, short iterators🔗

Design an iterator TakeN, that takes a source iterator and a number N, and returns at most the first N elements of the source iterator. For instance, if an iterator produced all the positive integers, then taking the first 10 of them would result in a finite sequence of numbers.

Design the "opposite" concept, DropN, that discards the first N elements of its source iterator, and then returns the rest of them.

8.2.4 Testing iterators🔗

In class we discussed the Fibonacci-number iterator, and you’ve worked on the Take-N iterator above. We briefly touched on how to test these, but did not write the tests out in class. Copy in the definitions of FibonacciIterator and TakeN. Create a test method that (a) ensures that a Take-N iterator applied to a Fibonacci iterator does indeed run out of values, and (b) the underlying Fibonacci iterator is not yet finished, and that its next value is the one you expect.

Look up the documentation for checkIterable. Create a test case that compares the contents of a Deque with the contents of an ArrayList, and confirm that your Deque iterates over itself correctly.

8.2.5 Challenging iterators🔗

In class we discussed implementing a MapIterator, that takes in a source iterator and a function object, and produces the sequence of objects obtained from applying the function to each result produced by the source iterator. Implement this iterator.

Assume that the source iterator is not infinite; that is, it’s ok to assume that this will terminate. Dealing with termination issues isn’t the point of this particular exercise.

In class we discussed implementing a FilterIterator, that takes in a source iterator and a predicate, and produces the sequence of objects obtained from the source that pass the predicate. The challenge here is making sure that hasNext returns the correct answer: it should only return true if the source iterator does eventually contain a value that passes the predicate. But once you’ve checked that value, you’ve used it up from the source iterator, and so it won’t be available for the next method to return! You’ll need to preserve this value somehow until it can be used by next. Try testing this iterator when nested: for instance, build a list with integers from 1 to 1000, then build an iterator that filters that list to only the even numbers, and then filter that to only the square numbers.

(Very challenging!) Lecture 25: Iterator and Iterable, near the end, describes four iteration orders over a binary tree: breadth-first, depth-first (also known as pre-order), in-order, and post-order. In class, we discussed breadth-first and depth-first iterators. Implement the other two.

Test each of these iterators.

8.3 The 15 Puzzle using impworld🔗

This is the same lab problem as from last week. If you did not finish it then, do so today.

The funworld library used methods (like onTick or onKeyEvent) that returned new World objects, which made testing easier: you could compare the old World to the new one.

The impworld library uses methods that return void, and you must use side effects to change the current world to update it between ticks and on key events...but you still need to figure out how to test it!

The 15 puzzle consists of four rows of four tiles, with one tile missing. Each tile has a number, and tiles can move into the hole if they are adjacent to it. Represent this information as follows:

// Represents an individual tile class Tile {
// The number on the tile. Use 0 to represent the hole int value;
...
// Draws this tile onto the background at the specified logical coordinates WorldImage drawAt(int col, int row, WorldImage background) { ... }
}
 
class FifteenGame extends World {
// represents the rows of tiles ArrayList<ArrayList<Tile>> tiles;
...
// draws the game public WorldScene makeScene() { ... }
// handles keystrokes public void onKeyEvent(String k) {
// needs to handle up, down, left, right to move the hole // extra: handle "u" to undo moves ...
}
}

To construct the tiles, you’ll need to construct 4 rows of 4 tiles each. Which loop structure (for-each or counted-for) do you think will be most appropriate here? (Hint: you’ll need two loops, one nested inside the other.)

Implement swapping two tiles by their indices — how will this have to change from the swap method we did in class?

This is similar to the perennial argument over whether scrolling "up" on a laptop trackpad should scroll the content up or scroll the viewport up. Everyone is convinced their preferred approach is correct...

To handle moving the tiles, you’ll need to determine whether a given move direction is currently possible: for example, if the hole is in the top-left corner, then you cannot move the hole any further up or left. It is up to you to interpret a keystroke of e.g. "left" as either “move the hole 1 cell left” or “move the tile to the right of the hole left to fill the hole”, and similarly for the other keys. You may find that one interpretation is more intuitive than the other, but it is a rather subjective choice. Be sure to document in you code which interpretation you chose!

To start the game, create a Run configuration as usual, set the main class to tester.Main, and set the arguments to ExampleFifteenGame. Then create the ExampleFifteenGame class with at least this method:

class ExampleFifteenGame {
void testGame(Tester t) {
FifteenGame g = new FifteenGame();
g.bigBang(120, 120);
}
}
Obviously, you’ll need to write tests, too!

To handle undoing moves: create another field in the FifteenGame class that is an ArrayList<String>, which you’ll update on each keystroke by adding the key that was just pressed to the front of the list. When the "u" key is pressed, the most recent move (if any) will then be stored at the front of the list — you just have to figure out how to undo it!

Reminder: read the The Image Library for documentation on how the image library works.

    contents    up