CS 61B part4 Iterators, Exceptions

prev:[[61B_Part_3_OOP]]
next: [[Git-intro]]
Hug61B chapter6

sets

a collection of unique elements.
you can only have one copy of each element. There is also no sense of order.

Java set example use:

Set<String> s = new HashSet<>();
s.add("Tokyo");
s.add("Lagos");
System.out.println(S.contains("Tokyo")); // true

Goal: make our own ArraySet, with the following methods:

• add(value): add the value to the set if not already present

• contains(value): check to see if ArraySet contains the key

• size(): return number of values

our code:

import java.util.Iterator;

public class ArraySet<T> implements Iterable<T> {
    private T[] items;
    private int size; // the next item to be added will be at position size

    public ArraySet() {
        items = (T[]) new Object[100];
        size = 0;
    }

    /* Returns true if this map contains a mapping for the specified key.
     */
    public boolean contains(T x) {
        for (int i = 0; i < size; i += 1) {
            if (items[i].equals(x)) {
                return true;
            }
        }
        return false;
    }

    /* Associates the specified value with the specified key in this map. */
    public void add(T x) {
        if (contains(x)) {
            return;
        }
        items[size] = x;
        size += 1;
    }

    /* Returns the number of key-value mappings in this map. */
    public int size() {
        return size;
    }
}

Expectations

Small error: when null was added to the set, the nullPointerException was raised.

So, we would throw expectations when null was added.

In Java, Exceptions are objects, and we throw exceptions using the following format:

throw new ExceptionObject(parameter1, ...)

the following code would be added:

if (x == null) {
        throw new IllegalArgumentException("can't add null");
    }

Why this one is better?

1. we have control of our own code
2. more useful error messages were got.

Also, we can check if it is null to completely avoid the error.

Iteration

we can do this with Java’s HashSet

Set<String> s = new HashSet<>();
s.add("Tokyo");
s.add("Lagos");
for (String city : s) {
    System.out.println(city);
}

Why with our ArraySet, there is some questions?

The nature of Enhanced For Loops

The for loops above can be translated as the Iterator version:

Set<String> s = new HashSet<>();
...
Iterator<String> seer = s.iterator();
while (seer.hasNext()) {
    String city = seer.next();
    ...
}

Iterator<String> seer = s.iterator();: build a new Iterator

seer.hasNext(): whether the Iterator is still have items left

seer.next(): return the next item and push the iterator by one item.

Implementing Iterators

Based on the implementations above,
the List interface have an iterator() method.

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

also, the Iterator interface have next/hasNext() methods.

public interface Iterator<T> {
boolean hasNext();
T next();
}

To implement it, we first write a new class called ArraySetIterator, nested inside ArraySet:

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;
    }
}

Afterwards, we need to make ArraySet implement the Iterable interface.

public Iterator<T> iterator() {
    return new ArraySetIterator();
}

Iterable: the interface that makes a class able to be iterated on

Iterator: the interface that defines the object with methods to actually do that iteration.

Object methods

the list of object methods

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)

we would explain the first two methods.

toString()

provides a string representation of an object

System.out.println(dog); Actually run like this:

String s = dog.toString();
System.out.println(s);

Default: print the location of the object in memory(hexadecimal(十六进制的) string)

Classes like Arraylist and java arrays have their own overridden versions of the toString() method.

Therefore, if we want to print our class in a readable format, Override toString() is necessary.

The overall solution of ArraySet is here.

possible solution 1:

public String toString() {
    String returnString = "{";
    for (int i = 0; i < size; i += 1) {
        returnString += keys[i];
        returnString += ", ";
    }
    returnString += "}";
    return returnString;
}

Its efficiency is very low!

when you use string concatenation in Java like so: returnString += keys[i]

you are actually not just appending to returnString, you are creating an entirely new string.

and it takes time.

To solve this problem, Stringbuilder in Java helps to build the mutable string.

public String toString() {
        StringBuilder returnSB = new StringBuilder("{");
        for (int i = 0; i < size - 1; i += 1) {
            returnSB.append(items[i].toString());
            returnSB.append(", ");
        }
        returnSB.append(items[size - 1]);
        returnSB.append("}");
        return returnSB.toString();
    }

equals()

In Java, == checks if the two objects are actually the same object in the memory.
If they are addresses, it means checking if the address is equal

However, equals() method, in default, checks the same as ==. However, we can override the method to
define whatever we want!

public boolean equals(Object other) {
        if (this == other) {
            return true;
        }
        if (other == null) {
            return false;
        }
        if (other.getClass() != this.getClass()) {
            return false;
        }
        ArraySet<T> o = (ArraySet<T>) other;
        if (o.size() != this.size()) {
            return false;
        }
        for (T item : this) {
            if (!o.contains(item)) {
                return false;
            }
        }
        return true;
    }

Rules for Equals in Java

1. equals must be an equivalence relation

• reflexive: x.equals(x) is true
• symmetric: x.equals(y) if and only if y.equals(x)
• transitive: x.equals(y) and y.equals(z) implies x.equals(z)

2. It must take an Object argument, in order to override the original .equals() method
3. It must be consistent if x.equals(y), then as long as x and y remain unchanged: x must continue to equal y
4. It is never true for null x.equals(null) must be false