View Javadoc
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.collections4.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   * <p>
39   * Calling a method that adds new Comparators or changes the ascend/descend sort
40   * <i>after compare(Object, Object) has been called</i> will result in an
41   * UnsupportedOperationException. However, <i>take care</i> to not alter the
42   * underlying List of Comparators or the BitSet that defines the sort order.
43   * </p>
44   * <p>
45   * Instances of ComparatorChain are not synchronized. The class is not
46   * thread-safe at construction time, but it <i>is</i> thread-safe to perform
47   * multiple comparisons after all the setup operations are complete.
48   * </p>
49   *
50   * @param <E> the type of objects compared by this comparator
51   * @since 2.0
52   */
53  public class ComparatorChain<E> implements Comparator<E>, Serializable {
54  
55      /** Serialization version from Collections 2.0. */
56      private static final long serialVersionUID = -721644942746081630L;
57  
58      /** The list of comparators in the chain. */
59      private final List<Comparator<E>> comparatorChain;
60      /** Order - false (clear) = ascend; true (set) = descend. */
61      private BitSet orderingBits = null;
62     /** Whether the chain has been "locked". */
63      private boolean isLocked = false;
64  
65      //-----------------------------------------------------------------------
66      /**
67       * Construct a ComparatorChain with no Comparators.
68       * You must add at least one Comparator before calling
69       * the compare(Object,Object) method, or an
70       * UnsupportedOperationException is thrown
71       */
72      public ComparatorChain() {
73          this(new ArrayList<Comparator<E>>(), new BitSet());
74      }
75  
76      /**
77       * Construct a ComparatorChain with a single Comparator,
78       * sorting in the forward order
79       *
80       * @param comparator First comparator in the Comparator chain
81       */
82      public ComparatorChain(final Comparator<E> comparator) {
83          this(comparator, false);
84      }
85  
86      /**
87       * Construct a Comparator chain with a single Comparator,
88       * sorting in the given order
89       *
90       * @param comparator First Comparator in the ComparatorChain
91       * @param reverse    false = forward sort; true = reverse sort
92       */
93      public ComparatorChain(final Comparator<E> comparator, final boolean reverse) {
94          comparatorChain = new ArrayList<>(1);
95          comparatorChain.add(comparator);
96          orderingBits = new BitSet(1);
97          if (reverse == true) {
98              orderingBits.set(0);
99          }
100     }
101 
102     /**
103      * Construct a ComparatorChain from the Comparators in the
104      * List.  All Comparators will default to the forward
105      * sort order.
106      *
107      * @param list   List of Comparators
108      * @see #ComparatorChain(List,BitSet)
109      */
110     public ComparatorChain(final List<Comparator<E>> list) {
111         this(list, new BitSet(list.size()));
112     }
113 
114     /**
115      * Construct a ComparatorChain from the Comparators in the
116      * given List.  The sort order of each column will be
117      * drawn from the given BitSet.  When determining the sort
118      * order for Comparator at index <i>i</i> in the List,
119      * the ComparatorChain will call BitSet.get(<i>i</i>).
120      * If that method returns <i>false</i>, the forward
121      * sort order is used; a return value of <i>true</i>
122      * indicates reverse sort order.
123      *
124      * @param list   List of Comparators.  NOTE: This constructor does not perform a
125      *               defensive copy of the list
126      * @param bits   Sort order for each Comparator.  Extra bits are ignored,
127      *               unless extra Comparators are added by another method.
128      */
129     public ComparatorChain(final List<Comparator<E>> list, final BitSet bits) {
130         comparatorChain = list;
131         orderingBits = bits;
132     }
133 
134     //-----------------------------------------------------------------------
135     /**
136      * Add a Comparator to the end of the chain using the
137      * forward sort order
138      *
139      * @param comparator Comparator with the forward sort order
140      */
141     public void addComparator(final Comparator<E> comparator) {
142         addComparator(comparator, false);
143     }
144 
145     /**
146      * Add a Comparator to the end of the chain using the
147      * given sort order
148      *
149      * @param comparator Comparator to add to the end of the chain
150      * @param reverse    false = forward sort order; true = reverse sort order
151      */
152     public void addComparator(final Comparator<E> comparator, final boolean reverse) {
153         checkLocked();
154 
155         comparatorChain.add(comparator);
156         if (reverse == true) {
157             orderingBits.set(comparatorChain.size() - 1);
158         }
159     }
160 
161     /**
162      * Replace the Comparator at the given index, maintaining
163      * the existing sort order.
164      *
165      * @param index      index of the Comparator to replace
166      * @param comparator Comparator to place at the given index
167      * @throws IndexOutOfBoundsException
168      *                   if index &lt; 0 or index &gt;= size()
169      */
170     public void setComparator(final int index, final Comparator<E> comparator) throws IndexOutOfBoundsException {
171         setComparator(index, comparator, false);
172     }
173 
174     /**
175      * Replace the Comparator at the given index in the
176      * ComparatorChain, using the given sort order
177      *
178      * @param index      index of the Comparator to replace
179      * @param comparator Comparator to set
180      * @param reverse    false = forward sort order; true = reverse sort order
181      */
182     public void setComparator(final int index, final Comparator<E> comparator, final boolean reverse) {
183         checkLocked();
184 
185         comparatorChain.set(index,comparator);
186         if (reverse == true) {
187             orderingBits.set(index);
188         } else {
189             orderingBits.clear(index);
190         }
191     }
192 
193     /**
194      * Change the sort order at the given index in the
195      * ComparatorChain to a forward sort.
196      *
197      * @param index  Index of the ComparatorChain
198      */
199     public void setForwardSort(final int index) {
200         checkLocked();
201         orderingBits.clear(index);
202     }
203 
204     /**
205      * Change the sort order at the given index in the
206      * ComparatorChain to a reverse sort.
207      *
208      * @param index  Index of the ComparatorChain
209      */
210     public void setReverseSort(final int index) {
211         checkLocked();
212         orderingBits.set(index);
213     }
214 
215     /**
216      * Number of Comparators in the current ComparatorChain.
217      *
218      * @return Comparator count
219      */
220     public int size() {
221         return comparatorChain.size();
222     }
223 
224     /**
225      * Determine if modifications can still be made to the
226      * ComparatorChain.  ComparatorChains cannot be modified
227      * once they have performed a comparison.
228      *
229      * @return true = ComparatorChain cannot be modified; false =
230      *         ComparatorChain can still be modified.
231      */
232     public boolean isLocked() {
233         return isLocked;
234     }
235 
236     /**
237      * Throws an exception if the {@link ComparatorChain} is locked.
238      *
239      * @throws UnsupportedOperationException if the {@link ComparatorChain} is locked
240      */
241     private void checkLocked() {
242         if (isLocked == true) {
243             throw new UnsupportedOperationException(
244                     "Comparator ordering cannot be changed after the first comparison is performed");
245         }
246     }
247 
248     /**
249      * Throws an exception if the {@link ComparatorChain} is empty.
250      *
251      * @throws UnsupportedOperationException if the {@link ComparatorChain} is empty
252      */
253     private void checkChainIntegrity() {
254         if (comparatorChain.size() == 0) {
255             throw new UnsupportedOperationException("ComparatorChains must contain at least one Comparator");
256         }
257     }
258 
259     //-----------------------------------------------------------------------
260     /**
261      * Perform comparisons on the Objects as per
262      * Comparator.compare(o1,o2).
263      *
264      * @param o1  the first object to compare
265      * @param o2  the second object to compare
266      * @return -1, 0, or 1
267      * @throws UnsupportedOperationException if the ComparatorChain does not contain at least one Comparator
268      */
269     @Override
270     public int compare(final E o1, final E o2) throws UnsupportedOperationException {
271         if (isLocked == false) {
272             checkChainIntegrity();
273             isLocked = true;
274         }
275 
276         // iterate over all comparators in the chain
277         final Iterator<Comparator<E>> comparators = comparatorChain.iterator();
278         for (int comparatorIndex = 0; comparators.hasNext(); ++comparatorIndex) {
279 
280             final Comparator<? super E> comparator = comparators.next();
281             int retval = comparator.compare(o1,o2);
282             if (retval != 0) {
283                 // invert the order if it is a reverse sort
284                 if (orderingBits.get(comparatorIndex) == true) {
285                     if (retval > 0) {
286                         retval = -1;
287                     } else {
288                         retval = 1;
289                     }
290                 }
291                 return retval;
292             }
293         }
294 
295         // if comparators are exhausted, return 0
296         return 0;
297     }
298 
299     //-----------------------------------------------------------------------
300     /**
301      * Implement a hash code for this comparator that is consistent with
302      * {@link #equals(Object) equals}.
303      *
304      * @return a suitable hash code
305      * @since 3.0
306      */
307     @Override
308     public int hashCode() {
309         int hash = 0;
310         if (null != comparatorChain) {
311             hash ^= comparatorChain.hashCode();
312         }
313         if (null != orderingBits) {
314             hash ^= orderingBits.hashCode();
315         }
316         return hash;
317     }
318 
319     /**
320      * Returns <code>true</code> iff <i>that</i> Object is
321      * is a {@link Comparator} whose ordering is known to be
322      * equivalent to mine.
323      * <p>
324      * This implementation returns <code>true</code>
325      * iff <code><i>object</i>.{@link Object#getClass() getClass()}</code>
326      * equals <code>this.getClass()</code>, and the underlying
327      * comparators and order bits are equal.
328      * Subclasses may want to override this behavior to remain consistent
329      * with the {@link Comparator#equals(Object)} contract.
330      *
331      * @param object  the object to compare with
332      * @return true if equal
333      * @since 3.0
334      */
335     @Override
336     public boolean equals(final Object object) {
337         if (this == object) {
338             return true;
339         }
340         if (null == object) {
341             return false;
342         }
343         if (object.getClass().equals(this.getClass())) {
344             final ComparatorChain<?> chain = (ComparatorChain<?>) object;
345             return (null == orderingBits ? null == chain.orderingBits : orderingBits.equals(chain.orderingBits)) &&
346                    (null == comparatorChain ? null == chain.comparatorChain :
347                                               comparatorChain.equals(chain.comparatorChain));
348         }
349         return false;
350     }
351 
352 }