Chapter 6: Abstract Data Type (ADT)

本章重点：

6.1 Abstraction and User-Defined Types

数据抽象（Abstraction）：由一组操作所刻画的数据类型。

抽象类型强调“作用于数据上的操作”，程序员和用户无需关心数据如何具体存储的，只需设计/使用操作即可。ADT是由操作定义的，与其内部如何实现无关。

除了编程语言所提供的基本数据类型和对象数据类型，程序员可定义自己的数据类型（用户定义类型）。

6.2 Classifying Types and Operations（类型与操作的分类）

可变和不可变数据类型：可变类型的对象提供了可改变其内部数据的值的操作，而对不变数据类型的操作不改变其内部值，而是构造新的对象。

抽象类型操作的分类：

Creator（构造器）：创建类型的新对象。

通常通过构造函数和静态方法实现。通过静态方法实现的构造器称作工厂方法（factory method)。

Producer（生产器）：在已有对象的基础上创建新对象。例如String类的concat()方法，就是输入两个string然后返回它们连接起来得到的string。

Observer（观察器）：输入抽象类型的对象，返回其他类型的对象。例如List类的size()方法。

Mutator（变值器）：改变对象。例如List类中的add()方法。

变值器通常返回void（此时意味着它改变了对象的某些内部状态），但有时候也返回boolean类型。

操作举例：

6.3. Abstract Data Type Examples

int：

构造器： the numeric literals 0 , 1 , 2 , …

生产器： arithmetic operators + , - , * , /

观察器： comparison operators == , != , < , >

变值器：int是不可变类，没有变值器。

String：

构造器： String constructors

生产器： concat , substring , toUpperCase

观察器： length , charAt

变值器：String是不可变类型，没有变值器。

List：List是可变类，同时也是一个接口。

构造器：ArrayList and LinkedList constructors，Collections.singletonList

生产器：Collections.unmodifiableList

观察器：size , get

变值器：add，remove，addAll，Collections.sort

一些其他例子：

6.4. Designing an Abstract Type

规则：

设计简洁、一致的操作；
要足以支持用户对数据所做的所有操作需要，且用操作满足用户需要的难度要低。

6.5 Representation Independence（表示独立性）

表示独立性：用户使用ADT时无需考虑其内部如何实现，ADT内部表示的变化不应影响外部规约和客户端。除非ADT的操作指明了具体的前置条件和后置条件，否则不能改变ADT的内部表示。

简单地说，调用者不应依赖其内部private字段，而实现者应该在不检查调用者代码的前提下进行代码更改。

一个例子：不同的字符串表示

假如其内部表示为：

则相应实现为：

如果内部表示为（更好）：

则相应实现为：

6.6 Testing an Abstract Data Type

测试creators, producers, and mutators：调用observers来观察这些operations的结果是否满足规约；

测试observers：调用creators, producers, and mutators等方法产生或 改变对象，来看结果是否正确。

这样测试的风险在于如果被依赖的其他方法有错误，可能导致被测试方法的测试结果失效。

划分ADT操作的输入空间：

具体测试实例：

6.7 Invariants（不变性）

ADT的不变性：在程序运行中程序始终保持不变，例如immutability就是一个典型的”不变量“，在任何时候都表现为相同的值。ADT有责任来保持其不变性而非依赖于用户和其他模块。

为什么需要不变性？因为当ADT保持自身不变性时，容易推理错误发生的地方。

避免表示泄露的最好办法就是使用immutable类型。

一个例子：

我们该如何保证Tweet类是不可变的？

当出现这种情况时：

不变性和表示独立性均会受到影响。我们可以将代码修改为：

注：由于timestamp是Date类的而Date是可变的，故timestamp不能避免表示泄露。

在规约中警告用户？只有在复制代价很高的时候，再这么做。

总结：避免表示泄露要注意的几点

（1）将public修改为private final

（2）return时防御式拷贝

（3）return时使用Collections.unmodifiableSet()

6.8 Rep Invariant and Abstraction Function（表示不变性和抽象方法）

R：表示空间，包括实际实现时的值。

A：抽象空间，包括用户看到和使用的值。

ADT开发者关注表示空间R，而用户关注抽象空间A。

从R空间到A空间的映射是满射，但未必是单射，也未必是双射。

抽象函数（AF：R->A）：R和A之间映射关系的函数，即如何去解释R中的每一个值为A中的每一个值。如果R中部分值不合法，这些值在A中无映射值。

表示不变性（RI：R->boolean）：某个具体的“表示”是否是“合法的”。也可以将RI看作所有表示值的一个子集，包含了所有合法的表示值；或是一个描述了什么是“合法”表示值的条件。

一个例子：

什么决定了AF和RI？

选择某种特定的表示方式R，进而指定某个子集是“合法”的（RI），并为该子集中的每个值做出“解释”（AF）—即如何映射到抽象空间中的值。

当我们有相同的R空间时，可能会有不同的RI：

当R空间和RI都相同时也可能会有不同AF

AF和RI如何影响ADT设计：

设计ADT时要选择R空间和A空间，还要决定合法表示值（RI）和如何解释合法表示值（AF）。

一个例子：

断言（assert）：在所有可能改变rep的方法中利用assert检查表示不变性，方法是调用checkRep()有助于尽早发现因表示泄露造成的不变性错误。

注：Observer方法可以不用，但是以防万一建议也检查。

6.9 Beneficent mutation（有益的可变性）

有益的可变性（Beneficent mutation）：抽象值（空间）永远不可改变，但是在保证表示值映射的抽象值不变的前提下，表示值可以改变。

例如，在上一个例子中，我们在计算时不要求分子和分母不含公约数，但是在将结果输出给用户时，我们要求结果中必须不含公约数：

这种可变性（mutation）只是改变了R值，并未改变A值。

注：这种有益可变性并不意味着在immutable类中可以随意出现mutator！

6.10 Documenting the AF, RI, and Safety from Rep Exposure

先改private 然后immutable引用返回无所谓 mutable看sets return

看AF是否合理；给AF和R空间的值判断A空间的值

1.Documenting AF and RI

在代码中用注释形式记录AF和RI（给程序员看）。要精确的记录RI：rep中的所有fields何为有效；要精确记录AF：如何解释每一个R值。

2.Documenting rep exposure safety argument

表示泄漏的安全声明（Safety from rep exposure）：给出代码并未对外泄露其内部表示的证明。

例：

对于ADT的规约总结：

（1）只能使用用户可见的内容来撰写，包括参数、返回值、异常等。如果规约里要提及“值”，只能使用A空间中的“值”。

（2）规约里也不应谈及任何内部表示的细节，以及R空间中的任何值。

（3）ADT的内部表示（私有属性）对外部都应严格不可见。

（4）在代码中以注释的形式写出AF和RI而不能在Javadoc文档中，防止被外部看到而破坏表示独立性/信息隐藏。

3.How to establish invariants

如何设置不变性

在对象的初始状态不变量为true，在对象发生变化时，不变量也要为true。

设置不变性的要点总结为以下三点：

6.11 ADT invariants replace preconditions

用ADT不变量取代复杂的前置条件，相当于将复杂的前置条件封装到了ADT内部，取消了对用户输入的限制，转而由程序员解决。