ADT and OOP

ADT and OOP

抽象数据类型（ADT）
ADT 的特性：表示泄漏、抽象函数 AF 、表示不变量 RI

基于数学的形式对 ADT 的这些核心特征进行描述并应用于设计中

ADT是由操作定义的，与其内部实现无关

ADT四种操作类型
构造器（Creator）：创建一个该类型的新对象（可能实现为构造函数或静态函数）
生产器（Producer）：从一个类型的旧对象创建一个新对象（如String中concat方法）
观察器（Observer）：返回一个不同类型的对象（如List中的size方法）
变值器（Mutator）：改变对象属性的方法（如List中的add方法）

如果一个构造器是用静态方法来实现的，通常称为工厂方法 (factory method)：如Java中String类的String.valueOf(Object obj)方法

Mutators通常返回void，但也可以返回非空类型，如Set.add()返回的类型为boolean

immutable类型的ADT无变值器（Mutator）

判断是哪种操作类型，首先需要确定是mutable还是immutable

注：Collections.unmodifiableList() 是 producer； 如果一个方法既改变了对象属性，也返回了不同类型的对象，它是变值器Mutator

表示独立性（Representation Independence）
表示独立性：client使用ADT时无需考虑其内部如何实现，ADT内部表示的变化不应该影响外部spec和客户端。

上述实例就违反了表示独立性，因为public限定了这是一个instance variable，但是后面的final又限定了客户端不能够实际改变这个类的immutability属性

*不变性（Invariants）
由ADT来负责其不变量，与client端的任何行为无关

表示泄露出现情况：

public 类型的数据 -> private final
mutable 类型共享引用
不应该包含mutate方法
当复制代价很高时，可在规约中强加条件（但是不推荐！）

*Rep Invariant and Abstraction Function(RI and AF)
R : 表示空间 A：抽象空间（ADT开发者关注表示空间R，client关注抽象空间A）

R -> A 的映射：1. 满射：所有抽象值都要有一个rep value 2. 未必单射：一个抽象值可能有多个表示 3. 未必双射：不是所有的表示值都有对应的抽象值

抽象函数（AF）：R和A之间映射关系的函数

表示不变性 RI：某个具体的“表示”是否是“合法的”（R -> boolean）

在ADT的规约里若出现"值"，也只能是A空间的"值"

有益的可变性（Beneficent mutation）
(该部分大概率会出选择)

即immutable的属性是可变的，但是要保证用户角度是一样的

例如：[1, 2] 和 [2, 4]在A空间可均表示1/2

书写AF和RI

可用ADT的不变量来代替前置条件（相当于将复杂的precondition封装到了ADT内部）

面向对象的编程（OOP）
静态/实例方法
在类中使用static修饰的静态方法会随着类的定义而被分配和装载入内存中；而非静态方法属于对象的具体实例，只有在类的对象创建时在对象的内存中才有这个方法的代码段

编译器只为整个类创建了一个静态变量的副本，也就是只分配一个内存空间，虽然可能有多个实例，但这些实例共享该内存

接口（Interface）
接口之间可以继承与扩展，一个类可以实现多个接口，一个接口可以有多种实现类

接口：确定ADT规约； 类：实现ADT

Java的接口中不能含有constructors，但是从Java 8开始接口中可以含有static工厂方法，可用其替代constructors

default
通过default方法，可以在接口中统一实现某些功能，无需在各个类中重复实现它。好处是以增量式为接口增加额外的功能而不破坏已经实现的类

重写（Overriding）
严格继承：子类只能添加新方法，无法重写超类中的方法

如果想要一个java中方法不能被重写，必须要加上前缀final

父类型中的被重写函数体不为空：意味着对其大多数子类型来说，该方法是可以被直接复用的。对某些子类型来说，有特殊性，故重写父类型中的函数，实现自己的特殊要求
如果父类型中的某个函数实现体为空，意味着其所有子类型都需要这个功能，但各有差异，没有共性，在每个子类中均需要重写
重写时，可以利用super()来复用父类型中函数的功能

抽象类（Abstract Class）
抽象方法：只有声明没有具体实现的方法。用关键词abstract来定义

抽象类：如果一个类含有至少一个抽象方法，则被称为抽象类

接口：一个只含有抽象方法的抽象类

如果某些操作是子类型都共有，但彼此有差别，可以在父类型中设计抽象方法，在各子类型中重写

接口和抽象类都不能实例化！

多态、子类型、重载（Polymorphism, subtyping and overloading）

多态的三种类型
特殊多态（Ad hoc polymorphism）：重载
参数化多态（Parametric polymorphism）：泛型
子类型多态、包含多态（Subtyping）：继承
特殊多态和重载（Overloading）
重载：多个方法具有同样的名字，但有不同的参数列表或返回值类型

重载是一种静态多态，根据参数列表进行"最佳匹配"，进行静态类型检查

重载的解析在编译阶段，与之相反，重写的方法是在运行阶段进行动态类型检查

参数列表必须不同
相同/不同的返回值类型
相同/不同的public/private/protected
可以声明新的异常
Overloading和Overriding的对比

参数多态和泛型（Generic）
泛型擦除：运行时泛型类型消除（如：List<String>运行时是不知道String的），所以，不能使用泛型数组（如： Pair < String >[] foo = new Pair < String >[42]; 是错误的！不能被编译！）

如下是一个错误的实例：

List<Object> a; List<String> b; a = b;

通配符（Wildcards），只在使用泛型的时候出现，不能在定义中出现。 如：List< ? extends Animal >

？extends T 和 ？super T 分别表示T和它的所有子/父类

子类型多态、继承
重写时，子类的规约要强于父类的规约（更弱的前置条件，更强的后置条件）
子类的可见性要强于父类（即父类如果是public，子类不能为private）
子类不能比父类抛出更多的异常
（详情见LSP原则）

注：Java无法检测1，但是可以检测出2、3

子类型多态：不同类型的对象可以统一的处理而无需区分。

instanceof
instanceof()判断对象运行时的类型

注：其父类也会判为true，如 a instanceof Object 始终为true

getclass()获取当前类型

List<Object>不是List<String>的父类
List<String>是ArrayList<String>的父类
List<?> 是 List<String>的父类
注：重写equal()方法时，需要注意参数类型，必须也是Object类型