[ソフトウェア構造]実験回顧:Lab 2


実験回顧:Lab 2

  • 実験目標:ADT and OOP
  • 第1部:Poetic Walks
  • Problem 1: Test Graph
  • Problem 2: Implement Graph
  • Problem 3: Implement generic Graph
  • Problem 4: Poetic walks
  • 第2部:Re-implement the Social Network in Lab 1
  • 第3部:Playing Chess
  • 設計ADT
  • 設計試験ファイル
  • 実験目標:ADT and OOP


    今回の実験では,抽象データ型(ADT)の設計,規約テストを訓練し,オブジェクト向けプログラミング(OOP)技術を用いてADTを実現した.具体的には、⚫ 所与の応用問題に対して、必要なADTを記述から識別する.⚫ ADT規約(pre-condition、post-condition)を設計し、規約の品質を評価する.⚫ ADTの規約に基づいて試験例を設計する.の規約設計試験例;⚫ ADTの汎用化⚫ 規定に基づいてADTを設計する多種の異なる実現;各実装について、その表現(representation)、不変性(rep invariant)、抽象プロセス(abstraction function)を設計する⚫ OOPを用いてADTを実現し、不変性が違反しているか、各実現に表示漏れがあるかを判定する.⚫ ADTの実装をテストし、テストカバー度を評価する.の実装とテストカバー度の評価;⚫ ADTとその実現を用いて、応用問題のためにプログラムを開発する.その実現は、応用問題のためにプログラムを開発する.⚫ テストコードではtesting strategyを書き出し、これに基づいてテスト例を設計することができる.

    第一部:Poetic Walks


    これはMITの実験です.

    Problem 1: Test Graph


    ここでは実験が始まったばかりの頃にテストしますが、どんな方法も書かれていないので、中のempty()の方法をテストすればいいです.当時ここをやっていたとき、私は同級生に長い間聞いてやっと分かった.

    Problem 2: Implement Graph


    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.一部のオブジェクトを修正または削除する場合は、そのオブジェクトが有効かどうかを確認する必要があります.チェックしないと、いろいろなエラーが発生する可能性があります.また,リスト,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("
    Edges:"
    ); for(Edge<L> edge : edges) sb.append("
    "
    + edge.toString()); return sb.toString(); }

    4.テスト用例を設計する時、できるだけ簡単で全面的に設計して、プログラムの中の各方法の各種の分岐をテストして、ほとんどの情況をカバーして、このようにできるだけADT内部の誤りを観察して位置決めすることができて、このADTを多重するもっと大規模なプログラムがそれを呼び出す時に誤りが発生することを減らすことができます.

    Problem 3: Implement generic Graph


    この中に難点はありません.StringをLに変えればいいです.しかし、注意しなければならないのは、emptyメソッドが後のLab 4で工場メソッドを記述する伏線であることです(ここではemptyは1つの選択肢しかありませんが).

    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);
        	}
        }
    

    第2部:Re-implement the Social Network in Lab 1


    今回の多重化は、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;
    	}
    

    第3部:Playing Chess


    設計ADT


    Boardを設計する時、囲碁と将棋にそれぞれ2つの碁盤を設計する必要はありません:囲碁と将棋に対して、座標はそれぞれ頂点と格子を表します;また,19 x 19の碁盤を設計し,将棋による碁盤へのアクセス空間を0−7間(Actionで体現)に制限すればよい.

    テストファイルの設計


    テストファイルでは、カバー度を確保するために手動テストしか挿入できませんが、コマンドラインプログラムではメニューが煩雑なので、テストの際にどこまで行ったのか忘れてエラーが発生しやすく、やり直すしかなく、ちょっとした挫折感がある場合があります.しかし、テストの結果は非常に満足しています.