又小鸽了一个多月，趁开学前再推一点进度……

在CS61A中，我们已经初步了解了面向对象编程中的继承关系，这里我们将进一步深化理解这一概念。

继承（Inheritance）

我们先从一个简单的例子看起：假设我们有一个字符串列表（SLList类型），我们需要计算这个列表中最长的字符串元素，其方法实现如下：

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

现在我们尝试将这个方法套用到字符串数组（AList）上。一种直接的方法是利用方法重载（之前我们简单提到过Java的这一特性），复制这一方法，并修改参数类型即可：

public static String longest(AList<String> list) {
    //同上（使用的方法名称都一样）
}

这样，在调用方法时，Java会自动根据调用对象的类型选择对应的方法。然而，这种重载的缺点也很明显：代码重复性高，不易维护。因此我们需要引入继承进行优化。

在CS61A中，我们已经知道了超类与子类这两个概念，下面我们来介绍它们在Java中的实现。以SLList与AList为例，记它们共同的超类为List61B【在Java中，它也被称为一种接口（interface）】，那么我们可以对这个超类作如下定义：
```
public interface List61B<Item> { //这里用`interface`代替`class`表示类接口
    //注：接口对象不需要构造器，因而无法直接定义List61B对象
    public void addFirst(Item x);//省略方法的具体实现
    public void add Last(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();
}
```
那么如何从这个超类继承出子类呢？这里我们需要使用implements关键字：
```
public class AList<Item> implements List61B<Item>{...} //SLList同理
```
这样上述longest方法就可以直接用List61B作为参数。

注：其实这里用超类与子类这两个概念不完全合适，这里更像是接口与实现类的关系（不过原理确实是类似的）。真正的超类与子类会在之后进行阐述。

接口继承（Interface Inheritance）

那么超类的方法如何在子类中具体实现呢？在Java中，可以在子类的方法实现上加一个@Override标签，比如：
```
public class AList<Item> implements List61B<Item>{
    @Override
    public void addFirst(Item x) { //注意，在超类中声明的所有方法都需要在子类中明确实现
        insert(x, 0);
    }
    ...
}
```
当然，实际上不加这个@Override标签也可以，但加上这个标签可以让编译器对这一方法进行校对，排查隐藏的bug。

注：如果在子类中直接修改超类方法的形式（如返回类型，参数类型等），那么这也属于方法重载。子类也可以定义超类中没有定义的新方法（不用加@Override）。
在建立的这种接口继承关系后，对于以超类作为参数的方法而言，它也可以接收子类作为参数。
另一方面，就像我们之前看到的内置数据结构一样，我们可以用超类<元素类型> 对象名 = new 子类<元素类型>()这样的形式定义对象，如：
```
public static void main(String[] args) {
    List61B<String> someList = new SLList<String>();
    someList.addFirst("gugugaga");
}
```
实际上，在超类中也可以编写方法的具体实现（作为默认方法），只需加上default关键字即可：
```
default public void print() {
    for (int i = 0; i < size(); i += 1) {
        System.out.print(get(i) + " ");
    }
    System.out.println();
}
```
而子类可以按需对超类的方法进行沿用（什么都不写）或覆盖（使用@Override）。这也被称为实现继承（Implementation inheritance）。

抽象数据类型（ADT）

在数据结构中，抽象数据类型是一个重要概念，其定义操作，而不指定具体实现方式。

由此可知，上述超类接口都属于抽象数据类型。除此之外，常用的抽象数据类型（都可作为接口）还包括：
1. 栈（Stack）
2. 列表（List）【LinkedList，ArrayList可看作其接口实现】
3. 集合（Set）
4. 映射（Map）
而上述ADT（除了映射）在java中又是一个更通用的接口的实现，这个接口就是Collections。使用ADT可以让我们我们能够更加高效且优雅地进行面向对象编程。

下面我们详细介绍一下Java中的集合类型Set。作为接口，其有若干实现子类，如HashSet等。其使用示例如下：

import java.util.Set;
import java.util.HashSet;

//此处省略public类修饰
Set<String> s = new HashSet<>();
s.add("Anon");
s.add("Tokyo");
System.out.println(s.contains("Tokyo")); // 输出true

可以看出除了定义比较繁琐之外，Java的集合类型与Python还是比较类似的。

接下来我们尝试自己实现这一数据类型。具体而言，我们会基于数组实现集合（称为ArraySet），初版代码如下：

