第六章抽象数据类型

Abstraction and User-Defined Types

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

Classifying Types and Operations

类型：无论是java内置的还是用户自定义的都可以分为mutable和immutable类型

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

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

ADT操作的四种类型

• Creators t* -> T 可能实现为构造函数或静态函数
• Producers (T+ , t*) -> T
• Observers (T+ , t*) -> t
• Mutators (T+, t*) -> void | t | T

Representation Independence

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

怎样测试一个ADT呢？对于ADT的测试不可避免地回互相影响：

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

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

Invariants

良好的ADT最重要的属性是保持不变量

防止表示泄露的方法：

? 对于不变量使用private final修饰

? 对于可变量使用defensive copy

Rep Invariant and Abstraction Function

存在两个空间：表示空间（实现者看到的）和抽象空间（client看到的）

Rep Invariant：R → boolean 例如R(r)，告诉我们R中的r是否被映射到了A空间中的某个值。可视为定义域

Abstraction Function：R → A 对应表示空间向抽象空间的映射。

从表示空间到抽象空间的映射是满射的，但不一定是单射的

RI和AF是需要写在ADT类步的，如下所示:

public class RatNum{
    private int numerator;
    private int denominator;

    // Rep invariant:
    //   denominator != 0

    // Abstraction function:
    //   AF(numerator, denominator) = numerator/denominator
    
    //有时还需要写safety from exposure（给出理由，证明代码并未对外泄露其内部表示）
    //比如在此处编写safety from exposure如下
    //safety from exposure:
    //   All fields are private, and all types in the rep are immutable
    ...
}

有的时候还可以使用ADT invariants来替代前置条件，例如下面这个例子：

/**
 * @param set1 is a sorted set of characters with no repeats
 * @param set2 is likewise
 * @return characters that appear in one set but not the other,
 *  in sorted order with no repeats
 */
 static String exclusiveOr(String set1, String set2);

变成

/** 
 * @return characters that appear in one set but not the other.
 */
static SortedSet<Character> exclusiveOr(SortedSet<Character> set1, SortedSet<Character> set2);

第六章抽象数据类型