抽象数据类型的实验训练（ADT）面向对象的设计、规则和测试

编程（OOP）技术实现 ADT。具体来说：

??从问题描述中识别给定的应用问题所需的问题 ADT；

??设计 ADT 规约（pre-condition、post-condition）评估规定的质量；

??根据 ADT 测试用例的规定设计；

??ADT 的泛型化；

??按规定设计 ADT 各种不同的实现；对于每种实现，设计表示

（representation）、表示不变性（rep invariant）、抽象过程（abstraction

function）

??使用 OOP 实现 ADT，判断不变性是否违反，各实现是否存在表

示泄露（rep exposure）；

??测试 ADT 测试覆盖度的实现和评估；

??使用 ADT 为应用问题开发程序；

??在测试代码中，能够写出 testing strategy 并设计测试用例。

简要说明本实验所需环境的配置过程，必要时可给屏幕截图。

特别是要记录配置过程中遇到的问题和困难，以及如何解决。

给你的GitHub Lab2仓库的URL地址（Lab2-学号）。

请仔细比较实验手册，记录您的实验过程，解释您的设计想法和问题解决方案，并辅以示意图或关键源代码（但不要粘贴您所有的源代码！

本实验的主要目的是测试 ADT 的规约设计和 ADT 各种不同的实现，并练习 TDD 测试优先编程的编程练习，以后练习 ADT 的泛型化。

如何从GitHub获取任务代码，在当地创建代码git仓库、使用git本地开发管理。

先检查一下Graph这里写了一些空的方法，需要我们用边和点来表示Graph，实现他提供给我们的Graph接口。从这里开始，实验要求我们规范程序设计：要求注明AF、RI避免发生rep exposure该方法的信息需要设计合理的检查函数checkRep()要求设计合理的结构器和观察器，并重写equals方法、hashCode方法以及toString方法。简要介绍以下相关概念的理解：

**Abstraction function：**抽象函数（AF），它可以被视为我们设计的成员变量对这些变量所表示的抽象概念的映射。换句话说，我们如何使用我们声明的具体变量来表示解决问题时的抽象对象，以及图中的信息：如何表示图中包含的顶点和边缘；

**Representation invariant：**表示不变量（RI），所有值的子集包含所有合法值，也可以看作是对合法信息的描述：什么样的数据（参数）是合法的，什么样的数据（参数）是非法的；

**Safety from rep exposure：**当代码提供给客户时，为了防止关键信息被修改导致程序崩溃或产生bug，需要对关键数据进行保护，最典型的方法就是使用私有类型变量以及不可变类型变量；

**hashCode与equals：**每个具体对象都在java中都自带有hashCode与equals前者用于搜索对象，后者用于比较对象。在实验中，如果需要使用这两种方法，则需要重写。

这部分需要我们使用边来实现Graph结构

1. 首先，我们实现了Edge类

   先给出三个必要的Field，分别代表源点、目标点和权值。

   然后我们设计规则

后续可以据次规约来设计checkRep函数；

接下来编写Edge类的constructor

然后依次实现Edge类的方法：

在重写equals的方法时，也要同时重写hashCode方法

最终我们按照要求来实现打印函数toString

和上一问比较类似，这一问要求我们用点来实现Graph接口，同时我们应该首先实现Vertex类，在根据其实现ConcreteVerticesGraph类。

1. 首先，我们设计Vertex类

   Vertex成员变量应当包含指向它的点的集合和它指向的点的集合，用Map键值对来保存上述信息，点的名字为键值，形成的边的权值作为键值。由于我们需要为每个Vertex变量定义特定的标识来区分不同的变量，因此增加L类型的变量name作为标记。
   
   然后我们设计规约
   
   给出构造性方法
   
   根据规约来设计checkRep方法
   
   然后设计Vertex类中剩余的各个方法：
   完成Vertex类中各个变量的观察器：返回点的名称、源点集、终点集；
   修改原点集函数public int setSources(L source, int weight)：根据Map类中remove()方法的返回值，若输入权值weight为0，直接使用remove()函数移除Map中键名为source的点，若source点存在，返回值为其原键值（int型），否则返回null。同理，根据Map类中put()方法的返回值，若输入权值weight不为0，直接使用put()函数修改Map中键名为source的点对应的键值为weight，若source点存在，返回值为其原键值（int型），否则返回null。定义Integer型变量pre记录两种分支下得到的返回值，若为null则返回0，否则返回对应int型变量。
   修改原点集函数public int setTargets(L target, int weight)：根据Map类中remove()方法的返回值，若输入权值weight为0，直接使用remove()函数移除Map中键名为target的点，若target点存在，返回值为其原键值（int型），否则返回null。同理，根据Map类中put()方法的返回值，若输入权值weight不为0，直接使用put()函数修改Map中键名为target的点对应的键值为weight，若target点存在，返回值为其原键值（int型），否则返回null。定义Integer型变量pre记录两种分支下得到的返回值，若为null则返回0，否则返回对应int型变量。
   重写Edge的equals函数与hashCode函数。定义标志变量name相同的两个点为同一个点，hashCode函数按照定义设计完成；
   最后完成toString函数的重写。根据对称性，打印该点的终点集信息即可。这里为保证统一性保留3.3.3.1中“源点–权值->终点”的格式。