public class ArraySet<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 += 1) {
            if (items[i].equals(x)) { //注意这里不能用==，因为Java中==只能用来判定地址相同
                return true;
            }
        }
        return false;
    }
    public void add(T x) {
        if (!contains(x)) {
            items[size] = x;
            size += 1;
        }
    }
}

注意到在上述代码中，如果我们尝试对集合添加null元素，那么会报出NullPointerException异常。实际上，我们也可以自己主动抛出异常，其格式为：throw new ExceptionObject(parameter1, ...)。将其加入到add方法中，我们得到：

public void add(T x) {
    if (x == null) {
        throw new IllegalArgumentException("can't add null");
    }
    if (contains(x)) {
        return;
    }
    items[size] = x;
    size += 1;
}

当然除了主动抛出异常还有其他解决方案，但这种特殊情况的确需要特殊考虑。

Java的内置HashSet类型支持在for循环中使用冒号进行迭代：

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

这其实隐含了一个迭代器（与CS61A中提到的python迭代器比较类似）：

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

下面我们尝试对ArraySet也写一个迭代器。具体而言，我们需要定义一个iterator()方法，其会返回一个Iterator对象。

迭代器实现

注意到，上述代码中是Set类型对象调用了iterator()方法。实际上，对于所有Collections接口继承的对象，都可以调用iterator()方法。而这一方法在Java中是在一个被称为Iterable的接口中声明的，并让Collections继承了这一接口。为简化上述表述，我们用下述代码框架进行表示：
```
import java.util.Iterator;

public interface Iterable<T> {
    Iterator<T> iterator();
}
public interface Set<T> extends Iterable<T>{ //当然可改为其他ADT
    ...
}
```
注意在Java中，如果是接口继承接口，那么应该使用extends而不是implements。【Java中extends才是真正的超类与子类的关系】

上述Iterable接口中使用了Iterator这一数据类型，它实际上也是一个独立的接口，定义如下：

import java.util.Iterator;
public interface Iterator<T> {
    boolean hasNext(); // 返回是否有下一个迭代值（作为迭代结束标志）
    T next(); // 返回下一个迭代值，并将迭代器向后迭代一次
}

然后我们从继承这个接口，构造针对ArraySet的迭代器实现：

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

    public ArraySetIterator() {
        arrayPos = 0;
    }

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

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

然后我们就可以构建完整的ArraySet框架看起来确实比较绕：

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;
    }
    //contains()，add()与size()方法省略

    public Iterator<T> iterator() { //迭代器方法
        return new ArraySetIterator();
    }

    private class ArraySetIterator implements Iterator<T> {
        //见上
    }
}

而在实际使用中就可以和内置集合类型一样对集合进行迭代：

import java.util.Iterator;

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

/* 也可以直接用下面的简化版本（由上面的迭代器方法实现）
for (int i : aset) {
    System.out.println(i);
}
*/

我们对迭代器实现进行一个简单总结。为实现上述增强循环（使用:），我们需要：
1. 在需要迭代的类中增加iterator()方法，其返回类型为Iterator<T>；
2. 在Iterator<T>类中定义hasNext()和next()方法；
3. 在迭代类定义后面增加implements Iterable<T>。

对象方法（Object Methods）

在Java中，最基础的类是Object，它是所有类的基石（即任何类都继承它的方法）。Object类内置的方法可参见Java官方文档，下面我们介绍其中两种方法：String toString()和boolean equals(Object obj)。

toString()

toString()方法会返回对象的字符串表示形式。Java的输出函数System.out.println()实际上就是隐式调用了这个方法，先将对象转为字符串再将其输出。

默认的toString()会直接返回对象的存储地址，而Java的一些内置类（如ArrayList）会对toString()方法进行覆盖，以返回期望的形式。当然，我们也可以对自定义类手动编写toString()来覆盖。以前面实现的ArraySet为例，我们可以编写一个初版toString()方法：

import java.util.Iterator;

public class ArraySet<T> implements Iterable<T> {
    //...
    @Override
    public String toString() {
        String returnString = "{";
        for (int i = 0; i < size; i += 1) {
            returnString += keys[i];
            returnString += ", ";
        }
        returnString += "}";
        return returnString;
    }

}

然而，上述方法实现中对字符串使用+=操作在Java里会创建一个新字符串，这会导致效率降低。

