1 The Problem of Generality

回顾一下我们上篇文章中实现的SLList和AList，它们支持相同的方法，例如addLast, addFirst等等，有些如果没有，那可能是我没实现（

Suppose we want to write a class WordUtilsthat includes functions we can run on lists of words, including a method that calculates the longest string in an SLList.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class WordUtils {
    /** Returns the word with the longest length. */
    public static String longest(SLList<String> list) {
        int maxDex = 0;
        for (int i = 0; i < list.size(); i += 1) {
            String longestString = list.get(maxDex);
            String thisString = list.get(i);
            if (thisString.length() > longestString.length()) {
                maxDex = i;
            }
        }
    return list.get(maxDex);
    }
}

但这个方法只能接受SLList的参数，如果是AList，只需要改成
public static String longest(AList<String> list)

我们在这个类里写两个方法，它们只是signature不一样，这称作method overloading

当我们调用WordUtils.longest时，Java会根据参数的类型来决定运行哪个方法。但是这么做有大量重复的代码；如果要对longest做修改，两个都要改；如果我们有更多list的类型(比如DLList)，我们还要复制更多方法

1.1 Hypernyms, Hyponyms, the Implements Keyword

1.1.1 Hypernyms and Hyponyms

In the English language and life in general, there exist logical hierarchies to words and objects.

Dog is what is called a hypernym(上位词) of poodle, malamute, husky, etc. In the reverse direction, poodle, malamute, and husky, are hyponyms(下位词) of dog.

These words form a hierarchy of “is-a” relationships:

  • a poodle “is-a” dog

  • a dog “is-a” canine(犬类)

  • a canine “is-a” carnivore(肉食动物)

  • a carnivore “is-an” animal

Hierarchy

The same hierarchy goes for SLLists and ALists! SLList and AList are both hyponyms of a more general list.

We will formalize this relationship in Java: if a SLList is a hyponym of List61B, then the SLList class is a subclass of the List61B class and the List61B class is a superclass of the SLList class.

1.1.2 Interface

In Java, in order to express this hierarchy, we need to do two things:

  • Step 1: Define a type for the general list hypernym – we will choose the name List61B.

  • Step 2: Specify that SLList and AList are hyponyms of that type.

The new List61B is what Java calls an interface(接口). It is essentially a contract that specifies what a list must be able to do, but it doesn’t provide any implementation for those behaviors.

1
2
3
4
5
6
7
8
9
10
public interface List61B<Item> {
    public void addFirst(Item x);
    public void addLast(Item y);
    public Item getFirst();
    public Item getLast();
    public Item removeLast();
    public Item get(int i);
    public void insert(Item x, int position);
    public int size();
}

Now, to complete step 2, we need to specify that AList and SLList are hyponyms of the List61B class. In Java, we define this relationship in the class definition.

We will add to

public class AList<Item> {...}

a relationship-defining word: implements.

public class AList<Item> implements List61B<Item>{...}

implements List61B<Item> is essentially a promise. AList is saying “I promise I will have and define all the attributes and behaviors specified in the List61B interface”.

1.2 Overriding, Interface Inheritance

1.2.1 Overriding

We promised we would implement the methods specified in List61B in the AList and SLList classes, so let’s go ahead and do that.

If a “subclass” has a method with the exact same signature as in the “superclass”, we say the subclass overrides(重写) the method.

Methods (in the same class) with the same name but different signatures are overloaded(重载)

When implementing the required functions in the subclass, it’s useful to include the @Override tag right on top of the method signature. For example,

1
2
3
4
@Override
public void addFirst(Item x) {
    insert(0, x);
}

我们来比较一下override和overload

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
public interface Animal {
    public void makeNoise();
}

public class Pig implements Animal {
    @Override
    public void makeNoise() {
        System.out.print("oink");
    }
    // Pig overrides makeNoise()
}

public class Dog implements Animal {
    @Override
    public void makeNoise() {
        System.out.print("bark");
    }

    public void makeNoise(Dog x) {
        // ...
    }
    // makeNoise is overloaded
}

public class Math {
    public int abs(int a) {
        // ...
    }

    public double abs(double a) {
        // ...
    }

    // abs is overloaded
}

1.2.2 Interface Inheritance

Interface Inheritance refers to a relationship in which a subclass inherits all the methods/behaviors of the superclass. As in the List61B class we defined in the Hyponyms and Hypernyms section, the interface includes all the method signatures, but not implementations. It’s up to the subclass to actually provide those implementations.

Specifying the capabilities of a subclass using the implements keyword is known as interface inheritance.

  • Interface: the list of all method signatures.
  • Subclasses must override all of these methods.
  • Interface inheritance is a powerful tool for generalizing code.

