View Javadoc
1 /*
2 * Copyright (c) 2003 Scott Howlett & Paul Libbrecht.
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 *
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in
14 * the documentation and/or other materials provided with the
15 * distribution.
16 *
17 * 3. The end-user documentation included with the redistribution,
18 * if any, must include the following acknowledgment:
19 * "This product includes software developed by the Xwing
20 * Project ( http://xwing.sourceforge.net/ )."
21 * Alternately, this acknowledgment may appear in the software itself,
22 * if and wherever such third-party acknowledgments normally appear.
23 *
24 * 4. The name "Xwing" must not be used to endorse or promote products
25 * derived from this software without prior written permission. For
26 * written permission, please contact the project authors via
27 * the Xwing project site, http://xwing.sourceforge.net/ .
28 *
29 * 5. Products derived from this software may not be called "Xwing",
30 * nor may "Xwing" appear in their name, without prior written
31 * permission of the Xwing project.
32 *
33 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
34 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
35 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
36 * DISCLAIMED. IN NO EVENT SHALL THE XWING AUTHORS OR THE PROJECT
37 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
38 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
39 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
40 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
41 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
42 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
43 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
44 * SUCH DAMAGE.
45 *
46 * For more information on Xwing, please see
47 * < http://xwing.sourceforge.net/ >.
48 */
49
50 package net.sourceforge.xwing.util;
51
52 import java.util.Collection;
53 import java.util.Iterator;
54
55 import org.apache.commons.collections.iterators.ArrayIterator;
56 import org.apache.commons.lang.ObjectUtils;
57
58 /***
59 * A utility class that reports simple difference information
60 * between two sequences.
61 *
62 * @author Scott Howlett
63 * @version $Revision: 1.2 $
64 */
65
66 public class SequenceUtils {
67
68 /***
69 * The two sequences are the same.
70 */
71 public static final int NO_CHANGE = 0;
72
73 /***
74 * The new sequence differs from the old sequence by
75 * having a set of values inserted into it at a
76 * single point.
77 */
78 public static final int INTERVAL_ADDED = 1;
79
80 /***
81 * The new sequence differs from the old sequence by
82 * having a set of values removed from it at a
83 * single point.
84 */
85 public static final int INTERVAL_REMOVED = 2;
86
87 /***
88 * The new sequence and the old sequence differ by some
89 * change that is more complex than a single insert or
90 * remove.
91 */
92 public static final int COMPLEX_CHANGE = 3;
93
94 /***
95 * A class that encapsulates the information about the
96 * change from an old sequence to a new sequence.
97 *
98 * @author Scott Howlett
99 * @version $Revision: 1.2 $
100 */
101 public static class ChangeInfo {
102
103 private int changeType;
104 private int firstIndex;
105 private int lastIndex;
106
107 ChangeInfo(int changeType, int firstIndex, int lastIndex) {
108 this.changeType = changeType;
109 this.firstIndex = firstIndex;
110 this.lastIndex = lastIndex;
111 }
112
113 /***
114 * The type of change, either NO_CHANGE, INTERVAL_ADDED,
115 * INTERVAL_REMOVED, or COMPLEX_CHANGE.
116 */
117 public int getChangeType() {
118 return changeType;
119 }
120
121 /***
122 * For changes of type INTERVAL_ADDED, the index in the new
123 * sequence of the first added element. For changes of type
124 * INTERVAL_REMOVED, the index in the old sequence of the
125 * first removed element.
126 */
127 public int getFirstIndex() {
128 return firstIndex;
129 }
130
131 /***
132 * For changes of type INTERVAL_ADDED, the index in the new
133 * sequence of the last added element. For changes of type
134 * INTERVAL_REMOVED, the index in the old sequence of the
135 * last removed element.
136 */
137 public int getLastIndex() {
138 return lastIndex;
139 }
140
141 }
142
143 private SequenceUtils() {
144 }
145
146 /***
147 * Report on the difference betwen two Collections.
148 * @param oldData The old sequence.
149 * @param newData The new sequence.
150 * @return A ChangeInfo describing the change.
151 */
152 public static ChangeInfo findDifference(
153 Collection oldData,
154 Collection newData) {
155
156 if (oldData == null && newData == null) {
157 return new ChangeInfo(NO_CHANGE, 0, 0);
158 } else if (oldData == null) {
159 return new ChangeInfo(INTERVAL_ADDED, 0, newData.size() - 1);
160 } else if (newData == null) {
161 return new ChangeInfo(INTERVAL_REMOVED, 0, oldData.size() - 1);
162 }
163
164 return findDifference(
165 oldData.iterator(),
166 oldData.size(),
167 newData.iterator(),
168 newData.size());
169 }
170
171 /***
172 * Report on the difference betwen two Arrays.
173 * @param oldData The old sequence.
174 * @param newData The new sequence.
175 * @return A ChangeInfo describing the change.
176 */
177 public static ChangeInfo findDifference(
178 Object[] oldData,
179 Object[] newData) {
180
181 if (oldData == null && newData == null) {
182 return new ChangeInfo(NO_CHANGE, 0, 0);
183 } else if (oldData == null) {
184 return new ChangeInfo(INTERVAL_ADDED, 0, newData.length - 1);
185 } else if (newData == null) {
186 return new ChangeInfo(INTERVAL_REMOVED, 0, oldData.length - 1);
187 }
188
189 return findDifference(
190 new ArrayIterator(oldData),
191 oldData.length,
192 new ArrayIterator(newData),
193 newData.length);
194 }
195
196 private static ChangeInfo findDifference(
197 Iterator oldData,
198 int oldDataLength,
199 Iterator newData,
200 int newDataLength) {
201
202 ChangeInfo result;
203
204 if (oldDataLength < newDataLength) {
205 result =
206 findAddition(oldData, oldDataLength, newData, newDataLength);
207 } else if (oldDataLength > newDataLength) {
208 result =
209 findAddition(newData, newDataLength, oldData, oldDataLength);
210 if (result.getChangeType() == INTERVAL_ADDED) {
211 result =
212 new ChangeInfo(
213 INTERVAL_REMOVED,
214 result.getFirstIndex(),
215 result.getLastIndex());
216 }
217 } else {
218 while (oldData.hasNext()) {
219 if (!ObjectUtils.equals(oldData.next(), newData.next())) {
220 return new ChangeInfo(COMPLEX_CHANGE, 0, 0);
221 }
222 }
223 result = new ChangeInfo(NO_CHANGE, 0, 0);
224 }
225
226 return result;
227 }
228
229 private static ChangeInfo findAddition(
230 Iterator smaller,
231 int smallerLength,
232 Iterator larger,
233 int largerLength) {
234
235 Object sm = null;
236 Object lg = null;
237
238 int changeStart = 0;
239
240 while (smaller.hasNext()) {
241 sm = smaller.next();
242 lg = larger.next();
243 if (!(ObjectUtils.equals(sm, lg))) {
244 break;
245 }
246 ++changeStart;
247 }
248
249 if (changeStart < smallerLength) {
250 for (int i = smallerLength; i < largerLength; ++i) {
251 lg = larger.next();
252 }
253
254 while (true) {
255 if (!ObjectUtils.equals(sm, lg)) {
256 return new ChangeInfo(COMPLEX_CHANGE, 0, 0);
257 }
258 if (!smaller.hasNext()) {
259 break;
260 }
261 sm = smaller.next();
262 lg = larger.next();
263 }
264
265 }
266
267 return new ChangeInfo(
268 INTERVAL_ADDED,
269 changeStart,
270 changeStart + largerLength - smallerLength - 1);
271 }
272 }
This page was automatically generated by Maven