    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;
    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 * <i>after compare(Object, Object) has been called</i> will result in an
    042 * UnsupportedOperationException. However, <i>take care</i> 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 <i>is</i> 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    /** Order - false (clear) = ascend; true (set) = descend. */
    062    private final BitSet orderingBits;
    063   /** Whether the chain has been "locked". */
    064    private boolean isLocked;
    065
    066    /**
    067     * Constructs 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<>(), new BitSet());
    074    }
    075
    076    /**
    077     * Constructs 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     * Constructs 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) {
    098            orderingBits.set(0);
    099        }
    100    }
    101
    102    /**
    103     * Constructs 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     * Constructs 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     * Add a Comparator to the end of the chain using the
    136     * forward sort order
    137     *
    138     * @param comparator Comparator with the forward sort order
    139     */
    140    public void addComparator(final Comparator<E> comparator) {
    141        addComparator(comparator, false);
    142    }
    143
    144    /**
    145     * Add a Comparator to the end of the chain using the
    146     * given sort order
    147     *
    148     * @param comparator Comparator to add to the end of the chain
    149     * @param reverse    false = forward sort order; true = reverse sort order
    150     */
    151    public void addComparator(final Comparator<E> comparator, final boolean reverse) {
    152        checkLocked();
    153
    154        comparatorChain.add(comparator);
    155        if (reverse) {
    156            orderingBits.set(comparatorChain.size() - 1);
    157        }
    158    }
    159
    160    /**
    161     * Throws an exception if the {@link ComparatorChain} is empty.
    162     *
    163     * @throws UnsupportedOperationException if the {@link ComparatorChain} is empty
    164     */
    165    private void checkChainIntegrity() {
    166        if (comparatorChain.isEmpty()) {
    167            throw new UnsupportedOperationException("ComparatorChains must contain at least one Comparator");
    168        }
    169    }
    170
    171    /**
    172     * Throws an exception if the {@link ComparatorChain} is locked.
    173     *
    174     * @throws UnsupportedOperationException if the {@link ComparatorChain} is locked
    175     */
    176    private void checkLocked() {
    177        if (isLocked) {
    178            throw new UnsupportedOperationException(
    179                    "Comparator ordering cannot be changed after the first comparison is performed");
    180        }
    181    }
    182
    183    /**
    184     * Perform comparisons on the Objects as per
    185     * Comparator.compare(o1,o2).
    186     *
    187     * @param o1  the first object to compare
    188     * @param o2  the second object to compare
    189     * @return -1, 0, or 1
    190     * @throws UnsupportedOperationException if the ComparatorChain does not contain at least one Comparator
    191     */
    192    @Override
    193    public int compare(final E o1, final E o2) throws UnsupportedOperationException {
    194        if (!isLocked) {
    195            checkChainIntegrity();
    196            isLocked = true;
    197        }
    198
    199        // iterate over all comparators in the chain
    200        final Iterator<Comparator<E>> comparators = comparatorChain.iterator();
    201        for (int comparatorIndex = 0; comparators.hasNext(); ++comparatorIndex) {
    202
    203            final Comparator<? super E> comparator = comparators.next();
    204            int retval = comparator.compare(o1, o2);
    205            if (retval != 0) {
    206                // invert the order if it is a reverse sort
    207                if (orderingBits.get(comparatorIndex)) {
    208                    if (retval > 0) {
    209                        retval = -1;
    210                    } else {
    211                        retval = 1;
    212                    }
    213                }
    214                return retval;
    215            }
    216        }
    217
    218        // if comparators are exhausted, return 0
    219        return 0;
    220    }
    221
    222    /**
    223     * Returns {@code true} iff <i>that</i> Object is
    224     * a {@link Comparator} whose ordering is known to be
    225     * equivalent to mine.
    226     * <p>
    227     * This implementation returns {@code true}
    228     * iff {@code <i>object</i>.{@link Object#getClass() getClass()}}
    229     * equals {@code this.getClass()}, and the underlying
    230     * comparators and order bits are equal.
    231     * Subclasses may want to override this behavior to remain consistent
    232     * with the {@link Comparator#equals(Object)} contract.
    233     *
    234     * @param object  the object to compare with
    235     * @return true if equal
    236     * @since 3.0
    237     */
    238    @Override
    239    public boolean equals(final Object object) {
    240        if (this == object) {
    241            return true;
    242        }
    243        if (null == object) {
    244            return false;
    245        }
    246        if (object.getClass().equals(this.getClass())) {
    247            final ComparatorChain<?> chain = (ComparatorChain<?>) object;
    248            return Objects.equals(orderingBits, chain.orderingBits) &&
    249                   Objects.equals(comparatorChain, chain.comparatorChain);
    250        }
    251        return false;
    252    }
    253
    254    /**
    255     * Implement a hash code for this comparator that is consistent with
    256     * {@link #equals(Object) equals}.
    257     *
    258     * @return a suitable hash code
    259     * @since 3.0
    260     */
    261    @Override
    262    public int hashCode() {
    263        int hash = 0;
    264        if (null != comparatorChain) {
    265            hash ^= comparatorChain.hashCode();
    266        }
    267        if (null != orderingBits) {
    268            hash ^= orderingBits.hashCode();
    269        }
    270        return hash;
    271    }
    272
    273    /**
    274     * Determine if modifications can still be made to the
    275     * ComparatorChain.  ComparatorChains cannot be modified
    276     * once they have performed a comparison.
    277     *
    278     * @return true = ComparatorChain cannot be modified; false =
    279     *         ComparatorChain can still be modified.
    280     */
    281    public boolean isLocked() {
    282        return isLocked;
    283    }
    284
    285    /**
    286     * Replace the Comparator at the given index, maintaining
    287     * the existing sort order.
    288     *
    289     * @param index      index of the Comparator to replace
    290     * @param comparator Comparator to place at the given index
    291     * @throws IndexOutOfBoundsException
    292     *                   if index &lt; 0 or index &gt;= size()
    293     */
    294    public void setComparator(final int index, final Comparator<E> comparator) throws IndexOutOfBoundsException {
    295        setComparator(index, comparator, false);
    296    }
    297
    298    /**
    299     * Replace the Comparator at the given index in the
    300     * ComparatorChain, using the given sort order
    301     *
    302     * @param index      index of the Comparator to replace
    303     * @param comparator Comparator to set
    304     * @param reverse    false = forward sort order; true = reverse sort order
    305     */
    306    public void setComparator(final int index, final Comparator<E> comparator, final boolean reverse) {
    307        checkLocked();
    308
    309        comparatorChain.set(index, comparator);
    310        if (reverse) {
    311            orderingBits.set(index);
    312        } else {
    313            orderingBits.clear(index);
    314        }
    315    }
    316
    317    /**
    318     * Change the sort order at the given index in the
    319     * ComparatorChain to a forward sort.
    320     *
    321     * @param index  Index of the ComparatorChain
    322     */
    323    public void setForwardSort(final int index) {
    324        checkLocked();
    325        orderingBits.clear(index);
    326    }
    327
    328    /**
    329     * Change the sort order at the given index in the
    330     * ComparatorChain to a reverse sort.
    331     *
    332     * @param index  Index of the ComparatorChain
    333     */
    334    public void setReverseSort(final int index) {
    335        checkLocked();
    336        orderingBits.set(index);
    337    }
    338
    339    /**
    340     * Number of Comparators in the current ComparatorChain.
    341     *
    342     * @return Comparator count
    343     */
    344    public int size() {
    345        return comparatorChain.size();
    346    }
    347
    348}