This inheritance is also multi-generational.(也就是说，比如List61B上面还有一个superclass叫Collection，那么AList也会继承Collection的所有method)

这样，我们就可以改写longest使它更普遍，不管参数是一个如何实现的list，只要有list的功能即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class WordUtils {
    /** Returns the word with the longest length. */
    public static String longest(List61B<String> list) {
        int maxDex = 0;
        for (int i = 0; i < list.size(); i += 1) {
            String longestString = list.get(maxDex);
            String thisString = list.get(i);
            if (thisString.length() > longestString.length()) {
                maxDex = i;
            }
        }
    return list.get(maxDex);
    }
}

1.2.3 GRoE

Recall the Golden Rule of Equals we introduced in the first chapter. This means whenever we make an assignment a = b , we copy the bits from b into a, with the requirement that b is the same type as a.

1
2
3
4
5
public static void main(String[] args) {
    AList<String> a1 = new AList<String>();
    a1.addLast("horse");
    WordUtils.longest(a1);
}

longest的签名是public static String longest(List61B<String> list)那么我们该如何把bits从a1复制到list呢，它们都不是一个类型？

如果X是Y的superclass，那么X的内存盒子也能装Y，例如一个AList也是一个List61B，所以List61B类型的变量能装AList变量的地址

1
2
3
4
5
6
7
public static void main(String[] args) {
    List61B<String> someList = new SLList<String>();
    someList.addFirst("elk");
}

// When it runs, a SLList is created and its address is stored in the someList variable. 
// Then the string "elk" is inserted into the SLList referred to by addFirst.

1.3 Implementation Inheritance, default

Previously, we had an interface List61B that only had method headers identifying what List61B’s should do. But, now we will see that we can write methods in List61B that already have their implementation filled out. These methods identify how hypernyms of List61B should behave.

In order to do this, you must include the default keyword in the method signature.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public interface List61B<Item> {
    public void addFirst(Item x);
    public void addLast(Item y);
    public Item getFirst();
    public Item getLast();
    public Item removeLast();
    public Item get(int i);
    public void insert(Item x, int position);
    public int size();
    default public void print() {
        for (int i = 0; i < size(); i++) {
            System.out.print(get(i) + " ");
        }
        System.out.println();
    }
}

Then everything that implements the List61B class can use the method!

For an SLList, the get method needs to jump through the entirety of the list during each call. It’s much better to just print while jumping through!

We want SLList to print a different way than the way specified in its interface. To do this, we need to override it. In SLList, we implement this method;

1
2
3
4
5
6
7
@Override
public void print() {
    for (Node p = sentinel.next; p != null; p = p.next) {
        System.out.print(p.item + " ");
    }
    System.out.println();
}

  • Interface inheritance (what): Simply tells what the subclasses are able to do.

    • EX) all lists should be able to print themselves, how they do it is up to them.

  • Implementation inheritance (how): Tells the subclasses how to implement their behavior.

    • EX) Lists should (by default) print themselves exactly this way: by getting each element in order and then printing them.

那么，现在有个问题，下面的程序，调用的是List61B.print()还是SLList.print()呢？

1
2
3
4
5
public static void main(String[] args) {
    List61B<String> someList = new SLList<String>();
    someList.insert("elk");
    someList.print();
}

Java中每个变量都有一个"compile-time type"，也叫"static type"
This is the type specified at declaration. Never changes!

变量也有一个"run-time type"，也叫"dynamic type"
This is the type specified at instantiation(e.g. when using new). Equal to the type of the object being pointed at.

Suppose we call a method of an object using a variable with:

  • compile-time type X
  • run-time type Y

Then if Y overrides the method, Y’s method is used instead. This is known as “dynamic method selection”.

因此，上面问题的答案是SLList.print()

注意，这对overloaded methods是不适用的，例如一个类中有两个method

1
2
3
4
5
6
public static void peek(List61B<String> list) {
    System.out.println(list.getLast());
}
public static void peek(SLList<String> list) {
    System.out.println(list.getFirst());
}

如果我们运行

1
2
3
4
5
6
7
SLList<String> SP = new SLList<String>();
List61B<String> LP = SP;
SP.addLast("elk");
SP.addLast("are");
SP.addLast("cool");
peek(SP);
peek(LP);

第一个peek()会调用第二个参数为SLList的peek方法，第二个peek()会调用第一个参数为List61B的peek方法，这是因为这两个overloaded的方法的区别在于参数类型，Java会检查静态类型来决定调用哪个方法

