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 &lt; 0 or index &gt;= 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    }