软件构造LAB2
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 并据此设计测试用例。
2实验环境配置
在 Eclipse IDE 中安装配置 EclEmma（一个用于统计 JUnit 测试用例的代码覆盖度的 plugin）直接从Eclipse Market下载安装即可。
https://github.com/ComputerScienceHIT/Lab2-1180300721
实验过程
请仔细对照实验手册，针对三个问题中的每一项任务，在下面各节中记录你的实验过程、阐述你的设计思路和问题求解思路，可辅之以示意图或关键源代码加以说明（但千万不要把你的源代码全部粘贴过来！）。
2.1Poetic Walks
分别在两个类ConcreteEdgesGraph，ConcreteVerticesGraph 实现Graph接口。
Graph接口要求实现add（添加新节点），set（添加新边），remove（移除节点），vertices（获得所有的节点集合），sources（target）获得以target为目标节点的边的起始节点，targes(source)获得以source为起始节点的边的目标节点。
Poet：假设存在一条由a到b的有向边，构造有向图，再给定一句子，如果句子中两个相邻单词在有向图中有一个中间单词，则将该单词插入到a与b中间，若存在多个中间单词，则插入权重最大的那个
2.1.1Get the code and prepare Git repository
git init
git remote add origin [email protected]m:ComputerScienceHIT/Lab2-1170301026.git
git pull origin master
git add .
git commit -m “init”
git push origin master
2.1.2Problem 1: Test Graph
测试Graph需将empty改成如下：
Public Graph empty(){
return new ConcreteEdgesGraph();
}
2.1.3Problem 2: Implement Graph
以下各部分，请按照MIT页面上相应部分的要求，逐项列出你的设计和实现思路/过程/结果。
2.1.3.1Implement ConcreteEdgesGraph
private L source 起始节点
private L target 目标节点
private int weight 边权值
getsource() 返回有向边起始节点
gettarget() 返回有向边目标节点
getweight() 返回边权值
/**
-
TODO specification Immutable. This class is internal to the rep of
-
ConcreteEdgesGraph.
-
-
PS2 instructions: the specification and implementation of this class is up to
-
you.
*/
class Edge {// TODO fields
private L source;
private L target;
private int weight;
// TODO constructor
public Edge(L source, L target, int weight) {
this.source = source;
this.target = target;
this.weight = weight;
checkRep();
}// TODO checkRep
public void checkRep() {
assert source != null;
assert target != null;
assert weight >= 0;
}
// TODO methods// TODO toString()
public L getSource() {
return source;
}public L getTarget() {
return target;
}public int getWeight() {
return weight;
}@Override
public String toString() { // 覆盖超类的toString方法
String s = this.getSource() + “->” + this.getTarget() + “:” + this.getWeight();
return s;
}
2.1.3.2Implement ConcreteVerticesGraph
private int findVertex(L str) {
for (int i = 0; i < vertices.size(); i++) {
if (vertices.get(i).getString().equals(str)) {
return i;
}
}
return -1;
}
@Override
public int set(L source, L target, int weight) {
assert weight >= 0;
assert source != target;
Vertex<L> vertexOfSource, vertexOfTarget;
int index;
if (vertices().contains(source)) {
index = findVertex(source);
vertexOfSource = vertices.get(index);
} else { // 如果string对应的点不在list中，创建新的点并且添加进去
vertexOfSource = new Vertex<>(source);
vertices.add(vertexOfSource);
}
if (vertices().contains(target)) {
index = findVertex(target);
vertexOfTarget = vertices.get(index);
} else {
vertexOfTarget = new Vertex<>(target);
vertices.add(vertexOfTarget);
}
final int a1 = vertexOfSource.setTarget(target, weight);
final int a2 = vertexOfTarget.setSource(source, weight);
assert a1 == a2;
checkRep();
return a1; // 返回pre_weight
}
@Override
public boolean remove(L vertex) {
assert vertex != null;
if (!vertices().contains(vertex)) {
return false;
}
for(Vertex<L> one :vertices) { //删除点的所有sources和targets
if(one.getOneSources().containsKey(vertex)) {
one.getOneSources().remove(vertex);
}
if(one.getOneTargets().containsKey(vertex)) {
one.getOneTargets().remove(vertex);
}
}
final int index = findVertex(vertex);
vertices.remove(index);
return true;
}
@Override
public Set<L> vertices() {
Set<L> s = new HashSet<L>();
for (Vertex<L> one : vertices) {
s.add(one.getString());
}
return s;
}
@Override
public Map<L, Integer> sources(L target) {
assert target != null;
int index = findVertex(target);
if (index < 0) {
return Collections.emptyMap();
} else {
return vertices.get(index).getOneSources();
}
}
@Override
public Map<L, Integer> targets(L source) {
assert source != null;
int index = findVertex(source);
if (index < 0) {
return Collections.emptyMap();
} else {
return vertices.get(index).getOneTargets();
}
}
// TODO toString()
@Override
public String toString() {
if (vertices.isEmpty()) {
return "This is An Empty Graph";
}
String stringGraph = "";
for (int i = 0; i < vertices.size(); i++) {
if(vertices.get(i).toString() != "") {
stringGraph = stringGraph.concat(vertices.get(i).toString()+"\n");
}
}
return stringGraph;
}
}
2.1.4Problem 3: Implement generic Graph
class Vertex {
// TODO fields
private L str;
private Map<L, Integer> oneSources = new HashMap<L, Integer>();
private Map<L, Integer> oneTargets = new HashMap<L, Integer>();
// Abstraction function:
// 顶点类刻画图的关键要素
// 使用HashMap存取映射关系
// key为该点的source或target , value为该点的weight
//
// Representation invariant:
// 每个顶点的source或target不能是自身
// HashMap中的values必须不小于0
//
// Safety from rep exposure:
// 所有fields是private final
// String是imutable类型
// 防御性编程
// TODO constructor
// TODO checkRep
// TODO methods
// TODO toString()
/*构造函数*/
public Vertex(L str) {
this.str = str;
}
/* 检查不变量，保证该点不会是自己的source或者target，weight不小于0*/
public void checkRep() {
assert !oneSources.keySet().contains(this.str);
assert !oneTargets.keySet().contains(this.str);
for(Integer v1 : oneSources.values()) {
assert v1 >=0;
}
for(Integer v2 : oneSources.values()) {
assert v2 >=0;
}
}
public L getString() {
return this.str;
}
public Map<L, Integer> getOneSources() {
return this.oneSources;
}
public Map<L, Integer> getOneTargets() {
return this.oneTargets;
}
/**
* 设置到该点的source，处理同ConcreteVerticesGraph中set方法
* weight = 0 , source存在 ：移除
* weight > 0 , source存在 ：更新
* weight > 0 , source不存在 ：添加
*
* @param source ,weight of an edge
* @return pre_weight of pre_edge
*/
public int setSource(L source, int weight) {
assert source != null;
assert source != this.str; // 不重合
assert weight >= 0;
int pre_weight = 0;
if (weight == 0 && this.oneSources.keySet().contains(source)) { // remove
pre_weight = oneSources.remove(source);
}
if (weight > 0 && this.oneSources.keySet().contains(source)) { // update
pre_weight = oneSources.put(source, weight);
}
if (weight > 0 && !this.oneSources.keySet().contains(source)) { // add
oneSources.put(source, weight);
pre_weight = 0;
}
checkRep();
return pre_weight;
}
/**
* 设置到该点的target，处理同ConcreteVerticesGraph中set方法
* weight = 0 , target存在 ：移除
* weight > 0 , target存在 ：更新
* weight > 0 , target不存在 ：添加
*
* @param target ,weight of an edge
* @return pre_weight of pre_edge
*/
public int setTarget(L target, int weight) {
assert target != null;
assert target != this.str; // 不重合
assert weight >= 0;
int pre_weight = 0;
if (weight == 0 && this.oneTargets.keySet().contains(target)) { // remove
pre_weight = oneTargets.remove(target);
}
if (weight > 0 && this.oneTargets.keySet().contains(target)) { // update
pre_weight = oneTargets.put(target, weight);
}
if (weight > 0 && !this.oneTargets.keySet().contains(target)) { // add
oneTargets.put(target, weight);
pre_weight = 0;
}
checkRep();
return pre_weight;
}
@Override
public String toString() {
String str = "";
for (L s : this.oneTargets.keySet()) {
str = str.concat(this.getString() + "->" + s + ":" + this.oneTargets.get(s));
}
return str;
}
}
2.1.4.1Make the implementations generic
将类及接口声明改为：
public class ConcreteVerticeGraph implements Graph{
private final List<Vertex> vertices =new ArrayList<>();
public class ConcreteEdgesGraph implements Graph {
private final Set vertices =new HashSet<>();
private final List<Edge> edges =new ArrayList<>();
2.1.4.2Implement Graph.empty()
使Graph.empty()能返回一个新的空实例。代码如下：
public static Graph empty() {
return new ConcreteEdgesGraph();
}
2.1.5Problem 4: Poetic walks
2.1.4.3Test GraphPoet
在基于预设的测试用例基础上，增加等价类划分的多种情况。
等价类划分：两个单词之间不存在连接词，两个单词之间只有一个连接词，两个单词之间有多个连接词。
此外还要注意句末的句号，测试当一个句子最后一个词是“桥”的一端。
2.1.4.4Impleme GraphPoet
1.表示不变量和检查不变量,该应用中的不变量是所有的点都不为空
2.用文件输入单词，String.split()分割为数组，通过String.toLowerCase()小写化。接下来构建图，相邻的单词加边。首先要在加边前通过Graph.add()加点，加边时要判断是否存在：由于Graph.set()能返回之前加的边的值，以此来判断是否存在，存在则在之前的值加一（之前的边的值保存为lastEdgeWeight）。
3.Poem(String input)当相邻两个单词任意一个不在之前创建的图里，则将后者单词加入即可（再加个空格）当存在时，由于Bridge长度只能为2，所以：分别求两个单词的sources和targets，将该Map转换为Set求交集；若交集为空，则无桥，若交集不空，则在交集中找最短的桥（可以在Map的value中查询weight）。
2.1.4.5Graph poetry slam
样例“This is a test of the Mugar Omni Theater sound system.”进行测试，测试成功
修改样例为“This is a the Mugar system Omni Theater sound system test of the.”，测试成功。该样例用于测试极端情况
2.1.5Before you’re done
请按照http://web.mit.edu/6.031/www/sp17/psets/ps2/#before_youre_done的说明，检查你的程序。
如何通过Git提交当前版本到GitHub上你的Lab2仓库。
在这里给出你的项目的目录结构树状示意图。
2.2Re-implement the Social Network in Lab1
这部分任务就是用我们在2.1中写的ADT，把第一次实验中的FriendshipGraph重新实现一遍，图中的节点仍然是Person类型，所以泛型L一律为Person. 而对于已经写好的FriendshipGraph中的方法，要用2.1中的Graph ADT中的方法来实现它们。
2.2.1FriendshipGraph类
public class FriendshipGraph extends ConcreteEdgesGraph{
public void addVertex(Person p) {
if (this.vertices().contains§) { //防止点重复
System.out.println(“This name is existed!”);
}
else {
this.add§;
}
}
public void addEdge(Person p1, Person p2) {
if(!this.targets(p1).containsKey(p2)) { //防止边重复
this.set(p1, p2, 1);
}
}
public int getDistance(Person p1, Person p2) {
Person now = p1 ;
int distance = 0;
Queue<Person> queue = new LinkedList<Person>();
ArrayList<Person> visited = new ArrayList<Person>();
if(p1 == p2) {
return distance;
}
queue.add(now);
visited.add(now);
while (!queue.isEmpty()) {
now = queue.poll(); //取出队首
distance ++;
for(Person friend : this.targets(now).keySet()){
if( friend == p2) { //找到了即返回当前的距离
return distance;
}
if(!visited.contains(friend)) {
queue.add(friend);
visited.add(friend);
}
}
}
return -1; //找不到说明P1和P2没关系
}
public static void main(String[] args) throws Exception {
FriendshipGraph graph = new FriendshipGraph();
Person rachel = new Person("Rachel");
Person ross = new Person("Ross");
Person ben = new Person("Ben");
Person kramer = new Person("Kramer");
ArrayList<Person> list = new ArrayList<Person>();
list.add(rachel);
list.add(ross);
list.add(ben);
list.add(kramer);
for(int i=0; i <list.size();i++) {
for(int j=i+1 ; j < list.size();j++) {
if(list.get(i).nameSameWith(list.get(j).getName())) {
System.out.println("Wrong name:"+list.get(i).getName());
throw new Exception("The name is repeated!");
}
}
}
graph.addVertex(rachel);
graph.addVertex(ross);
graph.addVertex(ben);
graph.addVertex(kramer);
graph.addEdge(rachel, ross);
graph.addEdge(ross, rachel);
graph.addEdge(ross, ben);
graph.addEdge(ben, ross);
System.out.println(graph.getDistance(rachel, ross));
//should print 1
System.out.println(graph.getDistance(rachel, ben));
//should print 2
System.out.println(graph.getDistance(rachel, rachel));
//should print 0
System.out.println(graph.getDistance(rachel, kramer));
//should print -1
}
}
2.2.2Person类
public class Person {
private String name;
public Person (String name) {
this.name = name;
}
public String getName() {
return this.name;
}
public boolean nameSameWith(String name) { //确定姓名是否重复
if(this.name.equals(name)) {
return true;
}
else
return false;
}
2.2.3客户端main()
public class FriendshipGraphTest {
private static final FriendshipGraph graph = new FriendshipGraph();
private static final Person rachel = new Person(“Rachel”);
private static final Person ross = new Person(“Ross”);
private static final Person ben = new Person(“Ben”);
private static final Person kramer = new Person(“Kramer”);
private static final Person jack = new Person(“Jack”);
private static final Person paul = new Person(“Paul”);
private static final Person trump = new Person(“Trump”);
/**
* Tests that assertions are enabled.
*/
@Test(expected = AssertionError.class)
public void testAssertionsEnabled() {
assert false;
}
/**
* Tests addVertex.
*/
@Test
public void testaddVertex() {
graph.addVertex(jack);
graph.addVertex(paul);
graph.addVertex(trump);
assertTrue("expected inclusion relationship", graph.vertices().contains(jack));
assertTrue("expected inclusion relationship", graph.vertices().contains(paul));
assertTrue("expected inclusion relationship", graph.vertices().contains(trump));
}
/**
* Tests addEdge.
*/
@Test
public void testaddEdge() {
graph.addEdge(rachel, ross);
graph.addEdge(ross, rachel);
graph.addEdge(ross, ben);
graph.addEdge(ben, ross);
assertTrue("expected connection", graph.targets(rachel).containsKey(ross));
assertTrue("expected connection", graph.targets(ross).containsKey(rachel));
assertTrue("expected connection", graph.targets(ross).containsKey(ben));
assertTrue("expected connection", graph.targets(ben).containsKey(ross));
assertFalse("expected unconnection", graph.targets(rachel).containsKey(kramer));
}
/**
* Tests getDistance.
*/
@Test
public void getDistanceTest() {
graph.addVertex(rachel);
graph.addVertex(ross);
graph.addVertex(ben);
graph.addVertex(kramer);
graph.addEdge(rachel, ross);
graph.addEdge(ross, rachel);
graph.addEdge(ross, ben);
graph.addEdge(ben, ross);
assertEquals(1, graph.getDistance(rachel, ross));
assertEquals(2, graph.getDistance(rachel, ben));
assertEquals(0, graph.getDistance(rachel, rachel));
assertEquals(-1, graph.getDistance(rachel, kramer));
}
@Test
public void testPerson() {
final Person rachel2 = new Person("Rachel");
assertEquals("Expected proper name","Rachel",rachel.getName());
assertTrue("Expected the same name",rachel.nameSameWith(rachel2.getName()));
assertFalse("Expected not the same name",rachel.nameSameWith(ross.getName()));
}
}
2.2.4测试用例
根据题目中的社交网络图:
分别测试：
Rachel和Ross距离是1，Rachel和Ben距离是2
Rachel和Rachel距离是0
Rachel和Kramer距离是-1
2.2.5提交至Git仓库
2.3Playing Chess
2.3.1ADT设计/实现方案
1，Position类
位置信息
属性：int横坐标x，纵坐标y；
构造器以很纵坐标为参数，包含横纵坐标
主要方法：
public boolean equal(Position p2)方法断给定位置是否与参数位置相同
public int getX() 方法进行防御性拷贝，返回该位置x坐标
public int getY()方法进行防御性拷贝，返回该位置y坐标
2，Piece类
棋子类
属性：position p棋子的位置、string namestring 棋子名称、player ownerplayer 所属玩家
构造器参数：名称 位置 所属玩家
主要方法：
public Position getPosition() 进行防御型拷贝，返回棋子位置
public void setPosition(Position pos) 设置棋子位置
3，Player 类
玩家类
属性：String nameString 玩家姓名，private int tag;玩家标号，private Set playerPieces 玩家所拥有的棋子集合，
主要方法：
public Piece getPiece(Position position) 返回给定位置上的棋子
public int pieceCounter() 返回玩家拥有的棋子数
……
4,Board类
棋盘类
属性：int nx，ny 棋盘大小，String gametypeString 游戏种类，int[][] occupied=new int[nx][ny] 棋盘被占用情况。
主要方法：
public void init()：根据游戏种类初始化棋盘，围棋初始为空，象棋初始在特定位置白方棋子
public boolean setBoard(int x,int y,int statue)：设置棋盘某一位置被占用的状态
public int getCondition(Position position)：查询棋盘被占用情况
public boolean isLegle(Position position)：判断位置是否合法
5，Action类
活动类
属性：无
主要方法：
public static boolean putPiece：在特定位置下子
public static boolean removePiece：提子
public static Player winner：获得胜利玩家
public static boolean movePiece：移动棋子操作
public static boolean eatPiece：吃子操作
6，Game类
属性：
String gameString：游戏类别；
Player player1,player2：玩家一号二号；
构造器：
游戏名称，玩家一号，玩家二号
主要方法：
public void initgame()：初始化游戏（主要是针对象棋初始化棋子）
2.3.2主程序MyChessAndGoGame设计/实现方案
设置计数器在一定的操作时加一模2使得两个玩家轮流操作。
按照要求选择完游戏类型输入玩家名称后，开始游戏。
1，放子操作针对围棋，检查输入合法性，将新生成坐标棋子添加到玩家的棋子集合中，并改变棋盘状态即可
2,移动棋子，检查输入合法性，检查现在位置棋子状态和目标位置状态，目标位置为空且现位置为本人棋子，改写棋子状态，棋盘状态，操作完成。
3，提子，检查输入合法性，合法则从检查棋盘状态，从玩家的棋子集合中删除该棋子，改写棋盘状态
4，吃子，检查输入合法性，检查现在位置棋子状态和目标位置状态，目标位置为对方棋子且现位置为本人棋子，改写棋子状态，从对方棋子集合中删除该棋子改写棋盘状态，操作完成
5，查询某位置占用情况，检查输入合法性，根据输入位置直接检查棋盘状态，根据棋盘状态返回值判断该位置被哪个棋手占用
6，获得玩家棋子数，调用玩家中的piececonter方法，直接得到棋子个数，输出
7，跳过，改写计数器，写一个玩家操作
2.3.3ADT和主程序的测试方案
模拟玩家进行操作，检查个数函数调用的返回值。采用assert断言。
其中chessgame经过实际操作验证为正确，不再进行测试。
,1，public void positionTest()：对其中的添加返回等操作数值模拟
,2，public void playerTest()：生成一个玩家，在玩家内对getTag()，getname()输入具体值进行测试，对.addPieces，pieceCounter，getPiece，remove返回值真假进行测试
3，public void pieceTest()：生成piece，对其中的getposition，setposition模拟数值，对返回真假进行验证
4，public void boardTest()：生成board，对其中每一条函数进行测试
5，public void gameTest()，对是否能正常生成初始化进行测试
6，public void actionTest()：生成一个完整的游戏，对每一步操作的结果进行真假测试