Lab 10: Working with equals, hashCode, stacks, and iterators
Goals: The goals of this lab are to work with stacks to solve interesting problems, and to write iterators
Problem 1: Equals and Hashcode
10.1 Questions
Why are equals and hashCode imporant? What method of a given object does the ArrayList contains use to check if that object is already in an array list?
How do you think Java’s HashMap decides if a given key is in the hash map? (hint: there are two method calls. First java calls one method which returns an integer, and then if necessary, it calls another method which returns a boolean. You have already seen both of these methods ).
Why do you think it isn’t enough for java’s HashMap to use just the key’s hash code to decide if a given key is in the map, and when do you think the extra call to the key’s equals method happens?
Override:
public boolean equals(Object o)
public int hashCode()
On the following class:
class Runner{ int age; String name; Runner(int age, String name){ this.age = age; this.name = name; } }
Write the appropriate tests to check that equals and hashCode work as expected.
Problem 2: Working with Stacks
Copy your implementation of Deques from Assignment 8: Mutation and ArrayLists into a new project.
10.1 Stack
A stack is a mutable list where we are permitted only to add, access and remove from one end of a list. We can also determine if the stack is empty. Real-world examples of stacks include a stack of books: we can only see the book on top of the stack, and we cannot remove the bottom-most book until we have removed all the books above it. Thus, the last thing to be added to a stack is the first thing that comes out of it. This behavior is described as “last-in-first-out” or LIFO.
class Stack<T> { Deque<T> contents; void push(T item); // adds an item to the stack boolean isEmpty(); T pop(); // removes and returns the top of the stack }
You can implement these methods by picking any end of the deque, and then adding, accessing or removing only from that end. You are not allowed to modify the implementation of Deque at all (except to fix bugs in your code), nor access any nodes directly. Treat the Deque class as a complete black box: you can instantiate it and call its methods, but cannot access its fields.
10.2 Reversing lists
class Utils { <T> ArrayList<T> reverse(ArrayList<T> source) { ... } }
10.3 Undoing operations
Define a simple class called StringCreator. It has a single String field, and three methods: void add(Character c) that adds a character to the end of the string, void remove() that removes the last character of the string, and getString() that returns the current string.
Now implement a fourth method void undo() that undoes the last operation done on the string. Here is an example of how an object of this class may be used:
void testRun(Tester t) { StringCreator creator = new StringCreator(); t.checkExpect(creator.getString(),""); creator.add('c'); creator.add('d'); t.checkExpect(creator.getString(),"cd"); creator.add('e'); t.checkExpect(creator.getString(),"cde"); creator.remove(); creator.remove(); t.checkExpect(creator.getString(),"c"); creator.undo(); //undoes the removal of 'd' t.checkExpect(creator.getString(),"cd"); creator.undo(); //undoes the removal of 'e' creator.undo(); //undoes the addition of 'e' t.checkExpect(creator.getString(),"cd"); creator.add('a'); t.checkExpect(creator.getString(),"cda"); creator.undo(); //undoes the addition of 'a' creator.undo(); //undoes the addition of 'd' creator.undo(); //undoes the addition of 'c' t.checkExpect(creator.getString(),""); creator.undo(); //no effect, there is nothing to undo }
Carefully work through the above test to reverse-engineer how the undo method works. Hint: one way to undo is to revert to the string before simply save the string before the operation and revert to it to undo.
Note that you do not have to undo an “undo” operation: only add and remove can be undone.
Problem 3: Iterators
Create a class ListOfLists<T> that stores an ArrayList of ArrayList<T>. This class must have the following methods:
A method void addNewList() that adds a new empty ArrayList<T> to the end of the list-of-lists.
A method void add(int index,T object) that adds the provided object to the end of the ArrayList<T> at the provided index in teh list-of-lists. If the index is invalid, this method should throw an IndexOutOfBoundsException with a suitable message.
A method ArrayList<T> get(int index) that returns the ArrayList<T> at the provided index in the list-of-lists. If the index is invalid, this method should throw an IndexOutOfBoundsException with a suitable message.
A method int size() that returns the number of lists in this list-of-lists.
Now make the ListOfLists<T> iterable. The intended behavior should be as follows:
void testListOfLists(Tester t) { ListOfLists<Integer> lol = new ListOfLists<Integer>(); //add 3 lists lol.addNewList(); lol.addNewList(); lol.addNewList(); //add elements 1,2,3 in first list lol.add(0,1); lol.add(0,2); lol.add(0,3); //add elements 4,5,6 in second list lol.add(1,4); lol.add(1,5); lol.add(1,6); //add elements 7,8,9 in third list lol.add(2,7); lol.add(2,8); lol.add(2,9); //iterator should return elements in order 1,2,3,4,5,6,7,8,9 int number = 1; for (Integer num:lol) { t.checkExpect(num,number); number = number + 1; } }