Skip to main content
aboutsummaryrefslogtreecommitdiffstats
blob: 07d8dd033454208bf66d87cf85646bd7238e094c (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
/*******************************************************************************
 * Copyright (c) 2006, 2011 IBM Corporation and others.
 *
 * This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License 2.0
 * which accompanies this distribution, and is available at
 * https://www.eclipse.org/legal/epl-2.0/
 *
 * SPDX-License-Identifier: EPL-2.0
 *
 * Contributors:
 *     IBM Corporation - initial API and implementation
 *******************************************************************************/
package org.eclipse.compare.internal.core;

import java.util.ArrayList;
import java.util.List;


public class TextLineLCS extends LCS {

	private final TextLine[] lines1;
	private final TextLine[] lines2;
	private TextLine[][] lcs;

	public TextLineLCS(TextLine[] lines1, TextLine[] lines2) {
		this.lines1 = lines1;
		this.lines2 = lines2;
	}

	public TextLine[][] getResult() {
		int length = getLength();
		if (length == 0)
			return new TextLine[2][0];
		TextLine[][] result = new TextLine[2][];

		// compact and shift the result
		result[0] = compactAndShiftLCS(this.lcs[0], length, this.lines1);
		result[1] = compactAndShiftLCS(this.lcs[1], length, this.lines2);

		return result;
	}

	@Override
	protected int getLength2() {
		return this.lines2.length;
	}

	@Override
	protected int getLength1() {
		return this.lines1.length;
	}

	@Override
	protected boolean isRangeEqual(int i1, int i2) {
		return this.lines1[i1].sameText(this.lines2[i2]);
	}

	@Override
	protected void setLcs(int sl1, int sl2) {
		this.lcs[0][sl1] = this.lines1[sl1];
		this.lcs[1][sl1] = this.lines2[sl2];
	}

	@Override
	protected void initializeLcs(int length) {
		this.lcs = new TextLine[2][length];
	}

	/**
	 * This method takes an lcs result interspersed with nulls, compacts it and
	 * shifts the LCS chunks as far towards the front as possible. This tends to
	 * produce good results most of the time.
	 *
	 * TODO: investigate what to do about comments. shifting either up or down
	 * hurts them
	 *
	 * @param lcsSide A subsequence of original, presumably it is the LCS of it and
	 *            some other collection of lines
	 * @param len The number of non-null entries in lcs
	 * @param original The original sequence of lines of which lcs is a
	 *            subsequence
	 *
	 * @return The subsequence lcs compacted and chunks shifted towards the
	 *         front
	 */
	private TextLine[] compactAndShiftLCS(TextLine[] lcsSide, int len,
			TextLine[] original) {
		TextLine[] result = new TextLine[len];

		if (len == 0) {
			return result;
		}

		int j = 0;

		while (lcsSide[j] == null) {
			j++;
		}

		result[0] = lcsSide[j];
		j++;

		for (int i = 1; i < len; i++) {
			while (lcsSide[j] == null) {
				j++;
			}

			if (original[result[i - 1].lineNumber() + 1].sameText(lcsSide[j])) {
				result[i] = original[result[i - 1].lineNumber() + 1];
			} else {
				result[i] = lcsSide[j];
			}
			j++;
		}

		return result;
	}

	/**
	 * Breaks the given text up into lines and returns an array of TextLine
	 * objects each corresponding to a single line, ordered according to the
	 * line number. That is result[i].lineNumber() == i and is the i'th line in
	 * text (starting from 0) Note: there are 1 more lines than there are
	 * newline characters in text. Corollary 1: if the last character is
	 * newline, the last line is empty Corollary 2: the empty string is 1 line
	 *
	 * @param text The text to extract lines from
	 * @return the array of TextLine object each corresponding to a line of text
	 */
	public static TextLine[] getTextLines(String text) {
		List lines = new ArrayList();
		int begin = 0;
		int end = getEOL(text, 0);
		int lineNum = 0;
		while (end != -1) {
			lines.add(new TextLine(lineNum++, text.substring(begin, end)));
			begin = end + 1;
			end = getEOL(text, begin);
			if (end == begin && text.charAt(begin - 1) == '\r'
					&& text.charAt(begin) == '\n') {
				// we have '\r' followed by '\n', skip it
				begin = end + 1;
				end = getEOL(text, begin);
			}
		}

		/*
		 * this is the last line, no more newline characters, so take the rest
		 * of the string
		 */
		lines.add(new TextLine(lineNum, text.substring(begin)));
		TextLine[] aLines = new TextLine[lines.size()];
		lines.toArray(aLines);
		return aLines;
	}

	/**
	 * Returns the index of the next end of line marker ('\n' or '\r') after
	 * start
	 *
	 * @param text The string to examine
	 * @param start The location in the string to start looking
	 * @return the index such that text.charAt(index) == '\n' or '\r', -1 if not
	 *         found
	 */
	private static int getEOL(String text, int start) {
		int max = text.length();
		for (int i = start; i < max; i++) {
			char c = text.charAt(i);
			if (c == '\n' || c == '\r') {
				return i;
			}
		}
		return -1;
	}

	/* used to store information about a single line of text */
	public static class TextLine {
		private int number; // the line number

		private String text; // the actual text

		public TextLine(int number, String text) {
			this.number = number;
			this.text = text;
		}

		/**
		 * Compares this TextLine to l and returns true if they have the same
		 * text
		 *
		 * @param l the TextLine to compare to
		 * @return true if this and l have the same text
		 */
		public boolean sameText(TextLine l) {
			// compare the hashCode() first since that is much faster and most
			// of the time the text lines won't match
			return this.text.hashCode() == l.text.hashCode() && l.text.equals(this.text);
		}

		/**
		 * Returns the line number of this line
		 *
		 * @return the line number
		 */
		public int lineNumber() {
			return this.number;
		}

		@Override
		public String toString() {
			return "" + this.number + " " + this.text + "\n"; //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$
		}
	}
}

Back to the top