001 /*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements. See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License. You may obtain a copy of the License at
008 *
009 * http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017 package org.apache.commons.collections.comparators;
018
019 import java.io.Serializable;
020 import java.util.ArrayList;
021 import java.util.BitSet;
022 import java.util.Comparator;
023 import java.util.Iterator;
024 import java.util.List;
025
026 /**
027 * <p>A ComparatorChain is a Comparator that wraps one or
028 * more Comparators in sequence. The ComparatorChain
029 * calls each Comparator in sequence until either 1)
030 * any single Comparator returns a non-zero result
031 * (and that result is then returned),
032 * or 2) the ComparatorChain is exhausted (and zero is
033 * returned). This type of sorting is very similar
034 * to multi-column sorting in SQL, and this class
035 * allows Java classes to emulate that kind of behaviour
036 * when sorting a List.</p>
037 *
038 * <p>To further facilitate SQL-like sorting, the order of
039 * any single Comparator in the list can be reversed.</p>
040 *
041 * <p>Calling a method that adds new Comparators or
042 * changes the ascend/descend sort <i>after compare(Object,
043 * Object) has been called</i> will result in an
044 * UnsupportedOperationException. However, <i>take care</i>
045 * to not alter the underlying List of Comparators
046 * or the BitSet that defines the sort order.</p>
047 *
048 * <p>Instances of ComparatorChain are not synchronized.
049 * The class is not thread-safe at construction time, but
050 * it <i>is</i> thread-safe to perform multiple comparisons
051 * after all the setup operations are complete.</p>
052 *
053 * @since Commons Collections 2.0
054 * @author Morgan Delagrange
055 * @version $Revision: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $
056 */
057 public class ComparatorChain implements Comparator, Serializable {
058
059 /** Serialization version from Collections 2.0. */
060 private static final long serialVersionUID = -721644942746081630L;
061
062 /** The list of comparators in the chain. */
063 protected List comparatorChain = null;
064 /** Order - false (clear) = ascend; true (set) = descend. */
065 protected BitSet orderingBits = null;
066 /** Whether the chain has been "locked". */
067 protected boolean isLocked = false;
068
069 //-----------------------------------------------------------------------
070 /**
071 * Construct a ComparatorChain with no Comparators.
072 * You must add at least one Comparator before calling
073 * the compare(Object,Object) method, or an
074 * UnsupportedOperationException is thrown
075 */
076 public ComparatorChain() {
077 this(new ArrayList(),new BitSet());
078 }
079
080 /**
081 * Construct a ComparatorChain with a single Comparator,
082 * sorting in the forward order
083 *
084 * @param comparator First comparator in the Comparator chain
085 */
086 public ComparatorChain(Comparator comparator) {
087 this(comparator,false);
088 }
089
090 /**
091 * Construct a Comparator chain with a single Comparator,
092 * sorting in the given order
093 *
094 * @param comparator First Comparator in the ComparatorChain
095 * @param reverse false = forward sort; true = reverse sort
096 */
097 public ComparatorChain(Comparator comparator, boolean reverse) {
098 comparatorChain = new ArrayList();
099 comparatorChain.add(comparator);
100 orderingBits = new BitSet(1);
101 if (reverse == true) {
102 orderingBits.set(0);
103 }
104 }
105
106 /**
107 * Construct a ComparatorChain from the Comparators in the
108 * List. All Comparators will default to the forward
109 * sort order.
110 *
111 * @param list List of Comparators
112 * @see #ComparatorChain(List,BitSet)
113 */
114 public ComparatorChain(List list) {
115 this(list,new BitSet(list.size()));
116 }
117
118 /**
119 * Construct a ComparatorChain from the Comparators in the
120 * given List. The sort order of each column will be
121 * drawn from the given BitSet. When determining the sort
122 * order for Comparator at index <i>i</i> in the List,
123 * the ComparatorChain will call BitSet.get(<i>i</i>).
124 * If that method returns <i>false</i>, the forward
125 * sort order is used; a return value of <i>true</i>
126 * indicates reverse sort order.
127 *
128 * @param list List of Comparators. NOTE: This constructor does not perform a
129 * defensive copy of the list
130 * @param bits Sort order for each Comparator. Extra bits are ignored,
131 * unless extra Comparators are added by another method.
132 */
133 public ComparatorChain(List list, BitSet bits) {
134 comparatorChain = list;
135 orderingBits = bits;
136 }
137
138 //-----------------------------------------------------------------------
139 /**
140 * Add a Comparator to the end of the chain using the
141 * forward sort order
142 *
143 * @param comparator Comparator with the forward sort order
144 */
145 public void addComparator(Comparator comparator) {
146 addComparator(comparator,false);
147 }
148
149 /**
150 * Add a Comparator to the end of the chain using the
151 * given sort order
152 *
153 * @param comparator Comparator to add to the end of the chain
154 * @param reverse false = forward sort order; true = reverse sort order
155 */
156 public void addComparator(Comparator comparator, boolean reverse) {
157 checkLocked();
158
159 comparatorChain.add(comparator);
160 if (reverse == true) {
161 orderingBits.set(comparatorChain.size() - 1);
162 }
163 }
164
165 /**
166 * Replace the Comparator at the given index, maintaining
167 * the existing sort order.
168 *
169 * @param index index of the Comparator to replace
170 * @param comparator Comparator to place at the given index
171 * @exception IndexOutOfBoundsException
172 * if index < 0 or index >= size()
173 */
174 public void setComparator(int index, Comparator comparator)
175 throws IndexOutOfBoundsException {
176 setComparator(index,comparator,false);
177 }
178
179 /**
180 * Replace the Comparator at the given index in the
181 * ComparatorChain, using the given sort order
182 *
183 * @param index index of the Comparator to replace
184 * @param comparator Comparator to set
185 * @param reverse false = forward sort order; true = reverse sort order
186 */
187 public void setComparator(int index, Comparator comparator, boolean reverse) {
188 checkLocked();
189
190 comparatorChain.set(index,comparator);
191 if (reverse == true) {
192 orderingBits.set(index);
193 } else {
194 orderingBits.clear(index);
195 }
196 }
197
198
199 /**
200 * Change the sort order at the given index in the
201 * ComparatorChain to a forward sort.
202 *
203 * @param index Index of the ComparatorChain
204 */
205 public void setForwardSort(int index) {
206 checkLocked();
207 orderingBits.clear(index);
208 }
209
210 /**
211 * Change the sort order at the given index in the
212 * ComparatorChain to a reverse sort.
213 *
214 * @param index Index of the ComparatorChain
215 */
216 public void setReverseSort(int index) {
217 checkLocked();
218 orderingBits.set(index);
219 }
220
221 /**
222 * Number of Comparators in the current ComparatorChain.
223 *
224 * @return Comparator count
225 */
226 public int size() {
227 return comparatorChain.size();
228 }
229
230 /**
231 * Determine if modifications can still be made to the
232 * ComparatorChain. ComparatorChains cannot be modified
233 * once they have performed a comparison.
234 *
235 * @return true = ComparatorChain cannot be modified; false =
236 * ComparatorChain can still be modified.
237 */
238 public boolean isLocked() {
239 return isLocked;
240 }
241
242 // throw an exception if the ComparatorChain is locked
243 private void checkLocked() {
244 if (isLocked == true) {
245 throw new UnsupportedOperationException("Comparator ordering cannot be changed after the first comparison is performed");
246 }
247 }
248
249 private void checkChainIntegrity() {
250 if (comparatorChain.size() == 0) {
251 throw new UnsupportedOperationException("ComparatorChains must contain at least one Comparator");
252 }
253 }
254
255 //-----------------------------------------------------------------------
256 /**
257 * Perform comparisons on the Objects as per
258 * Comparator.compare(o1,o2).
259 *
260 * @param o1 the first object to compare
261 * @param o2 the second object to compare
262 * @return -1, 0, or 1
263 * @exception UnsupportedOperationException
264 * if the ComparatorChain does not contain at least one
265 * Comparator
266 */
267 public int compare(Object o1, Object o2) throws UnsupportedOperationException {
268 if (isLocked == false) {
269 checkChainIntegrity();
270 isLocked = true;
271 }
272
273 // iterate over all comparators in the chain
274 Iterator comparators = comparatorChain.iterator();
275 for (int comparatorIndex = 0; comparators.hasNext(); ++comparatorIndex) {
276
277 Comparator comparator = (Comparator) comparators.next();
278 int retval = comparator.compare(o1,o2);
279 if (retval != 0) {
280 // invert the order if it is a reverse sort
281 if (orderingBits.get(comparatorIndex) == true) {
282 if(Integer.MIN_VALUE == retval) {
283 retval = Integer.MAX_VALUE;
284 } else {
285 retval *= -1;
286 }
287 }
288
289 return retval;
290 }
291
292 }
293
294 // if comparators are exhausted, return 0
295 return 0;
296 }
297
298 //-----------------------------------------------------------------------
299 /**
300 * Implement a hash code for this comparator that is consistent with
301 * {@link #equals(Object) equals}.
302 *
303 * @return a suitable hash code
304 * @since Commons Collections 3.0
305 */
306 public int hashCode() {
307 int hash = 0;
308 if(null != comparatorChain) {
309 hash ^= comparatorChain.hashCode();
310 }
311 if(null != orderingBits) {
312 hash ^= orderingBits.hashCode();
313 }
314 return hash;
315 }
316
317 /**
318 * Returns <code>true</code> iff <i>that</i> Object is
319 * is a {@link Comparator} whose ordering is known to be
320 * equivalent to mine.
321 * <p>
322 * This implementation returns <code>true</code>
323 * iff <code><i>object</i>.{@link Object#getClass() getClass()}</code>
324 * equals <code>this.getClass()</code>, and the underlying
325 * comparators and order bits are equal.
326 * Subclasses may want to override this behavior to remain consistent
327 * with the {@link Comparator#equals(Object)} contract.
328 *
329 * @param object the object to compare with
330 * @return true if equal
331 * @since Commons Collections 3.0
332 */
333 public boolean equals(Object object) {
334 if(this == object) {
335 return true;
336 } else if(null == object) {
337 return false;
338 } else if(object.getClass().equals(this.getClass())) {
339 ComparatorChain chain = (ComparatorChain)object;
340 return ( (null == orderingBits ? null == chain.orderingBits : orderingBits.equals(chain.orderingBits))
341 && (null == comparatorChain ? null == chain.comparatorChain : comparatorChain.equals(chain.comparatorChain)) );
342 } else {
343 return false;
344 }
345 }
346
347 }