diff options
Diffstat (limited to 'xmerge/java/org/openoffice/xmerge/merger/diff')
14 files changed, 2181 insertions, 0 deletions
diff --git a/xmerge/java/org/openoffice/xmerge/merger/diff/CellNodeIterator.java b/xmerge/java/org/openoffice/xmerge/merger/diff/CellNodeIterator.java new file mode 100644 index 000000000000..f39b818d9831 --- /dev/null +++ b/xmerge/java/org/openoffice/xmerge/merger/diff/CellNodeIterator.java @@ -0,0 +1,119 @@ +/************************************************************************ + * + * 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: CellNodeIterator.java,v $ + * $Revision: 1.3 $ + * + * 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 org.w3c.dom.Node; +import org.w3c.dom.Element; + +import org.openoffice.xmerge.ConverterCapabilities; +import org.openoffice.xmerge.merger.Iterator; +import org.openoffice.xmerge.converter.xml.OfficeConstants; +import org.openoffice.xmerge.util.Debug; +import org.openoffice.xmerge.util.Resources; + + +/** + * <p>This is an implementations of the <code>Iterator</code> interface. + * It will traverse the tree and find cell <code>Node</code> sequences.</p> + * + * <p>Note: Once the XML Tree is parsed, then the <code>Iterator</code> + * will be a snap shot of that tree. That means even the tree is + * modified later, than the cached paragraph <code>Node</code> list will + * not be updated accordingly. For this reason and for performance reasons + * this <code>Iterator</code> does not support any operation methods such + * as insert, remove or replace. The main purpose of this + * <code>Iterator</code> is to be used with difference, not with merge.</p> + * + * @author smak + */ +public final class CellNodeIterator extends NodeIterator { + + private Resources res = Resources.getInstance(); + + // can be expanded to an array in the future, not necessary right now + private static final String SUPPORTED_TAG1 = OfficeConstants.TAG_TABLE_CELL; + + /** + * The standard constructor. + * + * @param cc The <code>ConverterCapabilities</code>. + * @param node The initial root <code>Node</code>. + */ + public CellNodeIterator(ConverterCapabilities cc, Node node) { + super(cc, node); + } + + + /** + * Overwrite the parent <code>nodeSupported</code> method. Only cell + * <code>Node</code> objects are supported. + * + * @param node The <code>Node</code> to check. + * + * @return true if the <code>Node</code> is supported, false otherwise. + */ + protected boolean nodeSupported(Node node) { + + // can use an array later to check all possible tags for + // future expansion + if (node.getNodeType() == Node.ELEMENT_NODE && + node.getNodeName().equals(SUPPORTED_TAG1)) { + return true; + } else { + return false; + } + } + + + protected boolean childrenEqual(Node node1, Node node2) { + + boolean equal = false; + + if (node1.hasChildNodes() && node2.hasChildNodes()) { + Element cell1 = (Element)node1; + Element cell2 = (Element)node2; + + // only need compare the first <text:p> children node, don't want + // to compare any non-supported features + // TODO: need to confirm whether all the text string is the + // first <text:p>, though I checked with the openoffice 619 build + Node paraNode1 = cell1.getElementsByTagName( + OfficeConstants.TAG_PARAGRAPH).item(0); + Node paraNode2 = cell2.getElementsByTagName( + OfficeConstants.TAG_PARAGRAPH).item(0); + + equal = super.compareNode(paraNode1, paraNode2); + } + + return equal; + } +} + diff --git a/xmerge/java/org/openoffice/xmerge/merger/diff/CharArrayLCSAlgorithm.java b/xmerge/java/org/openoffice/xmerge/merger/diff/CharArrayLCSAlgorithm.java new file mode 100644 index 000000000000..9a7b09a4da61 --- /dev/null +++ b/xmerge/java/org/openoffice/xmerge/merger/diff/CharArrayLCSAlgorithm.java @@ -0,0 +1,238 @@ +/************************************************************************ + * + * 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: CharArrayLCSAlgorithm.java,v $ + * $Revision: 1.3 $ + * + * 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; + +/** + * <p>This is an implementations of <code>DiffAlgorithm</code> interface + * which will difference char arrays.</p> + * + * <p>It also use Longest Common Subsequence (LCS). The algorithm is based + * on the book "Introduction to Algorithms" by Thomas H.Cormen, + * Charles E.Leiserson, and Ronald L.Riverst (MIT Press 1990) page 314.</p> + * + * @author smak + */ +public class CharArrayLCSAlgorithm { + + /** + * Return an <code>Difference</code> array. This method finds out + * the difference between two sequences. + * + * @param orgSeq The original sequence. + * @param modSeq The modified (or changed) sequence to + * compare against the origial. + * + * @return A <code>Difference</code> array. + */ + public Difference[] computeDiffs(char[] orgSeq, char[] modSeq) { + + int orgSeqlen = orgSeq.length; + int modSeqlen = modSeq.length; + + 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... + // printDiffTable(diffTable); + + Vector diffResult = new Vector(); + + generateResult(diffTable, orgSeqlen, modSeqlen, diffResult); + + // don't need anymore if Difference do not contain content information + /* fillInDiffContent(diffResult, orgSeq, modSeq); */ + + 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) { + + for (int i = 0; i < diffTable.length; i++) { + for (int j = 0; j < diffTable[i].length; j++) { + System.out.print(" " + diffTable[i][j] + " "); + } + System.out.println(); + } + } + + + /** + * 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(char[] orgSeq, char[] modSeq) { + int orgSeqlen = orgSeq.length + 1; + int modSeqlen = modSeq.length + 1; + int[][] diffTable; + + // initialize the diffTable (it need to be 1 row/col bigger + // than the original str) + 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 + for (int i = 1; i < orgSeqlen; i++) { + for (int j = 1; j < modSeqlen; j++) { + + if (orgSeq[i-1] == modSeq[j-1]) { + 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> 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 filled in. + */ + private void generateResult(int[][] diffTable, + int i, int j, Vector diffVector) { + + // handle the first element + if (i == 0 || j == 0) { + 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); + } + } else { + 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); + + } + } + } +} + diff --git a/xmerge/java/org/openoffice/xmerge/merger/diff/CharacterParser.java b/xmerge/java/org/openoffice/xmerge/merger/diff/CharacterParser.java new file mode 100644 index 000000000000..0546c128e64b --- /dev/null +++ b/xmerge/java/org/openoffice/xmerge/merger/diff/CharacterParser.java @@ -0,0 +1,146 @@ +/************************************************************************ + * + * 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: CharacterParser.java,v $ + * $Revision: 1.3 $ + * + * 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 org.w3c.dom.Node; +import org.w3c.dom.Element; + +import org.openoffice.xmerge.converter.xml.OfficeConstants; + +import java.util.Vector; +import java.util.List; + + +/** + * <p>This is a parser to return a character array for difference purpose. + * It will use depth first search to traverse all the characters inside the + * text <code>Node</code> under a given <code>Node</code> (most likely to be + * a paragraph <code>Node</code>).</p> + * + * <p>Note: Once the XML Tree is parsed, then the <code>Iterator</code> will be + * a snap shot of that tree. That means even the tree is modified later, than + * the cached paragraph <code>Node</code> list will not be updated accordingly. + * For this reason and for performance reasons this <code>Iterator</code> does + * not support any operation methods such as insert, remove or replace. The + * main purpose of this <code>Iterator</code> is to be used with difference, + * not with merge.</p> + * + * @author smak + */ +public class CharacterParser { + + private TextNodeIterator textNodes; + private int currentPosition = 0; + private List nodeList_ = null; + private char[] charArray; + + + /** + * Standard constructor. + * + * @param node The initial root <code>Node</code>. + */ + public CharacterParser(Node node) { + textNodes = new TextNodeIterator(node); + nodeList_ = new Vector(); + + parseNodes(); + } + + + /** + * Returns the <code>Node</code> pointer with the given character position. + * + * @return The <code>Node</code> pointer with the given character position. + */ + public List getNodeList() { + // will go through the nodeList to find the corresponding node + return nodeList_; + } + + /** + * Returns the character array representation of the text. + * + * @return The character array representation of the text. + */ + public char[] getCharArray() { + return charArray; + } + + private void parseNodes() { + + StringBuffer strBuf = new StringBuffer(); + + /* create the character array by iterate the textnode iterator */ + Node currentNode = (Node)(textNodes.start()); + for (; + currentNode != null; + currentNode = (Node)(textNodes.next())) { + + // add the text value into the array + String textValue = null; + String nodeName = currentNode.getNodeName(); + + // TODO: Space node have a count attribute which is not handled! + if (currentNode.getNodeType() == Node.TEXT_NODE) { + textValue = currentNode.getNodeValue(); + } else if (nodeName.equals(OfficeConstants.TAG_SPACE)) { + textValue = " "; + } else if (nodeName.equals(OfficeConstants.TAG_TAB_STOP)) { + textValue = "\t"; + } + + if (textValue != null) { + strBuf.append(textValue); + addNewNodeEntry(textValue.length(), currentNode); + } + } + + charArray = strBuf.toString().toCharArray(); + } + + + /** + * Adds a new <code>Node</code> entry. + * + * @param textLen The text length. + * @param node The <code>Node</code>. + */ + private void addNewNodeEntry(int textLen, Node node) { + + TextNodeEntry nodeEntry = new TextNodeEntry(currentPosition, + currentPosition + textLen - 1, node); + currentPosition = currentPosition + textLen; + + nodeList_.add(nodeEntry); + } +} + diff --git a/xmerge/java/org/openoffice/xmerge/merger/diff/IteratorLCSAlgorithm.java b/xmerge/java/org/openoffice/xmerge/merger/diff/IteratorLCSAlgorithm.java new file mode 100644 index 000000000000..8f3f6f03636c --- /dev/null +++ b/xmerge/java/org/openoffice/xmerge/merger/diff/IteratorLCSAlgorithm.java @@ -0,0 +1,239 @@ +/************************************************************************ + * + * 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.3 $ + * + * 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); + + } + } + } +} + diff --git a/xmerge/java/org/openoffice/xmerge/merger/diff/IteratorRowCompare.java b/xmerge/java/org/openoffice/xmerge/merger/diff/IteratorRowCompare.java new file mode 100644 index 000000000000..a3a24fe1c15b --- /dev/null +++ b/xmerge/java/org/openoffice/xmerge/merger/diff/IteratorRowCompare.java @@ -0,0 +1,246 @@ +/************************************************************************ + * + * 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: IteratorRowCompare.java,v $ + * $Revision: 1.3 $ + * + * 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 org.w3c.dom.Node; +import org.w3c.dom.Element; + +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.converter.xml.OfficeConstants; + +/** + * <p>A very simple and direct difference algorithm for row + * <code>Node</code> objects in a spreadsheet. Basically, it will + * compare objects in sequence and does not look ahead (unlike LCS).</p> + * + * <p><ol><li> + * If two objects are the same, skip to next one. + * </li><li> + * Otherwise check whether the row repeated attribute is the same. + * </li><li> + * If the row repeated attribute is the same, then compare two rows + * and mark it as <i>change</i> if those rows are different. + * </li><li> + * If the row repeated attribute is different, then split the rows and + * continue to compare. + * </li><li> + * If there are more objects in the modseq than the original sequence, + * then all of the extra ones in the modified sequence are marked as add. + * </li><li> + * If there are more objects in the original sequence than the modified + * sequence, then all the extra one in the modified sequence are marked + * as delete. + * </li></ol></p> + * + * <p>NOTE: The algorithm will have potential side effect to split rows.</p> + * + * @author smak + */ + +public class IteratorRowCompare implements DiffAlgorithm { + + /** + * Compute the differences of the given two sequences. + * Refer to the class description. + * + * Return an array of <code>Difference</code> objects. This method finds + * out the difference between two sequences. + * + * @param orgSeq The original sequence. + * @param modSeq The modified (or changed) sequence to + * compare against with the origial. + * + * @return An array of Difference objects. + */ + public Difference[] computeDiffs(Iterator orgSeq, Iterator modSeq) { + + int orgSeqlen = orgSeq.elementCount(); + int modSeqlen = modSeq.elementCount(); + + Vector diffVector = new Vector(); + + // i and j are counters to keep track the current position in the + // iterator + int i = 0; + int j = 0; + Object orgSeqObject = orgSeq.start(); + Object modSeqObject = modSeq.start(); + Element orgRow, modRow; + boolean different = false; + boolean orgSplited = false; + boolean modSplited = false; + + while (orgSeqObject != null) { + + different = true; + + if (modSeqObject == null) { + // no more modsequence, all the remaining org sequence objs + // should consider as a delete. + Difference diff = new Difference(Difference.DELETE, i, j); + diffVector.add(diff); + orgSeqObject = orgSeq.next(); + + } else { + if (!orgSeq.equivalent(orgSeqObject, modSeqObject)) { + + orgRow = (Element)orgSeqObject; + modRow = (Element)modSeqObject; + + // check whether the original Row with multiple row + // if so, need to split one out for merge + String orgRowRepeated = orgRow.getAttribute( + OfficeConstants.ATTRIBUTE_TABLE_NUM_ROWS_REPEATED); + String modRowRepeated = modRow.getAttribute( + OfficeConstants.ATTRIBUTE_TABLE_NUM_ROWS_REPEATED); + + + int orgRowNum = 1; + int modRowNum = 1; + + if (orgRowRepeated.length() > 0) { + orgRowNum = + Integer.valueOf(orgRowRepeated).intValue(); + } + if (modRowRepeated.length() > 0) { + modRowNum = + Integer.valueOf(modRowRepeated).intValue(); + } + + // try to find out the common number of repeated Rows + if (orgRowNum == modRowNum) { + orgSeqObject = orgSeq.next(); + modSeqObject = modSeq.next(); + + // cut the original row into two halves, first half + // have the repeated attribute = modify row attr + } else if (orgRowNum > modRowNum) { + Element orgSplitRow = splitRepeatedRow( + orgRow, modRowNum, + orgRowNum - modRowNum); + // it may equal after the split! + if (orgSeq.equivalent(orgSplitRow, modRow)) { + different = false; + } + orgSplited = true; + modSeqObject = modSeq.next(); + + // cut the modified Row into two halves, first half + // have the repeated attribute = original Row attr + } else { + Element modSplitRow = splitRepeatedRow( + modRow, orgRowNum, + modRowNum - orgRowNum); + + // check whether rows are equal after the split + if (modSeq.equivalent(orgRow, modSplitRow)) { + different = false; + } + modSplited = true; + orgSeqObject = orgSeq.next(); + } + + if (different) { + Difference diff = new Difference(Difference.CHANGE, + i, j); + diffVector.add(diff); + } + + } else { + // Rows are equivalent, move on to next one. + orgSeqObject = orgSeq.next(); + modSeqObject = modSeq.next(); + } // end if-else + j++; + } // end if-else + i++; + } // end while loop + + // any extra objects in modify sequence should consider as an add + // to the original sequence + for (; modSeqObject != null; modSeqObject = modSeq.next(), j++) { + Difference diff = new Difference(Difference.ADD, i, j); + diffVector.add(diff); + } + + // need to refresh the iterator if we split the rows + if (orgSplited) { + orgSeq.refresh(); + } + + if (modSplited) { + modSeq.refresh(); + } + + + // convert the vector to array + Difference[] diffArray = new Difference[diffVector.size()]; + diffVector.copyInto(diffArray); + + return diffArray; + } + + + private Element splitRepeatedRow(Element orgRow, int splitNum, int orgNum) { + // NOTE: should we really want to do deep clone? + // in most the case, it is an empty Row, but the + // specification didn't forbid any node to use multiple + // column attributes. i.e. the node can contain text + // nodes or other things under it. + Element splitRow = (Element)(orgRow.cloneNode(true)); + + if (splitNum > 1) { + splitRow.setAttribute( + OfficeConstants.ATTRIBUTE_TABLE_NUM_ROWS_REPEATED, + String.valueOf(splitNum)); + } else if (splitNum == 1) { + splitRow.removeAttribute( + OfficeConstants.ATTRIBUTE_TABLE_NUM_ROWS_REPEATED); + } + if (orgNum > 1) { + orgRow.setAttribute( + OfficeConstants.ATTRIBUTE_TABLE_NUM_ROWS_REPEATED, + String.valueOf(orgNum)); + } else if (orgNum == 1) { + orgRow.removeAttribute( + OfficeConstants.ATTRIBUTE_TABLE_NUM_ROWS_REPEATED); + } + + Node parentNode = orgRow.getParentNode(); + parentNode.insertBefore(splitRow, orgRow); + + return splitRow; + } +} + diff --git a/xmerge/java/org/openoffice/xmerge/merger/diff/NodeIterator.java b/xmerge/java/org/openoffice/xmerge/merger/diff/NodeIterator.java new file mode 100644 index 000000000000..49c6b3db3403 --- /dev/null +++ b/xmerge/java/org/openoffice/xmerge/merger/diff/NodeIterator.java @@ -0,0 +1,389 @@ +/************************************************************************ + * + * 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: NodeIterator.java,v $ + * $Revision: 1.3 $ + * + * 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 org.w3c.dom.Node; +import org.w3c.dom.NodeList; +import org.w3c.dom.NamedNodeMap; +import org.w3c.dom.Element; + +import org.openoffice.xmerge.ConverterCapabilities; +import org.openoffice.xmerge.merger.Iterator; +import org.openoffice.xmerge.converter.xml.OfficeConstants; +import org.openoffice.xmerge.util.Debug; +import org.openoffice.xmerge.util.Resources; + +import java.util.Vector; +import java.util.List; + + +/** + * <p>This is an implementation of the <code>Iterator</code> interface. + * It will traverse the tree and find <code>Node</code> sequences.</p> + * + * <p>Note: Once the XML Tree is parsed, then the <code>Iterator</code> will + * be a snap shot of that tree. That means even the tree is modified later, + * than the cached paragraph <code>Node</code> list will not be updated + * accordingly. For this reason and for performance reasons this + * <code>Iterator</code> does not support any operation methods such as + * insert, remove or replace. The main purpose of this + * <code>Iterator</code> is to be used with difference, not with merge.</p> + * + * @author smak + */ +public abstract class NodeIterator implements Iterator { + + private List nodeList = null; + private int currentPosition = 0; + private Node root; + private ConverterCapabilities cc_ = null; + + + /** + * Standard constructor. + * + * @param cc The <code>ConverterCapabilities</code>. + * @param node The initial root <code>Node</code>. + */ + public NodeIterator(ConverterCapabilities cc, Node node) { + cc_ = cc; + nodeList = new Vector(); + root = node; + markTree(node); + } + + + public Object next() { + if (currentPosition < nodeList.size() - 1) { + currentPosition++; + return currentElement(); + } else { + return null; + } + } + + + public Object previous() { + if (currentPosition > 0) { + currentPosition--; + return currentElement(); + } else { + return null; + } + } + + + public Object start() { + currentPosition = 0; + return currentElement(); + } + + + public Object end() { + int size = nodeList.size(); + + if (size > 0) { + currentPosition = size - 1; + return currentElement(); + } else { + return null; + } + } + + + public Object currentElement() { + + if (currentPosition < 0 || currentPosition >= nodeList.size()) { + return null; + } + + return nodeList.get(currentPosition); + } + + + public int elementCount() { + return nodeList.size(); + } + + + public boolean equivalent(Object obj1, Object obj2) { + boolean equal = false; + String errMsg = null; + if (!(obj1 instanceof Node && obj2 instanceof Node)) { + errMsg = Resources.getInstance().getString("NOT_NODE_ERROR"); + Debug.log(Debug.ERROR, errMsg); + } else { + Node node1 = (Node)obj1; + Node node2 = (Node)obj2; + + equal = compareNode(node1, node2); + } + return equal; + } + + + public void refresh() { + nodeList = new Vector(); + markTree(root); + currentPosition = 0; + } + + + /** + * Used to compare two <code>Node</code> objects (type/name/value) + * and all their children <code>Node</code> objects. + * + * @param node1 The first <code>Node</code> to compare. + * @param node2 The second <code>Node</code> to compare. + * + * @return true if <code>Node</code> is equal, false otherwise. + */ + protected boolean compareNode(Node node1, Node node2) { + boolean equal = false; + + nodeCheck: { + + if (node1 == null || node2 == null) { + break nodeCheck; + } + + // nodevalue is short + if (node1.getNodeType() != node2.getNodeType()) { + break nodeCheck; + } + + // nodeName will not be null + if (!node1.getNodeName().equals(node2.getNodeName())) { + break nodeCheck; + } + + // nodeValue can be null for a lot of type of cells + if (node1.getNodeValue() == null && node2.getNodeValue() == null) { + // empty + } else if (node1.getNodeValue() == null || + node2.getNodeValue() == null) { + break nodeCheck; + } else if (!node1.getNodeValue().equals(node2.getNodeValue())) { + break nodeCheck; + } + + // try to compare attributes + if (!attributesEqual(node1, node2)) { + break nodeCheck; + } + + // don't need to compare if both node do not have children + if (!node1.hasChildNodes() && !node2.hasChildNodes()) { + equal = true; + break nodeCheck; + // don't need to compare if one node has children but not the other + } else if (!node1.hasChildNodes() || !node2.hasChildNodes()) { + equal = false; + break nodeCheck; + // need to compare if both node has children + } else if (!childrenEqual(node1, node2)) { + break nodeCheck; + } + + equal = true; + } + + return equal; + } + + + /** + * Compare the children of two <code>Node</code> objects. This + * method can be intentionally overridden by any class that + * extend from <code>NodeIterator</code> so that it can have + * its own children comparison if necessary. + * + * @param node1 The first <code>Node</code> to compare. + * @param node2 The second <code>Node</code> to compare. + * + * @return true if children are equal, false otherwise. + */ + protected boolean childrenEqual(Node node1, Node node2) { + + boolean equal = false; + + childrenCheck: { + NodeList node1Children = node1.getChildNodes(); + NodeList node2Children = node2.getChildNodes(); + + if (node1Children == null || node2Children == null) { + break childrenCheck; + } + + if (node1Children.getLength() != node2Children.getLength()) { + break childrenCheck; + } + + // compare all the childrens + equal = true; + + for (int i = 0; i < node1Children.getLength(); i++) { + if (!compareNode(node1Children.item(i), + node2Children.item(i))) { + equal = false; + break childrenCheck; + } + } + } + + return equal; + } + + + /** + * Compare attributes of two <code>Node</code> objects. This + * method can be intentionally overridden by any class that + * extends from <code>NodeIterator</code> so that it can have + * its own attribute comparison. + * + * @param node1 The first <code>Node</code> to compare. + * @param node2 The second <code>Node</code> to compare. + * + * @return true if attributes are equal, false otherwise. + */ + protected boolean attributesEqual(Node node1, Node node2) { + + boolean equal = false; + String nodeName = node1.getNodeName(); + NamedNodeMap attrNode[] = new NamedNodeMap[2]; + attrNode[0] = node1.getAttributes(); + attrNode[1] = node2.getAttributes(); + + // attribute node will be null if node is not an element node + // and attribute nodes are equal if both are not element node + if (attrNode[0] == null || attrNode[1] == null) { + if (attrNode[0] == null && attrNode[1] == null) { + equal = true; + } + return equal; + } + + // compare the attributes from node1 vs node2 and node2 vs node1 + // though it's a little inefficient for the duplication of comparison + // as the number of attributes is not so many, it should not be + // a big problem. + int len [] = new int[2]; + int src, dst; + + attrCheck: { + for (int i = 0; i < 2; i++) { + + if (i == 0) { + src = 0; + dst = 1; + } else { + src = 1; + dst = 0; + } + + len[src] = attrNode[src].getLength(); + + for (int j = 0; j < len[src]; j++) { + Node srcAttr = attrNode[src].item(j); + String srcAttrName = srcAttr.getNodeName(); + + // copy the supported attrs + if (cc_ == null || + cc_.canConvertAttribute(nodeName, srcAttrName)) { + + // check whether the attribute exist in dst node + Node dstAttr = attrNode[dst].getNamedItem(srcAttrName); + + if (dstAttr == null) { + Debug.log(Debug.INFO, + "[NodeIterator] Attr not exist in dst - " + + srcAttrName); + break attrCheck; + } + + // then compare the attribute values + if (!srcAttr.getNodeValue().equals( + dstAttr.getNodeValue())) { + Debug.log(Debug.INFO, + "[NodeIterator] Attr diff src: " + + srcAttr.getNodeValue() + " dst: "+ + dstAttr.getNodeValue()); + break attrCheck; + } + } // end if cc_ loop + } // end for j loop + } // end for i loop + + // the whole checking is done smoothly and all attributes are equal + equal = true; + } + + return equal; + } + + + /** + * Check whether a <code>Node</code> is supported. This method + * can be intentionally overridden by any class that extends from + * <code>NodeIterator</code> so that it can specify which + * <code>Node</code> to support. + * + * @param node <code>Node</code> to check. + * + * @return true if <code>Node</code> is supported, false otherwise. + */ + protected abstract boolean nodeSupported(Node node); + + // doing a depth first search for the tree and mark all supported nodes + private void markTree(Node node) { + + // if this is a supported node, then we add it to our cache table + if (nodeSupported(node)) { + nodeList.add(node); + } else { + // or we go through all children nodes recursively + // (can be optimized in future) + String nodeName = node.getNodeName(); + if ( cc_ == null || cc_.canConvertTag(nodeName)) { + NodeList nodeList = node.getChildNodes(); + int nodeListLength = nodeList.getLength(); + for (int i = 0; i < nodeListLength; i++) { + markTree(nodeList.item(i)); + } + } + else { + Debug.log(Debug.INFO, " [NodeIterator::markTree] Skipping node " + + nodeName); + } + } + } +} + diff --git a/xmerge/java/org/openoffice/xmerge/merger/diff/ObjectArrayIterator.java b/xmerge/java/org/openoffice/xmerge/merger/diff/ObjectArrayIterator.java new file mode 100644 index 000000000000..4faaf8b657b6 --- /dev/null +++ b/xmerge/java/org/openoffice/xmerge/merger/diff/ObjectArrayIterator.java @@ -0,0 +1,213 @@ +/************************************************************************ + * + * 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: ObjectArrayIterator.java,v $ + * $Revision: 1.3 $ + * + * 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 org.openoffice.xmerge.merger.Iterator; + +/** + * <p>This is an implementation of the <code>Iterator</code> interface. + * It is based upon a simple <code>Object</code> array.</p> + * + * <p>Note: this class is not thread safe for performance reasons.</p> + * + * @author smak + */ +public final class ObjectArrayIterator implements Iterator { + + + /** + * The <code>Object</code> array. + */ + private Object [] objArray; + private int currentPosition; + + + /** + * Private default constructor. + */ + private ObjectArrayIterator() { + // do not allow user new a ObjectArrayIterator without argument + } + + + /** + * Standard constructor. + * + * @param objArray The <code>Object</code> array. + */ + public ObjectArrayIterator(Object [] objArray) { + if (objArray != null) { + this.objArray = new Object[objArray.length]; + System.arraycopy(objArray, 0, this.objArray, 0, objArray.length); + currentPosition = 0; + } else { + this.objArray = new Object[0]; + } + } + + + public Object next() { + if (currentPosition < objArray.length - 1) { + currentPosition++; + return currentElement(); + } else { + return null; + } + + } + + + public Object previous() { + if (currentPosition > 0) { + currentPosition--; + return currentElement(); + } else { + return null; + } + } + + + public Object start() { + currentPosition = 0; + return currentElement(); + } + + + public Object end() { + if (objArray.length > 0) { + currentPosition = objArray.length - 1; + } + return currentElement(); + } + + + public Object currentElement() { + if (objArray.length > 0) { + return objArray[currentPosition]; + } else { + return null; + } + } + + + /** + * Replace current <code>Object</code>. + * + * @param object <code>Object</code> to replace. + */ + public void replace(Object object) { + objArray[currentPosition] = object; + } + + + /** + * Insert <code>Object</code> after current <code>Object</code>. + * + * @param object <code>Object</code> to insert. + */ + public void insert(Object object) { + Object [] objArray2 = new Object[objArray.length+1]; + + // copy the array content up before the currentposition + if (currentPosition > 0) { + System.arraycopy(objArray, 0, objArray2, 0, currentPosition); + } + + objArray2[currentPosition] = object; + + // copy the array content up after the currentposition + System.arraycopy(objArray, currentPosition, objArray2, + currentPosition + 1, objArray.length - currentPosition); + + objArray = objArray2; + currentPosition++; + } + + /** + * Append <code>Object</code> after current <code>Object</code>. + * + * @param object <code>Object</code> to append. + */ + public void append(Object object) { + Object [] objArray2 = new Object[objArray.length + 1]; + + int newPosition = currentPosition + 1; + + // copy the array content up to the currentposition + System.arraycopy(objArray, 0, objArray2, 0, newPosition); + + objArray2[newPosition] = object; + + // copy the array content up after the currentposition + if (currentPosition < objArray.length - 1) { + System.arraycopy(objArray, newPosition, objArray2, + newPosition + 1, objArray.length - newPosition); + } + + objArray = objArray2; + } + + /** + * Remove current <code>Object</code>. + */ + public void remove() { + Object [] objArray2 = new Object[objArray.length - 1]; + + // copy the array content up before the currentposition + if (currentPosition > 0) { + System.arraycopy(objArray, 0, objArray2, 0, currentPosition); + } + + // copy the array content up after the currentposition + if (currentPosition < objArray.length - 1) { + System.arraycopy(objArray, currentPosition + 1, objArray2, + currentPosition, objArray.length - currentPosition - 1); + } + + objArray = objArray2; + + if (currentPosition == objArray.length) + currentPosition--; + } + + public int elementCount() { + return objArray.length; + } + + public boolean equivalent(Object obj1, Object obj2) { + return obj1.equals(obj2); + } + + public void refresh() { + // do nothing + } +} + diff --git a/xmerge/java/org/openoffice/xmerge/merger/diff/ParaNodeIterator.java b/xmerge/java/org/openoffice/xmerge/merger/diff/ParaNodeIterator.java new file mode 100644 index 000000000000..8465fa1f7a0a --- /dev/null +++ b/xmerge/java/org/openoffice/xmerge/merger/diff/ParaNodeIterator.java @@ -0,0 +1,98 @@ +/************************************************************************ + * + * 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: ParaNodeIterator.java,v $ + * $Revision: 1.3 $ + * + * 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 org.w3c.dom.Node; +import org.w3c.dom.Element; + +import org.openoffice.xmerge.ConverterCapabilities; +import org.openoffice.xmerge.merger.Iterator; +import org.openoffice.xmerge.converter.xml.OfficeConstants; + +import java.util.Vector; +import java.util.List; + + +/** + * <p>This is an implementation of the <code>Iterator</code> interface. + * It will traverse the tree and find the Paragraph/Heading <code>Node</code> + * sequences.</p> + * + * <p>Note: Once the XML Tree is parsed, then the <code>Iterator</code> will + * be a snap shot of that tree. That means even the tree is modified later, + * than the cached paragraph <code>Node</code> list will not be updated + * accordingly. For this reason and for performance reasons this + * <code>Iterator</code> does not support any operation methods such as + * insert, remove or replace. The main purpose of this + * <code>Iterator</code> is to be used with difference, not with merge.</p> + * + * @author smak + */ +public final class ParaNodeIterator extends NodeIterator { + + // can be expanded to an array in the future, not necessary right now + private static final String SUPPORTED_TAG1 = OfficeConstants.TAG_PARAGRAPH; + private static final String SUPPORTED_TAG2 = OfficeConstants.TAG_HEADING; + + /** + * Standard constructor. + * + * @param cc The <code>ConverterCapabilities</code>. + * @param node The initial root <code>Node</code>. + */ + public ParaNodeIterator(ConverterCapabilities cc, Node node) { + // not using convertercapabilities unless it's needed in future. + super(cc, node); + } + + + /** + * Overwrite the parent <code>nodeSupported</code> method. + * + * @param node <code>Node</code> to check. + * + * @return true if the <code>Node</code> is supported, false + * otherwise. + */ + protected boolean nodeSupported(Node node) { + + // can use an array later to check all possible tags for + // future expansion + if (node.getNodeType() == Node.ELEMENT_NODE && + (node.getNodeName().equals(SUPPORTED_TAG1) || + node.getNodeName().equals(SUPPORTED_TAG2))) { + return true; + } else { + return false; + } + } +} + diff --git a/xmerge/java/org/openoffice/xmerge/merger/diff/RowIterator.java b/xmerge/java/org/openoffice/xmerge/merger/diff/RowIterator.java new file mode 100644 index 000000000000..0122bac87bc6 --- /dev/null +++ b/xmerge/java/org/openoffice/xmerge/merger/diff/RowIterator.java @@ -0,0 +1,87 @@ +/************************************************************************ + * + * 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: RowIterator.java,v $ + * $Revision: 1.3 $ + * + * 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 org.w3c.dom.Node; +import org.w3c.dom.Element; + +import org.openoffice.xmerge.ConverterCapabilities; +import org.openoffice.xmerge.merger.Iterator; +import org.openoffice.xmerge.converter.xml.OfficeConstants; +import org.openoffice.xmerge.util.Debug; +import org.openoffice.xmerge.util.Resources; + + +/** + * This is an implementation of the <code>Iterator</code> interface and extends + * <code>NodeIterator</code>. It will traverse the tree and find row sequences. + * + * @author smak + */ +public final class RowIterator extends NodeIterator { + + private Resources res = Resources.getInstance(); + + // TODO: should compare the ConverterCapabilities supported feature only! + // otherwise even though one with a chart, one without, will still be + // considered to be not equivalent. + + /** + * Standard constructor. + * + * @param cc The <code>ConverterCapabilities</code>. + * @param node The initial root <code>Node</code>. + */ + public RowIterator(ConverterCapabilities cc, Node node) { + super(cc, node); + } + + /** + * Overwrite the parent <code>nodeSupported</code> method. Only + * row <code>Node</code> objects are supported. + * + * @param node <code>Node</code> to check. + * + * @return true if the <code>Node</code> is supported, false otherwise. + */ + protected boolean nodeSupported(Node node) { + + // can use an array later to check all possible tags for + // future expansion + if (node.getNodeType() == Node.ELEMENT_NODE && + node.getNodeName().equals(OfficeConstants.TAG_TABLE_ROW)) { + return true; + } else { + return false; + } + } +} + diff --git a/xmerge/java/org/openoffice/xmerge/merger/diff/TextNodeEntry.java b/xmerge/java/org/openoffice/xmerge/merger/diff/TextNodeEntry.java new file mode 100644 index 000000000000..71b1c668a998 --- /dev/null +++ b/xmerge/java/org/openoffice/xmerge/merger/diff/TextNodeEntry.java @@ -0,0 +1,91 @@ +/************************************************************************ + * + * 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: TextNodeEntry.java,v $ + * $Revision: 1.3 $ + * + * 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 org.w3c.dom.Node; + +/** + * A small class to hold the start/end character position and the + * <code>Node</code> pointer in a text <code>Node</code>. It is + * mainly used for character parser to make a list of text + * <code>Node</code> cache entries. + * + * @author smak + */ +public class TextNodeEntry { + + private int startChar_; + private int endChar_; + private Node node_; + + /** + * Constructor + * + * @param startChar The start character position. + * @param endChar The end character position. + * @param node The text <code>Node</code>. + */ + public TextNodeEntry(int startChar, int endChar, Node node) { + startChar_ = startChar; + endChar_ = endChar; + node_ = node; + } + + /** + * Returns the start character. + * + * @return The start character. + */ + public int startChar() { + return startChar_; + } + + + /** + * Returns the end character. + * + * @return The end character. + */ + public int endChar() { + return endChar_; + } + + + /** + * Returns the <code>Node</code>. + * + * @return The <code>Node</code>. + */ + public Node node() { + return node_; + } +} + diff --git a/xmerge/java/org/openoffice/xmerge/merger/diff/TextNodeIterator.java b/xmerge/java/org/openoffice/xmerge/merger/diff/TextNodeIterator.java new file mode 100644 index 000000000000..f0e29fbe9b07 --- /dev/null +++ b/xmerge/java/org/openoffice/xmerge/merger/diff/TextNodeIterator.java @@ -0,0 +1,93 @@ +/************************************************************************ + * + * 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: TextNodeIterator.java,v $ + * $Revision: 1.3 $ + * + * 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 org.w3c.dom.Node; +import org.w3c.dom.Element; +import org.w3c.dom.Document; + +import org.openoffice.xmerge.merger.Iterator; +import org.openoffice.xmerge.converter.xml.OfficeConstants; + +import java.util.Vector; +import java.util.List; + + +/** + * <p>This is an implementation of the <code>Iterator</code> interface. + * It will traverse the tree and find text/space/tab <code>Node</code> + * sequences.</p> + * + * <p>Note: Once the XML Tree is parsed, then the <code>Iterator</code> + * will be a snap shot of that tree. That means even the tree is modified + * later, than the cached paragraph <code>Node</code> list will not be + * updated accordingly. For this reason and for performance reasons + * this <code>Iterator</code> does not support any operation methods + * such as insert, remove or replace. The main purpose of this + * <code>Iterator</code> is to be used with difference, not with merge.</p> + * + * @author smak + */ +public final class TextNodeIterator extends NodeIterator { + + /** + * Standard constructor. + * + * @param initial The initial root <code>Node</code>. + */ + public TextNodeIterator(Node node) { + super(null, node); + } + + /** + * Overwrite the parent <code>nodeSupported</code> method. Only text + * <code>Node</code> objects are supported. + * + * @param node <code>Node</code> to check. + * + * @return true if the <code>Node</code> is supported, false + * otherwise. + */ + protected boolean nodeSupported(Node node) { + + // can use an array later to check all possible tags for + // future expansion + if (node.getNodeType() == Node.TEXT_NODE || + node.getNodeName().equals(OfficeConstants.TAG_SPACE) || + node.getNodeName().equals(OfficeConstants.TAG_TAB_STOP) || + node.getNodeName().equals(OfficeConstants.TAG_LINE_BREAK)) { + return true; + } else { + return false; + } + } +} + diff --git a/xmerge/java/org/openoffice/xmerge/merger/diff/build.xml b/xmerge/java/org/openoffice/xmerge/merger/diff/build.xml new file mode 100644 index 000000000000..5a1e450919a8 --- /dev/null +++ b/xmerge/java/org/openoffice/xmerge/merger/diff/build.xml @@ -0,0 +1,141 @@ +<?xml version="1.0" encoding="UTF-8"?> +<!-- + + 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: build.xml,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. + +--> +<project name="xmrg_jooxm_diff" default="main" basedir="."> + + <!-- ================================================================= --> + <!-- settings --> + <!-- ================================================================= --> + + <!-- project prefix, used for targets and build.lst --> + <property name="prj.prefix" value="xmrg"/> + + <!-- name of this sub target used in recursive builds --> + <property name="target" value="xmrg_jooxm_diff"/> + + <!-- relative path to project directory --> + <property name="prj" value="../../../../../.."/> + + <!-- start of java source code package structure --> + <property name="java.dir" value="${prj}/java"/> + + <!-- path component for current java package --> + <property name="package" + value="org/openoffice/xmerge/merger/diff"/> + + <!-- define how to handle CLASSPATH environment --> + <property name="build.sysclasspath" value="ignore"/> + + <!-- classpath settings for javac tasks --> + <path id="classpath"> + <pathelement location="${build.class}"/> + <pathelement location="${solar.jar}/parser.jar"/> + <pathelement location="${solar.jar}/jaxp.jar"/> + <pathelement location="${solar.jar}/xerces.jar"/> + </path> + + <!-- set wether we want to compile with or without deprecation --> + <property name="deprecation" value="on"/> + + <!-- ================================================================= --> + <!-- solar build environment targets --> + <!-- ================================================================= --> + + <target name="build_dir" unless="build.dir"> + <property name="build.dir" value="${out}"/> + </target> + + <target name="solar" depends="build_dir" if="solar.update"> + <property name="solar.properties" + value="${solar.bin}/solar.properties"/> + </target> + + <target name="init" depends="solar"> + <property name="build.compiler" value="classic"/> + <property file="${solar.properties}"/> + <property file="${build.dir}/class/solar.properties"/> + </target> + + <target name="info"> + <echo message="--------------------"/> + <echo message="${target}"/> + <echo message="--------------------"/> + </target> + + + <!-- ================================================================= --> + <!-- custom targets --> + <!-- ================================================================= --> + + <!-- the main target, called in recursive builds --> + <target name="main" depends="info,prepare,compile"/> + + <!-- prepare output directories --> + <target name="prepare" depends="init" if="build.class"> + <mkdir dir="${build.dir}"/> + <mkdir dir="${build.class}"/> + </target> + + <!-- compile java sources in ${package} --> + <target name="compile" depends="prepare" if="build.class"> + <javac srcdir="${java.dir}" + destdir="${build.class}" + debug="${debug}" + deprecation="${deprecation}" + optimize="${optimize}"> + <classpath refid="classpath"/> + <include name="${package}/CharacterParser.java"/> + <include name="${package}/CharArrayLCSAlgorithm.java"/> + <include name="${package}/IteratorLCSAlgorithm.java"/> + <include name="${package}/IteratorRowCompare.java"/> + <include name="${package}/NodeIterator.java"/> + <include name="${package}/ObjectArrayIterator.java"/> + <include name="${package}/ParaNodeIterator.java"/> + <include name="${package}/CellNodeIterator.java"/> + <include name="${package}/TextNodeEntry.java"/> + <include name="${package}/TextNodeIterator.java"/> + <include name="${package}/RowIterator.java"/> + </javac> + </target> + + <!-- clean up --> + <target name="clean" depends="prepare"> + <delete includeEmptyDirs="true"> + <fileset dir="${build.class}"> + <patternset> + <include name="${package}/*.class"/> + </patternset> + </fileset> + </delete> + </target> + +</project> + diff --git a/xmerge/java/org/openoffice/xmerge/merger/diff/makefile.mk b/xmerge/java/org/openoffice/xmerge/merger/diff/makefile.mk new file mode 100644 index 000000000000..490ac59ef76a --- /dev/null +++ b/xmerge/java/org/openoffice/xmerge/merger/diff/makefile.mk @@ -0,0 +1,36 @@ +#*************************************************************************** +# +# 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: makefile.mk,v $ +# +# $Revision: 1.3 $ +# +# 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. +# +#*************************************************************************** + +TARGET=xmrg_jooxm_diff +PRJ=../../../../../.. + +.INCLUDE : ant.mk +ALLTAR: ANTBUILD diff --git a/xmerge/java/org/openoffice/xmerge/merger/diff/package.html b/xmerge/java/org/openoffice/xmerge/merger/diff/package.html new file mode 100644 index 000000000000..7ae7d3419fc2 --- /dev/null +++ b/xmerge/java/org/openoffice/xmerge/merger/diff/package.html @@ -0,0 +1,45 @@ +<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN"> +<!-- + + 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: package.html,v $ + + $Revision: 1.3 $ + + 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. + +--> +<html> +<head> +<title>org.openoffice.xmerge.merger.diff package</title> +</head> + +<body bgcolor="white"> +<p>Provides implementations for the {@link +org.openoffice.xmerge.merger.Iterator Iterator} +interface and related support classes. These are used by the {@link +org.openoffice.xmerge.merger.DiffAlgorithm +DiffAlgorithm} interface.</p> + +</body> +</html> |