2 Extends, Casting, Higher Order Functions

2.1 Implementation Inheritance: Extends

So, we have the idea of inheritance: the idea that a class/object does not need to redefine all its methods, and instead can use properties of a parent class.

When a class is a hyponym of an interface, we used implements. If you want one class to be a hyponym of another class, you use extends.

2.1.1 Rotating SLList

We’d like to build RotatingSLList that can perform any SLList operation as well as: rotateRight(): Moves back item to the front.

1
2
3
4
5
6
public class RotatingSLList<Item> extends SLList<Item> {
    public void rotateRight() {
        Item x = removeLast();
        addFirst(x);
    }
}

注：public class RotatingSLList<Item> extends SLList<Item>中第一个Item是声明的类型参数，表示RotatingSLList这个类有这一个叫Item的类型参数，而第二个Item是使用这个类型参数，即父类 SLList 的类型参数，使用刚才声明的那个Item

Because of extends, RotatingSLList inherits all members of SLList:

  • All instance and static variables.

  • All methods.

  • All nested classes.

  • Constructors are not inherited!

2.2.2 VengefulSLList

Suppose we want to build an SLList that:

  • Remembers all Items that have been destroyed by removeLast.

  • Has an additional method printLostItems(), which prints all deleted items.

要注意的是，VengefulSLList是不能访问SLList里的private成员的，我们可以使用super关键字来实现类似的效果

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
public class VengefulSLList<Item> extends SLList<Item> {
    private SLList<Item> deletedItems;
    public VengefulSLList() {
        deletedItems = new SLList<Item>();
    }

    @Override
    public Item removeLast() {
        Item oldBack = super.removeLast(); /*calls Superclass’s version of removeLast() */

        deletedItems.addLast(oldBack);
        return oldBack;
    }

    public void printLostItems() {
        deletedItems.print();
    }

    public static void main(String[] args) {
        VengefulSLList<Integer> vs1 = new VengefulSLList<Integer>();
        vs1.addLast(1);
        vs1.addLast(5);
        vs1.addLast(10);
        vs1.addLast(13); /* [1, 5, 10, 13]*/
        vs1.removeLast(); /* 13 gets deleted. */
        vs1.removeLast(); /* 10 gets deleted. */
        System.out.print("The fallen are: ");
        vs1.printLostItems(); /* Should print 10 and 13. */
    }
}

2.2.3 Constructor Behavior

Constructors are not inherited. However, the rules of Java say that all constructors must start with a call to one of the super class’s constructors.

Idea: If every VengefulSLList is-an SLList, every VengefulSLList must be set up like an SLList.

If you don’t explicitly call the constructor, Java will automatically do it for you.

These constructors below are exactly equivalent:

1
2
3
4
5
6
7
8
public VengefulSLList() {
   deletedItems = new SLList<Item>();
}

public VengefulSLList() {
   super();
   deletedItems = new SLList<Item>();
}

On the other hand, if you want to use a super constructor other than the no-argument constructor, can give parameters to super.

These constructors below are not equivalent! The code to below makes implicit call to super(), not super(x). This is because only the empty argument super() is called.

1
2
3
4
5
6
7
8
public VengefulSLList(Item x) {
   super(x);
   deletedItems = new SLList<Item>();
}

public VengefulSLList(Item x) {
   deletedItems = new SLList<Item>();
}

2.2.4 Is-a vs Has-a

Important Note: extends should only be used for is-a (hypernymic) relationships!

Common mistake is to use it for “has-a” relationships. (a.k.a. meronymic).

Possible to subclass SLList to build a Set, but conceptually weird, e.g. get(i) doesn’t make sense, because sets are not ordered.

2.2.5 The Object Class

As it happens, every type in Java is a descendant of the Object class.

  • VengefulSLList extends SLList.

  • SLList extends Object (implicitly).

2.2 Encapsulation

2.2.1 Complexity

When building large programs, our enemy is complexity.

Some tools for managing complexity:

  • Hierarchical abstraction. Create layers of abstraction, with clear abstraction barriers!

  • “Design for change” (D. Parnas)

    • Organize program around objects.
    • Let objects decide how things are done.
    • Hide information others don’t need.

抽象就是忽略不重要的细节，只暴露需要使用的东西。层次抽象，例如用户只需list.addFirst(5);，不需要知道SLList下面的Node是啥、next怎么连接，而SLList里的private IntNode sentinel;就形成了屏障，用户根本用不了sentinel

Design for change的思想是：未来一定会变化，代码结构应该提前考虑变化，正如我们之前的longest，它接受的参数只要是一个列表性质的东西就行，所以用一个接口List61B来方便我们之后适应不同实现的list

