1 57 58 package org.apache.commons.jrcs.diff; 59 60 import java.util.*; 61 62 138 public class SimpleDiff 139 implements DiffAlgorithm 140 { 141 142 static final int NOT_FOUND_i = -2; 143 static final int NOT_FOUND_j = -1; 144 static final int EOS = Integer.MAX_VALUE; 145 146 public SimpleDiff() 147 { 148 } 150 151 protected int scan(int[] ndx, int i, int target) 152 { 153 while (ndx[i] < target) 154 { 155 i++; 156 } 157 return i; 158 } 159 160 168 public Revision diff(Object [] orig, Object [] rev) 169 throws DifferentiationFailedException 170 { 171 Map eqs = buildEqSet(orig, rev); 174 175 int[] indx = buildIndex(eqs, orig, NOT_FOUND_i); 179 180 int[] jndx = buildIndex(eqs, rev, NOT_FOUND_j); 184 185 190 eqs = null; 192 Revision deltas = new Revision(); int i = 0; 194 int j = 0; 195 196 for (; indx[i] != EOS && indx[i] == jndx[j]; i++, j++) 202 { 203 204 } 205 206 while (indx[i] != jndx[j]) 207 { int ia = i; 210 int ja = j; 211 212 do 214 { 215 while (jndx[j] < 0 || jndx[j] < indx[i]) 220 { 221 j++; 222 } 223 while (indx[i] < 0 || indx[i] < jndx[j]) 228 { 229 i++; 230 } 231 232 } 235 while (indx[i] != jndx[j]); 236 237 239 while (i > ia && j > ja && indx[i - 1] == jndx[j - 1]) 242 { 243 --i; 244 --j; 245 } 246 247 deltas.addDelta(Delta.newDelta(new Chunk(orig, ia, i - ia), 248 new Chunk(rev, ja, j - ja))); 249 for (; indx[i] != EOS && indx[i] == jndx[j]; i++, j++) 251 { 252 253 } 254 } 255 return deltas; 256 } 257 258 265 protected Map buildEqSet(Object [] orig, Object [] rev) 266 { 267 269 Set items = new HashSet(Arrays.asList(orig)); 271 272 items.retainAll(Arrays.asList(rev)); 274 275 Map eqs = new HashMap(); 276 for (int i = 0; i < orig.length; i++) 277 { 278 if (items.contains(orig[i])) 280 { 281 eqs.put(orig[i], new Integer (i)); 283 items.remove(orig[i]); 285 } 286 } 287 return eqs; 288 } 289 290 297 protected int[] buildIndex(Map eqs, Object [] seq, int NF) 298 { 299 int[] result = new int[seq.length + 1]; 300 for (int i = 0; i < seq.length; i++) 301 { 302 Integer value = (Integer ) eqs.get(seq[i]); 303 if (value == null || value.intValue() < 0) 304 { 305 result[i] = NF; 306 } 307 else 308 { 309 result[i] = value.intValue(); 310 } 311 } 312 result[seq.length] = EOS; 313 return result; 314 } 315 316 } 317 | Popular Tags |