OSDN Git Service

cflib は plugins プロジェクトから,Stigmata直下のプロジェクトに移行したため,このリポジトリからは削除した.
[stigmata/stigmata-plugins.git] / osb / src / main / java / jp / sourceforge / stigmata / birthmarks / osb / LCSCalculator.java
1 package jp.sourceforge.stigmata.birthmarks.osb;\r
2 \r
3 /**\r
4  * LCS (Longest Common Subsequence; 最長共通部分列)の計算機.\r
5  * 与えられた型 T の配列2つから最長共通部分列を見つけ,長さを返す.\r
6  * \r
7  * @author Haruaki Tamada\r
8  */\r
9 public class LCSCalculator<T>{\r
10     /**\r
11      * elementA と elementB の最長共通部分列の長さを返す.\r
12      * 配列の要素はnullを許容する.両方の要素がnullの場合は一致するとみなし,\r
13      * 片一方の要素のみがnullの場合は,一致しないとする.\r
14      * @param elementA 最長共通部分列の長さを計算する集合1\r
15      * @param elementB \r
16      * @return 最長共通部分列の長さ\r
17      * @exception NullPointerException 与えらえた配列のどちらか,もしくは両方が null の場合.\r
18      */\r
19     public int calculate(T[] elementA, T[] elementB){\r
20         if(elementA == null || elementB == null){\r
21             throw new NullPointerException();\r
22         }\r
23         int[][] table = new int[elementA.length + 1][elementB.length + 1];\r
24         for(int i = 0; i <= elementA.length; i++){\r
25             for(int j = 0; j <= elementB.length; j++){\r
26                 if(i == 0 || j == 0){\r
27                     table[i][j] = 0;\r
28                 }\r
29                 else if((elementA[i - 1] == null && elementB[j - 1] == null) ||\r
30                         elementA[i - 1] != null && elementA[i - 1].equals(elementB[j - 1])){\r
31                     table[i][j] = max(table[i - 1][j - 1] + 1, table[i - 1][j], table[i][j - 1]);\r
32                 }\r
33                 else{\r
34                     table[i][j] = max(table[i - 1][j - 1], table[i - 1][j], table[i][j - 1]);\r
35                 }\r
36             }\r
37         }\r
38         return table[elementA.length][elementB.length];\r
39     }\r
40 \r
41     /**\r
42      * 与えられた3つの整数値のうち,一番大きな値を返す.\r
43      * 全て正の数が与えらえるものとする.\r
44      */\r
45     private int max(int value1, int value2, int value3){\r
46         assert value1 >= 0;\r
47         assert value2 >= 0;\r
48         assert value3 >= 0;\r
49 \r
50         int max = value1;\r
51         if(max < value2){\r
52             max = value2;\r
53         }\r
54         if(max < value3){\r
55             max = value3;\r
56         }\r
57         return max;\r
58     }\r
59 }\r