那么如何解决这一问题？我们可以使用Java中的一个特殊类StringBuilder，它可以创建一个可修改的字符串对象。这样我们的toString()方法实现可以修改如下：

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

当然，Java中还有一种类似Python的.join()函数的字符串拼接方法，示例如下：

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

这样的代码会更简洁，但效率会低于上面的StringBuilder。

equals()

前面我们提到，Java中.equals()与==是完全不同的。在Java中，==用于判断两个对象在内存中是否实际上是同一个对象。对于基本类型来说，这意味着要检查其值是否相等；而对于对象来说，则意味着要检查地址/指针是否相同。因此，对于下述对象：

public class Doge {

   public int age;
   public String name;

   public Doge(int age, String name){
      this.age = age;
      this.name = name;
   }
   public static void main(String[] args) {
      Doge anon = new Doge(5, "Anon");
      Doge soyo = new Doge(6, "soyo");
      Doge soyolin = new Doge(6, "soyo");
      Doge anonjian = anon;
   }
}

那么soyo == soyolin就会返回False，这在实际情况中往往是不合理的。于是这里我们就需要使用equals(Object o)。其默认方法与==一致，但我们可以对其进行覆盖。以ArraySet为例：

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

当然，我们也可以使用instanceof函数检验对象是否符合指定类型，比如：

@Override
public boolean equals(Object o) {
    if (o instanceof Dog newDog) {
        return this.size == newDog.size;
    }
    return false;
}

在构建equals()方法时，需要遵守以下规则：
1. equals()必须是等价关系，即满足自反性、对称性与传递性；
2. equals()方法必须接受一个对象参数以覆盖原始方法；
3. 任何对象都不可能与null相等，即x.equals(null)一定为False。

多态性与比较器

在Python中，我们对复杂对象进行比较/排序时，可以使用函数传递（Function Passing）。比如：

class Dog:
    def __init__(self, name, size):
        self.name = name
        self.size = size

def name_len(dog): # 注意这个函数定义在Dog类之外
    return len(dog.name)

def get_the_max(x, key):
    max_value = x[0]
    for item in x:
        if key(item) > key(max_value):
            max_value = item
    return max_value

max_dog = get_the_max(doglist, name_len) # 假设doglist已定义

这里name_len函数就作为参数传递到get_the_max。当然还有另一种比较的方法：运算符重载（operator overloading）。其示例如下：

class Dog:
   def __init__(self, name, size):
       self.name = name
       self.size = size
  
   def __gt__(self, other):
       return self.size > other.size

def get_the_max(x):
   max_value = x[0]
   for item in x:
       if item > max_value:
           max_value = item
   return max_value

max_dog = get_the_max(doglist)

实际上，运算符>（可以看作一个接口）可以被任意对象的__gt__方法覆盖。我们称这种性质为多态性（polymorphism）。【多态性的定义（来自百度百科）：为不同数据类型的实体提供统一接口，使相同操作在不同对象上引发差异化行为】

接下来我们继续在Java中研究这种多态性。考虑下述代码：

List<Dog> dogs = new ArrayList<>();
dogs.add(new Dog("Uika", 200));
dogs.add(new Dog("Miyako", 5));
dogs.add(new Dog("Blues", 9000));
Dog maxDog = Collections.max(dogs);

这段代码的问题在于Java无法直接比较两个Dog对象，所以会报错。在Java中，我们无法使用运算符重载，但我们可以采用继承方法实现。具体而言，我们需要对下述接口进行实现：

public interface Comparable<T> {
    int compareTo(T o);
}

这是Java的内置接口，其中compareTo函数会在大于、等于和小于情况下分别返回正值、零和负值。和上述实现方法类似，我们使用implements和@Override进行覆写：

public class Dog implements Comparable<Dog> {
    ...
    @Override
    public int compareTo(Dog uddaDog) {
        if (size > uddaDog.size) {
            return 1;
        }
        if (size < uddaDog.size) {
            return -1;
        }
        return 0;
    }
}

当然，我们也可以将这个方法简化如下：

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

事实上，这种类型的多态性也被称为子类多态性（subtype polymorphism），因为它的多态是由子类型（如上面的Dog）实现的。

当然，在Java中同样可以实现类似Python函数传递的方法，同样用接口实现。具体而言，我们基于下述接口（同样是Java内置接口）：

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

