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.
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) { ... } }
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.
If curr refers to a Node, then hasNext should return true, and next should return the value in that Node. It should also update curr to refer to the next node in the Deque.
If curr refers to the Sentinel, then hasNext should return false.
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 ScanLeftIterator, that takes in a source iterator, a starting value, and a function object, and produces the sequence of objects obtained from scanning the function across the results produced by the source iterator. (See Assignment 2: Designing methods for complex data, problem 3, to remind yourself how a left-scan works.) Implement this iterator.
(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. Try implementing at least one of these. (The depth-first one is likely the easiest.)
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 —
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 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); } }
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 —
Reminder: read the The Image Library for documentation on how the image library works.