TextLineLCS


1   /*******************************************************************************
2    * Copyright (c) 2006 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.internal;
12  
13  import java.util.ArrayList  ;
14  import java.util.List  ;
15  
16  
17  public class TextLineLCS extends LCS {
18  
19      private final TextLine[] lines1;
20      private final TextLine[] lines2;
21      private TextLine[][] lcs;
22  
23      public TextLineLCS(TextLine[] lines1, TextLine[] lines2) {
24          this.lines1 = lines1;
25          this.lines2 = lines2;
26      }
27  
28      public TextLine[][] getResult() {
29          int length = getLength();
30          if (length == 0)
31              return new TextLine[2][0];
32          TextLine[][] result = new TextLine[2][];
33  
34          // compact and shift the result
35          result[0] = compactAndShiftLCS(lcs[0], length, lines1);
36          result[1] = compactAndShiftLCS(lcs[1], length, lines2);
37  
38          return result;
39      }
40  
41      protected int getLength2() {
42          return lines2.length;
43      }
44  
45      protected int getLength1() {
46          return lines1.length;
47      }
48      
49      protected boolean isRangeEqual(int i1, int i2) {
50          return lines1[i1].sameText(lines2[i2]);
51      }
52      
53      protected void setLcs(int sl1, int sl2) {
54          lcs[0][sl1] = lines1[sl1];
55          lcs[1][sl1] = lines2[sl2];
56      }
57      
58      protected void initializeLcs(int length) {
59          lcs = new TextLine[2][length];
60      }
61      
62      /**
63       * This method takes an lcs result interspersed with nulls, compacts it and
64       * shifts the LCS chunks as far towards the front as possible. This tends to
65       * produce good results most of the time.
66       * 
67       * TODO: investigate what to do about comments. shifting either up or down
68       * hurts them
69       * 
70       * @param lcsSide A subsequence of original, presumably it is the LCS of it and
71       *            some other collection of lines
72       * @param len The number of non-null entries in lcs
73       * @param original The original sequence of lines of which lcs is a
74       *            subsequence
75       * 
76       * @return The subsequence lcs compacted and chunks shifted towards the
77       *         front
78       */
79      private TextLine[] compactAndShiftLCS(TextLine[] lcsSide, int len,
80              TextLine[] original) {
81          TextLine[] result = new TextLine[len];
82  
83          if (len == 0) {
84              return result;
85          }
86  
87          int j = 0;
88  
89          while (lcsSide[j] == null) {
90              j++;
91          }
92  
93          result[0] = lcsSide[j];
94          j++;
95  
96          for (int i = 1; i < len; i++) {
97              while (lcsSide[j] == null) {
98                  j++;
99              }
100 
101             if (original[result[i - 1].lineNumber() + 1].sameText(lcsSide[j])) {
102                 result[i] = original[result[i - 1].lineNumber() + 1];
103             } else {
104                 result[i] = lcsSide[j];
105             }
106             j++;
107         }
108 
109         return result;
110     }
111     
112     /**
113      * Breaks the given text up into lines and returns an array of TextLine
114      * objects each corresponding to a single line, ordered according to the
115      * line number. That is result[i].lineNumber() == i and is the i'th line in
116      * text (starting from 0) Note: there are 1 more lines than there are
117      * newline characters in text. Corollary 1: if the last character is
118      * newline, the last line is empty Corollary 2: the empty string is 1 line
119      * 
120      * @param text The text to extract lines from
121      * @return the array of TextLine object each corresponding to a line of text
122      */
123     public static TextLine[] getTextLines(String   text) {
124         List   lines = new ArrayList  ();
125         int begin = 0;
126         int end = getEOL(text, 0);
127         int lineNum = 0;
128         while (end != -1) {
129             lines.add(new TextLine(lineNum++, text.substring(begin, end)));
130             begin = end + 1;
131             end = getEOL(text, begin);
132             if (end == begin && text.charAt(begin - 1) == '\r'
133                     && text.charAt(begin) == '\n') {
134                 // we have '\r' followed by '\n', skip it
135                 begin = end + 1;
136                 end = getEOL(text, begin);
137             }
138         }
139 
140         /*
141          * this is the last line, no more newline characters, so take the rest
142          * of the string
143          */
144         lines.add(new TextLine(lineNum, text.substring(begin)));
145         TextLine[] aLines = new TextLine[lines.size()];
146         lines.toArray(aLines);
147         return aLines;
148     }
149 
150     /**
151      * Returns the index of the next end of line marker ('\n' or '\r') after
152      * start
153      * 
154      * @param text The string to examine
155      * @param start The location in the string to start looking
156      * @return the index such that text.charAt(index) == '\n' or '\r', -1 if not
157      *         found
158      */
159     private static int getEOL(String   text, int start) {
160         int max = text.length();
161         for (int i = start; i < max; i++) {
162             char c = text.charAt(i);
163             if (c == '\n' || c == '\r') {
164                 return i;
165             }
166         }
167         return -1;
168     }
169 
170     /* used to store information about a single line of text */
171     public static class TextLine {
172         private int number; // the line number
173 
174         private String   text; // the actual text
175 
176         public TextLine(int number, String   text) {
177             this.number = number;
178             this.text = text;
179         }
180 
181         /**
182          * Compares this TextLine to l and returns true if they have the same
183          * text
184          * 
185          * @param l the TextLine to compare to
186          * @return true if this and l have the same text
187          */
188         public boolean sameText(TextLine l) {
189             // compare the hashCode() first since that is much faster and most
190             // of the time the text lines won't match
191             return text.hashCode() == l.text.hashCode() && l.text.equals(text);
192         }
193 
194         /**
195          * Returns the line number of this line
196          * 
197          * @return the line number
198          */
199         public int lineNumber() {
200             return number;
201         }
202 
203         public String   toString() {
204             return "" + number + " " + text + "\n"; //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$
205         }
206     }
207 }
208
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags