    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 */
    017package org.apache.commons.collections4.comparators;
    018
    019import java.io.Serializable;
    020import java.util.ArrayList;
    021import java.util.BitSet;
    022import java.util.Comparator;
    023import java.util.Iterator;
    024import java.util.List;
    025
    026/**
    027 * A ComparatorChain is a Comparator that wraps one or more Comparators in
    028 * sequence. The ComparatorChain calls each Comparator in sequence until either
    029 * 1) any single Comparator returns a non-zero result (and that result is then
    030 * returned), or 2) the ComparatorChain is exhausted (and zero is returned).
    031 * This type of sorting is very similar to multi-column sorting in SQL, and this
    032 * class allows Java classes to emulate that kind of behaviour when sorting a
    033 * List.
    034 * <p>
    035 * To further facilitate SQL-like sorting, the order of any single Comparator in
    036 * the list can be reversed.
    037 * </p>
    038 * <p>
    039 * Calling a method that adds new Comparators or changes the ascend/descend sort
    040 * <i>after compare(Object, Object) has been called</i> will result in an
    041 * UnsupportedOperationException. However, <i>take care</i> to not alter the
    042 * underlying List of Comparators or the BitSet that defines the sort order.
    043 * </p>
    044 * <p>
    045 * Instances of ComparatorChain are not synchronized. The class is not
    046 * thread-safe at construction time, but it <i>is</i> thread-safe to perform
    047 * multiple comparisons after all the setup operations are complete.
    048 * </p>
    049 *
    050 * @param <E> the type of objects compared by this comparator
    051 * @since 2.0
    052 */
    053public class ComparatorChain<E> implements Comparator<E>, Serializable {
    054
    055    /** Serialization version from Collections 2.0. */
    056    private static final long serialVersionUID = -721644942746081630L;
    057
    058    /** The list of comparators in the chain. */
    059    private final List<Comparator<E>> comparatorChain;
    060    /** Order - false (clear) = ascend; true (set) = descend. */
    061    private BitSet orderingBits = null;
    062   /** Whether the chain has been "locked". */
    063    private boolean isLocked = false;
    064
    065    //-----------------------------------------------------------------------
    066    /**
    067     * Construct a ComparatorChain with no Comparators.
    068     * You must add at least one Comparator before calling
    069     * the compare(Object,Object) method, or an
    070     * UnsupportedOperationException is thrown
    071     */
    072    public ComparatorChain() {
    073        this(new ArrayList<Comparator<E>>(), new BitSet());
    074    }
    075
    076    /**
    077     * Construct a ComparatorChain with a single Comparator,
    078     * sorting in the forward order
    079     *
    080     * @param comparator First comparator in the Comparator chain
    081     */
    082    public ComparatorChain(final Comparator<E> comparator) {
    083        this(comparator, false);
    084    }
    085
    086    /**
    087     * Construct a Comparator chain with a single Comparator,
    088     * sorting in the given order
    089     *
    090     * @param comparator First Comparator in the ComparatorChain
    091     * @param reverse    false = forward sort; true = reverse sort
    092     */
    093    public ComparatorChain(final Comparator<E> comparator, final boolean reverse) {
    094        comparatorChain = new ArrayList<>(1);
    095        comparatorChain.add(comparator);
    096        orderingBits = new BitSet(1);
    097        if (reverse == true) {
    098            orderingBits.set(0);
    099        }
    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}