围绕对象组织程序的意思是把数据和操作放在一起，而让对象自己决定行为，我们举个例子
比如想让动物叫

1
2
3
4
5
6
7
8
9
public void makeAnimalNoise(Animal a) {
    if (a.type.equals("dog")) {
        System.out.println("bark");
    } else if (a.type.equals("cat")) {
        System.out.println("meow");
    } else if (a.type.equals("pig")) {
        System.out.println("oink");
    }
}

这里决定怎么叫这个行为的是函数makeAnimalNoise()，如果以后加了别的动物，又要多分支，而面向对象则是让对象自己决定怎么叫，例如

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public interface Animal {
    public void makeNoise();
}

public class Dog implements Animal {

    public void makeNoise() {
        System.out.println("bark");
    }
}

public class Cat implements Animal {

    public void makeNoise() {
        System.out.println("meow");
    }
}

现在，调用者只知道，a是个Animal，所以你应该会makeNoise，至于你怎么叫，叫的内容是啥，根据对象来决定，a是狗那就喊bark，是猫就meow，这跟之前的longest是一样的，list是一个满足列表性质的东西，它应该能addLast什么的，但具体怎么addLast，你是SLList还是AList，各有各的实现方式

1
2
3
public void makeAnimalNoise(Animal a) {
    a.makeNoise();
}

这也跟隐藏信息联系起来，对象自己决定行为，不需要别人知道的内部细节就别让别人知道，这样如果对象的内部细节出了问题，改这个类即可，如果别的地方用到了对象的内部细节，就也要相应地修改，很复杂

2.2.2 Modules

Module: A set of methods that work together as a whole to perform some task or set of related tasks. A module is said to be encapsulated(封装) if its implementation is completely hidden, and it can be accessed only through a documented interface.

2.3 Casting

2.3.1 Compile-Time Type Checking and Expressions

Compiler allows method calls based on compile-time type of variable. The compiler also allows assignments based on compile-time types.

1
2
3
4
5
6
7
8
9
10
11
public static void main(String[] args) {
    VengefulSLList<Integer> vsl = new VengefulSLList<Integer>(9);

    SLList<Integer> sl = vsl;

    sl.addLast(50);
    sl.removeLast();

    sl.printLostItems(); // Compilation error.
    VengefulSLList<Integer> vsl2 = sl; // Compilation error.
}

上面这段程序中，sl的run-time type是VengefulSLList，所以会调用VengefulSLList的addLast和removeLast函数，其中由于VengefulSLList没有override addLast函数，所以用的就是SLList的addLast函数

虽然我们知道sl实际上指向的是一个VengefulSLList类的对象，但是编译器是保守的，类型检查是在程序运行之前的，它发现sl所属的SLList类里没有printLostItems这个函数，因此会报错，同样地，编译器认为sl是SLList，而一个SLList不一定是VengefulSLList，所以不能进行最后一行的赋值

Expressions have compile-time types.
An expression using the new keyword has the specified compile-time type. Example:

1
SLList<Integer> sl = new VengefulSLList<Integer>();

Compile-time type of right hand side (RHS) expression is VengefulSLList.

A VengefulSLList is-an SLList, so assignment is allowed.

1
VengefulSLList<Integer> vsl = new SLList<Integer>();

Compile-time type of RHS expression is SLList.

An SLList is not necessarily a VengefulSLList, so compilation error results.

Expressions have compile-time types:

Method calls have compile-time type equal to their declared type.

1
2
3
public static Dog maxDog(Dog d1, Dog d2) { … }

Poodle d = maxDog(d1, d2); // RHS has compile-time type Dog.

Any call to maxDog will have compile-time type Dog!

2.3.2 Casting

Java has a special syntax for specifying the compile-time type of any expression.

  • Put desired type in parenthesis before the expression.

  • Tells compiler to pretend it sees a particular type.

Casting is a powerful but dangerous tool. It just asks Java to treat an expression as having a different compile-time type and ignore its type checking duties. We can think of it as a way to trick the compiler.

1
2
3
4
Poodle d1 = new Poodle("Frank", 5);
Malamute d2 = new Malamute("Frank Sr.", 100);

Poodle largerPoodle = (Poodle) maxDog(d1, d2);

If we run the code above, we get a ClassCastException at runtime because maxDog actually returns d2, a malamute. We can’t cast a malamute to a poodle.

1
2
3
4
5
6
Object o2 = new ShowDog(26);

Dog dx = (Dog) o2;
dx.bark(); 
// 调用的是ShowDog的bark函数而不是Dog的
// 假设ShowDog extends Dog并重写了bark

