1. 实验目标概述

本次实验训练抽象数据类型（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并据此设计测试用例。

1. 实验环境配置

简要陈述你配置本次实验所需环境的过程，必要时可以给出屏幕截图。

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

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

GitHub Lab2仓库的URL地址为：

https://github.com/ComputerScienceHIT/HIT-Lab2-120L020711.git

1. 实验过程

请仔细对照实验手册，针对两个问题中的每一项任务，在下面各节中记录你的实验过程、阐述你的设计思路和问题求解思路，可辅之以示意图或关键源代码加以说明（但千万不要把你的源代码全部粘贴过来！）。

1. 1. Poetic Walks

本次实验训练抽象数据类型（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 并据此设计测试用例。

1. 1. 1. Get the code and prepare Git repository

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

进入地址，输入git clone命令，将文件克隆到本地仓库。

1. 1. 1. Problem 1: Test Graph <String>

测试（然后实现）带有String顶点标签的图。

在GraphInstanceTest.java中为所有实例方法编写测试策略和测试。

对Graph.empty()静态方法的测试以及相应测试策略在GraphStaicTest.java中。该部分测试已经给出，不做改变。

add方法的测试策略和测试如下。

然后push到自己的仓库，完成Problem 1。

1. 1. 1. Problem 2: Implement Graph <String>
         1. Implement ConcreteEdgesGraph

首先要完成Edge类的spec和rep，同时确保它是immutable的。

然后要在ConcreteEdgesGraphTest.java完成对Edge类的测试。需要对Edge类的四个方法进行测试：String getSource()，String getTarget()，int getWeight()和String toString()。

之后要编写Edge类，同时保证它是immutable的。防止rep泄露的措施在前文阐述过，此处不再赘述。Edge类的各个方法以及它们的spec如下，其中checkRep()实现了对RI的检查。

然后要编写ConcreteEdgesGraph类，该类实现了泛型接口Graph，同时重写了toString方法。该类的spec、AF、RI以及Safety from rep exposure如下。

       构造方法为空，因为图的建立是依靠add方法和set方法的。

该类的checkRep方法能够检查两点间是否有重复边、顶点是否为空，不需要检查边的权值是否为正整数，因为这在Edge类的checkRep方法中被检查。

add方法首先先检查要加入的点是否已经在图中，然后再决定是否加入。

set方法实现边的设置。

remove方法从图中移去顶点以及它的相关边。

      vertices方法返回图中的顶点，为防止表示泄露，此处使用防御性拷贝。

sources方法返回一个点的所有source点。

targets方法返回一个点的所有target点。

toString方法完成了重写。首先先把所有的顶点存储到result内，然后再将所有的边存储到result内。

最后要完成对ConcreteEdgesGraph类的测试。注意到该类中的主要方法的测试已经在Problem 1中写出，这里只需要测试ConcreteEdgesGraph类的toString方法即可。

所有的测试编写完成之后，进行Junit测试，全部通过。最后push到仓库。

1. 1. 1. 1. Implement ConcreteVerticesGraph

首先要完成Vertex类的spec和rep的撰写，Vertex类必须是mutable的。

       然后要在ConcreteVerticesGraphTest.java中完成对Vertex类的各个方法的测试。

对getName方法只需测试返回值是否正确。

对getOutEdges方法的测试要分两种情况：该点有无出边。

setOutEdges方法要根据权值大于或等于0以及终点是否在图中来讨论。

toString方法只需检查返回的字符串是否正确。

       之后要完成Vertex类和ConcreteVerticesGraph类。

       Vertex类有两个成员变量：String name表示名称，Map<String, Integer> outEdges表示出边集。有如下方法：构造方法Vertex(String name)、checkRep()、getName()、getOutEdges()、setOutEdges(String target, int weight)和toString()。

       构造方法是通过顶点名称来构造对象的。

checkRep()方法需要检查图中有无重复点，以及顶点名称是否为null或空串。

       getName()方法返回顶点名称的拷贝。

       getOutEdges()返回该点出边集的拷贝。

setOutEdges()修改该顶点的出边集。weight大于0时实现边权值的修改以及边的添加，weight等于0则实现边的删除。

toString()则返回该点以及它的出边的相关信息，用字符串表示。

       再在ConcreteVerticesGraphTest.java中完成对ConcreteVerticesGraph.toString()的测试。检查返回字符串形式是否正确即可。

然后进行JUnit测试，测试通过，提交至github。

1. 1. 1. Problem 3: Implement generic Graph<L>

将已有的两个 Graph<String>的实现改为Graph<L>的泛型实现。

1. 1. 1. 1. Make the implementations generic

首先修改ConcreteEdgesGraph类和ConcreteVerticesGraph类的声明，将String修改为泛型。

然后要更新接口的两个实现，将ConcreteEdgesGraph、ConcreteVerticesGraph、Edge和Vertex都化为泛型类。详情见源代码。

最后进行测试。ConcreteEdgesGraphTest.java和ConcreteVerticesGraphTest.java都通过测试，结果如下。提交到github。

1. 1. 1. 1. Implement Graph.empty()

首先要选择Graph的两个实现中的一个，使用它来完成Graph.empty()。

之后要在GraphStaticTest.java中添加额外的测试，测试label为除String的其他两种情况时是否正确。需要测试的类型必须是immutable的，所以此处选择Long和Double。对测试函数tesetGraphLong和tesetGraphDouble运行JUnit测试，通过测试。

接下来要测试覆盖率。首先检测之前完成的ConcreteEdgesGraphTest.java，发现覆盖率特别高，达到%94.7。

