    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 * Calling a method that adds new Comparators or changes the ascend/descend sort
    039 * <i>after compare(Object, Object) has been called</i> will result in an
    040 * UnsupportedOperationException. However, <i>take care</i> to not alter the
    041 * underlying List of Comparators or the BitSet that defines the sort order.
    042 * <p>
    043 * Instances of ComparatorChain are not synchronized. The class is not
    044 * thread-safe at construction time, but it <i>is</i> thread-safe to perform
    045 * multiple comparisons after all the setup operations are complete.
    046 *
    047 * @param <E> the type of objects compared by this comparator
    048 * @since 2.0
    049 */
    050public class ComparatorChain<E> implements Comparator<E>, Serializable {
    051
    052    /** Serialization version from Collections 2.0. */
    053    private static final long serialVersionUID = -721644942746081630L;
    054
    055    /** The list of comparators in the chain. */
    056    private final List<Comparator<E>> comparatorChain;
    057    /** Order - false (clear) = ascend; true (set) = descend. */
    058    private BitSet orderingBits = null;
    059   /** Whether the chain has been "locked". */
    060    private boolean isLocked = false;
    061
    062    //-----------------------------------------------------------------------
    063    /**
    064     * Construct a ComparatorChain with no Comparators.
    065     * You must add at least one Comparator before calling
    066     * the compare(Object,Object) method, or an
    067     * UnsupportedOperationException is thrown
    068     */
    069    public ComparatorChain() {
    070        this(new ArrayList<Comparator<E>>(), new BitSet());
    071    }
    072
    073    /**
    074     * Construct a ComparatorChain with a single Comparator,
    075     * sorting in the forward order
    076     *
    077     * @param comparator First comparator in the Comparator chain
    078     */
    079    public ComparatorChain(final Comparator<E> comparator) {
    080        this(comparator, false);
    081    }
    082
    083    /**
    084     * Construct a Comparator chain with a single Comparator,
    085     * sorting in the given order
    086     *
    087     * @param comparator First Comparator in the ComparatorChain
    088     * @param reverse    false = forward sort; true = reverse sort
    089     */
    090    public ComparatorChain(final Comparator<E> comparator, final boolean reverse) {
    091        comparatorChain = new ArrayList<>(1);
    092        comparatorChain.add(comparator);
    093        orderingBits = new BitSet(1);
    094        if (reverse == true) {
    095            orderingBits.set(0);
    096        }
    097    }
    098
    099    /**
    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     * @throws IndexOutOfBoundsException
    165     *                   if index &lt; 0 or index &gt;= 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    @Override
    267    public int compare(final E o1, final E o2) throws UnsupportedOperationException {
    268        if (isLocked == false) {
    269            checkChainIntegrity();
    270            isLocked = true;
    271        }
    272
    273        // iterate over all comparators in the chain
    274        final Iterator<Comparator<E>> comparators = comparatorChain.iterator();
    275        for (int comparatorIndex = 0; comparators.hasNext(); ++comparatorIndex) {
    276
    277            final Comparator<? super E> 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 (retval > 0) {
    283                        retval = -1;
    284                    } else {
    285                        retval = 1;
    286                    }
    287                }
    288                return retval;
    289            }
    290        }
    291
    292        // if comparators are exhausted, return 0
    293        return 0;
    294    }
    295
    296    //-----------------------------------------------------------------------
    297    /**
    298     * Implement a hash code for this comparator that is consistent with
    299     * {@link #equals(Object) equals}.
    300     *
    301     * @return a suitable hash code
    302     * @since 3.0
    303     */
    304    @Override
    305    public int hashCode() {
    306        int hash = 0;
    307        if (null != comparatorChain) {
    308            hash ^= comparatorChain.hashCode();
    309        }
    310        if (null != orderingBits) {
    311            hash ^= orderingBits.hashCode();
    312        }
    313        return hash;
    314    }
    315
    316    /**
    317     * Returns <code>true</code> iff <i>that</i> Object is
    318     * is a {@link Comparator} whose ordering is known to be
    319     * equivalent to mine.
    320     * <p>
    321     * This implementation returns <code>true</code>
    322     * iff <code><i>object</i>.{@link Object#getClass() getClass()}</code>
    323     * equals <code>this.getClass()</code>, and the underlying
    324     * comparators and order bits are equal.
    325     * Subclasses may want to override this behavior to remain consistent
    326     * with the {@link Comparator#equals(Object)} contract.
    327     *
    328     * @param object  the object to compare with
    329     * @return true if equal
    330     * @since 3.0
    331     */
    332    @Override
    333    public boolean equals(final Object object) {
    334        if (this == object) {
    335            return true;
    336        }
    337        if (null == object) {
    338            return false;
    339        }
    340        if (object.getClass().equals(this.getClass())) {
    341            final ComparatorChain<?> chain = (ComparatorChain<?>) object;
    342            return (null == orderingBits ? null == chain.orderingBits : orderingBits.equals(chain.orderingBits)) &&
    343                   (null == comparatorChain ? null == chain.comparatorChain :
    344                                              comparatorChain.equals(chain.comparatorChain));
    345        }
    346        return false;
    347    }
    348
    349}