KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > eclipse > compare > rangedifferencer > RangeComparatorLCS


1 /*******************************************************************************
2  * Copyright (c) 2006, 2007 IBM Corporation and others.
3  * All rights reserved. This program and the accompanying materials
4  * are made available under the terms of the Eclipse Public License v1.0
5  * which accompanies this distribution, and is available at
6  * http://www.eclipse.org/legal/epl-v10.html
7  *
8  * Contributors:
9  * IBM Corporation - initial API and implementation
10  *******************************************************************************/
11 package org.eclipse.compare.rangedifferencer;
12
13 import java.util.ArrayList JavaDoc;
14 import java.util.List JavaDoc;
15
16 import org.eclipse.compare.internal.CompareMessages;
17 import org.eclipse.compare.internal.LCS;
18 import org.eclipse.core.runtime.*;
19
20 /* package */ class RangeComparatorLCS extends LCS {
21     
22     private final IRangeComparator comparator1, comparator2;
23     private int[][] lcs;
24     
25     public static RangeDifference[] findDifferences(IProgressMonitor pm, IRangeComparator left, IRangeComparator right) {
26         RangeComparatorLCS lcs = new RangeComparatorLCS(left, right);
27         SubMonitor monitor = SubMonitor.convert(pm, CompareMessages.RangeComparatorLCS_0, 100);
28         try {
29             lcs.longestCommonSubsequence(monitor.newChild(95));
30             return lcs.getDifferences(monitor.newChild(5));
31         } finally {
32             if (pm != null)
33                 pm.done();
34         }
35     }
36     
37     public RangeComparatorLCS(IRangeComparator comparator1, IRangeComparator comparator2) {
38         this.comparator1 = comparator1;
39         this.comparator2 = comparator2;
40     }
41     
42     protected int getLength1() {
43         return comparator1.getRangeCount();
44     }
45
46     protected int getLength2() {
47         return comparator2.getRangeCount();
48     }
49
50     protected void initializeLcs(int lcsLength) {
51         lcs = new int[2][lcsLength];
52     }
53
54     protected boolean isRangeEqual(int i1, int i2) {
55         return comparator1.rangesEqual(i1, comparator2, i2);
56     }
57
58     protected void setLcs(int sl1, int sl2) {
59         // Add one to the values so that 0 can mean that the slot is empty
60 lcs[0][sl1] = sl1 + 1;
61         lcs[1][sl1] = sl2 + 1;
62     }
63     
64     public RangeDifference[] getDifferences(SubMonitor subMonitor) {
65         try {
66             List JavaDoc differences = new ArrayList JavaDoc();
67             int length = getLength();
68             if (length == 0) {
69                 differences.add(new RangeDifference(RangeDifference.CHANGE, 0, comparator2.getRangeCount(), 0, comparator1.getRangeCount()));
70             } else {
71                 subMonitor.beginTask(null, length);
72                 int index1, index2;
73                 index1 = index2 = 0;
74                 int l1, l2;
75                 int s1 = -1;
76                 int s2 = -1;
77                 while(index1 < lcs[0].length && index2 < lcs[1].length) {
78                     // Move both LCS lists to the next occupied slot
79 while ((l1= lcs[0][index1]) == 0) {
80                         index1++;
81                         if (index1 >= lcs[0].length)
82                             break;
83                     }
84                     if (index1 >= lcs[0].length)
85                         break;
86                     while ((l2= lcs[1][index2]) == 0) {
87                         index2++;
88                         if (index2 >= lcs[1].length)
89                             break;
90                     }
91                     if (index2 >= lcs[1].length)
92                         break;
93                     // Convert the entry to an array index (see setLcs(int, int))
94 int end1 = l1 - 1;
95                     int end2 = l2 - 1;
96                     if (s1 == -1 && (end1 != 0 || end2 != 0)) {
97                         // There is a diff at the beginning
98 // TODO: We need to conform that this is the proper order
99 differences.add(new RangeDifference(RangeDifference.CHANGE, 0, end2, 0, end1));
100                     } else if (end1 != s1 + 1 || end2 != s2 + 1) {
101                         // A diff was found on one of the sides
102 int leftStart = s1 + 1;
103                         int leftLength = end1 - leftStart;
104                         int rightStart = s2 + 1;
105                         int rightLength = end2 - rightStart;
106                         // TODO: We need to conform that this is the proper order
107 differences.add(new RangeDifference(RangeDifference.CHANGE, rightStart, rightLength, leftStart, leftLength));
108                     }
109                     s1 = end1;
110                     s2 = end2;
111                     index1++;
112                     index2++;
113                     worked(subMonitor, 1);
114                 }
115                 if (s1 != -1 && (s1 + 1 < comparator1.getRangeCount() || s2 + 1 < comparator2.getRangeCount())) {
116                     // TODO: we need to find the proper way of representing an append
117 int leftStart = s1 < comparator1.getRangeCount() ? s1 + 1 : s1;
118                     int rightStart = s2 < comparator2.getRangeCount() ? s2 + 1 : s2;
119                     // TODO: We need to conform that this is the proper order
120 differences.add(new RangeDifference(RangeDifference.CHANGE, rightStart, comparator2.getRangeCount() - (s2 + 1), leftStart, comparator1.getRangeCount() - (s1 + 1)));
121                 }
122                 
123             }
124             return (RangeDifference[]) differences.toArray(new RangeDifference[differences.size()]);
125         } finally {
126             subMonitor.done();
127         }
128     }
129     
130     private void worked(SubMonitor subMonitor, int work) {
131         if (subMonitor.isCanceled())
132             throw new OperationCanceledException();
133         subMonitor.worked(work);
134     }
135
136 }
137
Popular Tags