Announcements
This is the last lecture specifically devoted to Java syntax.
Once you’ve digested this lecture you’ll know everything you need for project 1C.
Announcements
The new textbook is up.
If you notice any accessibility concerns in this videos, the textbook, or other course materials, please email cs61b@berkeley.edu ASAP and we’ll get it taken care of.
Announcements
Bargaining begins today regarding a side letter about EECS/Data courses staffing. You're all welcome to attend or listen in. Me and DeNero will be there.
When: 3:10pm-5pm Monday, Feb 13
Where: 310 Soda Hall
Zoom: https://berkeley.zoom.us/j/95216694463
You can expect that we'll debrief about the town hall (recording), review the data release, discuss issues DeNero raised in my video about course staffing, and hopefully come up with a shared plan for how to make progress on the concerns raised in the town hall (which include course access in addition to staffing shortages).
The End of Java
4
Lecture 12
CS61B, Spring 2023 @ UC Berkeley
Josh Hug and Justin Yokota
Today’s Goal: ArraySet
Lecture 12, CS61B, Spring 2023
Today’s Goal: ArraySet
Iteration
Object Methods
Sets in Java and Python
Today’s goal: Build an implementation of a Set called ArraySet.
ArraySet<String> S = new ArraySet<>();
S.add("Tokyo");
S.add("Beijing");
S.add("Lagos");
S.add("Tokyo"); // no effect
S.add("São Paulo");
System.out.println(S.contains("Tokyo"));
s = set()
s.add("Tokyo")
s.add("Beijing")
s.add("Lagos")
s.add("Tokyo") # no effect
s.add("São Paulo")
print("Tokyo" in s)
$ java SetExample
true
$ python set_example.py
True
Goals
Starting point: A class ArraySet with the following methods:
For simplicity, I’ll ignore resizing.
The basic functionality is quite straightforward, so I’ll avoid live coding.
ArraySet (Basic Implementation)
public class ArraySet<T> {
private T[] items;
private int size;
public ArraySet() {
items = (T[]) new Object[100];
size = 0;
}
...
}
Array implementation of a Set:
ArraySet (Basic Implementation)
public void add(T x) {
if (!contains(x)) {
items[size] = x;
size += 1;
}
}
public boolean contains(T x) {
for (int i = 0; i < size; i += 1) {
if (items[i].equals(x)) {
return true;
}
}
return false;
}
Can also throw an IllegalArgumentException if you want to disallow null.
The Enhanced For Loop
Lecture 12, CS61B, Spring 2023
Today’s Goal: ArraySet
Iteration
Object Methods
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<Integer> javaset = new HashSet<>();
javaset.add(5);
javaset.add(23);
javaset.add(42);
for (int i : javaset) {
System.out.println(i);
}
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.
ArraySet<Integer> aset = new ArraySet<>();
aset.add(5);
aset.add(23);
aset.add(42);
for (int i : aset) {
System.out.println(i);
}
$ javac IterationDemo
error: for-each not applicable to expression type
for (int i : S) {
^
required: array or java.lang.Iterable
found: ArraySet<Integer>
iterator, next, hasNext
Lecture 12, CS61B, Spring 2023
Today’s Goal: ArraySet
Iteration
Object Methods
Why Doesn’t the Enhanced For Loop Work?
The enhanced for loop works by first calling the .iterator method of the object.
ArraySet<Integer> aset = new ArraySet<>();
aset.add(5);
aset.add(23);
aset.add(42);
for (int i : aset) {
System.out.println(i);
}
What is missing?
How Iteration Really Works
An alternate, uglier way to iterate through a Set is to use the iterator() method.
Suppose we have a Set<Integer> called javaset.
for (int x : javaset) {
System.out.println(x);
}
public Iterator<E> iterator();
Set.java:
Iterator<Integer> seer
= javaset.iterator();
while (seer.hasNext()) {
int x = seer.next();
System.out.println(x);
}
“Nice” iteration.
“Ugly” iteration.
How Iterators Work
An alternate, uglier way to iterate through a Set is to use the iterator() method.
Iterator<Integer> seer
= javaset.iterator();
while (seer.hasNext()) {
System.out.println(seer.next());
}
5 | 23 | 42 |
javaset:
How Iterators Work
An alternate, uglier way to iterate through a Set is to use the iterator() method.
5 | 23 | 42 |
javaset:
$ java IteratorDemo.java
Iterator<Integer> seer
= javaset.iterator();
while (seer.hasNext()) {
System.out.println(seer.next());
}
How Iterators Work
An alternate, uglier way to iterate through a Set is to use the iterator() method.
5 | 23 | 42 |
javaset:
True
$ java IteratorDemo.java
Iterator<Integer> seer
= javaset.iterator();
while (seer.hasNext()) {
System.out.println(seer.next());
}
How Iterators Work
An alternate, uglier way to iterate through a Set is to use the iterator() method.
5 | 23 | 42 |
javaset:
5
$ java IteratorDemo.java
5
Iterator<Integer> seer
= javaset.iterator();
while (seer.hasNext()) {
System.out.println(seer.next());
}
How Iterators Work
An alternate, uglier way to iterate through a Set is to use the iterator() method.
5 | 23 | 42 |
javaset:
True
$ java IteratorDemo.java
5
Iterator<Integer> seer
= javaset.iterator();
while (seer.hasNext()) {
System.out.println(seer.next());
}
How Iterators Work
An alternate, uglier way to iterate through a Set is to use the iterator() method.
5 | 23 | 42 |
javaset:
23
$ java IteratorDemo.java
5
23
Iterator<Integer> seer
= javaset.iterator();
while (seer.hasNext()) {
System.out.println(seer.next());
}
How Iterators Work
An alternate, uglier way to iterate through a Set is to use the iterator() method.
5 | 23 | 42 |
javaset:
True
$ java IteratorDemo.java
5
23
Iterator<Integer> seer
= javaset.iterator();
while (seer.hasNext()) {
System.out.println(seer.next());
}
How Iterators Work
An alternate, uglier way to iterate through a Set is to use the iterator() method.
5 | 23 | 42 |
javaset:
42
$ java IteratorDemo.java
5
23
42
Iterator<Integer> seer
= javaset.iterator();
while (seer.hasNext()) {
System.out.println(seer.next());
}
How Iterators Work
An alternate, uglier way to iterate through a Set is to use the iterator() method.
5 | 23 | 42 |
javaset:
False
$ java IteratorDemo.java
5
23
42
Iterator<Integer> seer
= javaset.iterator();
while (seer.hasNext()) {
System.out.println(seer.next());
}
iterator, next, hasNext for ArraySet
Lecture 12, CS61B, Spring 2023
Today’s Goal: ArraySet
Iteration
Object Methods
The Secret of the Enhanced For Loop yellkey.com/may
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?
for (int x : javaset) {
System.out.println(x);
}
Iterator<Integer> seer
= javaset.iterator();
while (seer.hasNext()) {
System.out.println(seer.next());
}
Set<Integer> javaset = new HashSet<Integer>();
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?
for (int x : javaset) {
System.out.println(x);
}
Iterator<Integer> seer
= javaset.iterator();
while (seer.hasNext()) {
System.out.println(seer.next());
}
Set<Integer> javaset = new HashSet<Integer>();
Supporting Ugly Iteration in ArraySets
To support ugly iteration:
public interface Iterator<T> {
boolean hasNext();
T next();
}
Iterator<T>
Iterator<Integer> aseer
= aset.iterator();
while (aseer.hasNext()) {
System.out.println(aseer.next());
}
Completed ArraySet iterator Method
To support ugly iteration:
private class ArraySetIterator implements Iterator<T> {
private int wizPos;
public ArraySetIterator() { wizPos = 0; }
public boolean hasNext() { return wizPos < size; }
public T next() {
T returnItem = items[wizPos];
wizPos += 1;
return returnItem;
}
}
public Iterator<T> iterator() {
return new ArraySetIterator();
}
Iterable
Lecture 12, CS61B, Spring 2023
Today’s Goal: ArraySet
Iteration
Object Methods
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.
ArraySet<Integer> aset = new ArraySet<>();
aset.add(5);
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<Integer>
For-each Iteration And ArraySets
To support the enhanced for loop, we need to make ArraySet implement the Iterable interface.
public interface Iterable<T> {
Iterator<T> iterator();
}
public class ArraySet<T> implements Iterable<T> {
...
public Iterator<T> iterator() { ... }
}
ArraySet<T>
Iterable<T>
The Iterable Interface
By the way, this is how Set works as well.
Set<E>
Iterable<T>
public interface Iterable<T> {
Iterator<T> iterator(); ...
}
public interface Set<E> extends Collection<E> {
public Iterator<E> iterator();
}
Collection<E>
public interface Collection<E> extends Iterable<E> {
public Iterator<E> iterator();
}
Iteration Summary
To support the enhanced for loop:
We’ll do this in project 1C.
toString
Lecture 12, CS61B, Spring 2023
Today’s Goal: ArraySet
Iteration
Object Methods
Object Methods
All classes are hyponyms of Object.
Won’t discuss or use in 61B.
Today
Coming later.
toString()
The toString() method provides a string representation of an object.
Set<Integer> javaset = new HashSet<>();
javaset.add(5);
javaset.add(23);
javaset.add(42);
System.out.println(javaset);
$ java JavaSetPrintDemo
[5, 23, 42]
toString()
The toString() method provides a string representation of an object.
ArraySet<Integer> aset = new ArraySet<>();
aset.add(5);
aset.add(23);
aset.add(42);
System.out.println(aset);
$ java ArraySetPrintDemo
ArraySet@75412c2f
ArraySet toString
Let’s try implementing toString for ArraySet.
ArraySet toString
One approach is shown below.
@Override
public String toString() {
String returnString = "{";
for (int i = 0; i < size; i += 1) {
returnString += keys[i];
returnString += ", ";
}
returnString += "}";
return returnString;
}
Spoiler: It’s because Strings are “immutable”.
ArraySet toString
Much faster approach is shown below.
@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();
}
== vs. equals
Lecture 12, CS61B, Spring 2023
Today’s Goal: ArraySet
Iteration
Object Methods
Object Methods
All classes are hyponyms of Object.
Won’t discuss or use in 61B.
Coming in another lecture soon.
Coming later.
Equals vs. ==
As mentioned in an offhand manner previously, == and .equals() behave differently.
Set<Integer> javaset = Set.of(5, 23, 42);
Set<Integer> javaset2 = Set.of(5, 23, 42);
System.out.println(javaset == javaset2);
$ java EqualsDemo
False
Equals vs. ==
As mentioned in an offhand manner previously, == and .equals() behave differently.
To test equality in the sense we usually mean it, use:
Set<Integer> javaset = Set.of(5, 23, 42);
Set<Integer> javaset2 = Set.of(5, 23, 42);
System.out.println(javaset.equals(javaset2));
$ java EqualsDemo
True
this: Address of Current Object
this is a reference to the current object. Example from lecture 2:
public Dog maxDog(Dog uddaDog) {
if (size > uddaDog.size) {
return this;
}
return uddaDog;
}
this: Address of Current Object
Naturally, can also use this to access your own instance variables or methods.
public Dog maxDog(Dog o) {
if (this.size > o.size) {
return this;
}
return o;
}
public Dog maxDog(Dog o) {
if (size > o.size) {
return this;
}
return o;
}
this
Naturally, can also use this to access your own instance variables or methods.
public Dog(int size) {
this.size = size;
}
public Dog(int s) {
size = s;
}
public Dog(int s) {
this.size = s;
}
public Dog(int size) {
size = size;
}
Does nothing!
Works correctly!
Works correctly!
Works correctly!
The Default Implementation of Equals
Below, we see the actual code for the default equals method in Object.java.
public class Object {
...
public boolean equals(Object obj) {
return (this == obj);
}
}
The Default Implementation of Equals
ArraySet<Integer> aset = new ArraySet<>();
aset.add(5);
aset.add(23);
aset.add(42);
System.out.println(aset);
ArraySet<Integer> aset2 = new ArraySet<>();
aset2.add(5);
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 ==.
instanceOf Demo
The instanceof keyword is very powerful in Java.
Let’s try to write ArraySet’s equals method.
@Override
public boolean equals(Object o) {
if (o instanceof Dog uddaDog) {
return this.size == uddaDog.size;
}
return false;
}
ArraySet equals
The code below is pretty close to what a standard equals method looks like.
@Override
public boolean equals(Object other) {
if (this == other) { return true; }
if (other instanceof ArraySet otherSet) {
if (this.size != otherSet.size) { return false; }
for (T x : this) {
if (!otherSet.contains(x)) {
return false;
}
}
return true;
}
return false;
}
Historical Note: Old School Equals Methods
Equals methods written before March 2021 were ugly.
@Override // OLD SCHOOL APPROACH. NOT PREFERRED IN 61B.
public boolean equals(Object o) {
if (o == null) { return false; }
if (this == o) { return true; } // optimization
if (this.getClass() != o.getClass()) { return false; }
ArraySet<T> other = (ArraySet<T>) o;
…
}
Summary
We built our own Array based Set implementation.
To make it more industrial strength we:
Better toString (Bonus)
Lecture 12, CS61B, Spring 2023
Today’s Goal: ArraySet
Iteration
Object Methods
The Lazy Way
Can use the String.join method to convert list of strings into a single string.
@Override
public String toString() {
List<String> listOfItems = new ArrayList<>();
for (T x : this) {
listOfItems.add(x.toString());
}
return "{" + String.join(", ", listOfItems) + "}";
}
ArraySet.of (Bonus)
Lecture 12, CS61B, Spring 2023
Today’s Goal: ArraySet
Iteration
Object Methods
The of Method
We can write our own of method as follows:
public static <Glerp> ArraySet<Glerp> of(Glerp... stuff) {
ArraySet<Glerp> returnSet = new ArraySet<Glerp>();
for (Glerp x : stuff) {
returnSet.add(x);
}
return returnSet;
}
Citations