ADT抽象数据类型

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

抽象类型：强调作用于数据上的操作，程序员和客户端无需关心数据具体是如何存储的，只需设计/使用操作即可；

可变和不可变数据类型：

可变类型的对象：提供了可改变其内部数据的值的操作；

不可变数据对象：其操作不改变内部值，而是构造新的对象

Creator：构造器，可能实现为构造函数或静态函数(工厂方法)；

Producer：生产器，生成新的东西并呈现给客户，eg.String对象的连接方法concat()；

Observer：观察器，eg.String的size()；

Mutator：变值器，改变对象属性的方法，通常返回void，意味着它改变了对象的某些内部状态，也可能返回其他类型，比如boolean表示是否成功变值；

设计ADT

1. 最好有一些简单的操作，可以以强大的方式组合，而不是大量复杂的操作；每个操作都应该有一个明确定义的目的，并且应该有一个一致的行为，而不是各种特殊情况。
2. 要足以支持client对数据所做的所有操作需要，且用操作满足client需要的难度要低 用get()方法获取该数据类型的属性
3. 要么抽象、要么具体，不要混合 --- 要么针对抽象设计，要么针对具体应用的设计

表示独立性

client使用ADT时无需考虑其内部如何实现，ADT内部表示的变化不应影响外部spec和客户端；除非ADT的操作指明了具体的pre-

和post-condition，否则不能改变ADT的内部表示

抽象类型的使用独立于它的表示（用于实现它的实际数据结构或数据字段），因此表示中的更改对抽象类型本身之外的代码没有影响。–例如，List提供的操作与列表是表示为链表还是数组无关。

除非ADT的操作指明了具体的pre和post-condition，否则不能改变ADT的内部表示。比如一个Graph类型，我们不可以假设他内部是使用二维数组实现或是邻接矩阵实现，我们对Graph对象的使用仅限于其提供的方法。

测试一个ADT

测试creators, producers, 和mutators：调用observers来观察这些

operations的结果是否满足spec；

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

不变量：不变量是程序的一个属性，它对于程序的每个可能的运行时状态都是正确的

保持不变量：一个良好的抽象数据类型的最重要的特性是它保留了它自己的不变量；说ADT保留了它自己的不变量，这就意味着ADT负责确保它自己的不变量保持不变，与客户端的任何行为无关。

如果我们已知字符串是一个不变量，那么在调试使用字符串的代码或者试图为另一个使用字符串的ADT建立不变量时，就可以不考虑字符串；但如果没有这个不变性，只有在客户端承诺不改变它的时候，它才是不可变的，然后，我们必须检查代码中可能使用字符串的所有位置。

这里存在表示泄露：

//如果ADT不幸地让客户端得到了自己内部表示可变对象的引用，那//么客户端就可以不通过ADT的操作，而可以通过非法后门修改ADT  //的内部表示，产生表示泄露。

设置为public，使客户端也能访问，

影响了表示独立性：无法在不影响客户端的情况下改变其内部表示

影响了不变性：使客户端能够对其进行更改

解决方法：private类型和防御式拷贝(确保不会返回对变量的直接应用)

Copy和clone

可变类型通常有一个副本构造函数，它允许您创建一个新实例来复制现有实例的值。可变类型也可以用clone完成这项功能

如果所有rep都是可变类型，则都需要防御式拷贝

RI和AF

R空间：ADT开发者关注的空间，一般情况下ADT的表示比较简单，有些时候需要复杂表示；

A空间：由抽象值构成的空间，client看到和使用的值

AF：R和A之间映射关系的函数，满射，未必单射

RI：

对于一个rep值r，当且仅当r被AF映射时，RI (r)为真

▪ 表示不变性RI：某个具体的“表示”是否是“合法的”

▪ 也可将RI看作：所有表示值的一个子集，包含了所有合法的表示值

▪ 也可将RI看作：一个条件，描述了什么是“合法”的表示值

不同的内部表示，需要设计不同的AF和RI；

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

Eg.同样的R，不同的RI

但也可能，同样的R，同样的RI，有不同的AF

设计ADT：

(1) 选择R和A；

(2) RI --- 合法的表示值，对RI的描述即：合法的值是什么样的；

(3) 如何解释合法的表示值 ---映射AF

checkRep()在所有可能改变rep的地方都要检查。

有益的可变性

对于不可变的ADT来说，它在A空间的抽象值应是不变的，但其内部表示的R空间中的取值是可以变化的

这种mutation只是改变了R值，并未改变A值，对client来说是immutable的 →“AF并非单射”，从一个R值变成了另一个R值；但这并不代表在immutable的类中就可以随意出现mutator

记录AF和RI

要精确的记录RI：rep中的所有fields何为有效

要精确记录AF：如何解释每一个R值

要有安全声明：Safety from rep exposure

ADT的规约里只能使用client可见的内容来撰写，包括参数、返回值、异常等；

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

ADT的内部表示(私有属性)对外部都应严格不可见，故在代码中以注释的形式写出AF和RI而不能在Javadoc文档中，防止被外部看到而破坏表示独立性/信息隐藏；

构造器和生产器在创建对象时要确保不变量为true；

变值器和观察器在执行时必须保持不变性；

在每个方法return之前，用checkRep()检查不变量是否得以保持；

表示泄漏的风险：一旦泄露，ADT内部表示可能会在程序的任何位置发生改变（而不是限制在ADT内部），从而无法确保ADT的不变量是否能够始终保持为true；

由以下三个标准来判断ADT是否满足保持表示不变量：由创造者和生产者建立；由突变者和观察者保存；没有代表性暴露

用ADT不变量取代复杂的Precondition，相当于将复杂的precondition封装到了ADT内部。