定义一个比较器实现（沿用上述Dog对象，以name为比较指标）：

public static class NameComparator implements Comparator<Dog> {
    @Override
    public int compare(Dog a, Dog b) {
        return a.name.compareTo(b.name);
    }
}

然后我们就能在比较函数（如max）中使用这个比较器：

List<Dog> dogs = new ArrayList<>();
dogs.add(new Dog("Leo", 200));
dogs.add(new Dog("Coco", 5));
dogs.add(new Dog("Roscoe", 9000));
Dog maxNameDog = Collections.max(dogs, new Dog.NameComparator());

当然，这种代码形式不太美观（需要在max函数里实例化一个对象），我们实际上可以将实例化对象放进类本身中：

public class Dog {
    ...
    public static final Comparator<Dog> NAME_COMPARATOR = new NameComparator();
}

然后我们就能直接用下面这句代码替换上面的最后一行：

Dog maxNameDog = Collections.max(dogs, Dog.NAME_COMPARATOR);

补充

当然这种比较器还可以用类似Python的Lambda表达式形式表示：

List<Dog> dogs = new ArrayList<>();
dogs.add(new Dog("Grigometh", 200));
dogs.add(new Dog("Pelusa", 5));
dogs.add(new Dog("Clifford", 9000));
Comparator<Dog> dc = (a, b) -> a.name.compareTo(b.name);
Dog maxNameDog = Collections.max(dogs, dc);

不过具体细节不在这里展开。

使用Comparable与Comparator之间最大的区别在于：对于每一个类而言前者是唯一的，而后者可以构建多个（灵活性更强）。

泛化函数（Generic Functions）

在上述代码中，我们使用了Collections.max()这一函数。实际上，它的参数可以是任意类型，我们称这类函数为通用函数。下面我们就来尝试自己构建泛化函数。

以下面这个随机采样函数为例：
```
public class RandomPickerDemo {
    public static void main(String[] args) {
        String[] x = {"hi", "little", "cat"};
        System.out.println(RandomPicker.pickRandom(x)); //pickRandom函数的具体实现待定
    }
}
```
我们希望将这个pickRandom函数适用于任意数据类型的数组。一种直接的想法是使用泛化类型：
```
public class RandomPicker {
    public static <T> T pickRandom(T[] items) {
        Random random = new Random();
        int randomIndex = random.nextInt(x.length);
        return x[randomIndex];
    }
}
```
但是这会产生一个问题：由于函数需要T的具体类型，因此只能先实例化RandomPicker对象后再调用函数：
```
String[] x = {"hi", "little", "cat"};
RandomPicker<String> stringPicker = new RandomPicker<>();
System.out.println(stringPicker.pickRandom(x));
```
同时还需要将上述pickRandom改为非静态函数。总体而言比较麻烦。
下面给出真正的泛化（静态）函数形式：
```
public class RandomPicker {
    public static <T> T pickRandom(T[] x) {
        Random random = new Random();
        int randomIndex = random.nextInt(x.length);
        return x[randomIndex];
    }
}
```
其中声明行的三个T含义分别为：
- <T>：函数适用于任意数据类型数组；
- T：函数返回类型为T；
- T[] x：参数数组类型为T
后两个T都是对第一个T的引用。这种方案可以不需要实例化对象就能调用pickRandom函数。在调用时，不需要显式声明数组类型，函数会自动推断出数据类型。

注意：上述pickRandom函数只能处理引用数据类型，而不能处理原始数据类型（如int[]，string[]等）。~~这是Java语言本身的缺陷~~

类似地，我们也可以写出max函数的泛化版本：

public class Maximizer {
    public static <T> T max(T[] items) {
        T maxItem = items[0];
        for (int i = 0; i < items.length; i += 1) {
            int cmp = items[i].compareTo(maxItem);
            if (cmp > 0) {
                maxItem = items[i];
            }
        }
        return maxItem;
    }
}

当然，因为其中使用了compareTo函数，因此需要从Comparable接口进行继承：

public class Maximizer {
    public static <T extends Comparable<T>> T max(T[] items) {
        //同上
    }
}

因此传入的数组类型T必须为可比较类型，否则会导致编译错误。

补充

Java中实际使用的Maximizer类似下述形式（可参见官方文档）：

public class Maximizer {
    public static <T extends Comparable<? super T>> T max(T[] items) {
            ...
    }
}

CS61B CHAPTER 7