OOP and Algorithms

Course II notes

两个重要的组成部分：

1. 对象的行为（behaviors）
2. 对应的数据（data）

• Instance variables：所有 instances 都有的属性，但其值对于每个 instance 都是独特的
• Instance variables 在内存中拥有独立的空间
• Instance variables 的声明在 class 中声明；在类中申明的成员都被称为类成员。

instant variable 的声明位置应该在紧接 class header

public class Insect {
    //instance variables here
}

public class Insect {
    private double weight;
    private int x;
    private int y;
}

Visibility Modifiers 指在类/instance variable 声明的最前面的关键字。该关键字用于控制类对 instance variable 的管理权限。一些概念：

• encapsulation：类应该提供管理好自身 instance variables 的功能
• private: 只有类中的 method 能够修改本类的 instance variables
• public：允许类外的其他类访问本类的 instance varibales.

通常对类进行测试的手段一般是在类中直接新建一个 main 来测试：

public class Insect {
    private double weight;
    private int x;
    private int y;

    public static void main(String[] args) {
        Insect buzz1 = new Insect();
        Insect buzz2 = new Insect();
    }
}

• 同 C++
• 默认值：
  • int / double / float: 0 / 0.0
  • boolean: false
  • class: null

• 绝大部分情况使用 public，因为需要允许其他部分调用构造函数生成对象。
• 名字与类相同
• 没有返回值

构造函数的调用（Object 的实例化）需要配合自定义构造函数的参数列表：

//cstr
public Insect(double initWeight, int initX, int initY) {
    weight = initWeight;
    x = initX;
    y = initY;
}

//calling cstr
public static void main(String[] args) {
    Insect bug1 = new Insect(5.0, 1, 2);
    Insect bug2 = new Insect(3.0, 1, 3);
}

与其他 method 一样，constructor 也可以通过重载适应不同的参数列表：

public static final int DEFAULT_X = 0;
public static final int DEFAULT_Y = 0;

//cstr overloading
public Insect(double initWeight) 
{
    weight = initWeight;
    x = DEFAULT_X;
    y = DEFAULT_Y;
    count ++;
}

• 类似于 C++ 中的委托构造函数。
• 使用 this 作为创建方式
• Chain 是可以多级的，可以将委托构造函数本身作为底层函数实现更高层的构造函数。

//cstr chain
public Insect(double initWeight)
{
    this(initWeight, DEFAULT_X, DEFAULT_Y);
}

//cstr
public Insect(double initWeight, int initX, int initY) 
{
    weight = initWeight;
    x = initX;
    y = initY;
    count ++;
}

Instances methods 概念上类似 C++ 的成员函数。分为两类：

• Interface：这类函数一般都是 public 的，为其他外部调用者提供接口，因此没有 static 关键字。
• helper：这类函数一般是 private 的，只用于实现 interace 中的 Method。

//interface
public
void move(int newX, int newY)
{
    double distance = calDistance(x, y, newX, newY);
    System.out.println(distance);
    if (distance > 0) {
        x = newX;
        y = newY;
        weight = weight * distance;
        System.out.printf("Moved %.2f units\n", distance);
    }
    else {
        System.out.println("Staying put");
    }
}

//helper
private static 
double calDistance(double x_1, 
                    double y_1, 
                    double x_2, 
                    double y_2) {
                    
    return Math.sqrt(Math.pow(y_1-y_2, 2) + Math.pow(x_1-x_2, 2));
}

//call
bug1.move(1, 10);
bug2.move(10, -300);

class 的定义中通常会出现一些各个 Instance 都会共享的常量：

public static final double aConstant = 0.0001;

• static 将该常量从 instance 限定 转换为多个 instances 共享。
• 因为是常量，所以添加 public 并不会影响封装。

如果不是常量的话，需要设置为 private，避免除了 instances 以外的数据对其进行修改。比如我们在构造函数内部添加一个计数属性用于统计总共创建的对象数：

private static int count = 0;
public Insect {
    ..../
    count ++;
}

• 设计类函数的时候，需要更多的考虑通用性；比如使用 return 取代 打印，这样就能消除对命令行的依赖。
• 与类无关的函数（比如工具类函数），尽量设计为 public static method
• static method 无法访问 non-static member，构建之前需要仔细思考成员之间的关系。

Math.random() 返回 $[0,1)$ 之间的数。可以使用下面的表达式来返回 (min, max) 之间的 int：

