1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 package net.sf.collections15.comparators;
17
18 import java.io.Serializable;
19 import java.util.ArrayList;
20 import java.util.BitSet;
21 import java.util.Collection;
22 import java.util.Comparator;
23 import java.util.List;
24
25 /***
26 * A <code>ComparatorChain</code> is a <code>Comparator</code> that wraps one or
27 * more <code>Comparator</code>s in sequence. The <code>ComparatorChain</code>
28 * calls each <code>Comparator</code> in sequence until either <ol> <li>any
29 * single <code>Comparator</code> returns a non-zero result (and that result is
30 * then returned), or</li> <li>the <code>ComparatorChain</code> is exhausted
31 * (and zero is returned).</li> </ol> This type of sorting is very similar to
32 * multi-column sorting in SQL, and this class allows Java classes to emulate
33 * that kind of behaviour when sorting a <code>List</code>.
34 * <p/>
35 * To further facilitate SQL-like sorting, the order of any single
36 * <code>Comparator</code> in the list can be reversed.
37 * <p/>
38 * Calling a method that adds new <code>Comparators</code> or changes the
39 * ascend/descend sort <i>after <code>compare(Object, Object)</code> has been
40 * called</i> will result in an <code>UnsupportedOperationException</code>.
41 * <p/>
42 * Instances of <code>ComparatorChain</code> are not synchronized. The class is
43 * not thread-safe at construction time, but it <i>is</i> thread-safe to perform
44 * multiple comparisons after all the setup operations are complete.
45 *
46 * @author Morgan Delagrange
47 * @author Chris Lambrou (port to Java 5.0)
48 * @since Collections15 1.0
49 */
50 public class ComparatorChain <E> implements Comparator<E>, Serializable
51 {
52
53 static final long serialVersionUID = 5234069201819277501L;
54
55 /***
56 * The list of comparators in the chain.
57 */
58 protected List<Comparator<E>> comparatorChain = null;
59
60 /***
61 * Order - false (clear) = ascend; true (set) = descend.
62 */
63 protected BitSet orderingBits = null;
64
65 /***
66 * Whether the chain has been "locked".
67 */
68 protected boolean isLocked = false;
69
70 /***
71 * Construct a <code>ComparatorChain</code> with no <code>Comparator</code>s
72 * and the specified initial capacity.
73 *
74 * @param initialCapacity The initial capacity of the internal list of
75 * <code>Comparators</code> and ordering bits
76 * <code>BitSet</code>. A negative value indicates
77 * that the default initial capacity of the
78 * underlying storage elements should be used.
79 */
80 protected ComparatorChain(int initialCapacity)
81 {
82 if (initialCapacity < 0) {
83 comparatorChain = new ArrayList<Comparator<E>>();
84 orderingBits = new BitSet();
85 }
86 else {
87 comparatorChain = new ArrayList<Comparator<E>>(initialCapacity);
88 orderingBits = new BitSet(initialCapacity);
89 }
90 }
91
92 /***
93 * Construct an empty <code>ComparatorChain</code> with the default initial
94 * capacity.
95 */
96 public static <T> ComparatorChain<T> getInstance()
97 {
98 return new ComparatorChain<T>(-1);
99 }
100
101
102 /***
103 * Construct a <code>ComparatorChain</code> with a single
104 * <code>Comparator</code>, sorting in the forward order.
105 *
106 * @param comparator The first comparator in the <code>ComparatorChain</code>.
107 *
108 * @throws IllegalArgumentException Thrown if <code>comparator</code> is
109 * <code>null</code>.
110 */
111 public static <T> ComparatorChain<T> getInstance(Comparator<T> comparator)
112 {
113 return getInstance(comparator, false);
114 }
115
116 /***
117 * Construct a <code>ComparatorChain</code> with a single
118 * <code>Comparator</code>, sorting in the specified order.
119 *
120 * @param comparator The first comparator in the <code>ComparatorChain</code>.
121 * @param reverse If <code>false</code>, the natural order of
122 * <code>comparator</code> is used. If <code>true</code>,
123 * the reverse order of <code>comparator</code> is used.
124 *
125 * @throws IllegalArgumentException Thrown if <code>comparator</code> is
126 * <code>null</code>.
127 */
128 public static <T> ComparatorChain<T> getInstance(Comparator<T> comparator, boolean reverse)
129 {
130 ComparatorChain<T> comparatorChain = new ComparatorChain<T>(1);
131 comparatorChain.addComparator(comparator, reverse);
132 return comparatorChain;
133 }
134
135 /***
136 * Returns a <code>ComparatorChain</code> from the <code>Comparators</code>
137 * in the <code>List</code>. All <code>Comparators</code> will default to
138 * the forward sort order.
139 *
140 * @param comparators The <code>Collection</code> of <code>Comparators</code>
141 * to chain. The <code>Comparator</code> are added to the
142 * chain in the order that they are returned by the
143 * <code>iterator</code> method of the <code>Collection</code>.
144 *
145 * @throws IllegalArgumentException Thrown if <code>comparators</code> is
146 * <code>null</code>, or contains any
147 * <code>null</code> elements. It may be
148 * empty, however.
149 */
150 public static <T> ComparatorChain<T> getInstance(Collection<Comparator<T>> comparators)
151 {
152 if (comparators == null) {
153 throw new IllegalArgumentException("null comparator list specified");
154 }
155 ComparatorChain<T> comparatorChain = new ComparatorChain<T>(comparators.size());
156 for (Comparator<T> comparator : comparators) {
157 if (comparator == null) {
158 throw new IllegalArgumentException("null comparator specified in comparator list");
159 }
160 comparatorChain.addComparator(comparator, false);
161 }
162 return comparatorChain;
163 }
164
165 /***
166 * Returns a <code>ComparatorChain</code> from the <code>Comparators</code>
167 * in the <code>List</code>. All <code>Comparators</code> will default to
168 * the forward sort order.
169 *
170 * @param comparators The <code>List</code> of <code>Comparators</code> to
171 * chain.
172 * @param orderingBits Indicates the sort order for each of the
173 * <code>Comparator</code>s in <code>comparators</code>.
174 *
175 * @throws IllegalArgumentException Thrown if <code>comparators</code> is
176 * <code>null</code>, or contains any
177 * <code>null</code> elements. It may be
178 * empty, however.
179 * @throws IllegalArgumentException Thrown if <code>orderingBits</code> is
180 * <code>null</code>, or if <code>comparators</code>
181 * and <code>orderingBits</code> are of
182 * unequal lengths.
183 */
184 public static <T> ComparatorChain<T> getInstance(List<Comparator<T>> comparators, BitSet orderingBits)
185 {
186 if (comparators == null) {
187 throw new IllegalArgumentException("null comparator list specified");
188 }
189 if (orderingBits == null) {
190 throw new IllegalArgumentException("null orderingBits specified");
191 }
192 if (orderingBits.length() != comparators.size()) {
193 throw new IllegalArgumentException("comparators and orderingBits are of differing lengths");
194 }
195 ComparatorChain<T> comparatorChain = new ComparatorChain<T>(comparators.size());
196 int i = 0;
197 for (Comparator<T> comparator : comparators) {
198 if (comparator == null) {
199 throw new IllegalArgumentException("null comparator specified in comparator list");
200 }
201 comparatorChain.addComparator(comparator, orderingBits.get(i++));
202 }
203 return comparatorChain;
204 }
205
206 /***
207 * Add a <code>Comparator</code> to the end of the chain using the forward
208 * sort order.
209 *
210 * @param comparator The <code>Comparator</code> to add to the end of the
211 * chain, with the forward sort order.
212 *
213 * @throws IllegalArgumentException Thrown if <code>comparator</code> is
214 * <code>null</code>.
215 */
216 public void addComparator(Comparator<E> comparator)
217 {
218 addComparator(comparator, false);
219 }
220
221 /***
222 * Add a <code>Comparator</code> to the end of the chain using the specified
223 * sort order.
224 *
225 * @param comparator The <code>Comparator</code> to add to the end of the
226 * chain, with the forward sort order.
227 * @param reverse If <code>false</code>, the natural order of
228 * <code>comparator</code> is used. If <code>true</code>,
229 * the reverse order of <code>comparator</code> is used.
230 *
231 * @throws IllegalArgumentException Thrown if <code>comparator</code> is
232 * <code>null</code>.
233 */
234 public void addComparator(Comparator<E> comparator, boolean reverse)
235 {
236 checkLocked();
237 if (comparator == null) {
238 throw new IllegalArgumentException("null comparator specified");
239 }
240
241 comparatorChain.add(comparator);
242 if (reverse == true) {
243 orderingBits.set(comparatorChain.size() - 1);
244 }
245 }
246
247 /***
248 * Replace the <code>Comparator</code> at the given index, using the forward
249 * sort order for the new <code>Comparator</code>.
250 *
251 * @param index The index of the <code>Comparator</code> to replace.
252 * @param comparator The <code>Comparator</code> to place at the given
253 * index.
254 *
255 * @throws IndexOutOfBoundsException Thrown if <code>index < 0</code> or
256 * <code>index >= size()</code>.
257 * @throws IllegalArgumentException Thrown if <code>comparator</code> is
258 * <code>null</code>.
259 */
260 public void setComparator(int index, Comparator<E> comparator)
261 throws IndexOutOfBoundsException
262 {
263 setComparator(index, comparator, false);
264 }
265
266 /***
267 * Replace the <code>Comparator</code> at the given index, using the
268 * specified sort order for the new <code>Comparator</code>.
269 *
270 * @param index The index of the <code>Comparator</code> to replace.
271 * @param comparator The <code>Comparator</code> to place at the given
272 * index.
273 * @param reverse If <code>false</code>, the natural order of
274 * <code>comparator</code> is used. If <code>true</code>,
275 * the reverse order of <code>comparator</code> is used.
276 *
277 * @throws IndexOutOfBoundsException Thrown if <code>index < 0</code> or
278 * <code>index >= size()</code>.
279 * @throws IllegalArgumentException Thrown if <code>comparator</code> is
280 * <code>null</code>.
281 */
282 public void setComparator(int index, Comparator<E> comparator, boolean reverse)
283 {
284 checkLocked();
285 if (comparator == null) {
286 throw new IllegalArgumentException("null comparator specified");
287 }
288
289 comparatorChain.set(index, comparator);
290 if (reverse == true) {
291 orderingBits.set(index);
292 }
293 else {
294 orderingBits.clear(index);
295 }
296 }
297
298
299 /***
300 * Set the sort order at the given index in the <code>ComparatorChain</code>
301 * to the forward sort order of the <code>Comparator</code> at that
302 * position.
303 *
304 * @param index Index of the <code>Comparator</code> in the
305 * <code>ComparatorChain</code>.
306 *
307 * @throws IndexOutOfBoundsException Thrown if <code>index < 0</code> or
308 * <code>index >= size()</code>.
309 */
310 public void setForwardSort(int index)
311 {
312 checkLocked();
313 if (index < 0 || index >= size()) {
314 throw new IndexOutOfBoundsException("index lies outside of the valid range");
315 }
316 orderingBits.clear(index);
317 }
318
319 /***
320 * Set the sort order at the given index in the <code>ComparatorChain</code>
321 * to the reverse sort order of the <code>Comparator</code> at that
322 * position.
323 *
324 * @param index Index of the <code>Comparator</code> in the
325 * <code>ComparatorChain</code>.
326 *
327 * @throws IndexOutOfBoundsException Thrown if <code>index < 0</code> or
328 * <code>index >= size()</code>.
329 */
330 public void setReverseSort(int index)
331 {
332 checkLocked();
333 if (index < 0 || index >= size()) {
334 throw new IndexOutOfBoundsException("index lies outside of the valid range");
335 }
336 orderingBits.set(index);
337 }
338
339 /***
340 * Returns the number of <code>Comparator</code>s in the
341 * <code>ComparatorChain</code>.
342 *
343 * @return The length of the chain.
344 */
345 public int size()
346 {
347 return comparatorChain.size();
348 }
349
350 /***
351 * Determine if modifications can still be made to the
352 * <code>ComparatorChain</code>. <code>ComparatorChain</code>s cannot be
353 * modified once they have performed a comparison.
354 *
355 * @return <code>true</code> if the <code>ComparatorChain</code> cannot be
356 * modified; <code>false</code> if the <code>ComparatorChain</code>
357 * can still be modified.
358 */
359 public boolean isLocked()
360 {
361 return isLocked;
362 }
363
364 /***
365 * Checks to see if the <code>ComparatorChain</code> is locked. Invoked
366 * internally prior to any modifications being made to the chain.
367 *
368 * @throws UnsupportedOperationException Thrown if the chain is locked,
369 * indicating that the requested
370 * operation is now no longer
371 * supported by this chain.
372 */
373 private void checkLocked()
374 {
375 if (isLocked == true) {
376 throw new UnsupportedOperationException("Comparator ordering cannot be changed after the first comparison is performed");
377 }
378 }
379
380 /***
381 * Compares its two arguments for order. Returns a negative integer, zero,
382 * or a positive integer as the first argument is less than, equal to, or
383 * greater than the second.
384 *
385 * @param o1 The first object to compare.
386 * @param o2 The second object to compare.
387 *
388 * @return -1, 0, or 1
389 */
390 public int compare(E o1, E o2)
391 {
392 isLocked = true;
393
394
395 int comparatorIndex = 0;
396 for (Comparator<E> comparator : comparatorChain) {
397 int retval = comparator.compare(o1, o2);
398 if (retval != 0) {
399 return orderingBits.get(comparatorIndex)
400 ? (retval > 0 ? -1 : 1)
401 : (retval > 0 ? 1 : -1);
402 }
403 comparatorIndex++;
404 }
405
406
407 return 0;
408 }
409
410 /***
411 * Implement a hash code for this comparator that is consistent with {@link
412 * #equals(Object) equals}.
413 *
414 * @return A suitable hash code
415 *
416 * @since Collections15 1.0
417 */
418 public int hashCode()
419 {
420 return comparatorChain.hashCode() ^ orderingBits.hashCode();
421 }
422
423 /***
424 * Indicates whether or not the specified object is equal to this
425 * <code>ComparatorChain</code> instance.
426 * <p/>
427 * This implementation returns <code>true</code> only if
428 * <code>object.getClass()</code> equals <code>this.getClass()</code>, and
429 * the underlying comparators and order bits are equal. Subclasses may want
430 * to override this behavior to remain consistent with the {@link
431 * java.util.Comparator#equals(Object)} contract.
432 *
433 * @param object The object to compare to.
434 *
435 * @return <code>true</code> if <code>object</code> is equal to this
436 * instance.
437 *
438 * @since Collections15 1.0
439 */
440 public boolean equals(Object object)
441 {
442 if (this == object) {
443 return true;
444 }
445 else if (null == object) {
446 return false;
447 }
448 else if (object.getClass().equals(this.getClass())) {
449 ComparatorChain chain = (ComparatorChain) object;
450 return ((null == orderingBits ? null == chain.orderingBits : orderingBits.equals(chain.orderingBits))
451 && (null == comparatorChain ? null == chain.comparatorChain : comparatorChain.equals(chain.comparatorChain)));
452 }
453 else {
454 return false;
455 }
456 }
457
458 }