2.4 Higher Order Functions in Java

Higher Order Function: A function that treats another function as data.

1
2
3
4
5
6
7
def tenX(x):
    return 10 * x

def do_twice(f, x):
    return f(f(x)) 

print(do_twice(tenX, 2)) # 200

Old School (Java 7 and earlier)
Fundamental issue: Memory boxes (variables) cannot contain pointers to functions.

We can use an interface instead:

1
2
3
public interface IntUnaryFuncion {
    int apply(int x); // 默认public abstract
}
1
2
3
4
5
public class TenX implements IntUnaryFunction {
    public int apply(int x) {
        return 10 * x;
    }
}
1
2
3
4
5
6
7
8
9
10
public class HOFDemo {
    public static int do_twice(IntUnaryFunction f, int x) {
        return f.apply(f.apply(x));
    }

    public static void main(String[] args) {
        IntUnaryFunction tenX = new TenX();
        System.out.println(do_twice(tenX, 2));
    }
}

3 Subtype Polymorphism, Comparators, Comparable

We’ve seen how inheritance lets us reuse existing code in a superclass while implementing small modifications by overriding a superclass’s methods or writing brand new methods in the subclass. Inheritance also makes it possible to design general data structures and methods using polymorphism(多态).

Polymorphism, at its core, means ‘many forms’. In Java, polymorphism refers to how objects can have many forms or types. In object-oriented programming, polymorphism relates to how an object can be regarded as an instance of its own class, an instance of its superclass, an instance of its superclass’s superclass, and so on.

Consider a variable deque of static type Deque. A call to deque.addFirst() will be determined at the time of execution, depending on the run-time type, or dynamic type, of deque when addFirst is called. It can actually be an ArrayDeque or a LinkedListDeque. (同一个Deque类型的变量，可以指向LinkedListDeque，也可以指向ArrayDeque，实际执行什么取决于当前指向的真实对象，同一个类型、同一行方法调用，可以对应多种具体对象和多种具体行为，这就是子类型多态)As we saw in the last chapter, Java picks which method to call using dynamic method selection.

3.1 Comparables

Say we want to write a max function which takes in any array - regardless of type - and returns the maximum item in the array.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static Object max(Object[] items) {
    int maxDex = 0;
    for (int i = 0; i < items.length; i += 1) {
        if (items[i] > items[maxDex]) {
            maxDex = i;
        }
    }
    return items[maxDex];
}

public static void main(String[] args) {
    Dog[] dogs = {new Dog("Elyse", 3), new Dog("Sture", 9), new Dog("Benjamin", 15)};
    Dog maxDog = (Dog) max(dogs);
    maxDog.bark();
}

In the code above, there was only 1 error, found at this line:

1
if (items[i] > items[maxDex]) {

The reason why this results in a compilation error is because this line assumes that the > operator works with arbitrary Object types, when in fact it does not.

The fundamental issue that gives rise to this is that Objects cannot be compared with >. This makes sense, as how could Java know whether it should use the String representation of the object, or the size, or another metric, to make the comparison? In Python or C++, the way that the > operator works could be redefined to work in different ways when applied to different types. Unfortunately, Java does not have this capability. Instead, we turn to interface inheritance to help us out.

We can create an interface that guarantees that any implementing class, like Dog, contains a comparison method, which we’ll call compareTo.

1
2
3
4
5
6
7
8
public interface OurComparable {
    /**
     * Return negative if this is < o.
     * Return 0 if this is equals o.
     * Return positive if this is > o.
     */
    public int compareTo(Object o);
}
1
2
3
4
5
6
7
public class Dog implements OurComparable {
    // ...
    public int compareTo(Object o) {
        Dog d = (Dog) o;
        return this.size - d.size;
    }
}

于是有

1
2
3
4
5
6
7
8
9
10
public static Object max(OurComparable[] items) {
    int maxDex = 0;
    for (int i = 0; i < items.length; i += 1) {
        int cmp = items[i].compareTo(items[maxDex]);
        if (cmp > 0) {
            maxDex = i;
        }
    }
    return items[maxDex];
}

所有实现OurComparable的对象，都可以交给这个方法，这就是多态，它们的具体类型可以不同，但都承诺提供compareTo

实际上，我们可以用已经有的接口Comparable

1
2
3
public interface Comparable<T> {
    public int compareTo(T obj);
}
1
2
3
4
5
6
7
public class Dog implements Comparable<Dog> {
    // ...

    public int compareTo(Dog uddaDog) {
        return this.size - uddaDog.size;
    }
}

3.2 Comparators

We’ve just learned about the comparable interface, which imbeds into each Dog the ability to compare itself to another Dog. Now, we will introduce a new interface that looks very similar called Comparator.

As an example, the natural ordering of Dogs, as we stated previously, is defined according to the value of size. What if we’d like to sort Dogs in a different way than their natural ordering, such as by alphabetical order of their name?

Java’s way of doing this is by using Comparator’s. Since a comparator is an object, the way we’ll use Comparator is by writing a nested class inside Dog that implements the Comparator interface.

1
2
3
public interface Comparator<T> {
    int compare(T o1, T o2);
}

This shows that the Comparator interface requires that any implementing class implements the compare method. The rule for compare is just like compareTo. (Return negative if o1 < o2…)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import java.util.Comparator;

public class Dog implements Comparable<Dog> {
    ...
    public int compareTo(Dog uddaDog) {
        return this.size - uddaDog.size;
    }

    private static class NameComparator implements Comparator<Dog> {
        public int compare(Dog a, Dog b) {
            return a.name.compareTo(b.name); // String type is comparable.
        }
    }

    public static Comparator<Dog> getNameComparator() {
        return new NameComparator();
    }
}

Note that we’ve declared NameComparator to be a static class. A minor difference, but we do so because we do not need to instantiate a Dog to get a NameComparator.

1
2
3
4
5
6
7
8
9
10
11
12
Dog a = new Dog("Milo", 10);
Dog b = new Dog("Coco", 20);

// 由于NameComparator是private类，不能Dog.NameComparator，用Comparator<Dog>来装
Comparator<Dog> nc = new Dog.getNameComparator(); // nc是Comparator类，是NameComparator的上位词

int cmp = nc.compare(a, b);
if (cmp > 0) {
    a.bark();
} else {
    b.bark();
}

All in all, we have a Dog class that has a private NameComparator class and a method that returns a NameComparator we can use to compare dogs alphabetically by name.

Let’s see how everything works in the inheritance hierarchy - we have a Comparator interface that’s built-in to Java, which we can implement to define our own Comparators (NameComparator, SizeComparator, etc.) within Dog.

To summarize, interfaces in Java provide us with the ability to make callbacks(回调). Sometimes, a function needs the help of another function that might not have been written yet. A callback function is the helping function. In some languages, this is accomplished using explicit function passing; in Java, we wrap the needed function in an interface.

例如

1
2
3
4
5
6
public static Dog max(Dog a, Dog b, Comparator<Dog> c) {
    if (c.compare(a, b) > 0) {
        return a;
    }
    return b;
}

max被调用时，也要传入c，执行到c.compare(a, b)，调用提供的比较规则c，其中max调用提供的compare方法就是回调。

在max函数中，Comparator是接口，规定比较器必须提供compare；比较器对象c携带用户选择的比较规则；c可以指向不同实现，执行各自的compare，这是多态

A Comparable says, “I want to compare myself to another object”. It is imbedded within the object itself, and it defines the natural ordering of a type. A Comparator, on the other hand, is more like a third party machine that compares two objects to each other. Since there’s only room for one compareTo method, if we want multiple ways to compare, we must turn to Comparator.

4 Iterators, Object Methods

4.1 Lists and Sets in Java

In this course, we’ve already built two kinds of lists: AList and SLList. We also built an interface List61B to enforce specific list methods AList and SLList had to implement.

This is how we might use List61B type:

1
2
3
4
5
List61B<Integer> L = new AList<>();
L.addLast(5);
L.addLast(10);
L.addLast(15);
L.print();

We built a list from scratch, but Java provides a built-in List interface and several implementations, e.g. ArrayList.

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

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

Sets are a collection of unique elements - you can only have one copy of each element. Unlike Lists, there is also no sense of order: you can’t index into a set, nor can you control where each element is inserted into the set.

Java has the Set interface along with implementations, e.g. HashSet. Remember to import them if you don’t want to use the full name!

1
2
3
4
5
6
7
import java.util.Set;
import java.util.HashSet;

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

Now let’s make our own set, ArraySet.

4.2 Exceptions

我们先简单实现下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
public class ArraySet<T> implements Iterable<T>{
    private T[] items;
    private int size;

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

    public boolean contains(T x) {
        for (int i = 0; i < size; ++i) {
            if (items[i].equals(x)) {
                return true;
            }
        }
        return false;
    }

    public void add(T x) {
        if (!contains(x)) {
            items[size] = x;
            size += 1;
        }
    }

    public int size() {
        return size;
    }
}

The probelm lies in the contains method where we check items[i].equals(x). If the value at items[i] is null, then we are calling null.equals(x) -> NullPointerException.

Exceptions(异常) cause normal flow of control to stop. We can in fact choose to throw our own exceptions. In python you may have seen this with the raise keyword. In Java, Exceptions are objects and we throw exceptions using the following format:
throw new ExceptionObject(parameter1, ...)

1
2
3
4
5
6
7
8
9
public void add(T x) {
    if (x == null) {
        throw new IllegalArgumentException("Can't add null");
    }
    if (!contains(x)) {
        items[size] = x;
        size += 1;
    }
}

这样，虽然程序依然会异常，但我们可以决定在哪里停止我们程序的运行，而且我们提供的异常类型更加有用，对于使用我们代码的人来说，错误信息也更加清晰明了

不过，程序不停止运行当然更好，我们可以改变contains，比如如果items[i] == null那就单独判断x == null

4.3 Iteration

We can use a clean enhanced for loop with Java’s HashSet.

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

However, if we try to do the same with our ArraySet, we got an error. How can we enable this functionality?

4.2.1 Enhanced For Loop

Let’s first understand what is happening when we use an enhanced for loop. We can “translate” an enhanced for loop into an ugly, manual approach.

1
2
3
4
5
Set<String> s = new HashSet<>();
...
for (String city : s) {
    ...
}

The above code translates to:

1
2
3
4
5
6
7
Set<String> s = new HashSet<>();
...
Iterator<String> seer = s.iterator();
while (seer.hasNext()) {
    String city = seer.next();
    ...
}

The key here is an object called an iterator.

First, we get a new iterator object with Iterator<String> seer = s.iterator();

Next, we loop through the set with our while loop. We check that there are still items left with seer.hasNext(), which will return true if there are unseen items remaining, and false if all items have been processed.

Last, seer.next() does two things at once. It returns the next element of the set, and here we print it out. It also advances the iterator by one item. In this way, the iterator will only inspect each item once.

4.2.2 Implementing Iterators

Let’s start by thinking about what the compiler needs to know in order to successfully compile the following iterator example:

1
2
3
4
5
6
List<Integer> friends = new ArrayList<Integer>();
Iterator<Integer> seer = friends.iterator();

while(seer.hasNext()) {
    System.out.println(seer.next());
}

We can look at the static types of each object that calls a relevant method. friends is a List, on which iterator() is called, so we must ask:

Does the List interface have an iterator() method?

seer is an Iterator, on which hasNext() and next() are called, so we must ask:

Does the Iterator interface have next/hasNext() methods?

So how do we implement these requirements?

The List interface extends the Iterable interface, inheriting the abstract iterator() method. (Actually, List extends Collection which extends Iterable, but it’s easier to codethink of this way to start.)

1
2
3
4
5
6
7
8
public interface Iterable<T> {
    Iterator<T> iterator();
}


public interface List<T> extends Iterable<T>{
    ...
}

Next, the compiler checks that Iterators have hasNext() and next(). The Iterator interface specifies these abstract methods explicitly:

1
2
3
4
public interface Iterator<T> {
    boolean hasNext();
    T next();
}

下面我们就给自己的ArraySet加入遍历元素的功能

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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;
    }
}