(int)(Math.random() * ((max - min)  + 1)) + min;

this 关键字表示的是当前 object 的引用。Java 中可以在类的内部使用 this.attribute / this.method() 的方式来访问（调用）类成员。比如之前的构造函数可以改写成：

public Insect(double weight, int x, int x) 
{
    this.weight = weight;
    this.x = x;
    this.y = y;
}

某些情况下，我们可能需要在类外访问或者修改类中的私有变量。这种情况下我们是无法通过 className.classMember 的方式进行访问的。

访问解决方法是，在类中创建 public 的 method，通过该 method 去访问对应的私有变量。我们将这样的 method 称为 Accessor 或 Getter，比如：

class Insect {
//instance variable
private int count = 0;
private static final int aConstant = 1;
//Accessor
public int getCount() {
    return count;
}
//call
Insect bee = new insect(....);
bee.getCount();

public static getStaticConstant() {
    return aConstant;
}
//call by using class name instead of instance name:
Insect.getStaticConstant();

• 没有参数列表
• 返回值类型是对应私有变量的类型
• 只为有访问私有变量需求的类提供 Accessor

Mutator（Setter），用于在类外修改类中的私有变量。其实现方式与 Accessor 一致。几个 converntion：

• Mutator 返回类型为 void，因为只需要做修改
• 以 set 为前缀，比如 setName(para)
• 在修改对应的变量之前，需要做输入合法性检测

public void setCount(int newCount) {
    if(isLegalCount(newCount) {
        count = newCount;
    }
}

toString() 是 Java 自带的，所有 Object 都会继承的，一个将当前对象信息转化为 String 的 method。默认情况下，toString() 的输出结果为：

#className@instanceHASH
Insect@7699a589

public String toString() {
    return "weight: " + weight + " x: " + x + " y: " + y;
}
//call
System.out.println(bug3.toString());

System.out.println(bug3);

几个重点：

1. 结构：
   1. 负责存储骰子数据的数据类 Die ，以及骰子的行为 roll 的实现方法
   2. 负责运行游戏的游戏逻辑类 Craps
   3. 负责启动游戏的启动类 CrapLauncher
2. 注意事项：
   1. Method 的 visibility 取决于在哪里使用
   2. 访问私有变量一定要通过 Accessor
   3. 除了 Math.Random()，Java 还提供了 util.Random 供使用。本例使用了 Random.nexInt(bound) 实现了骰子的随机结果。
      1. Random.nexInt(bound) 返回的区域是 $[0, bound)$

Source code with comments: craps.zip

• describing this transfer of attributes and behaviors from one class to another
  • A derived class is called a subclass or child class

• Java 不允许多重继承，因此一个 chlid class 只允许有一个 parent class
• parent class 应该选与 chlid class 重合度最高那一个
• 继承代表的关系是 IS，比如 “yellow jacket is a Wasp, Wasp is an insect”
• Java 提供了一个名为 Class 的类；该类多用于继承时使用。

在 Java 的继承机制中：

• 私有成员不会被继承
• 通过 public 的方式继承会破坏封装

因此，如果一个 subclass，希望继承来自 Parent class 的私有成员，但又不希望这些成员被该 subclass 以外的类使用的话，使用 protected 关键字定义 parent class 中的成员：

public class Canine {
    protected double size;
    public Canine(double size) {
        this.size = size;
    }
}

访问权限表格：

• 声明子类使用关键字 extends

public class Canine {
    protected double size;
    public Canine(double size) {
        this.size = size;
    }
}

• 继承（引用）父类成员使用 super() method
• super() 代表了对父类构造函数的调用
• 必须处于子类构造函数定义中的第一列

public class Dog extends Canine {
    //for the subclasses under the dog, e.g. Husky
    protected String name;
    //cstr
    public Dog(String name, double size) {
        //refer to "size" in the parent class "Canine"
        super(size);
        this.name = name;
    }
}

//the Dog constructor is not going to work due to the above rule
//Canine() cannot apply to Dog()

public class Dog extends Canine {
    //....
    private size = 0;
    //cstr
    public Dog(String name, double size) {
        this.size = size;
        this.name = name;
    }
}

Java 中的重写只需要在子类中重新定义需要重写的函数即可：

public class Canine {
    //....
    public void bark() {
        System.out.println("wof wof");
    }
}

public Dog(String name, double size) {
    super(size);
    this.name = name;
}
//super bark override
public void bark() {
    for (int i = 0; i < 2; ++i) {
        super.bark();
    }
}
//call
Dog spot = new Dog("Spot", 9.6);
spot.bark();

//result
wof wof
wof wof

• Overriding 的前提是父类 method 与子类 method 的签名一致。
• 重写的子类 method 不一定遵守父类 method 的 visiblity；比如子类可以使用 public 的方式重写父类中可见性为 pravide 的 method

• final 关键字应用到 method 上，会阻止其被重写
• final 关键字应用到 class 上，会阻止其被继承
• 如果某个实现（优化）非常特别，或者数据非常敏感，使用 final 来确保其不会被重写。

• abstract method：声明了，但还没有定义（实现）的 method
• abstract class: 至少包含一个 abstract method 的 class
• 这两者绑定：包含 abstract method 的 class 必须声明为抽象类

• 概念同 C++ 的虚函数

什么是 abstract method? 在模拟现实生活的过程中，有一些行为的一致性是很低的。比如犬类给自己顺毛的行为，狼，狗，家狗，野狗，都不一样；这种情况下，在父类 Canine 中定义一个标准的 groom() method 是很难的。

我们处理的方式是，声明这个方法，但不实例化，将实现交给子类自行解决。这个要求是强制的；也就是说，在继承了 abstract method (class) 后，子类必须对对应的 abstract method 进行具体的实现。

定义抽象类 / 抽象方法只需要添加 abstract 关键字即可：

public abstract class Canine {
    //....
    public abstract void groom();
    //....
}

• Object Class 是所有类的 root
• 在引用类方法时，我们只能引用类中已有的方法，而不能考虑可能存在的方法，因为：
  • 子类是父类的一种，因此指向父类的引用，也可以说是指向子类
  • 但因为使用引用调用方法时，该方法必须要在类中有声明
  • 因此，不能因为子类中可能存在某种属于的方法，就使用父类的引用去调用子类的方法。所以使用 Object 类型的对象，去访问任意其他 Object 对象中没有声明的方法，都是错误的。
  • 通俗点来讲，你不知道你指向的具体是什么，所以不能乱来。比如猫是动物，狗也是动物，但你不能说因为猫是动物，所以我能让动物抓老鼠；因为很可能当前动物的实例是条狗。
  • 解决方案是使用多态（polymorphism），后面会讲到。

Object 中有一个 method 叫 equals（之前用过，String 类中对齐进行了重载）。默认情况下，Object.equals() 的作用是判断两个实例引用是否指向同一个实例。根据之前讨论的内容，设想一种情况：在不知道 Object 的实例类型具体是哪种子类的情况下，我们要如何使用该对象与其某种特定类型的子类进行比较呢？

一个可行的判断依据是，只有两个子类是同一类型的对象时，才能进行比较。以 Dog 为例，只有两边都是狗的时候，我们才能依据一些条件来进行比较。因此，首先需要做两种判断：

• 空对象不予考虑（值为 null 的对象）
• 对象类型不是 Dog 的不予考虑

Java 提供了 instanceof 运算符将上述的两个操作合二为一了。因此，要检测是不是同一类型的对象，有：

if (!(o instanceof Dog)) {
        return false;
    }

public boolean equals(Object o) {
    if (!(o instanceof Dog)) {
        return false;
    }
    Dog doggy = (Dog) o;
    return ((doggy.size == size) && (doggy.name.equals(name)));
}

Dog doggy = (Dog) o;

在实际的应用中会出现这么一种关系，某一类的对象具有某个行为上的共同点，但对象本身并不构成继承的关系。比如狗与车，都有 “洗” 的行为；但狗和车显然不构成 IS 的关系。

这种情况是无法使用子类重写的方式解决的。因为子类重写的方式要求两点：

• 继承
• 父类必须声明了这样的方法

比如如果都是犬类所属，那对象的 group 定义为犬类即可：

public class GroomEverything {
    public static void main(String[] args) {
        Canine[] groomer = {
            new Wolf(17,3),
            new Poodle("richie", 2,"Pantene", "Bodyshop")
        };
    
        for (Canine c : groomer) { 
            c.groom();
            }     
    }
}

• 声明一系列需要重新定义的 abstract method
• 编译 interface 之后，如果有 class 希望重写该 Interface 里的方法，都可以进行声明
• 如果是 concrete class，那么需要定义重写的方法。抽象类则不用，因为可以交给具体的子类实现。
• 一个 class 可以重写（实现）多个 interface

与 class 的定义类似，interface 也需要单开一个与 Interface 名称相同的文件。在 interface 中声明 method 的方式与 class 一致。在 interface 中，moidifer 的默认有两点：

• 所有声明的 method 默认都是 abstract method
• 所有声明的 method 默认都是 public method

//in Groomable.java
public interface Groomable {
    //lists of abstract methods
    public void groom();
}

• 首先需要为对应的 class 添加 implements 关键字：

//do it as well to other classes that need to be added into groommer
public class Car implements Groomable {
    //...
}

• 在对应的 class 中实现 interface 中的方法：

public class Car implements Groomable {
    //...
     public void groom() {
        if (speed == 0) {
            System.out.println("Car grooming!");
        }
    }
}

• 然后将使用类型替换为我们定义的 interface 的名字。这里从 Canine[] 替换为了 Groomable[]：

public class GroomEverything {
    public static void main(String[] args) {
        Groomable[] groomer = {
            new Wolf(17,3),
            new Poodle("richie", 2,"Pantene", "Bodyshop"),
            new Car("Honda", "Civic", 2004)
        };
    
        for (Groomable c : groomer)
            {
                c.groom();
            }     
    }  
}

public abstract class Canine implements Groomable{
    //...
     public abstract void groom();
}

//implements keyword is not needed for subclasses
public class Wolf extends Canine {
    public void groom() {
        System.out.println("wolf groom");
    }
}

Sorting 在 OOP 中有着重要的作用；但 Sorting 是一件具体的事情。以 Wolf 对象为例，我们可以根据其 rank 的值设计一个排序方法：

public wolfSort(Wolf[] wolfArry) {
    //...
    //condition
    return wolf1.getRank() > wolf2.getRank();
}

• 排序方法是通用的
• 具体的排序规则由具体类实现

我们将这个方法命名为 CompereTo()。由于所有的类都是 Object 的子类，因此通用排序方法可以改写为：

public genericSort(Object[] arry) {
    //...
    //condition
    return obj1.compareTo(obj2);
}

• 返回值类型为 int，分为三种情况：
  • 两者相等则返回零
  • 前者大于后者返回正数，反之返回负数
• 元素的访问通过 arr[index] 的方式。与 interface 绑定会确认这些元素内有可以执行的方法。

• 提供了一种 Interface java.lang.Comparable 类型作为 compareTo 的实现条件。
• 提供了 util.Array.sort() 作为对象排序的实现（使用 Timsort）
  • 执行期间先会将调用 compareTo 的对象转化为 Compareable 类型

(Comparable).arr[index].compareTo(arr[anotherIndex]);

Comparable 与 之前自定义 Interface 的使用方法一致，将其至于 implements 关键字后面。如果有多个 Interface，以逗号隔开：

public class Wolf extends Canine implements Groomable, Comparable {
    //...
}

public int compareTo(Object anotherWolf) {
    return -(rank - ((Wolf)anotherWolf).rank);
}

• 返回值是 int
• parameter 是 Object 类型
• 使用 parameter 的时候需要将 Object 类型转化为 Wolf 类型，这样才能访问 rank 变量。
• 注意用括号保证 casting 的部分的优先级。access operator . 的优先级非常高。

上述的解决方案中，由于 casting 是在 runtime 时进行的，因此 anotherWolf 的类型直到被转换的那一刻才会被检验。这个过程使得不正确的输入类型会导致 runtime error。

解决这个问题的方式是将条件判断转移到编译期。Java 提供了 Interface 的 Type Parameter 来解决这个问题。Type Parameter 可以让 compareTo() 在编译期就可以将真正需要的对象类型确定下来。具体写法：

public class Wolf extends Canine implements Comparable<Wolf> {
    /...
}

public int compareTo(Wolf anotherWolf) {
    return -(rank - anotherWolf.rank);
}

实现了 compareTo() 之后，我们就可以利用 Arrays.sort() 对 Wolf 对象进行排序了。使用前需要导入 Array package:

//import
import java.util.Arrays;

//rewrited toString for output:
public String toString() {
    return String.format("Rank: %d", rank);
}

//call in main
public static void main(String[] args) {
    Wolf[] wolfPack = {
        new Wolf(17.1, 2),
        new Wolf(3, 10),
        new Wolf(9.2, 7),
        new Wolf(17.01, 3),
        new Wolf(5, 9)
    };
    Arrays.sort(wolfPack);
    System.out.println("Sorted: " + Arrays.toString(wolfPack));
}

Sorted: [Rank: 10, Rank: 9, Rank: 7, Rank: 3, Rank: 2]

1. 查找最小数，标记 index
2. 与当前子数列第一位交换

//int version
public static void selectionSort(int[] arr)
{
    int minIdx = 0;
    for (int i = 0; i < arr.length-1; ++i)
        for(int j = i+1; j < arr.length; ++j)
        {
            minIdx = i;
            if (arr[j] < arr[minIdx])
            {
                minIdx = j;
            }
        int temp = arr[i];
        arr[i] = arr[minIdx];
        arr[minIdx] = temp;
        }
}

//Object version
public static void selectSort(Comparable[] arr)
{
    int minIdx = 0;
    for (int i = 0; i < arr.length-1; ++i)
        for(int j = i+1; j < arr.length; ++j)
        {
            minIdx = i;
            if (arr[j].compareTo(arr[minIdx]) < 0)
            {
                minIdx = j;
            }
        Comparable temp = arr[i];
        arr[i] = arr[minIdx];
        arr[minIdx] = temp;
        }
}

//call
Comparable[] groomer = {
            new Wolf(17,3),
            new Wolf(17,6),
            new Wolf(17,7),
            new Wolf(17,1),
            new Wolf(17,4),
};
    selectSort(groomer);

• 泛型版本的 sort 需要替换关系运算符为 compareTo()
• 该版本也可以使用 Type prarameter 在编译期阶段检测类型

loop 中的交换：

Comparable temp = arr[i];
arr[i] = arr[minIdx];
arr[minIdx] = temp;

if (minIndex != i) {
    Comparable temp = arr[i];
    arr[i] = arr[minIdx];
    arr[minIdx] = temp;
}

• 使用递归
• base case: 数组长度小于 2
  • 数组长度小于 2 时，数组为空（或是单元素），已经排好序了，因此什么都不做 (return;)
  • 数组长度大于 2 时：
    • divide：
      • 求数组的中间点，以中间点为分界线，将数组分为左右两部分
    • conquer
      • 对左右部分分别进行递归排序
      • 合并排好序的数组
• 排序以及合并的方法：
  • 比较左部分和右部分的第一个元素
  • 选取较小的元素赋值给结果数组的第一位
  • 被选取的部分 index 向前，结果数组 index 向前
  • 一直直到左右任意一个部分读取完毕
  • 如果有任何没有读取完毕的数组，合并到结果数组中

public class Merge {
    
    //[start, end)
    public static int[] copyRange(int[] arr, int start, int end)
    {
        int[] slicedArray = new int[end - start];
        for (int i = start, j = 0;i < end; ++i, ++j) {
            slicedArray[j] = arr[i];
        }
        return slicedArray;
    }
    
    public static void mergeArrays(int[] mergedArray, int[] left, int[] right)
    {
        int lLen = left.length;
        int rLen = right.length;

        int leftIdx = 0;
        int rightIdx = 0;
        int mergedIdx = 0;

        //sorting 
        while (leftIdx != lLen && rightIdx != rLen)
        {
            if (left[leftIdx] < right[rightIdx]) {
                mergedArray[mergedIdx++] = left[leftIdx++];
            }
            else {
                mergedArray[mergedIdx++] = right[rightIdx++];
            }
        }
        // merge if there is any left
        while(leftIdx < lLen) {
            mergedArray[mergedIdx++] = left[leftIdx++];
        }
        while(rightIdx < rLen) {
            mergedArray[mergedIdx++] = right[rightIdx++];
        }
    }

    public static void mergeSort(int arr[]) {
        int currArrayLen = arr.length;
        if (currArrayLen < 2) {
            return;
        }
        else {
            int midIndex = currArrayLen / 2;
        
            int[] left = copyRange(arr, 0, midIndex);
            int[] right = copyRange(arr, midIndex, currArrayLen);

            mergeSort(left);
            mergeSort(right);
            mergeArrays(arr, left, right);
        }     
    }
}

• 数组的类型，从 int 改为 Comparable 类型
• 比较的方法：从关系运算符改为 CompareTo

Source Code: mergecomparable.java

• 将数列分为两部分：左边为有序，右边为无序
• 默认有序部分为最左边的数
• 每次循环将无序部分中最左边的一位加入到有序部分中进行排序
  • 排序的顺序：新元素从右到左的顺序以此比较（因为左边有序，只要新元素小于某个元素就能插到前面了）
• 最坏情况下（倒序）也是所有元素都要比较一遍，因此也是 $n^2$ 复杂度
• 最好情况下（顺序）每次比较一个元素，因此是 $n$ 复杂度

Java 中的实现关键点：

• 比较的条件：有序部分还存在元素，且当前元素大于被比较的元素
• 插入的位置：上述条件不满足时，证明有序部分中当前元素是剩余元素中最大的，但小于被比较元素的数，因此插入的位置就应该在其右一位。
• 移位的模拟：需要保存被比较的元素，这样被比较的元素所占的位置可以拿出来做移位用。

public static void insertionSort(int[] arr) {

    for (int unSortIdx = 1; unSortIdx < arr.length; ++unSortIdx)
    {
       int currVal =  arr[unSortIdx];
       int sortIdx = unSortIdx - 1;
       
       while(sortIdx >= 0 && arr[sortIdx] > currVal)
       {
            arr[sortIdx + 1] = arr[sortIdx];
            sortIdx--;
       }
       arr[sortIdx + 1] = currVal;
    }        
}

• 分析的主要目标是算法运行花费的时间
• 参考的标准是时间与输入规模的关系
• 时间使用运算次数（number of operations）来衡量
• 讨论的是 worst case

使用 System.nanoTime() 来记录算法运行的时间：

long start = System.nanoTime();
selectionSort(input);
long end = System.nanoTime();
System.out.println("Elapsed time in ns:" + (end - start));

• 算法的运算次数不受输入规模的影响
• 关系图像为一条与 $x$ 轴平行直线

• 算法的运算次数的增长与输入规模呈线性比例
• 关系图像为带斜率的直线

public static int linearSearch(Comparable key, Comparable[] elementLst)
    {
        for (int i = 0; i < elementLst.length; ++i) {
            if (elementLst[i].compareTo(key) == 0) {
                return i;
            }
        }
        return -1;
    }

• Selection sort: 无论如何都要把元素都比一遍（$\frac{n^2-n}{2}$），因此无论是什么顺序，其复杂度都是 $n^2$ 级别的。

• Merge sort: $nlog_2(n)$
  • 归并的过程是 $log_2(n)$ 次

• single loop：提供线性的增长
• nested loop(2)：$n^2$

public static int binarySearch(int[] arr, int key)
    {
        int minIdx = 0;
        int maxIdx = arr.length - 1;
        int midIdx;
        
        while (minIdx <= maxIdx)
        {
            midIdx = (minIdx + maxIdx) / 2;
            
            if (arr[midIdx] == key) {
                return midIdx;
            }
            //key in [0:mid)
            else if (arr[midIdx] > key) {
                maxIdx = midIdx - 1;
            }
            else if (arr[midIdx] < key) {
                minIdx = minIdx + 1;
            }
        }
        return - 1;
    }

• 只有 abstract method 的 interface 被称为是 pure abstractions。这样的 interface 意味着设计者希望将 method 的 concept 和 detail 完全分开。
• Java 8 以后支持混合的实现模式：可以在 Interface 中实现 concrete method
• 支持两种方式：default method 和 static method

这是一种允许在 interface 中直接定义 Method 的方式。主要适应的场景是快速为 interface 下的各种类型添加新的共同 Method。比如之前例子中，动物与车都有“洗”的行为；如果希望给这个“洗”加一个付款 pay()，如果不使用 default method，那么只能在 interface 中声明虚函数，再去每个类里单独实现了。 有了 default method 以后，则可以直接在 interface 里写；所有 interface 下的实现类都会自动得到该 Method:

public interface Groomable {
    public void groom();
    //public, by default
    default void pay() {
        System.out.println("All should pay!");
    }
}

重写与一般重写一致：

public void pay() {
        System.out.println("I am the wolf and I don't need to pay!");
    }

如果不要求重写，那么没有必要给每一个 interface 的参与类都添加一个 Method。为此，Interface 中也提供了用于定义 static method 的方法：

public interface Groomable {
    //...
    static String calTip(double price, double percentage) {
        double rawTip = price *(percentage / 100);
        return String.format("%.2f" , rawTip);
    }
}

Groomable.rawTip(9.99, 20);

• Interface 中允许定义常量
• 任何在 interface 中声明的变量，都会被视为 public static final 类型，无论是否带有 Modifier。

public interface Mascot {
    public static final double MAX_CELEBRATION_SEC = 30;
    //equivalent
    double MAX_CELEBRATION_SEC = 30;
}

• 对 Interface 本身的期望是一个存储 concept 的地方，这些常量为概念服务
• Class 中的常量是存放在类中而非对象中，interface 中也应该如此

相比起在 interface 中存放常量，选择在类中存放是更好的选择。因为 class 中同时允许 instance variable 的存在。

Constant Interfaces 指 Interface 中包含的成员均为常量。其应用场景为：程序需要使用很多常量。将这些常量全放在一个地方，可以方便读取。

• Interface 允许继承
• Interface 允许多重继承

• 在 UML 使用 «interface» 表示 interface
• interface 到 interface 之间的关系用实线加空三角表示（extends）
• class 到 interface 的关系用虚线加空三角表示（implements）
• client（比如运行游戏的主程序，不是 Interface，也没有任何继承关系）使用虚线加箭头表示；指向的是该 client 的依赖（dependences）

多态（Polymorphism）允许我们使用一段代码灵活吃处理不同类型的对象。

Canine pixy;
pixy = new Poodle(..);
pixy.bark();

1. Java 会首先查找声明中的类型（declar type）
2. 找到后，再查找实例化的类型（new 后面那个类型，instantiate type）
3. 找到这两者之后，编译器会考虑以下两点：
   1. declar type 的引用能指向具有 instantiate type 的对象吗?
   2. 如果我们想通过该对象访问某些方法，那么这些方法在 declar type 中有没有声明且定义？

如果上述条件都不满足，Java 编译器会认为该 assignment 是不合法的。

Java 会对针对第一个问题进行所谓的 Relationshio test：

• 如果 declar type 是 class
  • 检查 instantiate type 是不是 declar type 本身，或是其 subclass

比如：

//ok, pixy is a Poodle, Poodle is a dog
Dog pixy;
pixy = new Poodle();

//error, pixy is a Dog, a Dog may not be a Poodle
Poodle pixy;
pixy = new Dog(...);

• argument 指向的类型是 object type
• parameter 指向的类型是 instantiate type

比如：

public class Human {
    public void playFetch(Dog myPet) {
        //....
    }
}
Dog richie = new Dog(...);
Poodle pixy = new Poodle(...);

//ok, richie is a Dog
owner.playFetch(richie);
//ok, pixy is a Poodle, Poodle is a Dog
owner.playFetch(pixy);

• 如果 declar type 是 instance
  • 检查 instantiate type 本身或是其任意父类（祖先）有没有实现 interface

第二个需要检查的是 method 的调用：

• 如果 declar type 中包含了该 method，那是没有问题的，比如：

//Canine defines bark()
//Poodle defines enterDogShow()

//declar type
Canine pixy;
Poodle richie = new Poodle(...);
pixy = richie;

//ok, bark() is defined in Canine
pixy.bark();

//error, Canine doesn't define enterDogShow, even if pixy's instantiate type is Poodle
pixy.enterDogShow()；

上述例子中，如果我们希望使用 pixy 直接访问 enterDogShow()，我们需要将其转换为 Poodle 类型：

//ok, in case of using enterDogshow(), we need casting 
// !!!notice the praentheses!!!
((Poodle)pixy).enterDogShow();

Casting 带来了一个问题。来看以下例子：

Canine dg;
dg = new Dog(...);

//is thi legal?
((Poodle)dg).enterDogShow();

在检测 method call 是否合法的同时，JVM 还会同时在运行期检测哪一个版本最适合当前的 call。处理该调用匹配的过程被称为动态绑定（Dynamic Binding）。总的来说：

• 如果 object type 和 declar type 中存在不一样的实现（即 object type 中有重写），那么选择 object type 的版本

//if Canine & Poodle both have a bark() implementation
Canine pixy;  
pixy = new Poodle(...); 

//call Poodle.bark()
pixy.bark();

• 如果 object type 中不存在重写，JVM 会按照继承树逐级往上查询，直到找到对应的实现

//if Canine & Dog both have a bark() implementation, but Poodle dosen't
Canine pixy;  
pixy = new Poodle(...); 

//call Dog.bark()
pixy.bark();