[软件构造]实验回顾：Lab2

实验目标：ADT and OOP

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

第一部分：Poetic Walks

这是MIT的一个实验。

Problem 1: Test Graph <L>

此处在实验刚开始设计的时候测试，因为什么方法都没有编写，所以测试里边的empty()方法即可。当时做这里的时候，我和同学问了好久才明白。

Problem 2: Implement Graph <String>

1.在这里，我们开始接触各种注释：AF（抽象功能），RI（表示不变量），Safety from rep exposure，mutable或者immutable。在编写这些注释的时候，要尽量清晰易懂，方便以后复用。

// Abstraction function:
//   vertices consists of all vertices in the graph; edges consists of all weighted edges in the graph.

// Representation invariant:
//   vertices != null; edges != null

// Safety from rep exposure:
//   use private final to prevent rep exposure

针对RI，编写checkRep方法，使用断言assert，在程序进行操作的时候时刻检查RI的正确性。

    public void checkRep(){
    	assert vertices != null;
    	assert edges != null;
    }

2.在对某些对象进行修改或者删除操作的时候，需要检查这个对象是否有效。如果不检查，可能会发生各种错误。而且当他们是存在List，Set中的时候，如果找不到对象，集合本身不会返回“未找到”的信息，使错误隐藏的更深。

  if (!vertices.contains(source) || !vertices.contains(target)) {
    checkRep();
    return 0;
  }

3.对于toString函数的重写：
自己创建的类，其默认toString返回的是当前对象的地址。通过重写toString方法，使ADT能以容易读懂的文字形式输出自己。

    // toString()
    @Override 
    public String toString() {
    	StringBuilder sb = new StringBuilder();
    	sb.append("Vertices:");
    	for(L vertex : vertices)
    		sb.append("\t" + vertex);
    	sb.append("\nEdges:");
    	for(Edge<L> edge : edges)
    		sb.append("\n" + edge.toString());
    	return sb.toString();
    }

4.设计测试用例的时候，尽量设计的简单而又全面，测试到程序中各方法的各种分支，覆盖绝大多数情况，这样可以尽量观察并定位ADT内部错误，减少复用该ADT的更大规模的程序在调用它的时候发生错误。

Problem 3: Implement generic Graph<L>

这里边没什么难点，把String都换成L就可以了。
但是有一点要注意，empty方法其实是后边Lab4编写工厂方法的一个伏笔（虽然这里empty只有一个选择）。

Problem 4: Poetic walks

这里就是应用刚刚编写的图ADT，进行一个实例设计。思路还是很简单的 ：首先读文件，构造图；然后根据有向图，往句子里插入单词写诗。整个文件的核心，就是寻找被插入单词的mid方法：

    /**To find a two-edge-long path with maximum-weight weight among all 
     * the two-edge-long paths from w1 to w2 in the affinity graph, use 
     * mid to find the midword.
     * 
     * @param str0 the source point's name 
     * @param str1 the target point's name 
     * @return the word to be inserted
     */
    public String mid(String str0 , String str1) {
    	List <String> midWords = new ArrayList<>();
    	List <Integer> weights = new ArrayList<>();
    	
    	Map<String, Integer> targets0 = graph.targets(str0.toLowerCase());
    	for(String key0 : targets0.keySet()) {//find potential midwords
    		if(!(key0.equals(str0.toLowerCase()))) {
    			Map<String, Integer> targets1 = graph.targets(key0);
    			boolean exist = false;
    			for(String key1 : targets1.keySet()) {
    				if (key1.equals(str1.toLowerCase())) {
    					exist = true;
    					break;
    				}
    			}
    			if(exist) {
    					midWords.add(key0);
    					weights.add(targets0.get(key0));
    			}
    		}
    	}
    	if (midWords.size() == 0)
    		return null;
    	else {
    		for(int i = 0; i < weights.size(); i++) {//sort the weights
    			for(int j = i; j < weights.size() ; j++) {
    				if(weights.get(i) < weights.get(j)) {
    					Integer w = weights.get(i);
    					weights.set(i, weights.get(j));
    					weights.set(j, w);
    					String v = midWords.get(i);
    					midWords.set(i, midWords.get(j));
    					midWords.set(j, v);
    				}
    			}
    		}
    	return midWords.get(0);
    	}
    }

第二部分：Re-implement the Social Network in Lab1

这次复用，Person和main直接用就可以，只需修改FriendshipGraph类，使其实现Graph就可以了。而修改的重点，就是下面的计算举例方法。

	public int getDistance(Person a , Person b) {
		checkExist(a);
		checkExist(b);
		if (a == b)
			return 0;
		
		int n = graph.vertices().size(), dist = 0;
		List<Person> personList = new ArrayList<>();
		boolean[] visited = new boolean[n];
		Queue <Person> q = new ArrayBlockingQueue<>((n*n-n)/2);
		for(Person p : graph.vertices())
			personList.add(p);
		int i = personList.indexOf(a);
		
		do {//BFS
			if (!visited[i]) {
				visited[i] = true;
				for(Person p: graph.targets(personList.get(i)).keySet()) {
					if (!visited[personList.indexOf(p)])
						q.add(p);
				}
				dist++;
			}
			if (q.isEmpty())
				break;
			i = personList.indexOf(q.remove());
			if (personList.get(i).equals(b))
				return dist;
		}while(true);
		
		return -1;
	}

第三部分：Playing Chess

设计ADT

设计Board的时候，并不需要给围棋和象棋分别设计两个棋盘：对于围棋和象棋，坐标表示的分别是顶点和格子；而且，只需设计一个19x19的棋盘，然后将象棋对棋盘的访问空间限制到0-7之间（在Action中体现）就可以了。

设计测试文件

测试文件中，为了保证覆盖度，只能插入手动测试（无奈），然而对于命令行程序来说，菜单比较繁琐，所以在测试的时候容易因为忘了进行到哪里而出错，就只能重新来过，有时会有点小小的挫败感。但是测试结果还是非常令人满意的。