CS61B(11): Exceptions, Iterators, Object Methods

Posted on | In , |

This is the lecture note of CS61B - Lecture 11.

Lists and Sets in Java

In real world, we won't built the data structures such as LinkedList, AList, Deque etc. from scratch. Instead, we will use the Java's built-in data structures directly.

In this part, let's see Java's built-in data structures.

Lists

Java provides a built-in List interface, and several implementations such as ArrayList.

1
2
3
4
5
6
7
8
9
10
11
12
import java.util.List;
import java.util.ArrayList;

public class ListDemo {
    public static void main(String[] args) {
        List<Integer> L = new ArrayList<>();
        L.add(5);
        L.add(10);
        L.add(15);
        System.out.println(L);
    }
}

Sets

Another handy data structure is Set.

1
2
3
4
5
6
7
8
9
10
11
12
13
import java.util.Set;
import java.util.HashSet;

public class ListDemo {
    public static void main(String[] args) {
        Set<String> S = new HashSet<>();
        S.add("Tokyo");
        S.add("Beijing");	
        S.add("Lagos");
        S.add("São Paulo");
        System.out.println(S.contains("Tokyo"));
    }
}

For the rest of the blog, we will talk about how to implement our own Set called ArraySet.

Basic ArraySet

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public class ArraySet<T> {
    private T[] items;
    private int 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.
       Throws an IllegalArgumentException if the key is null. */
    public void add(T x) {
        // ignore resizign now

        if (contains(x)) {
            return;
        }
        items[size] = x;
        size += 1;
    }

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

    public static void main(String[] args) {
        ArraySet<Integer> aset = new ArraySet<>();
        // aset.add(null);  // error: NullPointerException
        aset.add(5);
        aset.add(23);
        aset.add(42);
    }
}

Exceptions

The above code has a subtle bug. See the comment in main method.

Since the bug, if we uncomment and run the above code, it will crash and break the normal flow of control. And the compiler will throw the exception.

We can throw our own exceptions, too.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public void add(T x) {
    // ignore resizign now

    if (x == null) {
        throw new IllegalArgumentException("Cannot add null!");
    }
    if (contains(x)) {
        return;
    }
    items[size] = x;
    size += 1;
}

/**
 * However, this will still cause crash.
 * So maybe we can fix our code by:
 *  - ingore null;
 *  - fix contains so that it doesn't crash if items[i] is null;
 * /

Iterable

Our ArraySet doesn't support enhanced for loop, that means it isn't iterable.

Before trying to make our ArraySet supports enhanced for loop, firstly, let's try to use an alternative way to iterate.

Actually, the enhanced for loop is just shorthand of this ugly while loop. The extra you need to do is declaring that public class ArraySet<T> implements Iterable<T>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
import java.util.Iterator;

public class ArraySet<T> implements Iterable<T> {
    private T[] items;
    private int 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.
       Throws an IllegalArgumentException if the key is null. */
    public void add(T x) {
        // ignore resizign now

        if (x == null) {
            throw new IllegalArgumentException("Cannot add null!");
        }
        if (contains(x)) {
            return;
        }
        items[size] = x;
        size += 1;
    }

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

    private class ArraySetIterator implements Iterator<T> {
        private int wizPos;

        private ArraySetIterator() {
            wizPos = 0;
        }

        public boolean hasNext() {
            return wizPos  < size;
        }

        public Integer next() {
            T returnItem = items[wizPos];
            wizPos += 1;
            return returnItem;
        }
    }

    /** Returns an iterator (a.k.a seer) into ME. */
    public Iterator<T> iterator() {
        return new ArraySetIterator();
    }

    public static void main(String[] args) {
        ArraySet<Integer> aset = new ArraySet<>();
        // aset.add(null);  // error: NullPointerException
        aset.add(5);
        aset.add(23);
        aset.add(42);

        Iterator<Integer> aseer = aset.iterator();
        while(aseer.hasNext()) {
            int i = aseer.next();
            System.out.println(i);
        }
    }
}

Object Methods:

#1: toString

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import java.util.Iterator;

public class ArraySet<T> implements Iterable<T> {
    
    // ......

    @Override
    public String toString() {
        // String is immutable, so we use StringBuilder
        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();
    }

    public static void main(String[] args) {
        ArraySet<Integer> aset = new ArraySet<>();
        aset.add(5);
        aset.add(23);
        aset.add(42);

        //iteration
        for (int i : aset) {
            System.out.println(i);
        }

        //toString
        System.out.println(aset);
    }
}

#2: equals

As mentioned before, == and .equals() behave differently.

  • == compares the bits. For reference, it means "referencing the same object"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
import java.util.Iterator;

public class ArraySet<T> implements Iterable<T> {
    
    // ......

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

    public static void main(String[] args) {
        ArraySet<Integer> aset = new ArraySet<>();
        aset.add(5);
        aset.add(23);
        aset.add(42);

        //iteration
        for (int i : aset) {
            System.out.println(i);
        }

        //toString
        System.out.println(aset);

        //equals
        ArraySet<Integer> aset2 = new ArraySet<>();
        aset2.add(5);
        aset2.add(23);
        aset2.add(42);

        System.out.println(aset.equals(aset2));  // true
        System.out.println(aset.equals(null));  // false
        System.out.println(aset.equals("fish"));  // false
        System.out.println(aset.equals(aset));  // true

        //EXTRA VIDEO CODE
        //ArraySet<String> asetOfStrings = ArraySet.of("hi", "I'm", "here");
        //System.out.println(asetOfStrings);
    }
}

Extra: Better toString and ArraySet.of

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
import java.util.Iterator;

public class ArraySet<T> implements Iterable<T> {
    
    // ......

    /*@Override
    public String toString() {
        // String is immutable, so we use StringBuilder
        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();
    }*/

    // Better `toString` method
    @Override
    public String toString() {
        List<String> listOfItems = new ArrayList<>();
        for (T x: this) {
            listOfItems.add(x.toString());
        }
        return "{" + String.join(",", listOfItems) + "}";
    }

    // of method
    public static <Glerp> ArraySet<Glerp> of(<Glerp> ..stuff) {  // var arg
        ArraySet<Glerp> returnSet = new ArraySet<>();
        for (Glerp x: stuff) {
            returnSet.add(x);
        }
        return returnSet;
    }

    public static void main(String[] args) {
        ArraySet<Integer> aset = new ArraySet<>();
        aset.add(5);
        aset.add(23);
        aset.add(42);

        //iteration
        for (int i : aset) {
            System.out.println(i);
        }

        //toString
        System.out.println(aset);

        // of method
        ArraySet<String> aset2 = ArraySet.of("hi", "I'm", "here.");
    }
}