然后检测之前完成的ConcreteVerticesGraphTest.java的覆盖率，同样特别高，达到%96.6。

最后检测GraphStaticTest.java的覆盖率，仍然很高，达到%94.7。

       提交到github。

1. 1. 1. Problem 4: Poetic walks

这个问题一部分是用给的语料生成图，相邻的单词间用一条有向边连接，另一部分是给定一个输入字符串，通过在图中判断它们之间是否有bridge来对字符串进行扩充。

1. 1. 1. 1. Test GraphPoet

首先要在GraphPoetTest.java完成对GraphPoet的测试，部分测试函数如下，需要根据input的可能情况作出讨论，防止错误的情况。

测试所需要的文件已经调整到文件目录中。

1. 1. 1. 1. Implement GraphPoet

构造函数如下。

AF、RI、safety如下。

需要实现的方法如下。

GraphPoet：先将文件corpus中的所有点读入，考虑到其中存在相同的点，集合Set并不适用，因此将所有点都读入列表。循环遍历列表，每次读入一前一后两个点作为起点和终点，建成一条边，其权值为该边在corpus中出现的次数；

poem：生成poem。

JUnit测试通过，覆盖率非常高。

1. 1. 1. 1. Graph poetry slam

将该方法修改。

输出。

1. 1. 1. Before you’re done

进入本次实验的仓库打开git bash，依次输入：git add .   git commit -m “P1”   git push，完成传送。

1. 1. Re-implement the Social Network in Lab1

这个任务主要是重新实现 Lab1 中的 Social Network，利用在P1中已经写好的 Graph接口来实现，尽量重用已有的函数。

1. 1. 1. FriendshipGraph类

给出你的设计和实现思路/过程/结果。

该类有如下方法。

personExist(Person person)，检查人物是否在关系图中。

existOrThrow(Person person)，检查人物是否出现在关系图中，若没有，抛出KeyException错误。

notExistOrThrow(Person person)，检查姓名是否出现在关系图中，若存在，抛出KeyAlreadyExistsException错误。

addVertex(Person person) ，在关系图中添加一个新人，若存在则抛出KeyAlreadyExistsException。

addEdge(Person from, Person to)，在关系图中添加一个新关系，若人物不存在存在则抛出KeyException。

getDistance(Person from, Person to)，查找两人的社交距离。

1. 1. 1. Person类

给出你的设计和实现思路/过程/结果。

Person类有一个成员变量name，还有三个方法：getName()，equals(Object o)， hashCode()，后两个方法实现了重写。具体代码如下。

1. 1. 1. 客户端main()

利用 Lab1 中已有的 main 客户端即可。

1. 1. 1. 测试用例

测试策略：1.空图的测试；2.仅有顶点的图的测试；3.复杂图的测试。测试全部通过，覆盖率也很高。

1. 1. 1. 提交至Git仓库

进入本次实验的仓库打开git bash，依次输入：git add .   git commit -m “P1”   git push，完成传送。

1. 实验进度记录

请使用表格方式记录你的进度情况，以超过半小时的连续编程时间为一行。

每次结束编程时，请向该表格中增加一行。不要事后胡乱填写。

不要嫌烦，该表格可帮助你汇总你在每个任务上付出的时间和精力，发现自己不擅长的任务，后续有意识的弥补。

日期	时间段	计划任务	实际完成情况
2022-05-23	17:00-18:00	P1 Problem 1	按计划完成
2022-05-23	20:30-22:30	P1 Problem 2 2.1	未按计划完成
2022-05-24	00:30-02:30	P1 Problem 2 2.1	按计划完成
2022-05-24	20:00-22:00	P1 Problem 2 2.2	未按计划完成
2022-05-25	00:30-02:20	P1 Problem 2 2.2	未按计划完成
2022-05-25	20:30-22:00	P1 Problem 2 2.2	按计划完成
2022-05-26	00:30-03:00	P1 Problem 3	未按计划完成
2022-05-26	16:30-18:00	P1 Problem 3	按计划完成
2022-05-29	16:00-23:00	全部	按计划完成

1. 实验过程中遇到的困难与解决途径

遇到的难点	解决途径
对于泛型的掌握不够熟练	阅读书籍，上网搜资料。

1. 实验过程中收获的经验、教训、感想
   1. 实验过程中收获的经验和教训

需要多记一些常用类的常用方法，这样才能在编程的时候有清晰的思路。

1. 1. 针对以下方面的感受
2. 面向ADT的编程和直接面向应用场景编程，你体会到二者有何差异？

面向应用场景的编程泛用性不如面向ADT的编程。

1. 使用泛型和不使用泛型的编程，对你来说有何差异？

使用泛型对我来说较为陌生，但我也体会到了泛型的功能的强大之处，泛用性之高。

1. 在给出ADT的规约后就开始编写测试用例，优势是什么？你是否能够适应这种测试方式？

这样可以保证站在用户的视角上编写测试用例，可以更好地检查程序是否有漏洞。能够适应。

1. P1设计的ADT在多个应用场景下使用，这种复用带来什么好处？

可以减少程序员的工作量，还能使java程序在逻辑上更易于理解。

1. 为ADT撰写specification, invariants, RI, AF，时刻注意ADT是否有rep exposure，这些工作的意义是什么？你是否愿意在以后编程中坚持这么做？

意义是

1. 关于本实验的工作量、难度、deadline。

工作量非常大，难度较高，deadline非常不合理，数次实验deadline都和期末考试安排在同一天，无法兼顾。

1. 《软件构造》课程进展到目前，你对该课程有何体会和建议？

该课程能够让我们学会一门新的编程语言，建议是合理安排实验deadline