Java > Open Source Codes > org > enhydra > xml > driver > diff


1 package org.enhydra.xml.driver.diff;
2
3 import java.io.BufferedReader ;
4 import java.io.FileReader ;
5 import java.io.IOException ;
6 import java.util.ArrayList ;
7 import java.util.Enumeration ;
8 import java.util.Vector ;
9
10 /**
11  * The <code>diff</code> class compares two files. it compares also two
12  * BufferedReaders or two strings.
13  * after the comparison the vector will represents a list of hunk
14  * corresponding with blocks of difference.
15  * <p>
16  * to generate a file of difference, one can instanciate as follows the class
17  * diff:
18  * <p><blockquote><pre>
19  * diff d = new diff(file1,file2);
20  * </pre></blockquote><p>
21  * which is equivalent to:
22  * <p><blockquote><pre>
23  * diff d = new diff();
24  * d.diffFile(file1,file2);
25  * </pre></blockquote><p>
26  * To compare two BufferedReaders or two String we have to instanciate
27  * as follows:
28  * <p><blockquote><pre>
29  * diff d = new diff();
30  * d.diffBuffer(BufferedReader1,BufferedReader2);
31  * </pre></blockquote><p>
32  * or:
33  * <p><blockquote><pre>
34  * diff d = new diff();
35  * d.diffString(String1,String2);
36  * </pre></blockquote><p>
37  * The class <code>diff</code> includes methods for examining, printing
38  * or saveing blocks of difference: (Hunks).
39  * Here are some more examples of how <code>diff</code> can be used:
40  * <p><blockquote><pre>
41  * diff d=new diff(args[0],args[1]);
42  * d.print();
43  * d.save("diff.txt");
44  * </pre></blockquote><p>
45  * Example using BufferedReader and ED_format:
46  * <p><blockquote><pre>
47  * BufferedReader in=new BufferedReader(new FileReader(args[0]));
48  * BufferedReader inn=new BufferedReader(new FileReader(args[1]));
49  * diff d = new diff();
50  * d.diffBuffer(in,inn);
51  * d.print_ED();
52  * d.save_ED("diff.txt");
53  * </pre></blockquote><p>
54  * To go throw the list of Hunks we can choose between an Enumeration
55  * or a loop by spesifyng index in the vector to get at each time
56  * the corresponding Hunk.
57   *
58   * <p><blockquote><pre>
59   * Vector v=d.getHunk();
60   * for(Enumeration e=v.element();e.hasMoreElements(); )
61   * {
62   * System.out.print(((Hunk)e.nextElement()).convert());
63   * }
64   * </pre></blockquote><p>
65   *
66   * or:
67   * <p><blockquote><pre>
68   * diff d = new diff(file1,file2);
69   * for(int i=0; i<d.numberOfHunk(); i++){
70   * Object k=d.hunkAt(i);
71   * if(k instanceof Hunk)
72   * System.out.print(k.convert());
73   * }
74   * </pre></blockquote><p>
75   * @see diff.diff#getHunk()
76   * @see diff.diff#hunkAt()
77   * @see diff.diff#numberOfHunk()
78   * @see diff.diff#print()
79   * @see diff.diff#print_ED()
80   * @see diff.diff#print_RCS()
81   * @see diff.diff#save()
82   * @see diff.diff#save_ED()
83   * @see diff.diff#save_RCS()
84   */
85
86 public class diff implements define, HunkVisitable {
87     private static final int MAXEDITS = 2000;
88  
89     Vector v=new Vector ();
90   
91     /**
92      * Allocates a new <code>diff</code> containing no Hunks.
93      */
94     public diff(){}
95   
96     /**
97      * Allocates a new <code>diff</code> which contains Hunks corresponding
98      * to the difference between the two files passed in arguments.
99      *
100      * @param s1 first file to compare.
101      * @param s2 second file to compare.
102      */
103     public diff(String s1,String s2)throws IOException {
104     diffFile(s1,s2);
105     }
106
107     /**
108      * Returns a vector containing Hunks.
109      */
110     public Vector getHunk(){
111     return v;
112     }
113
114     /**
115      * Returns the number of hunks in the vector.
116      */
117     public int numberOfHunk(){
118     return v.size();
119     }
120
121     /**
122      * Return the hunk at the specified index.
123      *
124      * @param i index of the hunk that will be returned.
125      */
126     public Hunk hunkAt(int i){
127     return (Hunk)v.elementAt(i);
128     }
129
130     /**
131      * Accept a visitor in order to visit the collection of hunks.
132      *
133      * @param visitor the HunkVisitor.
134      */
135     public void accept(HunkVisitor visitor) {
136     for (Enumeration e = v.elements() ; e.hasMoreElements() ;) {
137         Hunk h = (Hunk) e.nextElement();
138         h.accept(visitor);
139     }
140     }
141
142     /**
143      * Compares two files and updates the vector of Hunks.
144      *
145      * @param s1 first file to compare.
146      * @param s2 second file to compare.
147      */
148     public void diffFile(String s1,String s2)throws IOException {
149
150     BufferedReader in=new BufferedReader (new FileReader (s1));
151         try {
152             BufferedReader inn=new BufferedReader (new FileReader (s2));
153             try {
154                 diffBuffer(in,inn);
155             } finally {
156                 inn.close();
157             }
158         } finally {
159             in.close();
160         }
161     }
162
163     /**
164      * Compares two BufferedReaders and updates the vector of Hunks.
165      *
166      * @param in first BufferedReader to compare.
167      * @param inn second BufferedReader to compare.
168      */
169     public void diffBuffer(BufferedReader in,BufferedReader inn)throws IOException {
170     
171         // Modified by markd@lutris.com to not have a fixed limit on
172 // the number of lines.
173
174     String s;
175         ArrayList Alist = new ArrayList ();
176         ArrayList Blist = new ArrayList ();
177     
178         int m=0,n=0;
179     while((s=in.readLine())!=null)
180         {
181         Alist.add(s);
182         m++;
183         }
184     while((s=inn.readLine())!=null)
185         {
186         Blist.add(s);
187         n++;
188         }
189     String A[] =(String [])Alist.toArray(new String [Alist.size()]);
190     String B[] =(String [])Blist.toArray(new String [Blist.size()]);
191         int maxLines = (m > n) ? m : n;
192
193     int i,j,max_d=2*maxLines,
194         lower,upper,
195         d=1,k,row,col;
196     
197     int last_d[]=new int[2*maxLines+1]; //row containing last d
198 //pour chaque diag
199 edit script[]=new edit[2*maxLines+1]; //correspond a l'edit script */
200 int origin = maxLines;
201
202     
203     for(row=0;row<m&&row<n&&A[row].equals(B[row]);row++);
204     last_d[origin]=row;
205     script[origin]=null;
206     if(row==m)
207         lower=origin+1;
208     else
209         lower=origin-1;
210     if(row==n)
211         upper=origin-1;
212     else
213         upper=origin+1;
214     if(lower>upper)
215         return ;
216     else
217         {
218                 int numEdits = 0;
219         for(d=1;d<=max_d;d++){ //for each value of edit distance
220 for(k=lower;k<=upper;k+=2) //for each relevant diagonal
221 {
222                 edit e=new edit();
223                             numEdits++;
224                 if(k==origin-d||k!=origin+d&&last_d[k+1]>=last_d[k-1])
225                 {
226                     row=last_d[k+1]+1;
227                     e.setnext(script[k+1]);
228                     e.setop(DELETE);
229                 }
230                 else
231                 {
232                     row=last_d[k-1];
233                     e.setnext(script[k-1]);
234                     e.setop(INSERT);
235                 }
236                 e.setline1(row);
237                 col=row+k-origin;
238                 e.setline2(col);
239                 script[k]=e;
240                 while(row<m&&col<n&&A[row].equals(B[col]))
241                 {
242                     row++;
243                     col++;
244                 }
245                 last_d[k]=row;
246                 if((row==m&&col==n) || (numEdits == MAXEDITS))
247                 {
248                     v=getHunk(script[k],A,B);
249                     return ;
250                 }
251                 if(row==m)
252                 lower=k+2;
253                 if(col==n)
254                 upper=k-2;
255             }
256       
257             lower--;
258             upper++;
259       
260         }
261         }
262     }
263     
264     /**
265      * Compares two strings and updates the vector of Hunks.
266      *
267      * @param s1 first string to compare.
268      * @param s2 second string to compare.
269      */
270     public void diffString(String s1,String s2)throws IOException {
271       
272     int i,j,max_d=2*MAXLINES,
273         m=0,n=0,
274         lower,upper,
275         d=1,k,row,col;
276       
277    
278     int last_d[]=new int[2*MAXLINES+1];
279                                            
280     edit script[]=new edit[2*MAXLINES+1];
281     
282    
283     char c,A[]=new char[MAXLINES],B[]=new char[MAXLINES];
284
285     s1.getChars(0,s1.length(),A,0);
286     s2.getChars(0,s2.length(),B,0);
287
288     m=s1.length();
289     n=s2.length();
290
291     for(row=0;row<m&&row<n&&A[row]==B[row];row++);
292     last_d[ORIGIN]=row;
293     script[ORIGIN]=null;
294     if(row==m)
295         lower=ORIGIN+1;
296     else
297         lower=ORIGIN-1;
298     if(row==n)
299         upper=ORIGIN-1;
300     else
301         upper=ORIGIN+1;
302     if(lower>upper)
303         return ;
304     else
305         {
306     
307         for(d=1;d<=max_d;d++){
308             for(k=lower;k<=upper;k+=2)
309             {
310                 edit e=new edit();
311                 if(k==ORIGIN-d||k!=ORIGIN+d&&last_d[k+1]>=last_d[k-1])
312                 {
313                     row=last_d[k+1]+1;
314                     e.setnext(script[k+1]);
315                     e.setop(DELETE);
316                 }
317                 else
318                 {
319                     row=last_d[k-1];
320                     e.setnext(script[k-1]);
321                     e.setop(INSERT);
322                 }
323                 e.setline1(row);
324                 col=row+k-ORIGIN;
325                 e.setline2(col);
326                 script[k]=e;
327                 while(row<m&&col<n&&A[row]==B[col])
328                 {
329                     row++;
330                     col++;
331                 }
332                 last_d[k]=row;
333                 if(row==m&&col==n)
334                 {
335                     v=getHunk(script[k],A,B);
336                     return ;
337                 }
338                 if(row==m)
339                 lower=k+2;
340                 if(col==n)
341                 upper=k-2;
342             }
343
344             lower--;
345             upper++;
346       
347         }
348         System.out.println(";;;;exceed"+d);
349         }
350     }
351
352     /*
353      * Generates Hunks and returns them in a vector.
354      */
355     private static Vector getHunk(edit start,String A[],String B[])throws IOException {
356     Vector v=new Vector ();
357     boolean change;
358     int i;
359     edit ep=new edit();
360     edit behind=new edit();
361     edit ahead=new edit();
362     edit a=new edit();
363     edit b=new edit();
364     ahead=start;
365     ahead=start;
366     ep=null;
367     while(ahead!=null)
368         {
369         behind=ep;
370         ep=ahead;
371         ahead=ahead.next;
372         ep.next=behind;
373         }
374  
375     while(ep!=null)
376         {
377         b=ep;
378         if(ep.op==INSERT)
379             {
380             a=ep;
381             behind=ep.next;
382             while(behind!=null&&behind.op==INSERT&&ep.line1==behind.line1)
383                 {
384                 a=behind;
385                 behind=behind.next;
386                 }
387             HunkAdd add=new HunkAdd();
388             add.ld1=ep.line1;
389             add.ld2=ep.line2;
390             add.lf2=a.line2;
391             do{
392                 add.b.addElement(B[ep.line2-1]+"\n");
393                 ep=ep.next;
394             }while(ep!=null&&ep.op==INSERT&&ep.line1==b.line1);
395             add.next=null;
396             if(v.size()!=0)
397                 ((Hunk)v.lastElement()).next=add;
398             v.addElement(add);
399             }
400     
401         else
402             {
403             do{
404                 a=b;
405                 b=b.next;
406             }while(b!=null&&b.op==DELETE&&b.line1==a.line1+1);
407             change=(b!=null&&b.op==INSERT&&b.line1==a.line1);
408             if(change)
409                 {
410                 HunkChange cha=new HunkChange();
411                 cha.ld1=ep.line1;
412                 cha.lf1=a.line1;
413                 i=0;
414                 behind=b;
415                 while(behind!=null&&behind.op==INSERT&&behind.line1==b.line1)
416                     {
417                     i++;
418                     behind=behind.next;
419                     }
420                 cha.ld2=b.line2;
421                 cha.lf2=i-1+b.line2;
422                 do{
423                     cha.a.addElement(A[ep.line1-1]+"\n");
424                     ep=ep.next;
425                 }while(ep!=b);
426                 if(!change)
427                     continue;
428                 do{
429                     cha.b.addElement(B[ep.line2-1]+"\n");
430                     ep=ep.next;
431                 }while(ep!=null&&ep.op==INSERT&&ep.line1==b.line1);
432                 cha.next=null;
433                 if(v.size()!=0)
434                     ((Hunk)v.lastElement()).next=cha;
435                 v.addElement(cha);
436                 }
437             else
438                 {
439        
440                 HunkDel del=new HunkDel();
441                 del.ld1=ep.line1;
442                 del.lf1=a.line1;
443                 del.ld2=ep.line2;
444       
445                 do{
446                     del.a.addElement(A[ep.line1-1]+"\n");
447                     ep=ep.next;
448                 }while(ep!=b);
449                 del.next=null;
450                 if(v.size()!=0)
451                     ((Hunk)v.lastElement()).next=del;
452                 v.addElement(del);
453     
454                 }
455             }
456         }
457     return v;
458     }
459  
460     /*
461      * Generates Hunks and returns them in a vector.
462      */
463     private static Vector getHunk(edit start,char A[],char B[])throws IOException {
464     Vector v=new Vector ();
465
466     boolean change;
467     int i;
468     edit ep=new edit();
469     edit behind=new edit();
470     edit ahead=new edit();
471     edit a=new edit();
472     edit b=new edit();
473     ahead=start;
474     ep=null;
475     while(ahead!=null)
476         {
477         behind=ep;
478         ep=ahead;
479         ahead=ahead.next;
480         ep.next=behind;
481         }
482     while(ep!=null)
483         {
484         b=ep;
485         if(ep.op==INSERT)
486             {
487             a=ep;
488             behind=ep.next;
489             while(behind!=null&&behind.op==INSERT&&ep.line1==behind.line1)
490                 {
491                 a=behind;
492                 behind=behind.next;
493                 }
494             HunkAdd add=new HunkAdd();
495             add.ld1=ep.line1;
496             add.ld2=ep.line2;
497             add.lf2=a.line2;
498             String s=new String ();
499             do{
500                 s=s+B[ep.line2-1];
501                 ep=ep.next;
502             }while(ep!=null&&ep.op==INSERT&&ep.line1==b.line1);
503             add.b.addElement(s+"\n");
504             v.addElement(add);
505             }
506         else
507             {
508             do{
509                 a=b;
510                 b=b.next;
511             }while(b!=null&&b.op==DELETE&&b.line1==a.line1+1);
512             change=(b!=null&&b.op==INSERT&&b.line1==a.line1);
513             if(change)
514                 {
515                 HunkChange cha=new HunkChange();
516                 cha.ld1=ep.line1;
517                 cha.lf1=a.line1;
518                 i=0;
519                 behind=b;
520                 while(behind!=null&&behind.op==INSERT&&behind.line1==b.line1)
521                     {
522                     i++;
523                     behind=behind.next;
524                     }
525                 cha.ld2=b.line2;
526                 cha.lf2=i-1+b.line2;
527                 String s=new String ();
528                 do{
529                     s=s+A[ep.line1-1];
530                     ep=ep.next;
531                 }while(ep!=b);
532                 cha.a.addElement(s+"\n");
533                 s=new String ();
534                 do{
535                     s=s+B[ep.line2-1];
536                     ep=ep.next;
537                 }while(ep!=null&&ep.op==INSERT&&ep.line1==b.line1);
538                 cha.b.addElement(s+"\n");
539                 v.addElement(cha);
540                 }
541             else
542                 {
543                 HunkDel del=new HunkDel();
544                 del.ld1=ep.line1;
545                 del.lf1=a.line1;
546                 del.ld2=ep.line2;
547                 String s=new String ();
548                 do{
549                     s=s+A[ep.line1-1];
550                     ep=ep.next;
551                 }while(ep!=b);
552                 del.a.addElement(s+"\n");
553                 v.addElement(del);
554                 }
555
556             }
557         }
558     return v;
559     }
560 }
561
562
563

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags