1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.commons.collections.comparators;
18
19 import java.io.Serializable;
20 import java.util.ArrayList;
21 import java.util.BitSet;
22 import java.util.Comparator;
23 import java.util.Iterator;
24 import java.util.List;
25
26 /**
27 * A ComparatorChain is a Comparator that wraps one or more Comparators in
28 * sequence. The ComparatorChain calls each Comparator in sequence until either
29 * 1) any single Comparator returns a non-zero result (and that result is then
30 * returned), or 2) the ComparatorChain is exhausted (and zero is returned).
31 * This type of sorting is very similar to multi-column sorting in SQL, and this
32 * class allows Java classes to emulate that kind of behaviour when sorting a
33 * List.
34 * <p>
35 * To further facilitate SQL-like sorting, the order of any single Comparator in
36 * the list can be reversed.
37 * <p>
38 * Calling a method that adds new Comparators or changes the ascend/descend sort
39 * <i>after compare(Object, Object) has been called</i> will result in an
40 * UnsupportedOperationException. However, <i>take care</i> to not alter the
41 * underlying List of Comparators or the BitSet that defines the sort order.
42 * <p>
43 * Instances of ComparatorChain are not synchronized. The class is not
44 * thread-safe at construction time, but it <i>is</i> thread-safe to perform
45 * multiple comparisons after all the setup operations are complete.
46 *
47 * @since 2.0
48 * @version $Id: ComparatorChain.java 1437016 2013-01-22 16:07:33Z tn $
49 */
50 public class ComparatorChain<E> implements Comparator<E>, Serializable {
51
52 /** Serialization version from Collections 2.0. */
53 private static final long serialVersionUID = -721644942746081630L;
54
55 /** The list of comparators in the chain. */
56 protected List<Comparator<E>> comparatorChain = null;
57 /** Order - false (clear) = ascend; true (set) = descend. */
58 protected BitSet orderingBits = null;
59 /** Whether the chain has been "locked". */
60 protected boolean isLocked = false;
61
62 //-----------------------------------------------------------------------
63 /**
64 * Construct a ComparatorChain with no Comparators.
65 * You must add at least one Comparator before calling
66 * the compare(Object,Object) method, or an
67 * UnsupportedOperationException is thrown
68 */
69 public ComparatorChain() {
70 this(new ArrayList<Comparator<E>>(), new BitSet());
71 }
72
73 /**
74 * Construct a ComparatorChain with a single Comparator,
75 * sorting in the forward order
76 *
77 * @param comparator First comparator in the Comparator chain
78 */
79 public ComparatorChain(final Comparator<E> comparator) {
80 this(comparator, false);
81 }
82
83 /**
84 * Construct a Comparator chain with a single Comparator,
85 * sorting in the given order
86 *
87 * @param comparator First Comparator in the ComparatorChain
88 * @param reverse false = forward sort; true = reverse sort
89 */
90 public ComparatorChain(final Comparator<E> comparator, final boolean reverse) {
91 comparatorChain = new ArrayList<Comparator<E>>(1);
92 comparatorChain.add(comparator);
93 orderingBits = new BitSet(1);
94 if (reverse == true) {
95 orderingBits.set(0);
96 }
97 }
98
99 /**
100 * Construct a ComparatorChain from the Comparators in the
101 * List. All Comparators will default to the forward
102 * sort order.
103 *
104 * @param list List of Comparators
105 * @see #ComparatorChain(List,BitSet)
106 */
107 public ComparatorChain(final List<Comparator<E>> list) {
108 this(list, new BitSet(list.size()));
109 }
110
111 /**
112 * Construct a ComparatorChain from the Comparators in the
113 * given List. The sort order of each column will be
114 * drawn from the given BitSet. When determining the sort
115 * order for Comparator at index <i>i</i> in the List,
116 * the ComparatorChain will call BitSet.get(<i>i</i>).
117 * If that method returns <i>false</i>, the forward
118 * sort order is used; a return value of <i>true</i>
119 * indicates reverse sort order.
120 *
121 * @param list List of Comparators. NOTE: This constructor does not perform a
122 * defensive copy of the list
123 * @param bits Sort order for each Comparator. Extra bits are ignored,
124 * unless extra Comparators are added by another method.
125 */
126 public ComparatorChain(final List<Comparator<E>> list, final BitSet bits) {
127 comparatorChain = list;
128 orderingBits = bits;
129 }
130
131 //-----------------------------------------------------------------------
132 /**
133 * Add a Comparator to the end of the chain using the
134 * forward sort order
135 *
136 * @param comparator Comparator with the forward sort order
137 */
138 public void addComparator(final Comparator<E> comparator) {
139 addComparator(comparator, false);
140 }
141
142 /**
143 * Add a Comparator to the end of the chain using the
144 * given sort order
145 *
146 * @param comparator Comparator to add to the end of the chain
147 * @param reverse false = forward sort order; true = reverse sort order
148 */
149 public void addComparator(final Comparator<E> comparator, final boolean reverse) {
150 checkLocked();
151
152 comparatorChain.add(comparator);
153 if (reverse == true) {
154 orderingBits.set(comparatorChain.size() - 1);
155 }
156 }
157
158 /**
159 * Replace the Comparator at the given index, maintaining
160 * the existing sort order.
161 *
162 * @param index index of the Comparator to replace
163 * @param comparator Comparator to place at the given index
164 * @exception IndexOutOfBoundsException
165 * if index < 0 or index >= size()
166 */
167 public void setComparator(final int index, final Comparator<E> comparator) throws IndexOutOfBoundsException {
168 setComparator(index, comparator, false);
169 }
170
171 /**
172 * Replace the Comparator at the given index in the
173 * ComparatorChain, using the given sort order
174 *
175 * @param index index of the Comparator to replace
176 * @param comparator Comparator to set
177 * @param reverse false = forward sort order; true = reverse sort order
178 */
179 public void setComparator(final int index, final Comparator<E> comparator, final boolean reverse) {
180 checkLocked();
181
182 comparatorChain.set(index,comparator);
183 if (reverse == true) {
184 orderingBits.set(index);
185 } else {
186 orderingBits.clear(index);
187 }
188 }
189
190 /**
191 * Change the sort order at the given index in the
192 * ComparatorChain to a forward sort.
193 *
194 * @param index Index of the ComparatorChain
195 */
196 public void setForwardSort(final int index) {
197 checkLocked();
198 orderingBits.clear(index);
199 }
200
201 /**
202 * Change the sort order at the given index in the
203 * ComparatorChain to a reverse sort.
204 *
205 * @param index Index of the ComparatorChain
206 */
207 public void setReverseSort(final int index) {
208 checkLocked();
209 orderingBits.set(index);
210 }
211
212 /**
213 * Number of Comparators in the current ComparatorChain.
214 *
215 * @return Comparator count
216 */
217 public int size() {
218 return comparatorChain.size();
219 }
220
221 /**
222 * Determine if modifications can still be made to the
223 * ComparatorChain. ComparatorChains cannot be modified
224 * once they have performed a comparison.
225 *
226 * @return true = ComparatorChain cannot be modified; false =
227 * ComparatorChain can still be modified.
228 */
229 public boolean isLocked() {
230 return isLocked;
231 }
232
233 /**
234 * Throws an exception if the {@link ComparatorChain} is locked.
235 *
236 * @throws UnsupportedOperationException if the {@link ComparatorChain} is locked
237 */
238 private void checkLocked() {
239 if (isLocked == true) {
240 throw new UnsupportedOperationException(
241 "Comparator ordering cannot be changed after the first comparison is performed");
242 }
243 }
244
245 /**
246 * Throws an exception if the {@link ComparatorChain} is empty.
247 *
248 * @throws UnsupportedOperationException if the {@link ComparatorChain} is empty
249 */
250 private void checkChainIntegrity() {
251 if (comparatorChain.size() == 0) {
252 throw new UnsupportedOperationException("ComparatorChains must contain at least one Comparator");
253 }
254 }
255
256 //-----------------------------------------------------------------------
257 /**
258 * Perform comparisons on the Objects as per
259 * Comparator.compare(o1,o2).
260 *
261 * @param o1 the first object to compare
262 * @param o2 the second object to compare
263 * @return -1, 0, or 1
264 * @throws UnsupportedOperationException if the ComparatorChain does not contain at least one Comparator
265 */
266 public int compare(final E o1, final E o2) throws UnsupportedOperationException {
267 if (isLocked == false) {
268 checkChainIntegrity();
269 isLocked = true;
270 }
271
272 // iterate over all comparators in the chain
273 final Iterator<Comparator<E>> comparators = comparatorChain.iterator();
274 for (int comparatorIndex = 0; comparators.hasNext(); ++comparatorIndex) {
275
276 final Comparator<E> comparator = comparators.next();
277 int retval = comparator.compare(o1,o2);
278 if (retval != 0) {
279 // invert the order if it is a reverse sort
280 if (orderingBits.get(comparatorIndex) == true) {
281 if (Integer.MIN_VALUE == retval) {
282 retval = Integer.MAX_VALUE;
283 } else {
284 retval *= -1;
285 }
286 }
287 return retval;
288 }
289 }
290
291 // if comparators are exhausted, return 0
292 return 0;
293 }
294
295 //-----------------------------------------------------------------------
296 /**
297 * Implement a hash code for this comparator that is consistent with
298 * {@link #equals(Object) equals}.
299 *
300 * @return a suitable hash code
301 * @since 3.0
302 */
303 @Override
304 public int hashCode() {
305 int hash = 0;
306 if (null != comparatorChain) {
307 hash ^= comparatorChain.hashCode();
308 }
309 if (null != orderingBits) {
310 hash ^= orderingBits.hashCode();
311 }
312 return hash;
313 }
314
315 /**
316 * Returns <code>true</code> iff <i>that</i> Object is
317 * is a {@link Comparator} whose ordering is known to be
318 * equivalent to mine.
319 * <p>
320 * This implementation returns <code>true</code>
321 * iff <code><i>object</i>.{@link Object#getClass() getClass()}</code>
322 * equals <code>this.getClass()</code>, and the underlying
323 * comparators and order bits are equal.
324 * Subclasses may want to override this behavior to remain consistent
325 * with the {@link Comparator#equals(Object)} contract.
326 *
327 * @param object the object to compare with
328 * @return true if equal
329 * @since 3.0
330 */
331 @Override
332 public boolean equals(final Object object) {
333 if (this == object) {
334 return true;
335 }
336 if (null == object) {
337 return false;
338 }
339 if (object.getClass().equals(this.getClass())) {
340 final ComparatorChain<?> chain = (ComparatorChain<?>) object;
341 return (null == orderingBits ? null == chain.orderingBits : orderingBits.equals(chain.orderingBits)) &&
342 (null == comparatorChain ? null == chain.comparatorChain :
343 comparatorChain.equals(chain.comparatorChain));
344 }
345 return false;
346 }
347
348 }