抽象数据类型ADT
- ADT操作的四种类型
-
- Creator 构造器
- Producer 生产器
- Observer 观察器
- Mutator 变值器
- 测试四种类型
- ADT特性
-
- 表示独立性 Representation Independence
- 不变量 Invariants
- AF和RI
-
- 两个空间
- 抽象函数AF
- 表示不变量RI
- 总结
抽象类型：强调“作用于数据上的操作”，程序员和client无需关心数据如何具体存储的，只需设计/使用操作即可。
可变类型的对象：提供了可改变其内部数据的值的操作
不变数据类型： 其操作不改变内部值，而是构造新的对象
ADT操作的四种类型
Creator 构造器
1.构造器创建该类型的新对象。
2.构造器可以接受一个对象作为参数，但不能接受正在构造的类型的对象。
3.可能实现为构造函数或静态函数
Producer 生产器
生产器从该类型的旧对象创建新对象
例如，String的concat()方法是一个生成器:它接受两个字符串并生成一个表示它们的连接的新字符串。
Observer 观察器
观察器接受抽象类型的对象并返回不同类型的对象。
例如，List的size()方法返回一个int。
Mutator 变值器
1.变值器是改变对象属性的方法
例如，List的add()方法通过在列表的末尾添加一个元素来改变列表。
2.变值器通常返回void， 如果返回值为void，则必然意味着它改变了对象的某些内部状态；变值器也可能返回非空类型
测试四种类型
1.测试creators, producers, and mutators：调用observers来观察这些operations的结果是否满足spec；
2.测试observers：调用creators, producers, and mutators等方法产生或
改变对象，来看结果是否正确。
ADT特性
表示独立性 Representation Independence
client使用ADT 时无需考虑其内部如何实现，ADT内部表示的变化不应影响外部spec和客户端。
例如，List提供的操作与列表是作为链表还是以数组表示无关。
违反表示独立性的例子：函数直接调用内部rep的方法进行实现，也就是只有知道内部实现才能进行如下调用，所以破坏了独立性
下图中能看出右边修改后的例子调用getMembers()函数，调用的方法是返回值List的get方法，而不是内部实现的set的方法。换句话说，外部实现只需要关注外部已知的内容，而不需要关注内部的实现，保持了很好的独立性
不变量 Invariants
由ADT来负责其不变量，与client端的任何行为无关
为什么需要表示不变量？
举例来说
这是一个不可变的ADT，但由于字段都定义为public，既可以被外部访问，所以客户端可以直接对字段进行操作，对安全性有威胁。
这被称为表示泄露representation exposure：这意味着类之外的代码可以直接修改字段。不仅影响不变性，也影响了表示独立性：无法在不影响客户端的情况下改变其内部表示
首先进行第一步修改，将字段修饰为private final
private和public关键字指示哪些字段和方法只能在类内部访问，哪些字段和方法可以从类外部访问。
final关键字还有助于保证该不可变类型的字段在对象构造后不会被重新赋值。
但是还是存在一些问题，retweetLater应该返回另一条信息，但却是一个小时之后才返回，所以Tweet的不变性被破坏了，原因是该方法泄露了对可变对象的引用。
解决方法：进行防御式拷贝
另外一个例子
这个代码会导致date都为23
因为Date()是可变类型，在每次调用时，Tweet都指向相同的Date()对象
解决方法：防御式拷贝
注意：通常，应该仔细检查所有ADT操作的参数类型和返回类型。如果任何类型是可变的，请确保不会返回对其表示的直接引用。因为这样做会造成表示泄露。
AF和RI
表示不变量Rep Invariant和抽象函数 Abstraction Function
两个空间
表示值(代表值)的空间由实际实现实体的值组成。
抽象值构成的空间：client看到和使用的值。
ADT开发者关注表示空间R，client关注抽象空间A
抽象函数AF
抽象函数：R和A之间映射关系的函数，即如何去解释R中的每一个值为A中的每一个值。关系：AF: R->A
R中的部分值并非合法的，在A中无映射值
1.每个抽象值都被一些代表值映射到（满射）
2.一些抽象值被多个代表值映射到（未必单射）
3.并不是所有的rep值都被映射（未必双射）
表示不变量RI
RI: R -> boolean
表示不变性RI ：某个具体的“表示”是否是“合法的”
也可将RI 看作：所有表示值的一个子集，包含了所有合法的表示值
也可将RI 看作：一个条件，描述了什么是“合法”的表示值
下图是AF和RI的书写
选择某种特定的表示方式R，进而指定某个子集是“合法”的(RI)，并为该子集中的每个值做出“解释”(AF)——即如何映射到抽象空间中的值。
总结
设计ADT：
(1) 选择R和A；
(2) RI — 合法的表示值；
(3) 如何解释合法的表示值 —映射AF
做出具体的解释：每个rep value如何映射到abstract value