这样就可以遍历ArraySet里的元素了：

1
2
3
4
5
6
7
8
9
10
ArraySet<Integer> aset = new ArraySet<>();
aset.add(5);
aset.add(23);
aset.add(42);

Iterator<Integer> iter = aset.iterator();

while(iter.hasNext()) {
    System.out.println(iter.next());
}

We still want to be able to support the enhanced for loop, though, to make our calls cleaner. So, we need to make ArraySet implement the Iterable interface. The essential method of the Iterable interface is iterator(), which returns an Iterator object for that class.

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
import java.util.Iterator;
public class ArraySet<T> implements Iterable<T>{
    ...

    /** Returns an iterator. */
    public Iterator<T> iterator() {
        return new ArraySetIterator();
    }

    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 static void main(String[] args) {
        ArraySet<Integer> aset = new ArraySet<>();
        aset.add(5);
        aset.add(23);
        aset.add(42);
        for (int i : aset) {
            System.out.println(i);
        }
    }
}

Here we’ve seen Iterable, the interface that makes a class able to be iterated on, and requires the method iterator(), which returns an Iterator object. And we’ve seen Iterator, the interface that defines the object with methods to actually do that iteration. You can think of an Iterator as a machine that you put onto an iterable that facilitates the iteration. Any iterable is the object on which the iterator is performing. (e.g. An ArraySetIterator is performing, or iterating on an ArraySet, which implements iterable and is an iterable.)

4.4 Object Methods