随后编写测试最上述方法逐一进行测试。

1. 然后利用Vertex类实现ConcreteVerticesGraph类：

   首先是成员与规约以及构造性的方法，同样的，构造性的方法只需给出一个空图。

   然后根据规约设计checkRep方法

随后设计剩余的其他方法

public boolean add(L vertex)：

根据函数规约，只需遍历vertices集合，查找有无与点vertex相同的点即可。若存在，则返回false；不存在，则在vertices集合中添加点vertex，然后返回true；

public int set(L source, L target, int weight)：

根据函数规约，该方法主要分三种操作：修改已有的边，移除已有的边，添加新的边。因此，先遍历vertices集合，确定源点和终点是否存在。若源点存在，则在其终点集中进行setTargets操作；若终点存在，则在其源点集进行setSources操作。若某一端点不存在，则创建该点，设置对应的源点/终点集，然后在vertices集合加入新生成的点。返回值与对应setTargets/setSources操作返回值相同（checkRep()函数保证了setTargets/setSources操作返回值是相同的，返回任意一个即可）。

public boolean remove(L vertex)：

根据函数规约，在vertices集合中找到vertex点，若找到，先将vertex从vertices集合中其他点的源点集与终点集中去除，然后在vertices集合中删除vertex并返回true；若未找到，直接返回false。

public Set vertices()

根据函数规约，这里只需要返回由图的顶点构成的集合即可。构建一个新的集合，将vertices集合中所有点的标识加入该集合中即可。

public Map sources(L target)：

根据函数规约，直接返回target点的源点集即可。注意到保证数据信息不泄露，需要返回一个由target点的源点集复制的新集合。

public Map targets(L source)：

根据函数规约，直接返回source点的终点集即可。注意到保证数据信息不泄露，需要返回一个由source点的源点集复制的新集合。

public String toString()：

函数需要将图的所有信息打印出来，即所有的点与边的信息。故先将所有的点的名称打印出来，随后遍历vertices集合，循环调用vertices类的toString方法即可

最后对上述的类设计测试，以此检验上述功能

调用IDEA的插件查看测试的覆盖度

可以看到，我们的代码通过了上述的测试，并且测试的覆盖度接近100%，除了一小部分未达到，几乎覆盖了全部的空间，表明基本实现了预期的功能。

这一部分要求我们将原有的Graph转化为泛型定义，注意同时要修改empty的方法。

我们可以在声明中改为Graph即可。

这一部分要求我们借助刚刚实现的Graph类，来实现一个简单的语句扩充程序。

对程序进行测试，分为以下三种情况：

1. 空文件
2. 单段文字
3. 多段文字

我们后续将根据读入的处理好的文本来依次编写上述三个测试文本来满足测试空间。

此程序应该具备以下几个功能：

1. 在读取.txt文件中的所有的单词，并将所有相邻的点添加到图中，这些边每出现一次会使得权值加1（初始权值设置为0）

2. 读取后检查图是否合法

3. 对目标字符串进行扩充：

   首先要遍历给定文本的左右的单词，对于每一个单词，我们要找出该点所指向的终点集中权值最大的元素，将其添加在原来的两个单词之间。遍历结束后，返回扩充后的字符串。

4. 全部实现后进行单元测试验证上述功能的正确性和健壮性。

   经过设计和测试，代码测试结果如下：
   
   测试的覆盖度较高，测试均被通过，证明上述的程序基本符合了预期的要求。

在这里按照要求添加一段代码，在main函数中添加一个测试样例“a cool example”

在这里改编了一段William Butler Yeats的短诗《Down By the Salley Garden》

随后测试一下：

符合预期的结果。

请按照http://web.mit.edu/6.031/www/sp17/psets/ps2/#before_youre_done的说明，检查你的程序。