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