diff options
Diffstat (limited to 'xmerge/source/xmerge/java/org/openoffice/xmerge/merger')
24 files changed, 3126 insertions, 0 deletions
diff --git a/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/DiffAlgorithm.java b/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/DiffAlgorithm.java new file mode 100644 index 000000000..a39649b03 --- /dev/null +++ b/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/DiffAlgorithm.java @@ -0,0 +1,43 @@ +/* + * This file is part of the LibreOffice project. + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. + * + * This file incorporates work covered by the following license notice: + * + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed + * with this work for additional information regarding copyright + * ownership. The ASF licenses this file to you under the Apache + * License, Version 2.0 (the "License"); you may not use this file + * except in compliance with the License. You may obtain a copy of + * the License at http://www.apache.org/licenses/LICENSE-2.0 . + */ + +package org.openoffice.xmerge.merger; + +/** + * This is the difference algorithm interface. + * + * <p>It is an interface so that different algorithms may be plugged-in to + * actually compute the differences.</p> + * + * <p>NOTE: this code may not be thread safe.</p> + */ +public interface DiffAlgorithm { + + /** + * Returns a {@code Difference} array. + * + * <p>This method finds out the difference between two sequences.</p> + * + * @param orgSeq The original sequence of object. + * @param modSeq The modified (or changed) sequence to compare against + * with the original. + * + * @return A {@code Difference} array. + */ + Difference[] computeDiffs(Iterator orgSeq, Iterator modSeq); +}
\ No newline at end of file diff --git a/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/Difference.java b/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/Difference.java new file mode 100644 index 000000000..74e95fb38 --- /dev/null +++ b/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/Difference.java @@ -0,0 +1,223 @@ +/* + * This file is part of the LibreOffice project. + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. + * + * This file incorporates work covered by the following license notice: + * + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed + * with this work for additional information regarding copyright + * ownership. The ASF licenses this file to you under the Apache + * License, Version 2.0 (the "License"); you may not use this file + * except in compliance with the License. You may obtain a copy of + * the License at http://www.apache.org/licenses/LICENSE-2.0 . + */ + +package org.openoffice.xmerge.merger; + +/** + * This is the {@code Difference} basic unit. + * + * Used by the {@code DiffAlgorithm} as a set of difference between two + * {@code Iterators} (the original and modified {@code Iterators}). + */ +public final class Difference { + + /** Add operation. */ + public static final int ADD = 1; + + /** Delete operation. */ + public static final int DELETE = 2; + + /** Change operation. */ + public static final int CHANGE = 3; + + /** Unchange operation (i.e. no change). */ + public static final int UNCHANGE = 4; + + /** The action of the diff - either {@link #ADD} or {@link #DELETE} */ + private final int operation; + + /** + * The position of the content that should be operated on (original + * {@code iterator}). + * + * <p>For {@code ADD}, the {@code orgPosition} is the position of the + * original sequence where the diff will insert (the element count is + * starting from 0, and always insert before the element). The + * {@code modPosition} is the position of the diff in the modified sequence + * (also starting from 0).</p> + * + * <blockquote><pre>{@literal example: + * + * diff - <B D> and <A B C D E F> + * note: <B D> is original sequence and <A B C D E F> + * is the modified one. + * + * and here is the position of those sequence: + * <B D> <A B C D E F> + * 0 1 0 1 2 3 4 5 + * + * result: + * <diff orgPos=0 modPos=0 operation=ADD> <-- element A + * <diff orgPos=1 modPos=2 operation=ADD> <-- element C + * <diff orgPos=2 modPos=4 operation=ADD> <-- element E + * <diff orgPos=2 modPos=5 operation=ADD> <-- element F}</pre></blockquote> + * + * <p>One can notice the add operation is inserted before the position. + * Hence, in order to append an element, we will have a position of original + * sequence length + 1 to denote an append.</p> + * + * <p>For {@code DELETE}, {@code orgPosition} is the position that the + * element will be deleted (starting from 0) and {@code modPosition} is the + * position where the deleted element should be (consider as an {@code ADD}). + * </p> + * + * <p>The {@code modPosition} is less useful and it is difficult to + * understand how the position is calculated. One can just skip this piece + * of information. It is useful if one wants to reverse the role of original + * sequence and modified sequence and find out the diff easily (just change + * add to delete and delete to add for operation and swap the + * {@code orgPosition} and {@code modPosition}).</p> + * + * <blockquote><pre>{@literal example: + * + * diff - <A B C D E F> and <B D> + * note: <A B C D E F> is original sequence and <B D> + * is the modified one. + * + * and here is the position of those sequence: + * <A B C D E F> <B D> + * 0 1 2 3 4 5 0 1 + * + * result: + * <diff orgPos=0 modPos=0 operation=DELETE> <-- element A + * <diff orgPos=2 modPos=1 operation=DELETE> <-- element C + * <diff orgPos=4 modPos=2 operation=DELETE> <-- element E + * <diff orgPos=5 modPos=2 operation=DELETE> <-- element F}</pre></blockquote> + */ + private final int orgPosition; + + /** + * The position of the content that should be operated (modified iterator). + * + * <p>For explanation and examples, see {@link #orgPosition}</p>. + */ + private final int modPosition; + + /** + * Constructor. + * + * This is the standard way to create a {@code Difference} object. + * + * @param operation Either {@link #ADD} or {@link #DELETE}. + * @param orgPosition The position in the original (first) {@code Iterator}. + * @param modPosition The position in the modified (second) {@code Iterator}. + */ + public Difference(int operation, int orgPosition, + int modPosition) { + this.operation = operation; + this.orgPosition = orgPosition; + this.modPosition = modPosition; + } + + /** + * Get the operation of the {@code Difference}. + * + * @return the operation of the {@code Difference}, either {@link #ADD} or + * {@link #DELETE}. + */ + public int getOperation() { + return operation; + } + + /** + * Get the original {@code Iterator} position. + * + * @return The position in the original (first) {@code Iterator}. + */ + public int getOrgPosition() { + return orgPosition; + } + + /** + * Get the modified {@code Iterator} position. + * + * @return The position in the modified (second) {@code Iterator}. + */ + public int getModPosition() { + return modPosition; + } + + /** + * Two {@code Difference} objects will equal if and only if all + * {@code operation}, {@code orgPosition}, {@code modPosition} and + * {@code content} are equal. + * + * @param obj {@code Object} to compare. + * + * @return {@code true} if equal, {@code false} otherwise. + */ + @Override + public boolean equals(Object obj) { + if (obj instanceof Difference) { + Difference diff = (Difference) obj; + if ((operation == diff.operation) && + (orgPosition == diff.orgPosition) && + (modPosition == diff.modPosition)) { + return true; + } + } + + return false; + } + + @Override + public int hashCode() { + return 0; + } + + /** + * Display debug information. + * + * @return Debug string. + */ + public String debug() { + + String opStr = ""; + + switch (operation) { + case ADD: + opStr = "add"; + break; + case DELETE: + opStr = "del"; + break; + case CHANGE: + opStr = "chg"; + break; + case UNCHANGE: + opStr = "uch"; + break; + default: + break; + } + return "<diff orgPos=" + orgPosition + " modPos=" + modPosition + + " op=" + opStr + ">"; + } + + /** + * Returns position and operation values as a single string. + * + * @return {@code orgPosition}, {@code modPosition} and {@code operation} + * as a single {@code String}. + */ + @Override + public String toString() { + + return orgPosition + " " + modPosition + " " + operation; + } +} diff --git a/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/Iterator.java b/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/Iterator.java new file mode 100644 index 000000000..c53988076 --- /dev/null +++ b/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/Iterator.java @@ -0,0 +1,85 @@ +/* + * This file is part of the LibreOffice project. + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. + * + * This file incorporates work covered by the following license notice: + * + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed + * with this work for additional information regarding copyright + * ownership. The ASF licenses this file to you under the Apache + * License, Version 2.0 (the "License"); you may not use this file + * except in compliance with the License. You may obtain a copy of + * the License at http://www.apache.org/licenses/LICENSE-2.0 . + */ + +package org.openoffice.xmerge.merger; + +/** + * This is an interface used by the {@link + * org.openoffice.xmerge.merger.DiffAlgorithm DiffAlgorithm} and {@link + * org.openoffice.xmerge.merger.MergeAlgorithm MergeAlgorithm} to access a + * {@code Document}. + */ +public interface Iterator { + + /** + * Move to next element in the sequence. + * + * @return The {@code Object} of the next element in the sequence. If there + * is no next element, then return {@code null}. + */ + Object next(); + + /** + * Move to the beginning of the sequence. + * + * @return The {@code Object} of the first element in the sequence. If it + * is empty, then return {@code null}. + */ + Object start(); + + /** + * Return the current element {@code Object} content. + * + * @return The {@code Object} at current position. + */ + Object currentElement(); + + /** + * Return the total element count in the sequence. + * + * @return The total element count. + */ + int elementCount(); + + /** + * A method to allow the difference algorithm to test whether the {@code obj1} + * and {@code obj2} in the {@code Iterator} are considered equal. + * + * <p>As not every {@code Object} in the {@code Iterator} can implement its + * own equal method, with this equivalent method, we can allow flexibility + * for the {@code Iterator} to choose a custom way to compare two objects. + * Two objects can even be compared based on the position in the + * {@code Iterator} rather than by the content via this option. + * + * @param obj1 The first {@code Object} + * @param obj2 The second {@code Object}. + * + * @return {@code true} if equal, {@code false} otherwise. + */ + boolean equivalent(Object obj1, Object obj2); + + /** + * A method to force the {@code Iterator} to traverse the tree again to + * refresh the content. + * + * <p>It is used mainly for {@code Iterator} objects which take a snapshot + * instead of dynamically traversing the tree. The current position will + * be set to the beginning.</p> + */ + void refresh(); +} diff --git a/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/MergeAlgorithm.java b/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/MergeAlgorithm.java new file mode 100644 index 000000000..11e337b57 --- /dev/null +++ b/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/MergeAlgorithm.java @@ -0,0 +1,46 @@ +/* + * This file is part of the LibreOffice project. + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. + * + * This file incorporates work covered by the following license notice: + * + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed + * with this work for additional information regarding copyright + * ownership. The ASF licenses this file to you under the Apache + * License, Version 2.0 (the "License"); you may not use this file + * except in compliance with the License. You may obtain a copy of + * the License at http://www.apache.org/licenses/LICENSE-2.0 . + */ + +package org.openoffice.xmerge.merger; + +import org.openoffice.xmerge.MergeException; + +/** + * This is the {@code MergeAlgorithm} interface. + * + * <p>It is an interface so that different merge algorithms may be plugged-in + * to actually merge the diffs back to an original document.</p> + */ +public interface MergeAlgorithm { + + /** + * This method is to merge the difference to an {@code Iterator}. + * + * <p>The original {@code Iterator} will be modified after the call.</p> + * + * @param orgSeq The original sequence which the difference will be + * applied. It will be modified. + * @param modSeq The modified sequence where the difference content + * will be extracted. + * @param differences The {@code Difference} array. + * + * @throws MergeException If an error occurs during the merge. + */ + void applyDifference(Iterator orgSeq, Iterator modSeq, + Difference[] differences) throws MergeException; +}
\ No newline at end of file diff --git a/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/NodeMergeAlgorithm.java b/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/NodeMergeAlgorithm.java new file mode 100644 index 000000000..98a9a8bd1 --- /dev/null +++ b/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/NodeMergeAlgorithm.java @@ -0,0 +1,40 @@ +/* + * This file is part of the LibreOffice project. + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. + * + * This file incorporates work covered by the following license notice: + * + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed + * with this work for additional information regarding copyright + * ownership. The ASF licenses this file to you under the Apache + * License, Version 2.0 (the "License"); you may not use this file + * except in compliance with the License. You may obtain a copy of + * the License at http://www.apache.org/licenses/LICENSE-2.0 . + */ + +package org.openoffice.xmerge.merger; + +import org.w3c.dom.Node; + +/** + * This is an interface for a {@link org.openoffice.xmerge.merger.MergeAlgorithm + * MergeAlgorithm} to merge two {@code Node} objects. + * + * <p>It is an interface so that different merge algorithms may be plugged-in.</p> + */ +public interface NodeMergeAlgorithm { + + /** + * This method is used to merge two given {@code Node} objects. + * + * <p>Note: the original {@code Node} may be modified.</p> + * + * @param originalNode The original {@code Node}. + * @param modifyNode The {@code Node} to be merged. It may be modified. + */ + void merge(Node originalNode, Node modifyNode); +}
\ No newline at end of file diff --git a/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/diff/CellNodeIterator.java b/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/diff/CellNodeIterator.java new file mode 100644 index 000000000..791c809f9 --- /dev/null +++ b/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/diff/CellNodeIterator.java @@ -0,0 +1,96 @@ +/* + * This file is part of the LibreOffice project. + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. + * + * This file incorporates work covered by the following license notice: + * + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed + * with this work for additional information regarding copyright + * ownership. The ASF licenses this file to you under the Apache + * License, Version 2.0 (the "License"); you may not use this file + * except in compliance with the License. You may obtain a copy of + * the License at http://www.apache.org/licenses/LICENSE-2.0 . + */ + +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.converter.xml.OfficeConstants; + +/** + * This is an implementations of the {@code Iterator} interface. + * + * <p>It will traverse the tree and find cell {@code Node} sequences.</p> + * + * <p>Note: Once the XML Tree is parsed, then the {@code Iterator} will be a + * snapshot of that tree. That means even the tree is modified later, then the + * cached paragraph {@code Node} list will not be updated accordingly. For this + * reason and for performance reasons this {@code Iterator} does not support any + * operation methods such as insert, remove or replace. The main purpose of this + * {@code Iterator} is to be used with difference, not with merge.</p> + */ +public final class CellNodeIterator extends NodeIterator { + + // 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}. + * @param node The initial root {@code Node}. + */ + public CellNodeIterator(ConverterCapabilities cc, Node node) { + super(cc, node); + } + + /** + * Overwrite the parent {@code nodeSupported} method. + * + * <p>Only cell {@code Node} objects are supported.</p> + * + * @param node The {@code Node} to check. + * + * @return {@code true} if the {@code Node} is supported, {@code false} + * otherwise. + */ + @Override + protected boolean nodeSupported(Node node) { + + // can use an array later to check all possible tags for + // future expansion + return node.getNodeType() == Node.ELEMENT_NODE && + node.getNodeName().equals(SUPPORTED_TAG1); + } + + @Override + 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/source/xmerge/java/org/openoffice/xmerge/merger/diff/CharArrayLCSAlgorithm.java b/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/diff/CharArrayLCSAlgorithm.java new file mode 100644 index 000000000..9e9eaf369 --- /dev/null +++ b/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/diff/CharArrayLCSAlgorithm.java @@ -0,0 +1,188 @@ +/* + * This file is part of the LibreOffice project. + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. + * + * This file incorporates work covered by the following license notice: + * + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed + * with this work for additional information regarding copyright + * ownership. The ASF licenses this file to you under the Apache + * License, Version 2.0 (the "License"); you may not use this file + * except in compliance with the License. You may obtain a copy of + * the License at http://www.apache.org/licenses/LICENSE-2.0 . + */ + +package org.openoffice.xmerge.merger.diff; + +import java.util.ArrayList; +import org.openoffice.xmerge.merger.Difference; + +/** + * This is an implementations of {@code DiffAlgorithm} interface which will + * difference char arrays. + * + * <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> + */ +public class CharArrayLCSAlgorithm { + + /** + * Return an {@code Difference} array. + * + * <p>This method finds out the difference between two sequences.</p> + * + * @param orgSeq The original sequence. + * @param modSeq The modified (or changed) sequence to compare against + * the original. + * + * @return A {@code Difference} array. + */ + public Difference[] computeDiffs(char[] orgSeq, char[] modSeq) { + + int orgSeqlen = orgSeq.length; + int modSeqlen = modSeq.length; + + // Diff table is used to keep track which element is the same or not + // in those 2 sequences + int[][] diffTable = createDiffTable(orgSeq, modSeq); + + ArrayList<Difference> diffResult = new ArrayList<Difference>(); + + generateResult(diffTable, orgSeqlen, modSeqlen, diffResult); + + // convert the vector to array, it has to do it here as + // generateResult is called recursively + Difference[] diffArray = new Difference[diffResult.size()]; + diffResult.toArray(diffArray); + + return diffArray; + } + + /** + * Create the difference table. + * + * <p>The difference table is used internal to keep track what elements are + * common or different in the two sequences.</p> + * + * @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 needs 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} result vector. + * + * <p>This method will be called recursively to backtrack the difference + * table to get the difference result (and also the LCS).</p> + * + * @param diffTable The difference table containing the {@code Difference} + * result. + * @param i The nth element in original sequence to compare. This + * method is called recursively with {@code i} and + * {@code j} decreased until {@code 0}. + * @param j The nth element in modified sequence to compare. + * @param diffVector A vector to output the {@code Difference} result. + * Can not use a return variable as it is a recursive + * method. The vector will contain {@code Difference} + * objects with operation and positions filled in. + */ + private void generateResult(int[][] diffTable, int i, int j, + ArrayList<Difference> 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/source/xmerge/java/org/openoffice/xmerge/merger/diff/CharacterParser.java b/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/diff/CharacterParser.java new file mode 100644 index 000000000..622fedf9e --- /dev/null +++ b/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/diff/CharacterParser.java @@ -0,0 +1,127 @@ +/* + * This file is part of the LibreOffice project. + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. + * + * This file incorporates work covered by the following license notice: + * + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed + * with this work for additional information regarding copyright + * ownership. The ASF licenses this file to you under the Apache + * License, Version 2.0 (the "License"); you may not use this file + * except in compliance with the License. You may obtain a copy of + * the License at http://www.apache.org/licenses/LICENSE-2.0 . + */ + +package org.openoffice.xmerge.merger.diff; + +import org.w3c.dom.Node; + +import org.openoffice.xmerge.converter.xml.OfficeConstants; + +import java.util.ArrayList; +import java.util.List; + +/** + * This is a parser to return a character array for difference purpose. + * + * <p>It will use depth first search to traverse all the characters inside the + * text {@code Node} under a given {@code Node} (most likely to be a paragraph + * {@code Node}).</p> + * + * <p>Note: Once the XML Tree is parsed, then the {@code Iterator} will be a + * snapshot of that tree. That means even the tree is modified later, then + * the cached paragraph {@code Node} list will not be updated accordingly. For + * this reason and for performance reasons this {@code Iterator} does not + * support any operation methods such as insert, remove or replace. The main + * purpose of this {@code Iterator} is to be used with difference, not with + * merge.</p> + */ +public class CharacterParser { + + private final TextNodeIterator textNodes; + private int currentPosition = 0; + private final List<TextNodeEntry> nodeList_; + private char[] charArray; + + /** + * Standard constructor. + * + * @param node The initial root {@code Node}. + */ + public CharacterParser(Node node) { + textNodes = new TextNodeIterator(node); + nodeList_ = new ArrayList<TextNodeEntry>(); + + parseNodes(); + } + + /** + * Returns the {@code Node} pointer with the given character position. + * + * @return The {@code Node} pointer with the given character position. + */ + public List<TextNodeEntry> 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} entry. + * + * @param textLen The text length. + * @param node The {@code Node}. + */ + 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/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 000000000..a5298df19 --- /dev/null +++ b/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/diff/IteratorLCSAlgorithm.java @@ -0,0 +1,210 @@ +/* + * This file is part of the LibreOffice project. + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. + * + * This file incorporates work covered by the following license notice: + * + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed + * with this work for additional information regarding copyright + * ownership. The ASF licenses this file to you under the Apache + * License, Version 2.0 (the "License"); you may not use this file + * except in compliance with the License. You may obtain a copy of + * the License at http://www.apache.org/licenses/LICENSE-2.0 . + */ + +package org.openoffice.xmerge.merger.diff; + +import java.util.ArrayList; +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} interface. + * + * <p>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.</p> + */ +public class IteratorLCSAlgorithm implements DiffAlgorithm { + + public Difference[] computeDiffs(Iterator orgSeq, Iterator modSeq) { + + int orgSeqlen = orgSeq.elementCount(); + int modSeqlen = modSeq.elementCount(); + + // Diff table is used to keep track which element is the same or not + // in those 2 sequences + int[][] diffTable = createDiffTable(orgSeq, modSeq); + + // debug purpose... + if (Debug.isFlagSet(Debug.INFO)) { + printDiffTable(diffTable); + } + + ArrayList<Difference> diffResult = new ArrayList<Difference>(); + + generateResult(diffTable, orgSeqlen, modSeqlen, diffResult); + + // convert the vector to array, it has to do in here as + // generateResult is called recursively + Difference[] diffArray = new Difference[diffResult.size()]; + diffResult.toArray(diffArray); + + 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++) { + StringBuilder sb = new StringBuilder(); + for (int j = 0; j < diffTable[i].length; j++) { + sb.append(" ").append(diffTable[i][j]).append(" "); + } + Debug.log(Debug.INFO, sb.toString()); + } + } + + /** + * Create the difference table. + * + * <p>The difference table is used internal to keep track what elements are + * common or different in the two sequences.</p> + * + * @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} object result vector. + * + * <p>This method will be called recursively to backtrack the difference + * table to get the difference result (and also the LCS).</p> + * + * @param diffTable The difference table containing the {@code Difference} + * result. + * @param i The nth element in original sequence to compare. This + * method is called recursively with {@code i} and + * {@code j} decreased until {@code 0}. + * @param j The nth element in modified sequence to compare. + * @param diffVector A vector to output the {@code Difference} result. + * Can not use a return variable as it is a recursive + * method. The vector will contain {@code Difference} + * objects with operation and positions fill in. + */ + private void generateResult(int[][] diffTable, + int i, int j, ArrayList<Difference> 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/source/xmerge/java/org/openoffice/xmerge/merger/diff/IteratorRowCompare.java b/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/diff/IteratorRowCompare.java new file mode 100644 index 000000000..ce1644002 --- /dev/null +++ b/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/diff/IteratorRowCompare.java @@ -0,0 +1,229 @@ +/* + * This file is part of the LibreOffice project. + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. + * + * This file incorporates work covered by the following license notice: + * + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed + * with this work for additional information regarding copyright + * ownership. The ASF licenses this file to you under the Apache + * License, Version 2.0 (the "License"); you may not use this file + * except in compliance with the License. You may obtain a copy of + * the License at http://www.apache.org/licenses/LICENSE-2.0 . + */ + +package org.openoffice.xmerge.merger.diff; + +import org.w3c.dom.Node; +import org.w3c.dom.Element; + +import java.util.ArrayList; +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; + +/** + * A very simple and direct difference algorithm for row {@code Node} objects in + * a spreadsheet. + * + * <p>Basically, it will compare objects in sequence and does not look ahead + * (unlike LCS).</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>NOTE: The algorithm will have potential side effect to split rows.</p> + */ + +public class IteratorRowCompare implements DiffAlgorithm { + + /** + * Compute the differences of the given two sequences. + * + * <p>Refer to the class description.</p> + * + * <p>Return an array of {@code Difference} objects. This method finds out + * the difference between two sequences.</p> + * + * @param orgSeq The original sequence. + * @param modSeq The modified (or changed) sequence to compare against + * with the original. + * + * @return An array of Difference objects. + */ + public Difference[] computeDiffs(Iterator orgSeq, Iterator modSeq) { + + ArrayList<Difference> diffVector = new ArrayList<Difference>(); + + // 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.parseInt(orgRowRepeated); + } + if (modRowRepeated.length() > 0) { + modRowNum = Integer.parseInt(modRowRepeated); + } + + // 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.toArray(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/source/xmerge/java/org/openoffice/xmerge/merger/diff/NodeIterator.java b/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/diff/NodeIterator.java new file mode 100644 index 000000000..fe5bfdd08 --- /dev/null +++ b/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/diff/NodeIterator.java @@ -0,0 +1,358 @@ +/* + * This file is part of the LibreOffice project. + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. + * + * This file incorporates work covered by the following license notice: + * + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed + * with this work for additional information regarding copyright + * ownership. The ASF licenses this file to you under the Apache + * License, Version 2.0 (the "License"); you may not use this file + * except in compliance with the License. You may obtain a copy of + * the License at http://www.apache.org/licenses/LICENSE-2.0 . + */ + +package org.openoffice.xmerge.merger.diff; + +import java.util.ArrayList; +import java.util.List; + +import org.openoffice.xmerge.ConverterCapabilities; +import org.openoffice.xmerge.merger.Iterator; +import org.openoffice.xmerge.util.Debug; +import org.openoffice.xmerge.util.Resources; +import org.w3c.dom.NamedNodeMap; +import org.w3c.dom.Node; +import org.w3c.dom.NodeList; + +/** + * This is an implementation of the {@code Iterator} interface. + * + * <p>It will traverse the tree and find {@code Node} sequences.</p> + * + * <p>Note: Once the XML Tree is parsed, then the {@code Iterator} will be a + * snapshot of that tree. That means even the tree is modified later, then the + * cached paragraph {@code Node} list will not be updated accordingly. For this + * reason and for performance reasons this {@code Iterator} does not support any + * operation methods such as insert, remove or replace. The main purpose of this + * {@code Iterator} is to be used with difference, not with merge.</p> + */ +public abstract class NodeIterator implements Iterator { + + private List<Node> nodeList = null; + private int currentPosition = 0; + private final Node root; + private final ConverterCapabilities cc_; + + /** + * Standard constructor. + * + * @param cc The {@code ConverterCapabilities}. + * @param node The initial root {@code Node}. + */ + public NodeIterator(ConverterCapabilities cc, Node node) { + cc_ = cc; + nodeList = new ArrayList<Node>(); + 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; + if (!(obj1 instanceof Node && obj2 instanceof Node)) { + String 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 ArrayList<Node>(); + markTree(root); + currentPosition = 0; + } + + /** + * Used to compare two {@code Node} objects (type/name/value) and all their + * children {@code Node} objects. + * + * @param node1 The first {@code Node} to compare. + * @param node2 The second {@code Node} to compare. + * + * @return {@code true} if {@code Node} is equal, {@code 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} objects. + * + * <p>This method can be intentionally overridden by any class that extend + * from {@code NodeIterator} so that it can have its own children comparison + * if necessary.</p> + * + * @param node1 The first {@code Node} to compare. + * @param node2 The second {@code Node} to compare. + * + * @return {@code true} if children are equal, {@code 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 children + 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} objects. + * + * <p>This method can be intentionally overridden by any class that extends + * from {@code NodeIterator} so that it can have its own attribute comparison. + * </p> + * + * @param node1 The first {@code Node} to compare. + * @param node2 The second {@code Node} to compare. + * + * @return {@code true} if attributes are equal, {@code false} otherwise. + */ + private 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} is supported. + * + * <p>This method can be intentionally overridden by any class that extends + * from {@code NodeIterator} so that it can specify which {@code Node} to + * support.</p> + * + * @param node {@code Node} to check. + * + * @return {@code true} if <code>Node</code> is supported, {@code 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 auxNodeList = node.getChildNodes(); + int nodeListLength = auxNodeList.getLength(); + for (int i = 0; i < nodeListLength; i++) { + markTree(auxNodeList.item(i)); + } + } + else { + Debug.log(Debug.INFO, " [NodeIterator::markTree] Skipping node " + + nodeName); + } + } + } +} diff --git a/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/diff/ObjectArrayIterator.java b/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/diff/ObjectArrayIterator.java new file mode 100644 index 000000000..ecfe89786 --- /dev/null +++ b/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/diff/ObjectArrayIterator.java @@ -0,0 +1,179 @@ +/* + * This file is part of the LibreOffice project. + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. + * + * This file incorporates work covered by the following license notice: + * + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed + * with this work for additional information regarding copyright + * ownership. The ASF licenses this file to you under the Apache + * License, Version 2.0 (the "License"); you may not use this file + * except in compliance with the License. You may obtain a copy of + * the License at http://www.apache.org/licenses/LICENSE-2.0 . + */ + +package org.openoffice.xmerge.merger.diff; + +import org.openoffice.xmerge.merger.Iterator; + +/** + * This is an implementation of the {@code Iterator} interface. + * + * <p>It is based upon a simple {@code Object} array.</p> + * + * <p>Note: this class is not thread safe for performance reasons.</p> + */ +public final class ObjectArrayIterator implements Iterator { + + /** The {@code Object} array. */ + private Object [] objArray; + private int currentPosition; + + /** + * Standard constructor. + * + * @param objArray The {@code Object} 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}. + * + * @param object {@code Object} to replace. + */ + public void replace(Object object) { + objArray[currentPosition] = object; + } + + /** + * Insert {@code Object} after current {@code Object}. + * + * @param object {@code Object} 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} after current {@code Object}. + * + * @param object {@code Object} 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}. + */ + 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 + } +}
\ No newline at end of file diff --git a/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/diff/ParaNodeIterator.java b/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/diff/ParaNodeIterator.java new file mode 100644 index 000000000..0ab96e9b8 --- /dev/null +++ b/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/diff/ParaNodeIterator.java @@ -0,0 +1,69 @@ +/* + * This file is part of the LibreOffice project. + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. + * + * This file incorporates work covered by the following license notice: + * + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed + * with this work for additional information regarding copyright + * ownership. The ASF licenses this file to you under the Apache + * License, Version 2.0 (the "License"); you may not use this file + * except in compliance with the License. You may obtain a copy of + * the License at http://www.apache.org/licenses/LICENSE-2.0 . + */ + +package org.openoffice.xmerge.merger.diff; + +import org.w3c.dom.Node; + +import org.openoffice.xmerge.ConverterCapabilities; +import org.openoffice.xmerge.converter.xml.OfficeConstants; + +/** + * This is an implementation of the {@code Iterator} interface. + * + * <p>It will traverse the tree and find the Paragraph/Heading {@code Node} + * sequences.</p> + * + * <p>Note: Once the XML Tree is parsed, then the {@code Iterator} will be a + * snapshot of that tree. That means even the tree is modified later, then the + * cached paragraph {@code Node} list will not be updated accordingly. For this + * reason and for performance reasons this {@code Iterator} does not support any + * operation methods such as insert, remove or replace. The main purpose of this + * {@code Iterator} is to be used with difference, not with merge.</p> + */ +public final class ParaNodeIterator extends NodeIterator { + + /** + * Standard constructor. + * + * @param cc The {@code ConverterCapabilities}. + * @param node The initial root {@code Node}. + */ + 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} to check. + * + * @return {@code true} if the {@code Node} is supported, {@code false} + * otherwise. + */ + @Override + protected boolean nodeSupported(Node node) { + // can use an array later to check all possible tags for + // future expansion + String nodeName = node.getNodeName(); + return node.getNodeType() == Node.ELEMENT_NODE && + (nodeName.equals(OfficeConstants.TAG_PARAGRAPH) || + nodeName.equals(OfficeConstants.TAG_HEADING)); + } +} diff --git a/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/diff/RowIterator.java b/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/diff/RowIterator.java new file mode 100644 index 000000000..972e38802 --- /dev/null +++ b/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/diff/RowIterator.java @@ -0,0 +1,66 @@ +/* + * This file is part of the LibreOffice project. + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. + * + * This file incorporates work covered by the following license notice: + * + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed + * with this work for additional information regarding copyright + * ownership. The ASF licenses this file to you under the Apache + * License, Version 2.0 (the "License"); you may not use this file + * except in compliance with the License. You may obtain a copy of + * the License at http://www.apache.org/licenses/LICENSE-2.0 . + */ + +package org.openoffice.xmerge.merger.diff; + +import org.w3c.dom.Node; + +import org.openoffice.xmerge.ConverterCapabilities; +import org.openoffice.xmerge.converter.xml.OfficeConstants; + +/** + * This is an implementation of the {@code Iterator} interface and extends + * {@code NodeIterator}. + * + * <p>It will traverse the tree and find row sequences.</p> + */ +public final class RowIterator extends NodeIterator { + + // 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}. + * @param node The initial root {@code Node}. + */ + public RowIterator(ConverterCapabilities cc, Node node) { + super(cc, node); + } + + /** + * Overwrite the parent {@code nodeSupported} method. + * + * <p>Only row {@code Node} objects are supported.</p> + * + * @param node {@code Node} to check. + * + * @return {@code true} if the {@code Node} is supported, {@code false} + * otherwise. + */ + @Override + protected boolean nodeSupported(Node node) { + + // can use an array later to check all possible tags for + // future expansion + return node.getNodeType() == Node.ELEMENT_NODE && + node.getNodeName().equals(OfficeConstants.TAG_TABLE_ROW); + } +}
\ No newline at end of file diff --git a/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/diff/TextNodeEntry.java b/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/diff/TextNodeEntry.java new file mode 100644 index 000000000..cbfb9e93f --- /dev/null +++ b/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/diff/TextNodeEntry.java @@ -0,0 +1,75 @@ +/* + * This file is part of the LibreOffice project. + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. + * + * This file incorporates work covered by the following license notice: + * + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed + * with this work for additional information regarding copyright + * ownership. The ASF licenses this file to you under the Apache + * License, Version 2.0 (the "License"); you may not use this file + * except in compliance with the License. You may obtain a copy of + * the License at http://www.apache.org/licenses/LICENSE-2.0 . + */ + +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} + * pointer in a text {@code Node}. + * + * <p>It is mainly used for character parser to make a list of text {@code Node} + * cache entries.</p> + */ +public class TextNodeEntry { + + private final int startChar_; + private final int endChar_; + private final Node node_; + + /** + * Constructor + * + * @param startChar The start character position. + * @param endChar The end character position. + * @param node The text {@code Node}. + */ + 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}. + * + * @return The {@code Node}. + */ + public Node node() { + return node_; + } +}
\ No newline at end of file diff --git a/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/diff/TextNodeIterator.java b/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/diff/TextNodeIterator.java new file mode 100644 index 000000000..aa1e14cbb --- /dev/null +++ b/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/diff/TextNodeIterator.java @@ -0,0 +1,69 @@ +/* + * This file is part of the LibreOffice project. + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. + * + * This file incorporates work covered by the following license notice: + * + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed + * with this work for additional information regarding copyright + * ownership. The ASF licenses this file to you under the Apache + * License, Version 2.0 (the "License"); you may not use this file + * except in compliance with the License. You may obtain a copy of + * the License at http://www.apache.org/licenses/LICENSE-2.0 . + */ + +package org.openoffice.xmerge.merger.diff; + +import org.w3c.dom.Node; + +import org.openoffice.xmerge.converter.xml.OfficeConstants; + +/** + * This is an implementation of the {@code Iterator} interface. + * + * <p>It will traverse the tree and find text/space/tab {@code Node} sequences. + * </p> + * + * <p>Note: Once the XML Tree is parsed, then the {@code Iterator} will be a + * snapshot of that tree. That means even the tree is modified later, then the + * cached paragraph {@code Node} list will not be updated accordingly. For this + * reason and for performance reasons this {@code Iterator} does not support + * any operation methods such as insert, remove or replace. The main purpose of + * this {@code Iterator} is to be used with difference, not with merge.</p> + */ +public final class TextNodeIterator extends NodeIterator { + + /** + * Standard constructor. + * + * @param node The initial root {@code Node}. + */ + public TextNodeIterator(Node node) { + super(null, node); + } + + /** + * Overwrite the parent {@code nodeSupported} method. + * + * <p>Only text {@code Node} objects are supported.</p> + * + * @param node {@code Node} to check. + * + * @return {@code true} if the {@code Node} is supported, {@code false} + * otherwise. + */ + @Override + protected boolean nodeSupported(Node node) { + // can use an array later to check all possible tags for + // future expansion + String nodeName = node.getNodeName(); + return node.getNodeType() == Node.TEXT_NODE || + nodeName.equals(OfficeConstants.TAG_SPACE) || + nodeName.equals(OfficeConstants.TAG_TAB_STOP) || + nodeName.equals(OfficeConstants.TAG_LINE_BREAK); + } +} diff --git a/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/diff/package-info.java b/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/diff/package-info.java new file mode 100644 index 000000000..17a66ec6a --- /dev/null +++ b/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/diff/package-info.java @@ -0,0 +1,26 @@ +/* + * This file is part of the LibreOffice project. + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. + * + * This file incorporates work covered by the following license notice: + * + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed + * with this work for additional information regarding copyright + * ownership. The ASF licenses this file to you under the Apache + * License, Version 2.0 (the "License"); you may not use this file + * except in compliance with the License. You may obtain a copy of + * the License at http://www.apache.org/licenses/LICENSE-2.0 . + */ + +/** + * Provides implementations for the {@link org.openoffice.xmerge.merger.Iterator + * Iterator} interface and related support classes. + * + * <p>These are used by the {@link org.openoffice.xmerge.merger.DiffAlgorithm + * DiffAlgorithm} interface.</p> + */ +package org.openoffice.xmerge.merger.diff; diff --git a/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/merge/CharacterBaseParagraphMerge.java b/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/merge/CharacterBaseParagraphMerge.java new file mode 100644 index 000000000..f2db38b65 --- /dev/null +++ b/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/merge/CharacterBaseParagraphMerge.java @@ -0,0 +1,281 @@ +/* + * This file is part of the LibreOffice project. + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. + * + * This file incorporates work covered by the following license notice: + * + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed + * with this work for additional information regarding copyright + * ownership. The ASF licenses this file to you under the Apache + * License, Version 2.0 (the "License"); you may not use this file + * except in compliance with the License. You may obtain a copy of + * the License at http://www.apache.org/licenses/LICENSE-2.0 . + */ + +package org.openoffice.xmerge.merger.merge; + +import java.util.List; +import org.w3c.dom.Node; +import org.openoffice.xmerge.merger.Difference; +import org.openoffice.xmerge.merger.NodeMergeAlgorithm; +import org.openoffice.xmerge.merger.diff.CharacterParser; +import org.openoffice.xmerge.merger.diff.CharArrayLCSAlgorithm; +import org.openoffice.xmerge.merger.diff.TextNodeEntry; +import org.openoffice.xmerge.util.Debug; + +/** + * This is an implementation of the {@code NodeMergeAlgorithm} interface. + * + * <p>It is used to merge two paragraph {@code Node} objects based on character + * comparisons.</p> + */ +public final class CharacterBaseParagraphMerge implements NodeMergeAlgorithm { + + /** + * Merge two paragraphs {@code Node} by using Longest Common Subsequence + * (LCS) character algorithm defined in {@link + * org.openoffice.xmerge.merger.diff.CharArrayLCSAlgorithm + * CharArrayLCSAlgorithm}. + * + * @param orgPara The original paragraph {@code Node}. + * @param modPara The modified paragraph {@code Node}. + */ + public void merge(Node orgPara, Node modPara) { + CharacterParser orgParser = new CharacterParser(orgPara); + CharacterParser modParser = new CharacterParser(modPara); + + char[] orgCharArray = orgParser.getCharArray(); + char[] modCharArray = modParser.getCharArray(); + + CharArrayLCSAlgorithm diffAlgo = new CharArrayLCSAlgorithm(); + + Difference[] diffResult = diffAlgo.computeDiffs(orgCharArray, + modCharArray); + // debug use + System.out.println("Diff Result: "); + for (int i = 0; i < diffResult.length; i++) { + Debug.log(Debug.INFO, diffResult[i].debug()); + } + + applyDifference(orgParser, modParser, diffResult); + } + + private void applyDifference(CharacterParser orgParser, + CharacterParser modParser, + Difference[] diffs) { + + List<TextNodeEntry> orgNodeList = orgParser.getNodeList(); + int diffCount = 0; + int numNode = orgNodeList.size(); + + for (int i = 0; i < numNode; i++) { + + int extraChar = 0; + int orgDiffCount = diffCount; + TextNodeEntry orgTextNode = orgNodeList.get(i); + + Debug.log(Debug.INFO, "checking node " + (i + 1) + " of " + numNode); + + // check any difference in this node and estimate the new char num + for (; diffCount < diffs.length; diffCount++) { + + Debug.log(Debug.INFO, " checking diff " + (diffCount + 1) + + " of " + diffs.length); + Debug.log(Debug.INFO, " OrgPosision <" + + diffs[diffCount].getOrgPosition() + "> diffCount <" + + diffCount + "> orgDiffCount <" + orgDiffCount + ">"); + + // don't need to check and diffs beyond the current node text + // range except the last node + if (diffs[diffCount].getOrgPosition() > orgTextNode.endChar() && + i < numNode - 1) { + Debug.log(Debug.INFO, " breaking!"); + break; + } + + if (diffs[diffCount].getOrgPosition() + >= orgTextNode.startChar()) { + if (diffs[diffCount].getOperation() == Difference.DELETE) { + extraChar--; + } else if (diffs[diffCount].getOperation() + == Difference.ADD) { + extraChar++; + } + + } + } + + Debug.log(Debug.INFO, " final diffCount <" + diffCount + + "> final orgDiffCount <" + orgDiffCount + ">"); + + // will only try to merge if there is a difference in this node + if (diffCount > orgDiffCount) { + + Debug.log(Debug.INFO, " There is a difference, doing merge"); + Debug.log(Debug.INFO, " TextNode name <" + + orgTextNode.node().getNodeName() + ">"); + Debug.log(Debug.INFO, " TextNode value <" + + orgTextNode.node().getNodeValue() + ">"); + Debug.log(Debug.INFO, " TextNode start char <" + + orgTextNode.startChar() + "> TextNode end char <" + + orgTextNode.endChar() + ">"); + Debug.log(Debug.INFO, " extraChar value <" + extraChar + ">"); + + coreMerge(orgDiffCount, diffCount, diffs, + modParser, orgTextNode, extraChar); + } + } + } + + private void coreMerge(int startDiffNum, int endDiffNum, Difference[] diffs, + CharacterParser modParser, + TextNodeEntry orgTextNode, int extraChar) { + + Node orgNode = orgTextNode.node(); + char[] modTextArray = modParser.getCharArray(); + String tmpString; + + // Handle situation where getNodeValue returns null + if (orgNode.getNodeValue() != null) + tmpString = orgNode.getNodeValue(); + else + tmpString = ""; + + char[] orgNodeText = tmpString.toCharArray(); + char[] newNodeText; + + if (orgNodeText.length + extraChar > 0) + newNodeText = new char[orgNodeText.length + extraChar]; + else + newNodeText = new char[0]; + + int orgTextPosition = orgTextNode.startChar(); // used for block copy + int newTextPosition = 0; // used for block copy + int unChangedTextLength = 0; + + char[] cacheCharArray = new char[endDiffNum - startDiffNum]; + int cacheLength = 0; + int lastDiffOperation = Difference.UNCHANGE; + int lastDiffPosition = -1; + + // starting to diff + for (int j = startDiffNum; j < endDiffNum; j++) { + + // copy any contents before the diff + if (diffs[j].getOrgPosition() > orgTextPosition) { + // need to flush first + if (cacheLength > 0) { + System.arraycopy(cacheCharArray, 0, + newNodeText, newTextPosition, cacheLength); + newTextPosition += cacheLength; + + // reset the markers + lastDiffPosition = -1; + lastDiffOperation = Difference.UNCHANGE; + cacheLength = 0; + } + + // find out the length how many characters are + // untouched by the diff + unChangedTextLength = diffs[j].getOrgPosition() - + orgTextPosition; + System.arraycopy(orgNodeText, + orgTextPosition - orgTextNode.startChar(), + newNodeText, newTextPosition, + unChangedTextLength); + orgTextPosition += unChangedTextLength; + newTextPosition += unChangedTextLength; + } + + // for any deleted characters, just skip without copy + // but still need to take care the cached characters + if (diffs[j].getOperation() == Difference.DELETE) { + orgTextPosition++; + + // flush out the cache and copy the content to new Text + if (cacheLength > 0) { + System.arraycopy(cacheCharArray, 0, + newNodeText, newTextPosition, cacheLength); + newTextPosition += cacheLength; + + // reset the markers + lastDiffPosition = -1; + lastDiffOperation = Difference.UNCHANGE; + cacheLength = 0; + } + + continue; + + // check whether we should flush the cache. + // For changed diffs, only continuous changes can be cached + // For Add diffs, only same insertion point can be cached + // and for both changed/add diffs, need to have same operation + // as last cached diffs. + + } else { + if (lastDiffOperation != diffs[j].getOperation() || + (diffs[j].getOperation() == Difference.CHANGE && + diffs[j].getOrgPosition() != lastDiffPosition + 1) || + (diffs[j].getOperation() == Difference.ADD && + diffs[j].getOrgPosition() != lastDiffPosition)) { + + // flush the cache + if (cacheLength > 0) { + System.arraycopy(cacheCharArray, 0, newNodeText, + newTextPosition, cacheLength); + newTextPosition += cacheLength; + + // reset the markers + cacheLength = 0; + } + } + + // add the diffs to the cache, now the diffs will be either + // a new 'changed' char or is an adjacent following change of + // last difference + cacheCharArray[cacheLength] = + modTextArray[diffs[j].getModPosition()]; + cacheLength++; + lastDiffOperation = diffs[j].getOperation(); + lastDiffPosition = diffs[j].getOrgPosition(); + + // need to increment the original text position + // after we cached it + if (lastDiffOperation == Difference.CHANGE) { + orgTextPosition++; + } + } + } + + // flush any contents remaining in the cache + if (cacheLength > 0) { + System.arraycopy(cacheCharArray, 0, newNodeText, + newTextPosition, cacheLength); + newTextPosition += cacheLength; + // no need to reset any cache-related info as this is a last flush + } + + // copy any contents after all the diffs + int orgStartPosition = orgTextNode.startChar(); + if (orgNodeText.length + orgStartPosition > orgTextPosition) { + unChangedTextLength = orgNodeText.length + orgStartPosition + - orgTextPosition; + System.arraycopy(orgNodeText, orgTextPosition - orgStartPosition, + newNodeText, newTextPosition, + unChangedTextLength); + } + + // set the text to the original node if there are any diffs processed. + // can't use newNodeText.length to check as even it is empty, we may + // process a whole bunch of deletion already (i.e. the whole + // orgNodeText deleted). + if (endDiffNum > startDiffNum) { + String newString = new String(newNodeText); + orgNode.setNodeValue(newString); + } + } +} diff --git a/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/merge/DocumentMerge.java b/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/merge/DocumentMerge.java new file mode 100644 index 000000000..2c208dba0 --- /dev/null +++ b/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/merge/DocumentMerge.java @@ -0,0 +1,218 @@ +/* + * This file is part of the LibreOffice project. + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. + * + * This file incorporates work covered by the following license notice: + * + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed + * with this work for additional information regarding copyright + * ownership. The ASF licenses this file to you under the Apache + * License, Version 2.0 (the "License"); you may not use this file + * except in compliance with the License. You may obtain a copy of + * the License at http://www.apache.org/licenses/LICENSE-2.0 . + */ + +package org.openoffice.xmerge.merger.merge; + +import org.w3c.dom.Element; +import org.w3c.dom.Node; + +import org.openoffice.xmerge.ConverterCapabilities; +import org.openoffice.xmerge.MergeException; +import org.openoffice.xmerge.merger.MergeAlgorithm; +import org.openoffice.xmerge.merger.NodeMergeAlgorithm; +import org.openoffice.xmerge.merger.Iterator; +import org.openoffice.xmerge.merger.Difference; +import org.openoffice.xmerge.util.XmlUtil; + +/** + * This is an implementation of the {@code MergeAlgorithm} interface. + * + * <p>This class will merge two {@code Document} classes. It utilizes the + * appropriate class which implements {@link + * org.openoffice.xmerge.merger.NodeMergeAlgorithm NodeMergeAlgorithm} to + * perform the merge.</p> + */ +public class DocumentMerge implements MergeAlgorithm { + + private final NodeMergeAlgorithm subDocumentMerge; + + /** The capabilities of this converter. */ + protected ConverterCapabilities cc_; + + /** + * Constructor. + * + * @param cc The {@code ConverterCapabilities}. + * @param merge The {@code NodeMergeAlgorithm}. + */ + public DocumentMerge(ConverterCapabilities cc, NodeMergeAlgorithm merge) { + cc_ = cc; + subDocumentMerge = merge; + } + + public void applyDifference(Iterator orgSeq, Iterator modSeq, + Difference[] differences) throws MergeException { + + // a quick test whether the differences array is in ascending order + int currentPosition = -1; + boolean haveDeleteOperation = false; + + for (Difference difference : differences) { + if (difference.getOrgPosition() > currentPosition) { + currentPosition = difference.getOrgPosition(); + haveDeleteOperation = difference.getOperation() == Difference.DELETE; + } else if (difference.getOrgPosition() == currentPosition) { + if (difference.getOperation() == Difference.DELETE) { + haveDeleteOperation = true; + } else if (difference.getOperation() == Difference.ADD && + haveDeleteOperation) { + throw new MergeException( + "Differences array is not sorted. Delete before Add"); + } + } else { + throw new MergeException("Differences array need to be sorted."); + } + } + + // reset sequence counters + orgSeq.start(); + int orgSeqCounter = 0; + + modSeq.start(); + int modSeqCounter = 0; + + // check for each diff unit in the diff array to apply the diff + for (Difference currentDiff : differences) { + + int operation = currentDiff.getOperation(); + + switch (operation) { + + case Difference.DELETE: + // loop through the original sequence up to the expected + // position. note that we use delta (see above comment) + // also. we will just continue the counter without reset it. + for (; + orgSeqCounter < currentDiff.getOrgPosition(); + orgSeqCounter++, orgSeq.next()) { + // empty + } + + // remove the Node. note that it will NOT affect the + // iterator sequence as ParaNodeIterator is a static one. + removeNode((Node)(orgSeq.currentElement())); + + break; + + // if it's an add operation, then get content from original seq + case Difference.ADD: + // loop through the modified sequence up to the expected + // position to get the content. As we don't need to modify + // the sequence. we don't need to use delta to do adjustment. + for (; + modSeqCounter < currentDiff.getModPosition(); + modSeqCounter++, modSeq.next()) { + // empty + } + + for (; + orgSeqCounter < currentDiff.getOrgPosition(); + orgSeqCounter++, orgSeq.next()) { + // empty + } + + if (orgSeqCounter > orgSeq.elementCount() - 1) { + // append the element to the end of the original sequence + appendNode((Node)(orgSeq.currentElement()), + (Node)(modSeq.currentElement())); + } else { + // insert the element BEFORE the current element + insertNode((Node)(orgSeq.currentElement()), + (Node)(modSeq.currentElement())); + } + + break; + + case Difference.CHANGE: + for (; + modSeqCounter < currentDiff.getModPosition(); + modSeqCounter++, modSeq.next()) { + // empty + } + + for (; + orgSeqCounter < currentDiff.getOrgPosition(); + orgSeqCounter++, orgSeq.next()) { + // empty + } + + if (subDocumentMerge == null) { + // use a simple replace if no row merge algorithm supply + replaceElement((Element)orgSeq.currentElement(), + (Element)modSeq.currentElement()); + } else { + subDocumentMerge.merge((Element)orgSeq.currentElement(), + (Element)modSeq.currentElement()); + + } + break; + + default: + break; + } + } + } + + /** + * Removes the specified {@code Node}. + * + * @param node {@code Node} to remove. + */ + protected void removeNode(Node node) { + + Node parent = node.getParentNode(); + parent.removeChild(node); + } + + /** + * Appends {@code Node} after the specified {@code Node}. + * + * @param oldNode {@code Node} to append after. + * @param newNode {@code Node} to append. + */ + private void appendNode(Node oldNode, Node newNode) { + Node clonedNode = XmlUtil.deepClone(oldNode, newNode); + Node parent = oldNode.getParentNode(); + parent.appendChild(clonedNode); + } + + /** + * Insert {@code Node} before the specified {@code Node}. + * + * @param oldNode {@code Node} to insert before. + * @param newNode {@code Node} to insert. + */ + private void insertNode(Node oldNode, Node newNode) { + Node clonedNode = XmlUtil.deepClone(oldNode, newNode); + Node parent = oldNode.getParentNode(); + parent.insertBefore(clonedNode, oldNode); + } + + /** + * Replace <code>Element</code>. + * + * @param currElem {@code Element} to be replaced. + * @param newElem {@code Element} to replace. + */ + private void replaceElement(Element currElem, Element newElem) { + + Node clonedNode = XmlUtil.deepClone(currElem, newElem); + Node parent = currElem.getParentNode(); + parent.replaceChild(clonedNode, currElem); + } +}
\ No newline at end of file diff --git a/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/merge/PositionBaseRowMerge.java b/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/merge/PositionBaseRowMerge.java new file mode 100644 index 000000000..afc03935e --- /dev/null +++ b/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/merge/PositionBaseRowMerge.java @@ -0,0 +1,242 @@ +/* + * This file is part of the LibreOffice project. + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. + * + * This file incorporates work covered by the following license notice: + * + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed + * with this work for additional information regarding copyright + * ownership. The ASF licenses this file to you under the Apache + * License, Version 2.0 (the "License"); you may not use this file + * except in compliance with the License. You may obtain a copy of + * the License at http://www.apache.org/licenses/LICENSE-2.0 . + */ + +package org.openoffice.xmerge.merger.merge; + +import org.w3c.dom.Node; +import org.w3c.dom.Element; +import org.w3c.dom.NodeList; +import org.w3c.dom.NamedNodeMap; + +import org.openoffice.xmerge.ConverterCapabilities; +import org.openoffice.xmerge.merger.Iterator; +import org.openoffice.xmerge.merger.NodeMergeAlgorithm; +import org.openoffice.xmerge.merger.diff.CellNodeIterator; +import org.openoffice.xmerge.converter.xml.OfficeConstants; +import org.openoffice.xmerge.util.XmlUtil; + +/** + * This is an implementation of the {@code NodeMergeAlgorithm} interface. + * + * <p>It is used to merge two rows using a positional comparison base method. + * </p> + */ +public final class PositionBaseRowMerge implements NodeMergeAlgorithm { + + /** The capabilities of this converter. */ + private final ConverterCapabilities cc_; + + /** + * Constructor. + * + * @param cc The {@code ConverterCapabilities}. + */ + public PositionBaseRowMerge(ConverterCapabilities cc) { + cc_ = cc; + } + + public void merge(Node orgRow, Node modRow) { + + Iterator orgCells = new CellNodeIterator(cc_, orgRow); + Iterator modCells = new CellNodeIterator(cc_, modRow); + + mergeCellSequences(orgCells, modCells); + } + + // used to compare the cell 1 by 1 + private void mergeCellSequences(Iterator orgSeq, Iterator modSeq) { + + boolean needMerge = true; + Element orgCell, modCell; + + Object orgSeqObject = orgSeq.start(); + Object modSeqObject = modSeq.start(); + + while (orgSeqObject != null) { + + needMerge = true; + + if (modSeqObject == null) { + // no corresponding cell in the target, empty out the cell + SheetUtil.emptyCell(cc_, (Node)orgSeqObject); + orgSeqObject = orgSeq.next(); + + } else { + + // compare the cell directly + if (!orgSeq.equivalent(orgSeqObject, modSeqObject)) { + + orgCell = (Element)orgSeqObject; + modCell = (Element)modSeqObject; + + // check whether the original cell with multiple column + // if so, need to split one out for merge + String orgColRepeated = orgCell.getAttribute( + OfficeConstants.ATTRIBUTE_TABLE_NUM_COLUMNS_REPEATED); + String modColRepeated = modCell.getAttribute( + OfficeConstants.ATTRIBUTE_TABLE_NUM_COLUMNS_REPEATED); + + int orgColNum = 1; + int modColNum = 1; + + if (orgColRepeated.length() > 0) { + orgColNum = Integer.parseInt(orgColRepeated); + } + if (modColRepeated.length() > 0) { + modColNum = Integer.parseInt(modColRepeated); + } + + // try to find out the common number of repeated cols + if (orgColNum == modColNum) { + orgSeqObject = orgSeq.next(); + modSeqObject = modSeq.next(); + + // cut the original cell into 2 half, first half + // have the repeated attribute = modify cell attr + } else if (orgColNum > modColNum) { + Element orgSplitCell = splitColRepeatedCell( + orgCell, modColNum, + orgColNum - modColNum); + // it may equal after the split! + if (orgSeq.equivalent(orgSplitCell, modCell)) { + needMerge = false; + } + orgCell = orgSplitCell; + modSeqObject = modSeq.next(); + + // cut the modified cell into 2 half, first half + // have the repeated attribute = original cell attr + } else { + Element modSplitCell = splitColRepeatedCell( + modCell, orgColNum, + modColNum - orgColNum); + // it may equal after the split! + if (modSeq.equivalent(orgCell, modSplitCell)) { + needMerge = false; + } + modCell = modSplitCell; + orgSeqObject = orgSeq.next(); + } + + if (needMerge) { + mergeCells(orgCell, modCell); + } + + } else { + // cells are equivalent, move on to next one. + orgSeqObject = orgSeq.next(); + modSeqObject = modSeq.next(); + } // end if-else + } // end if-else + } // end while loop + + // get the one of the original cell, so that the cloned node + // can base it to find the document node + orgCell = (Element)orgSeq.start(); + + // add any extra cells to the original cell sequence. + for (; modSeqObject != null; modSeqObject = modSeq.next()) { + Node clonedNode = XmlUtil.deepClone(orgCell, (Node)modSeqObject); + Node parent = orgCell.getParentNode(); + parent.appendChild(clonedNode); + } + } + + private Element splitColRepeatedCell(Element orgCell, int splitNum, + int orgNum) { + // NOTE: should we really want to do deep clone? + // in most the case, it is an empty cell, 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 splitCell = (Element)(orgCell.cloneNode(true)); + + if (splitNum > 1) { + splitCell.setAttribute( + OfficeConstants.ATTRIBUTE_TABLE_NUM_COLUMNS_REPEATED, + String.valueOf(splitNum)); + } else if (splitNum == 1) { + splitCell.removeAttribute( + OfficeConstants.ATTRIBUTE_TABLE_NUM_COLUMNS_REPEATED); + } + if (orgNum > 1) { + orgCell.setAttribute( + OfficeConstants.ATTRIBUTE_TABLE_NUM_COLUMNS_REPEATED, + String.valueOf(orgNum)); + } else if (orgNum == 1) { + orgCell.removeAttribute( + OfficeConstants.ATTRIBUTE_TABLE_NUM_COLUMNS_REPEATED); + } + + Node parentNode = orgCell.getParentNode(); + parentNode.insertBefore(splitCell, orgCell); + + return splitCell; + } + + private void mergeCells(Element orgCell, Element modCell) { + + // remove all the supported attributes and possible text child for + // string cells + SheetUtil.emptyCell(cc_, orgCell); + + // copy all the supported attributes and possible text child from + // the modified cell + NamedNodeMap attrNodes = modCell.getAttributes(); + + if (attrNodes != null) { + + // copy the first text:p node. As it's not necessary only string + // type cell can have a text:p section. + NodeList paraNodes = + modCell.getElementsByTagName(OfficeConstants.TAG_PARAGRAPH); + + Node firstParaNode = paraNodes.item(0); + + // try to clone the node + if (firstParaNode != null) { + + Node clonedNode = XmlUtil.deepClone(orgCell, firstParaNode); + + // insert as the first child of the original cell + Node firstChild = orgCell.getFirstChild(); + if (firstChild != null) { + orgCell.insertBefore(clonedNode, firstChild); + } else { + orgCell.appendChild(clonedNode); + } + } + + // check all the attributes and copy those we supported in + // converter + // NOTE: for attribute list, refer to section 4.7.2 in specification + int len = attrNodes.getLength(); + + for (int i = 0; i < len; i++) { + Node attr = attrNodes.item(i); + + // copy the supported attrs + if (cc_.canConvertAttribute(OfficeConstants.TAG_TABLE_CELL, + attr.getNodeName())) { + orgCell.setAttribute(attr.getNodeName(), + attr.getNodeValue()); + } + } + } + } +} diff --git a/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/merge/SheetMerge.java b/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/merge/SheetMerge.java new file mode 100644 index 000000000..f21be1591 --- /dev/null +++ b/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/merge/SheetMerge.java @@ -0,0 +1,76 @@ +/* + * This file is part of the LibreOffice project. + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. + * + * This file incorporates work covered by the following license notice: + * + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed + * with this work for additional information regarding copyright + * ownership. The ASF licenses this file to you under the Apache + * License, Version 2.0 (the "License"); you may not use this file + * except in compliance with the License. You may obtain a copy of + * the License at http://www.apache.org/licenses/LICENSE-2.0 . + */ + +package org.openoffice.xmerge.merger.merge; + +import org.w3c.dom.Node; +import org.w3c.dom.NodeList; + +import org.openoffice.xmerge.ConverterCapabilities; +import org.openoffice.xmerge.merger.NodeMergeAlgorithm; + +/** + * This class extends the {@code DocumentMerge} class. + * + * <p>This class will merge two spreadsheet documents.</p> + * + * <p>The main difference between this implementation and {@code DocumentMerge} + * is that this merge will try to maintain unsupported features by examining the + * cell {@code node} objects one by one when it removes a node from the original + * {@code Iterator}.</p> + */ +public final class SheetMerge extends DocumentMerge { + + /** + * Constructor. + * + * @param cc The {@code ConverterCapabilities}. + * @param merge The {@code NodeMergeAlgorithm}. + */ + public SheetMerge(ConverterCapabilities cc, NodeMergeAlgorithm merge) { + super(cc, merge); + } + + /** + * Remove specified {@code Node}. + * + * @param node {@code Node} to remove. + */ + @Override + protected void removeNode(Node node) { + clearRow(node); + } + + /** + * Clear the row corresponding to the {@code Node}. + * + * @param node {@code Node} containing the row to clear. + */ + private void clearRow(Node node) { + NodeList children = node.getChildNodes(); + int numOfChildren = children.getLength(); + + // clear all the cells under the row node but maintain any unsupported + // features + // TODO: we can actually check anything left after the clear up. + // if there is nothing left, then we can even delete the cell nodes + for (int i = 0; i < numOfChildren; i++) { + SheetUtil.emptyCell(cc_, children.item(i)); + } + } +}
\ No newline at end of file diff --git a/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/merge/SheetUtil.java b/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/merge/SheetUtil.java new file mode 100644 index 000000000..2f5a8ebe9 --- /dev/null +++ b/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/merge/SheetUtil.java @@ -0,0 +1,99 @@ +/* + * This file is part of the LibreOffice project. + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. + * + * This file incorporates work covered by the following license notice: + * + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed + * with this work for additional information regarding copyright + * ownership. The ASF licenses this file to you under the Apache + * License, Version 2.0 (the "License"); you may not use this file + * except in compliance with the License. You may obtain a copy of + * the License at http://www.apache.org/licenses/LICENSE-2.0 . + */ + +package org.openoffice.xmerge.merger.merge; + +import org.w3c.dom.Node; +import org.w3c.dom.Element; +import org.w3c.dom.NodeList; +import org.w3c.dom.NamedNodeMap; + +import org.openoffice.xmerge.ConverterCapabilities; +import org.openoffice.xmerge.converter.xml.OfficeConstants; + +/** + * Utility methods to handle sheet XML tree. + */ +public class SheetUtil { + + /** + * Empty the content of a cell value. + * + * <p>This includes the following:</p> + * + * <ul> + * <li> + * Remove all of the supported attributes. + * </li><li> + * Remove the first <i>text:p</i> {@code Node} for most of the cells. + * </li> + * </ul> + * + * @param cc The {@code ConverterCapabilities}. + * @param node The {@code Node}. + */ + public static void emptyCell(ConverterCapabilities cc, Node node) { + + NamedNodeMap attrNodes = node.getAttributes(); + + if (attrNodes != null) { + + // empty the first text:p node. + // Note: it's not necessary only string type cell contain text:p + // basically, all different type of cell will contain one + Element cell = (Element)node; + + // get the paragraph node list + NodeList paraNodes = + cell.getElementsByTagName(OfficeConstants.TAG_PARAGRAPH); + + Node firstParaNode = paraNodes.item(0); + + // remove the first paragraph element node + if (firstParaNode != null) { + Node parent = firstParaNode.getParentNode(); + parent.removeChild(firstParaNode); + } + + // check all the attributes and remove those we supported in + // converter + // NOTE: for attribute list, refer to section 4.7.2 in specification + int len = attrNodes.getLength(); + + for (int i = 0; i < len; ) { + Node attr = attrNodes.item(i); + + // when we hit the end of the attribute nodes, return + // it may happen sooner as we keep on removing nodes + if (attr == null) { + break; + } + // remove the supported attr except columns repeated attribute + if (cc.canConvertAttribute(OfficeConstants.TAG_TABLE_CELL, + attr.getNodeName()) && + !attr.getNodeName().equals( + OfficeConstants.ATTRIBUTE_TABLE_NUM_COLUMNS_REPEATED)) { + + attrNodes.removeNamedItem(attr.getNodeName()); + } else { + i++; + } + } + } + } +}
\ No newline at end of file diff --git a/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/merge/package-info.java b/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/merge/package-info.java new file mode 100644 index 000000000..6f65cb62c --- /dev/null +++ b/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/merge/package-info.java @@ -0,0 +1,25 @@ +/* + * This file is part of the LibreOffice project. + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. + * + * This file incorporates work covered by the following license notice: + * + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed + * with this work for additional information regarding copyright + * ownership. The ASF licenses this file to you under the Apache + * License, Version 2.0 (the "License"); you may not use this file + * except in compliance with the License. You may obtain a copy of + * the License at http://www.apache.org/licenses/LICENSE-2.0 . + */ + +/** + * Provides implementations for the {@link + * org.openoffice.xmerge.merger.MergeAlgorithm MergeAlgorithm} interface, the + * {@link org.openoffice.xmerge.merger.NodeMergeAlgorithm NodeMergeAlgorithm} + * interface, and related support classes. + */ +package org.openoffice.xmerge.merger.merge; diff --git a/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/package-info.java b/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/package-info.java new file mode 100644 index 000000000..8b51dcbe7 --- /dev/null +++ b/xmerge/source/xmerge/java/org/openoffice/xmerge/merger/package-info.java @@ -0,0 +1,56 @@ +/* + * This file is part of the LibreOffice project. + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. + * + * This file incorporates work covered by the following license notice: + * + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed + * with this work for additional information regarding copyright + * ownership. The ASF licenses this file to you under the Apache + * License, Version 2.0 (the "License"); you may not use this file + * except in compliance with the License. You may obtain a copy of + * the License at http://www.apache.org/licenses/LICENSE-2.0 . + */ + +/** + * The {@code DiffAlgorithm} and {@code MergeAlgorithm} are used to provide + * the merge capabilities of this project. + * + * <p>Merge is useful when an {@code OfficeDocument} is converted to a + * {@literal "Device"} {@code Document} format, and the {@literal "Device"} + * {@code Document} version is modified. + * Those changes can be merged back into the original {@code OfficeDocument} + * with the merger. The merger is capable of doing this even if the + * {@literal "Device"} format is lossy in comparison to the + * {@code OfficeDocument} format.</p> + * + * <p>The {@code DiffAlgorithm} generates a list of {@code Difference} objects + * that represent the differences between two {@code OfficeDocument} objects. + * It is assumed that one is the original {@code OfficeDocument} object and the + * other is a "lossy" version of the same {@code Document} with edits + * to be merged. Typically the {@literal "lossy"} version is created by + * converting a {@literal "Device"} {@code Document} back into an + * {@code OfficeDocument}.</p> + * + * <p>The {@code MergeAlgorithm} takes the {@code Difference} objects as input, + * and creates a merged {@code OfficeDocument}. + * A merged {@code OfficeDocument} has the following features:</p> + * + * <ul> + * <li>Tags in the {@code OfficeDocument} that are not supported in the device + * format are not altered or removed.</li> + * <li>Changes made to the device format are merged back into the + * {@code OfficeDocument} in the location determined by the + * {@code DiffAlgorithm}.</li> + * </ul> + * + * <p>Each converter provides an implementation of the {@link + * org.openoffice.xmerge.ConverterCapabilities ConverterCapabilities} which + * specifies which {@code OfficeDocument} tags are supported for the device + * format.</p> + */ +package org.openoffice.xmerge.merger; |