CS61B: 2021
Lecture 11: The End of Java ● Lists and Sets
● Exceptions
● Iteration
● toString and Equals
datastructur.es
Lists and Sets in Java
datastructur.es
Lists
In lecture, we’ve build two types of lists: ALists and SLLists. ● Similar to Python lists.
List61B
L.addLast(10);
L.addLast(15);
L.print();
L = [] L.append(3) L.append(4) L.append(5) print(L)
$ java ListExample
3 45
$ python list_example.py [3 4 5]
Note: We saw this in an earlier lecture, but repeated here for narrative flow.
datastructur.es
Lists in Real Java Code
We built a list from scratch, but Java provides a built-in List interface and several implementations, e.g. ArrayList.
List61B
L.addLast(10);
L.addLast(15);
L.print();
java.util.List
L.add(10);
L.add(15);
System.out.println(L);
datastructur.es
Lists in Real Java Code
By including “import java.util.List” and “import java.util.ArrayList” at the top of the file, we can make our code more compact.
import java.util.List; import java.util.ArrayList;
public class SimpleBuiltInListExample { public static void main(String[] args) {
List
L.add(10);
L.add(15);
System.out.println(L); }
If we import, we can use the “simple name” (ArrayList) as opposed to the longer “canonical name” (java.util.ArrayList).
}
datas
tructur.es
Sets in Java and Python
Another handy data structure is the set.
● Stores a set of values with no duplicates. Has no sense of order.
Set
S.add(“São Paulo”); System.out.println(S.contains(“Tokyo”));
s = set() s.add(“Tokyo”) s.add(“Beijing”) s.add(“Lagos”) s.add(“São Paulo”) print(“Tokyo” in s)
$ java SetExample
true
$ python set_example.py
True
datastructur.es
ArraySet
Today we’re going to write our own Set called ArraySet.
● Won’t be implementing any specific interface (for now).
ArraySet
S.add(“Beijing”);
S.add(“Lagos”);
S.add(“São Paulo”); System.out.println(S.contains(“Tokyo”)); System.out.println(S.size());
datastructur.es
Goals
Goal 1: Create a class ArraySet with the following methods:
● add(value): Add the value to the ArraySet if it is not already present.
● contains(value): Checks to see if ArraySet contains the key.
● size(): Returns number of values.
Ok to ignore resizing for this exercise.
● In lecture, I’ll just give away the answer, but you might find implementing it useful. See DIY folder in the lectureCode repo for starter code.
datastructur.es
ArraySet (Basic Implementation)
public class ArraySet
public ArraySet() {
items = (T[]) new Object[100]; size = 0;
}
… }
Array implementation of a Set:
● Use an array as the core data structure.
● contains(x): Checks to see if x is in the underlying array. ● add(x): Checks to see if x is
in the underlying array, and if not, adds it.
datastructur.es
ArraySet (Basic Implementation)
public boolean contains(T x) {
for (int i = 0; i < size; i += 1) {
if (items[i].equals(x)) { return true;
} }
return false; }
public void add(T x) { if (!contains(x)) {
items[size] = x;
size += 1; }
}
datastructur.es
Using An ArraySet
Generic type variables
public class ArraySet
public ArraySet() {
items = (T[]) new Object[100]; size = 0;
}
… }
Actual type arguments
ArraySet
S.add(“fish”);
datastruct
ur.es
Exceptions
datastructur.es
Exceptions
Basic idea:
● When something goes really wrong, break the normal flow of control.
● So far, we’ve only seen implicit exceptions, like the one below.
public static void main(String[] args) { ArraySet
s.add(“horse”);
}
$ java ExceptionDemo
Exception in thread “main”
java.lang.NullPointerException
at ArraySet.contains(ArraySet.java:16)
at ArraySet.add(ArraySet.java:26)
at ArraySet.main(ArraySet.java:40)
datastructur.es
Explicit Exceptions
We can also throw our own exceptions using the throw keyword. More on
● Can provide more informative message to a user.
● Can provide more information to code that “catches” the exception. course.
“catching” at end of the
public void add(T x) { if (x == null) {
throw new IllegalArgumentException(“Cannot add null!”); }
…
}
$ java ExceptionDemo
Exception in thread “main”
java.lang.IllegalArgumentException: Cannot add null!
at ArraySet.add(ArraySet.java:27)
at ArraySet.main(ArraySet.java:42)
datastructur.es
Explicit Exceptions
Arguably this is a bad exception.
● Our code now crashes when someone tries to add a null.
● Other fixes:
○ Ignore nulls.
○ Fix contains so that it doesn’t crash if items[i] is null.
public void add(T x) { if (x == null) {
throw new IllegalArgumentException(“Cannot add null!”); }
…
}
datastructur.es
Iteration
datastructur.es
The Enhanced For Loop
Java allows us to iterate through Lists and Sets using a convenient shorthand syntax sometimes called the “foreach” or “enhanced for” loop.
Set
javaset.add(23);
javaset.add(42);
for (int i : javaset) { System.out.println(i);
}
datastructur.es
The Enhanced For Loop
Java allows us to iterate through Lists and Sets using a convenient shorthand syntax sometimes called the “foreach” or “enhanced for” loop.
● This doesn’t work with our ArraySet.
● Let’s strip away the magic so we can build our own classes that support this.
ArraySet
aset.add(5);
aset.add(23);
aset.add(42); $ javac IterationDemo
for (int i : aset) { error: for-each not applicable to expression type
System.out.println(i); for (int i : S) { ^
}
required: array or java.lang.Iterable
found: ArraySet
datastructur.es
How Iteration Really Works
An alternate, uglier way to iterate through a List is to use the iterator() method.
“Nice” iteration.
Set.java:
public Iterator
Set
…
Iterator
= javaset.iterator();
while (seer.hasNext()) { System.out.println(seer.next());
}
Set
…
for (int x : javaset) {
System.out.println(x); }
“Ugly” iteration.
datastructur.es
How Iterators Work
An alternate, uglier way to iterate through a List is to use the iterator() method.
5
23
42
javaset:
Iterator
= javaset.iterator();
while (seer.hasNext()) { System.out.println(seer.next());
}
datastructur.es
How Iterators Work
An alternate, uglier way to iterate through a List is to use the iterator() method.
$ java IteratorDemo.java
5
23
42
javaset:
Iterator
= javaset.iterator();
while (seer.hasNext()) { System.out.println(seer.next());
}
datastructur.es
How Iterators Work
An alternate, uglier way to iterate through a List is to use the iterator() method.
True
$ java IteratorDemo.java
5
23
42
javaset:
Iterator
= javaset.iterator();
while (seer.hasNext()) { System.out.println(seer.next());
}
datastructur.es
How Iterators Work
An alternate, uglier way to iterate through a List is to use the iterator() method.
5
$ java IteratorDemo.java
5
5
23
42
javaset:
Iterator
= javaset.iterator();
while (seer.hasNext()) { System.out.println(seer.next());
}
datastructur.es
How Iterators Work
An alternate, uglier way to iterate through a List is to use the iterator() method.
True
$ java IteratorDemo.java
5
5
23
42
javaset:
Iterator
= javaset.iterator();
while (seer.hasNext()) { System.out.println(seer.next());
}
datastructur.es
How Iterators Work
An alternate, uglier way to iterate through a List is to use the iterator() method.
23
$ java IteratorDemo.java
5
23
5
23
42
javaset:
Iterator
= javaset.iterator();
while (seer.hasNext()) { System.out.println(seer.next());
}
datastructur.es
How Iterators Work
An alternate, uglier way to iterate through a List is to use the iterator() method.
True
$ java IteratorDemo.java
5
23
5
23
42
javaset:
Iterator
= javaset.iterator();
while (seer.hasNext()) { System.out.println(seer.next());
}
datastructur.es
How Iterators Work
An alternate, uglier way to iterate through a List is to use the iterator() method.
42
$ java IteratorDemo.java
5
23
42
5
23
42
javaset:
Iterator
= javaset.iterator();
while (seer.hasNext()) { System.out.println(seer.next());
}
datastructur.es
How Iterators Work
An alternate, uglier way to iterate through a List is to use the iterator() method.
False
$ java IteratorDemo.java
5
23
42
5
23
42
javaset:
Iterator
= javaset.iterator();
while (seer.hasNext()) { System.out.println(seer.next());
}
datastructur.es
The Secret of the Enhanced For Loop yellkey.com/art
The secret: The code on the left is just shorthand for the code on the right. For
code on right to compile, which checks does the compiler need to do?
A. Does the Set interface have an iterator() method?
B. Does the Set interface have next/hasNext() methods?
C. Does the Iterator interface have an iterator method?
D. Does the Iterator interface have next/hasNext() methods?
Iterator
= javaset.iterator();
while (seer.hasNext()) { System.out.println(seer.next());
}
for (int x : javaset) { System.out.println(x);
}
datastructur
Set
.es
The Secret of the Enhanced For Loop
The secret: The code on the left is just shorthand for the code on the right. For code on right to compile, which checks does the compiler need to do?
A. Does the Set interface have an iterator() method?
B. Does the Set interface have next/hasNext() methods?
C. Does the Iterator interface have an iterator method?
D. Does the Iterator interface have next/hasNext() methods?
Iterator
= javaset.iterator();
while (seer.hasNext()) { System.out.println(seer.next());
}
for (int x : javaset) { System.out.println(x);
}
datastructur
Set
.es
Supporting Ugly Iteration in ArraySets
To support ugly iteration:
● Add an iterator() method to ArraySet that returns an Iterator
● The Iterator
next() method.
Iterator
Iterator
while (aseer.hasNext()) { System.out.println(aseer.next());
}
datastructur
public interface Iterator
T next(); }
.es
Completed ArraySet iterator Method
To support ugly iteration:
● Add an iterator() method to ArraySet that returns an Iterator
● The Iterator
next() method.
datastructur.es
private class ArraySetIterator implements Iterator
public ArraySetIterator() { wizPos = 0; }
public boolean hasNext() { return wizPos < size; } public T next() {
T returnItem = items[wizPos]; wizPos += 1;
return returnItem;
} }
public Iterator
}
The Enhanced For Loop
Our code now supports “ugly” iteration, but enhanced for loop still doesn’t work. The problem: Java isn’t smart enough to realize that our ArraySet has an
iterator() method.
● Luckily there’s an interface for that.
ArraySet
aset.add(23);
aset.add(42);
for (int i : aset) { …
}
$ javac IterationDemo
error: for-each not applicable to expression type
for (int i : aset) {
^
required: array or java.lang.Iterable
found: ArraySet
datastructur.es
For-each Iteration And ArraySets
To support the enhanced for loop, we need to make ArraySet implement the Iterable interface.
● There are also some default methods in Iterable, not shown.
public interface Iterable
}
Iterable
public class ArraySet
public Iterator
ArraySet
datastructur.es
The Iterable Interface
By the way, this is how Set works as well.
● Source code for Iterable: Link, Set: Link, Collection: Link.
Iterable
public interface Iterable
}
Collection
public interface Collection
}
Set
public interface Set
}
datastructur.es
Iteration Summary
To support the enhanced for loop:
● Add an iterator() method to your class that returns an Iterator
● The Iterator
method.
● Add implements Iterable
Part 5 of HW1 gives you a chance to try this out yourself.
datastructur.es
Object Methods: Equals and toString()
datastructur.es
Objects
All classes are hyponyms of Object.
● String toString()
● boolean equals(Object obj)
● Class getClass()
● int hashCode()
● protected Objectclone()
● protected void finalize()
● void notify()
● void notifyAll()
● void wait()
● void wait(long timeout)
● void wait(long timeout, int nanos)
Very important, but won’t discuss for a few weeks.
Won’t discuss or use in 61B.
datastructur.es
toString()
The toString() method provides a string representation of an object.
● System.out.println(Object x) calls x.toString()
○ If you’re curious: println calls String.valueOf which calls toString
Set
javaset.add(23);
javaset.add(42);
System.out.println(javaset);
$ java JavaSetPrintDemo
[5, 23, 42]
datastructur.es
toString()
The toString() method provides a string representation of an object.
● System.out.println(Object x) calls x.toString()
● The implementation of toString() in Object is the the name of the class,
then an @ sign, then the memory location of the object.
○ See 61C for what the “memory location” really means.
ArraySet
aset.add(23);
aset.add(42);
System.out.println(aset);
$ java ArraySetPrintDemo
ArraySet@75412c2f
datastructur.es
ArraySet toString
Let’s try implementing toString for ArraySet.
datastructur.es
ArraySet toString
One approach is shown below.
● Warning: This code is slow. Intuition: Adding even a single character to a string creates an entirely new string. Will discuss why at end of course.
Spoiler: It’s because Strings are “immutable”.
@Override
public String toString() {
String returnString = “{“;
for (int i = 0; i < size; i += 1) {
returnString += keys[i];
returnString += ", "; }
returnString += "}";
return returnString; }
datastructur.es
ArraySet toString
Much faster approach is shown below.
● Intuition: Append operation for a StringBuilder is fast.
@Override
public String toString() {
StringBuilder returnSB = new StringBuilder("{"); for (int i = 0; i < size; i += 1) {
returnSB.append(items[i]);
returnSB.append(", "); }
returnSB.append("}");
return returnSB.toString(); }
datastructur.es
Objects
All classes are hyponyms of Object.
● String toString()
● boolean equals(Object obj)
● Class getClass()
● int hashCode()
● protected Objectclone()
● protected void finalize()
● void notify()
● void notifyAll()
● void wait()
● void wait(long timeout)
● void wait(long timeout, int nanos)
Very important, but won’t discuss for a few weeks.
Won’t discuss or use in 61B.
datastructur.es
Equals vs. ==
As mentioned in an offhand manner previously, == and .equals() behave differently. ● == compares the bits. For references, == means “referencing the same object.”
Set
$ java EqualsDemo
False
datastructur.es
Equals vs. ==
As mentioned in an offhand manner previously, == and .equals() behave differently. ● == compares the bits. For references, == means “referencing the same object.”
To test equality in the sense we usually mean it, use:
● .equals for classes. Requires writing a .equals method for your classes.
○ Default implementation of .equals uses == (probably not what you want).
● BTW: Use Arrays.equal or Arrays.deepEquals for arrays.
Set
$ java EqualsDemo
True
datastructur.es
The Default Implementation of Equals
ArraySet
aset.add(23);
aset.add(42);
System.out.println(aset);
ArraySet
aset2.add(23);
aset2.add(42);
System.out.println(aset.equals(aset2));
$ java EqualsDemo
False
Returns false because the default implementation of equals just uses ==.
datastructur.es
ArraySet equals
Let’s try implementing equals for ArraySet.
datastructur.es
ArraySet equals
The implementation below is a good start, but fails if o is null or another class.
@Override
public boolean equals(Object o) {
ArraySet
if (this.size() != other.size()) { return false; }
for (T item : this) {
if (!other.contains(item)) {
return false; }
}
return true;
}
datastructur.es
ArraySet equals
The implementation below is much better, but we can speed things up.
@Override
public boolean equals(Object o) {
if (o == null) { return false; }
if (this.getClass() != o.getClass()) { return false; } ArraySet
if (this.size() != other.size()) { return false; }
for (T item : this) {
if (!other.contains(item)) {
return false; }
}
return true;
}
datastructur.es
ArraySet equals
The code below is pretty close to what a standard equals method looks like.
@Override
public boolean equals(Object o) {
if (o == null) { return false; }
if (this == o) { return true; } // optimization
if (this.getClass() != o.getClass()) { return false; } ArraySet
if (this.size() != other.size()) { return false; }
for (T item : this) {
if (!other.contains(item)) {
return false; }
}
return true;
}
datastructur.es
Summary
We built our own Array based Set implementation. To make it more industrial strength we:
● Added an exception if a user tried to add null to the set.
○ There are other ways to deal with nulls. Our choice was arguably bad.
● Added support for “ugly” then “nice” iteration.
○ Ugly iteration: Creating a subclass with next and hasNext methods.
○ Nice iteration: Declaring that ArraySet implements Iterable.
● Added a toString() method.
○ Beware of String concatenation.
● Added an equals(Object) method.
○ Make sure to deal with null and non-ArraySet arguments!
○ Used getClass to check the class of the passed object. Use sparingly.
datastructur.es
Even Better toString and ArraySet.of
(Extra)
datastructur.es
Citations
Seer:
http://www.clipartoday.com/_thumbs/022/Fantasy/astrology_crystal_190660_ tnb.png
Edge of the world:
datastructur.es
datastructur.es