LibreOffice Module xmerge (master)  1
CharArrayLCSAlgorithm.java
Go to the documentation of this file.
1 /*
2  * This file is part of the LibreOffice project.
3  *
4  * This Source Code Form is subject to the terms of the Mozilla Public
5  * License, v. 2.0. If a copy of the MPL was not distributed with this
6  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
7  *
8  * This file incorporates work covered by the following license notice:
9  *
10  * Licensed to the Apache Software Foundation (ASF) under one or more
11  * contributor license agreements. See the NOTICE file distributed
12  * with this work for additional information regarding copyright
13  * ownership. The ASF licenses this file to you under the Apache
14  * License, Version 2.0 (the "License"); you may not use this file
15  * except in compliance with the License. You may obtain a copy of
16  * the License at http://www.apache.org/licenses/LICENSE-2.0 .
17  */
18 
19 package org.openoffice.xmerge.merger.diff;
20 
21 import java.util.ArrayList;
23 
32 public class CharArrayLCSAlgorithm {
33 
45  public Difference[] computeDiffs(char[] orgSeq, char[] modSeq) {
46 
47  int orgSeqlen = orgSeq.length;
48  int modSeqlen = modSeq.length;
49 
50  // Diff table is used to keep track which element is the same or not
51  // in those 2 sequences
52  int[][] diffTable = createDiffTable(orgSeq, modSeq);
53 
54  ArrayList<Difference> diffResult = new ArrayList<Difference>();
55 
56  generateResult(diffTable, orgSeqlen, modSeqlen, diffResult);
57 
58  // convert the vector to array, it has to do it here as
59  // generateResult is called recursively
60  Difference[] diffArray = new Difference[diffResult.size()];
61  diffResult.toArray(diffArray);
62 
63  return diffArray;
64  }
65 
77  private int[][] createDiffTable(char[] orgSeq, char[] modSeq) {
78  int orgSeqlen = orgSeq.length + 1;
79  int modSeqlen = modSeq.length + 1;
80  int[][] diffTable;
81 
82  // initialize the diffTable (it needs to be 1 row/col bigger
83  // than the original str)
84  diffTable = new int[orgSeqlen][];
85  for (int i = 0; i < orgSeqlen; i++) {
86  diffTable[i] = new int[modSeqlen];
87  }
88 
89  // compute the diff Table using LCS algorithm, refer to the book
90  // mentioned at the top of the program
91  for (int i = 1; i < orgSeqlen; i++) {
92  for (int j = 1; j < modSeqlen; j++) {
93 
94  if (orgSeq[i-1] == modSeq[j-1]) {
95  diffTable[i][j] = diffTable[i-1][j-1]+1;
96  } else {
97  if (diffTable[i-1][j] >= diffTable[i][j-1]) {
98  diffTable[i][j] = diffTable[i-1][j];
99  } else {
100  diffTable[i][j] = diffTable[i][j-1];
101  }
102  }
103  }
104  }
105 
106  return diffTable;
107  }
108 
126  private void generateResult(int[][] diffTable, int i, int j,
127  ArrayList<Difference> diffVector) {
128 
129  // handle the first element
130  if (i == 0 || j == 0) {
131  if (i == 0 && j == 0) {
132  // return
133  } else if (j == 0) {
134  for (int cnt = 0; cnt < i; cnt++) {
135  Difference diff =
136  new Difference(Difference.DELETE, cnt, j);
137  diffVector.add(diff);
138  }
139  } else {
140  for (int cnt = 0; cnt < j; cnt++) {
141  Difference diff =
142  new Difference(Difference.ADD, i, cnt);
143  diffVector.add(diff);
144  }
145  }
146  return;
147  }
148 
149  // for the detail of this algorithm, refer to the book mentioned on
150  // the top and page 317 and 318.
151  if ((diffTable[i-1][j-1] == diffTable[i][j] -1) &&
152  (diffTable[i-1][j-1] == diffTable[i-1][j]) &&
153  (diffTable[i-1][j-1] == diffTable[i][j-1])) {
154 
155  // the element of ith and jth in org and mod sequence is the same
156  generateResult(diffTable, i-1, j-1, diffVector);
157  } else {
158  if (diffTable[i-1][j] > diffTable[i][j-1]) {
159 
160  // recursively call first, then add the result so that
161  // the beginning of the diffs will be stored first
162  generateResult(diffTable, i-1, j, diffVector);
163 
164  Difference diff =
165  new Difference(Difference.DELETE, i-1, j);
166  diffVector.add(diff);
167  } else if (diffTable[i-1][j] < diffTable[i][j-1]) {
168 
169  // recursively call first, then add the result so that
170  // the beginning of the diffs will be stored first
171  generateResult(diffTable, i, j-1, diffVector);
172 
173  Difference diff =
174  new Difference(Difference.ADD, i, j-1);
175  diffVector.add(diff);
176  } else { // diffTable[i-1][j] == diffTable[i][j-1]
177  // recursively call first, then add the result so that
178  // the beginning of the diffs will be stored first
179  generateResult(diffTable, i-1, j-1, diffVector);
180 
181  Difference diff =
182  new Difference(Difference.CHANGE, i-1, j-1);
183  diffVector.add(diff);
184 
185  }
186  }
187  }
188 }
int[][] createDiffTable(char[] orgSeq, char[] modSeq)
Create the difference table.
void generateResult(int[][] diffTable, int i, int j, ArrayList< Difference > diffVector)
Generate the.
static final int DELETE
Delete operation.
Definition: Difference.java:33
static final int CHANGE
Change operation.
Definition: Difference.java:36
exports com.sun.star. java
int i
Difference[] computeDiffs(char[] orgSeq, char[] modSeq)
Return an.
Provides interfaces for converting between two.
Definition: Convert.java:19
static final int ADD
Add operation.
Definition: Difference.java:30