/*************************************************************************
*
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* Copyright 2008 by Sun Microsystems, Inc.
*
* OpenOffice.org - a multi-platform office productivity suite
*
* $RCSfile: IteratorLCSAlgorithm.java,v $
* $Revision: 1.4 $
*
* 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);
}
}
}
}