抽象数据类型ADT
抽象数据类型与表示独立性： 如何设计良好的抽象数据结构，通过封装来避免客户端获取数据的内部表示（即“表示泄露”），避免潜在的bug——在client和implementer之间建立“防火墙”
ADT特性：表示泄露、抽象函数、表示不变量Representation Invariance 数学形式描述设计
抽象与用户定义的数据类型
数据抽象：不在乎它本来是什么，而是“我们能如何操作它”。
抽象类型：强调“作用于数据上的操作”，程序员和client无需关心数据如何具体存储的，只需设计/使用操作即可。
例如我们对布尔值抽象地定义：
对数据类型与运算分类
数据类型：可变/不可变
运算类型：构造器/生产器/观察器/变值器
- 构造器：通常以构造方法/静态方法实现，静态实现——工厂方法Factory Method
- 变值器：大多返回void，意味改变了对象内部状态
实例
ADT设计
提供一组操作，设计这些操作的spec
准则：
- 设计简洁、一致的操作
- 要足以支持client对数据所做的所有操作需要，且用操作满足client需要的难度要低
- 要么抽象、要么具体，不要混合 --- 要么针对抽象设计，要么针对具体应用的设计（数据类型要么用泛型L，要么针对具体情境设计，不能混合使用）
表示独立性 （重点）
表示独立性： client使用ADT时无需考虑其内部如何实现， ADT内部表示的变化不应影响外部spec和客户端。
除非ADT的操作指明了具体的pre-和post-condition，否则不能改变ADT的内部表示——spec规定了client和implementer之间的契约。
客户端使用了List的方法——一旦内部peopel数据结构不采用List实现，客户端需要做代码修改，考虑内部实现。不满足表示独立性。
ADT测试
- 测试creators, producers, 和 mutators：调用observers来观察这些operations的结果是否满足spec；
- 测试observers：调用creators, producers, 和 mutators等方法产生或改变对象，来看结果是否正确。
- 风险：如果被依赖的其他方法有错误，可能导致被测试方法的测试结果失效。“方法测试之间的相互依赖性”
- 按等价类划分编写测试用例测试
不变量
保持不变量：任何时候均为True 由ADT负责 与客户端行为无关
用来保持程序的“正确性”
总是要假设有程序恶意破坏不变量——防御式编程
mutable->表示泄露：不仅影响不变性，也影响了表示独立性：无法在不影响客户端的情况下改变其内部表示
保护方法：
- final关键字
- private属性
- 返回mutable时的防御式拷贝
- 最好还是使用Immutable类型数据
表示独立性与抽象函数
ADT开发者关注表示空间R， client关注抽象空间A
抽象函数AF：R->A 映射 可多对一 满射（R中部分值不一定合法）
表示不变性RI：RI : R → boolean
- 表示不变性RI：某个具体的“表示”是否是“合法的”
- 也可将RI看作：所有表示值的一个子集，包含了所有合法表示值
- 也可将RI看作：一个条件，描述了什么是“合法”的表示值
AF与RI根据不同的内部表示有不同的设计形式
RI（子集合法标准） R（表示方式）一样 AF可能不同（解释不同）
设计ADT：
- 选择R和A
- RI --- 合法的表示值
- 如何解释合法的表示值 ---映射AF（做出具体的解释：每个rep value如何映射到abstract value）
设计的思路 选择和解释要写入代码
- 注意写checkRep方法，在任何可能改变Rep的方法最后执行（都检查最好），确保RI时刻满足
有益可变性
immutable ADT:A应当不变 R中取值是可变的
通过牺牲immutability的部分原则来换取“效率”和“性能”
文档化
在代码中用注释形式记录AF和RI
- 要精确的记录RI： rep中的所有fields何为有效
- 要精确记录AF：如何解释每一个R值
- 给出理由，证明代码并未对外泄露其内部表示——自证清白（预防表示泄露措施）
- 注意：这个是用户可见的，只能用用户可见的内容撰写（参数，返回值，异常等），涉及到的值不可以是内部表示
- 可以考虑用ADT不变量取代复杂的Precondition，相当于将复杂的precondition封装到了ADT内部。