All classes inherit from the overarching(首要的、支配一切的) Object class. There are some methods that are inherited, and we’re going to focus on toString() and equals() in this chapter. We will take advantage of inheritance to override these two methods in our classes to behave in the ways we want them to.

4.4.1 toString()

The toString() method provides a string representation of an object. The System.out.println() function implicitly calls this method on whatever object is passed to it and prints the string returned.

1
2
3
4
System.out.println(dog); 
// 等价于
String s = dog.toString();
System.out.println(s);

The default Object class’ toString()method prints the location of the object in memory. This is a hexadecimal string. Classes like Arraylist and java arrays have their own overridden versions of the toString() method.

1
2
3
4
5
6
7
8
9
10
11
@Override
public String toString() {
    String returnString = "{";
    for (int i = 0; i < size; i += 1) {
        returnString += items[i];
        // actually returnString += items[i].toString();
        returnString += ", ";
    }
    returnString += "}";
    return returnString;
}

This solution, although seemingly simple and elegant, is actually very naive. This is because when you use string concatenation in Java like so: returnString += items[i]; you are actually not just appending to returnString, you are creating an entirely new string. This is incredibly inefficient because creating a new string object takes time too! Specifically, linear in the length of the string.

Bonus Question
Let’s say concatenating one character to a string takes 1 second. If we have an ArraySet of size 5: {1, 2, 3, 4, 5}, how long would it take to run the toString() method?

Answer: We set returnString to the left bracket which takes one second because this involves adding { to the empty string "". Adding the first element will involve creating an entirely new string, adding } and 1 which would take 2 seconds. Adding the second element takes 3 seconds because we need to add {, 1, 2. This process continues, so for the entire array set the total time is 1 + 2 + 3 + 4 + 5 + 6 + 7.

To remedy this, Java has a special class called StringBuilder. It creates a string object that is mutable, so you can continue appending to the same string object instead of creating a new one each time.

1
2
3
4
5
6
7
8
9
10
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();
}

这里我们再提供一种方式

1
2
3
4
5
6
7
8
9
10
11
12
@Override
public String toString() {
    StringBuilder returnSB = new StringBuilder("{");
    List<String> listOfItems = new ArrayList<>();
    for (T x : this) {
        listOfItems.add(x.toString());
    }
    returnSB.append(String.join(", ", listOfItems));
    // Append "5, 23, 42"
    returnSB.append("}");
    return returnSB.toString();
}

4.4.2 equals(Object o)

equals(Object o) is a method in the Object class that, by default, acts like == in that it checks if the memory address(or the bits in the “box”) of the this is the same as o. However, we can override it to define equality in whichever way we wish! For example, for two Arraylists to be considered equal, they just need to have the same elements in the same order.

1
2
3
4
5
6
7
@Override
public boolean equals(Object o) {
    if (o instanceof Dog uddaDog) {
        return this.size == uddaDog.size;
    }
    return false;
}

The instanceof keyword is very powerful in Java.

  • Checks to see if o’s dynamic type is Dog (or one of its subtypes).
  • Casts o into a variable of static type Dog called uddaDog.
  • Works correctly, even if o is null.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
@Override
public boolean equals(Object o) {
    if (this == o) {
        // An efficiency optimization.
        return true;
    }
    if (o instanceof ArraySet oas) {
        // Check sets are of the same size.
        if (oas.size() != this.size()) {
            return false;
        }

        // Check that all of my items are in the other array set.
        for (T x : this) {
            if (!oas.contains(x)) {
                return false;
            }
        }
        return true;
    }
    return false;
}

4.5 of

最后，我们来实现一个of方法，它的效果是

1
2
3
4
5
ArraySet<Integer> aset = ArraySet.of(5, 23, 42, 5);
// {5, 23, 42}

// 右边省略了类型参数，编译器会进行类型推断
// 也可以是ArraySet.<Integer>of
1
2
3
4
5
6
7
public static <Glerp> ArraySet<Glerp> of(Glerp... stuff) {
    ArraySet<Glerp> returnSet = new ArraySet<Glerp>();
    for (Glerp x : stuff) {
        returnSet.add(x);
    }
    return returnSet;
}

静态方法不能使用类声明的类型参数，但可以使用自己声明的类型参数，第一个<Glerp>就是声明这个方法自己的类型参数叫做Glerp，而ArraySet<Glerp>是返回值的类型

Glerp... stuff中的...表示调用者可传入0个或多个参数，在方法内部，stuff是一个Glerp[]类型的数组，里面的元素就是传入的参数，一个方法最多有一个可变参数，必须放在参数列表最后