|
1
57
58 package org.apache.commons.jrcs.diff.myers;
59
60 import org.apache.commons.jrcs.diff.*;
61
62
77 public class MyersDiff
78 implements DiffAlgorithm
79 {
80
83 public MyersDiff()
84 {
85 }
87
88
91 public Revision diff(Object  [] orig, Object [] rev)
92 throws DifferentiationFailedException
93 {
94 PathNode path = buildPath(orig, rev);
95 return buildRevision(path, orig, rev);
96 }
97
98
108 public static PathNode buildPath(Object [] orig, Object [] rev)
109 throws DifferentiationFailedException
110 {
111 if (orig == null)
112 throw new IllegalArgumentException ("original sequence is null");
113 if (rev == null)
114 throw new IllegalArgumentException ("revised sequence is null");
115
116 final int N = orig.length;
118 final int M = rev.length;
119
120 final int MAX = N + M + 1;
121 final int size = 1 + 2 * MAX;
122 final int middle = (size + 1) / 2;
123 final PathNode diagonal[] = new PathNode[size];
124
125 diagonal[middle + 1] = new Snake(0, -1, null);
126 for (int d = 0; d < MAX; d++)
127 {
128 for (int k = -d; k <= d; k += 2)
129 {
130 final int kmiddle = middle + k;
131 final int kplus = kmiddle + 1;
132 final int kminus = kmiddle - 1;
133 PathNode prev = null;
134
135 int i;
136 if ( (k == -d) ||
137 (k != d && diagonal[kminus].i < diagonal[kplus].i))
138 {
139 i = diagonal[kplus].i;
140 prev = diagonal[kplus];
141 }
142 else
143 {
144 i = diagonal[kminus].i + 1;
145 prev = diagonal[kminus];
146 }
147
148 diagonal[kminus] = null;
150 int j = i - k;
151
152 PathNode node = new DiffNode(i, j, prev);
153
154 while (i < N && j < M && orig[i].equals(rev[j]))
158 {
159 i++;
160 j++;
161 }
162 if (i > node.i)
163 node = new Snake(i, j, node);
164
165 diagonal[kmiddle] = node;
166
167 if (i >= N && j >= M)
168 {
169 return diagonal[kmiddle];
170 }
171 }
172 diagonal[middle+d-1] = null;
173
174 }
175 throw new DifferentiationFailedException("could not find a diff path");
177 }
178
179
189 public static Revision buildRevision(PathNode path, Object [] orig, Object [] rev)
190 {
191 if (path == null)
192 throw new IllegalArgumentException ("path is null");
193 if (orig == null)
194 throw new IllegalArgumentException ("original sequence is null");
195 if (rev == null)
196 throw new IllegalArgumentException ("revised sequence is null");
197
198 Revision revision = new Revision();
199 if (path.isSnake())
200 path = path.prev;
201 while (path != null && path.prev != null && path.prev.j >= 0)
202 {
203 if(path.isSnake())
204 throw new IllegalStateException ("bad diffpath: found snake when looking for diff");
205 int i = path.i;
206 int j = path.j;
207
208 path = path.prev;
209 int ianchor = path.i;
210 int janchor = path.j;
211
212 Delta delta = Delta.newDelta(new Chunk(orig, ianchor, i - ianchor),
213 new Chunk(rev, janchor, j - janchor));
214 revision.insertDelta(delta);
215 if (path.isSnake())
216 path = path.prev;
217 }
218 return revision;
219 }
220
221 }
222 |
Popular Tags |
Java API By Example, From Geeks To Geeks.