diff options
Diffstat (limited to 'xmerge/source/xmerge/java/org/openoffice/xmerge/merger/diff/IteratorLCSAlgorithm.java')
| -rw-r--r-- | xmerge/source/xmerge/java/org/openoffice/xmerge/merger/diff/IteratorLCSAlgorithm.java | 236 |
1 files changed, 236 insertions, 0 deletions
diff --git a/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/diff/IteratorLCSAlgorithm.java b/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/diff/IteratorLCSAlgorithm.java new file mode 100644 index 000000000000..ae90274bfaf1 --- /dev/null +++ b/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/diff/IteratorLCSAlgorithm.java @@ -0,0 +1,236 @@ +/************************************************************************* + * + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * Copyright 2000, 2010 Oracle and/or its affiliates. + * + * OpenOffice.org - a multi-platform office productivity suite + * + * This file is part of OpenOffice.org. + * + * OpenOffice.org is free software: you can redistribute it and/or modify + * it under the terms of the GNU Lesser General Public License version 3 + * only, as published by the Free Software Foundation. + * + * OpenOffice.org is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU Lesser General Public License version 3 for more details + * (a copy is included in the LICENSE file that accompanied this code). + * + * You should have received a copy of the GNU Lesser General Public License + * version 3 along with OpenOffice.org. If not, see + * <http://www.openoffice.org/license.html> + * for a copy of the LGPLv3 License. + * + ************************************************************************/ + +package org.openoffice.xmerge.merger.diff; + +import java.util.Vector; +import org.openoffice.xmerge.merger.DiffAlgorithm; +import org.openoffice.xmerge.merger.Difference; +import org.openoffice.xmerge.merger.Iterator; +import org.openoffice.xmerge.util.Debug; + +/** + * This is one of the implementations of <code>DiffAlgorithm</code> interface. + * Using Longest Common Subsequence (LCS). The algorithm here is based + * on the book "Introduction to Algorithms" by Thomas H.Cormen, + * Charles E.Leiserson and Ronald L.Riverst (MIT Press 1990) page 314. + * + * @author smak + */ +public class IteratorLCSAlgorithm implements DiffAlgorithm { + + public Difference[] computeDiffs(Iterator orgSeq, Iterator modSeq) { + + int orgSeqlen = orgSeq.elementCount(); + int modSeqlen = modSeq.elementCount(); + + int[][] diffTable; + + // Diff table is used to keep track which element is the same or not + // in those 2 sequences + diffTable = createDiffTable(orgSeq, modSeq); + + // debug purpose... + if (Debug.isFlagSet(Debug.INFO)) { + printDiffTable(diffTable); + } + + Vector diffResult = new Vector(); + + generateResult(diffTable, orgSeqlen, modSeqlen, diffResult); + + Difference[] diffArray = new Difference[0]; + + // convert the vector to array, it has to do in here as + // generateResult is called recursively + if (diffResult.size() > 0) { + diffArray = new Difference[diffResult.size()]; + diffResult.copyInto(diffArray); + } + + diffTable = null; + diffResult = null; + + return diffArray; + } + + + /** + * Debug function used to print out the nicely formatted + * difference table. + * + * @param diffTable The difference table to display. + */ + private void printDiffTable(int[][] diffTable) { + + String tmpString = ""; + + for (int i = 0; i < diffTable.length; i++) { + for (int j = 0; j < diffTable[i].length; j++) { + tmpString = tmpString + " " + diffTable[i][j] + " "; + } + Debug.log(Debug.INFO, tmpString); + tmpString = ""; + } + } + + /** + * Create the difference table. + * The difference table is used internal to keep track what + * elements are common or different in the two sequences. + * + * @param orgSeq The original sequence to be used as a base. + * @param modSeq The modified sequence to compare. + * + * @return A difference table as a two-dimensional array of + * integers. + */ + private int[][] createDiffTable(Iterator orgSeq, Iterator modSeq) { + int orgSeqlen = orgSeq.elementCount() + 1; + int modSeqlen = modSeq.elementCount() + 1; + int[][] diffTable; + + // initialize the diffTable + diffTable = new int[orgSeqlen][]; + for (int i = 0; i < orgSeqlen; i++) { + diffTable[i] = new int[modSeqlen]; + } + + // compute the diff Table using LCS algorithm, refer to the book + // mentioned at the top of the program + + int i, j; + + Object orgSeqObject, modSeqObject; + + for (orgSeqObject = orgSeq.start(), i = 1; + orgSeqObject != null; + orgSeqObject = orgSeq.next(), i++) { + + for (modSeqObject = modSeq.start(), j = 1; + modSeqObject != null; + modSeqObject = modSeq.next(), j++) { + + if (orgSeq.equivalent(orgSeqObject, modSeqObject)) { + diffTable[i][j] = diffTable[i-1][j-1]+1; + } else { + if (diffTable[i-1][j] >= diffTable[i][j-1]) { + diffTable[i][j] = diffTable[i-1][j]; + } else { + diffTable[i][j] = diffTable[i][j-1]; + } + } + } + } + + return diffTable; + } + + + /** + * Generate the <code>Difference</code> object result vector. + * This method will be called recursively to backtrack the difference + * table to get the difference result (and also the LCS). + * + * @param diffTable The difference table containing the + * <code>Difference</code> result. + * @param i The nth element in original sequence to + * compare. This method is called recursively + * with i and j decreased until 0. + * @param j The nth element in modified sequence to + * compare. + * @param diffVector A vector to output the <code>Difference</code> + * result. Can not use a return variable as it + * is a recursive method. The vector will contain + * <code>Difference</code> objects with operation + * and positions fill in. + */ + private void generateResult(int[][] diffTable, + int i, int j, Vector diffVector) { + + // handle the first element + if (i == 0 && j == 0) { + return; + + } else if (j == 0) { + for (int cnt = 0; cnt < i; cnt++) { + Difference diff = + new Difference(Difference.DELETE, cnt, j); + diffVector.add(diff); + } + return; + + } else if (i == 0) { + for (int cnt = 0; cnt < j; cnt++) { + Difference diff = + new Difference(Difference.ADD, i, cnt); + diffVector.add(diff); + } + return; + } + + // for the detail of this algorithm, refer to the book mentioned on + // the top and page 317 and 318. + if ((diffTable[i-1][j-1] == diffTable[i][j] -1) && + (diffTable[i-1][j-1] == diffTable[i-1][j]) && + (diffTable[i-1][j-1] == diffTable[i][j-1])) { + + // the element of ith and jth in org and mod sequence is the same + generateResult(diffTable, i-1, j-1, diffVector); + } else { + if (diffTable[i-1][j] > diffTable[i][j-1]) { + + // recursively call first, then add the result so that + // the beginning of the diffs will be stored first + generateResult(diffTable, i-1, j, diffVector); + + Difference diff = + new Difference(Difference.DELETE, i-1, j); + diffVector.add(diff); + } else if (diffTable[i-1][j] < diffTable[i][j-1]) { + + // recursively call first, then add the result so that + // the beginning of the diffs will be stored first + generateResult(diffTable, i, j-1, diffVector); + + Difference diff = + new Difference(Difference.ADD, i, j-1); + diffVector.add(diff); + } else { // diffTable[i-1][j] == diffTable[i][j-1] + // recursively call first, then add the result so that + // the beginning of the diffs will be stored first + generateResult(diffTable, i-1, j-1, diffVector); + + Difference diff = + new Difference(Difference.CHANGE, i-1, j-1); + diffVector.add(diff); + + } + } + } +} + |