/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.commons.collections4.comparators;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;

A ComparatorChain is a Comparator that wraps one or more Comparators in
sequence. The ComparatorChain calls each Comparator in sequence until either
1) any single Comparator returns a non-zero result (and that result is then
returned), or 2) the ComparatorChain is exhausted (and zero is returned).
This type of sorting is very similar to multi-column sorting in SQL, and this
class allows Java classes to emulate that kind of behaviour when sorting a
List.

To further facilitate SQL-like sorting, the order of any single Comparator in
the list can be reversed.


Calling a method that adds new Comparators or changes the ascend/descend sort
after compare(Object, Object) has been called will result in an
UnsupportedOperationException. However, take care to not alter the
underlying List of Comparators or the BitSet that defines the sort order.


Instances of ComparatorChain are not synchronized. The class is not
thread-safe at construction time, but it is thread-safe to perform
multiple comparisons after all the setup operations are complete.

Type parameters:
<E> – the type of objects compared by this comparator
Since:
2.0/**
 * A ComparatorChain is a Comparator that wraps one or more Comparators in
 * sequence. The ComparatorChain calls each Comparator in sequence until either
 * 1) any single Comparator returns a non-zero result (and that result is then
 * returned), or 2) the ComparatorChain is exhausted (and zero is returned).
 * This type of sorting is very similar to multi-column sorting in SQL, and this
 * class allows Java classes to emulate that kind of behaviour when sorting a
 * List.
 * <p>
 * To further facilitate SQL-like sorting, the order of any single Comparator in
 * the list can be reversed.
 * </p>
 * <p>
 * Calling a method that adds new Comparators or changes the ascend/descend sort
 * <i>after compare(Object, Object) has been called</i> will result in an
 * UnsupportedOperationException. However, <i>take care</i> to not alter the
 * underlying List of Comparators or the BitSet that defines the sort order.
 * </p>
 * <p>
 * Instances of ComparatorChain are not synchronized. The class is not
 * thread-safe at construction time, but it <i>is</i> thread-safe to perform
 * multiple comparisons after all the setup operations are complete.
 * </p>
 *
 * @param <E> the type of objects compared by this comparator
 * @since 2.0
 */
public class ComparatorChain<E> implements Comparator<E>, Serializable {

    
Serialization version from Collections 2.0. /** Serialization version from Collections 2.0. */
    private static final long serialVersionUID = -721644942746081630L;

    
The list of comparators in the chain. /** The list of comparators in the chain. */
    private final List<Comparator<E>> comparatorChain;
    
Order - false (clear) = ascend; true (set) = descend. /** Order - false (clear) = ascend; true (set) = descend. */
    private BitSet orderingBits = null;
   
Whether the chain has been "locked". /** Whether the chain has been "locked". */
    private boolean isLocked = false;

    //-----------------------------------------------------------------------
    
Construct a ComparatorChain with no Comparators.
You must add at least one Comparator before calling
the compare(Object,Object) method, or an
UnsupportedOperationException is thrown
/**
     * Construct a ComparatorChain with no Comparators.
     * You must add at least one Comparator before calling
     * the compare(Object,Object) method, or an
     * UnsupportedOperationException is thrown
     */
    public ComparatorChain() {
        this(new ArrayList<Comparator<E>>(), new BitSet());
    }

    
Construct a ComparatorChain with a single Comparator,
sorting in the forward order
Params:
comparator – First comparator in the Comparator chain/**
     * Construct a ComparatorChain with a single Comparator,
     * sorting in the forward order
     *
     * @param comparator First comparator in the Comparator chain
     */
    public ComparatorChain(final Comparator<E> comparator) {
        this(comparator, false);
    }

    
Construct a Comparator chain with a single Comparator,
sorting in the given order
Params:
comparator – First Comparator in the ComparatorChain
reverse –    false = forward sort; true = reverse sort/**
     * Construct a Comparator chain with a single Comparator,
     * sorting in the given order
     *
     * @param comparator First Comparator in the ComparatorChain
     * @param reverse    false = forward sort; true = reverse sort
     */
    public ComparatorChain(final Comparator<E> comparator, final boolean reverse) {
        comparatorChain = new ArrayList<>(1);
        comparatorChain.add(comparator);
        orderingBits = new BitSet(1);
        if (reverse == true) {
            orderingBits.set(0);
        }
    }

    
Construct a ComparatorChain from the Comparators in the
List.  All Comparators will default to the forward
sort order.
Params:
list –   List of Comparators
See Also:
ComparatorChain(List, BitSet)/**
     * Construct a ComparatorChain from the Comparators in the
     * List.  All Comparators will default to the forward
     * sort order.
     *
     * @param list   List of Comparators
     * @see #ComparatorChain(List,BitSet)
     */
    public ComparatorChain(final List<Comparator<E>> list) {
        this(list, new BitSet(list.size()));
    }

    
Construct a ComparatorChain from the Comparators in the
given List.  The sort order of each column will be
drawn from the given BitSet.  When determining the sort
order for Comparator at index i in the List,
the ComparatorChain will call BitSet.get(i).
If that method returns false, the forward
sort order is used; a return value of true
indicates reverse sort order.
Params:
list –   List of Comparators.  NOTE: This constructor does not perform a
              defensive copy of the list
bits –   Sort order for each Comparator.  Extra bits are ignored,
              unless extra Comparators are added by another method./**
     * Construct a ComparatorChain from the Comparators in the
     * given List.  The sort order of each column will be
     * drawn from the given BitSet.  When determining the sort
     * order for Comparator at index <i>i</i> in the List,
     * the ComparatorChain will call BitSet.get(<i>i</i>).
     * If that method returns <i>false</i>, the forward
     * sort order is used; a return value of <i>true</i>
     * indicates reverse sort order.
     *
     * @param list   List of Comparators.  NOTE: This constructor does not perform a
     *               defensive copy of the list
     * @param bits   Sort order for each Comparator.  Extra bits are ignored,
     *               unless extra Comparators are added by another method.
     */
    public ComparatorChain(final List<Comparator<E>> list, final BitSet bits) {
        comparatorChain = list;
        orderingBits = bits;
    }

    //-----------------------------------------------------------------------
    
Add a Comparator to the end of the chain using the
forward sort order
Params:
comparator – Comparator with the forward sort order/**
     * Add a Comparator to the end of the chain using the
     * forward sort order
     *
     * @param comparator Comparator with the forward sort order
     */
    public void addComparator(final Comparator<E> comparator) {
        addComparator(comparator, false);
    }

    
Add a Comparator to the end of the chain using the
given sort order
Params:
comparator – Comparator to add to the end of the chain
reverse –    false = forward sort order; true = reverse sort order/**
     * Add a Comparator to the end of the chain using the
     * given sort order
     *
     * @param comparator Comparator to add to the end of the chain
     * @param reverse    false = forward sort order; true = reverse sort order
     */
    public void addComparator(final Comparator<E> comparator, final boolean reverse) {
        checkLocked();

        comparatorChain.add(comparator);
        if (reverse == true) {
            orderingBits.set(comparatorChain.size() - 1);
        }
    }

    
Replace the Comparator at the given index, maintaining
the existing sort order.
Params:
index –      index of the Comparator to replace
comparator – Comparator to place at the given index
Throws:
IndexOutOfBoundsException – 
                  if index < 0 or index >= size()/**
     * Replace the Comparator at the given index, maintaining
     * the existing sort order.
     *
     * @param index      index of the Comparator to replace
     * @param comparator Comparator to place at the given index
     * @throws IndexOutOfBoundsException
     *                   if index &lt; 0 or index &gt;= size()
     */
    public void setComparator(final int index, final Comparator<E> comparator) throws IndexOutOfBoundsException {
        setComparator(index, comparator, false);
    }

    
Replace the Comparator at the given index in the
ComparatorChain, using the given sort order
Params:
index –      index of the Comparator to replace
comparator – Comparator to set
reverse –    false = forward sort order; true = reverse sort order/**
     * Replace the Comparator at the given index in the
     * ComparatorChain, using the given sort order
     *
     * @param index      index of the Comparator to replace
     * @param comparator Comparator to set
     * @param reverse    false = forward sort order; true = reverse sort order
     */
    public void setComparator(final int index, final Comparator<E> comparator, final boolean reverse) {
        checkLocked();

        comparatorChain.set(index,comparator);
        if (reverse == true) {
            orderingBits.set(index);
        } else {
            orderingBits.clear(index);
        }
    }

    
Change the sort order at the given index in the
ComparatorChain to a forward sort.
Params:
index –  Index of the ComparatorChain/**
     * Change the sort order at the given index in the
     * ComparatorChain to a forward sort.
     *
     * @param index  Index of the ComparatorChain
     */
    public void setForwardSort(final int index) {
        checkLocked();
        orderingBits.clear(index);
    }

    
Change the sort order at the given index in the
ComparatorChain to a reverse sort.
Params:
index –  Index of the ComparatorChain/**
     * Change the sort order at the given index in the
     * ComparatorChain to a reverse sort.
     *
     * @param index  Index of the ComparatorChain
     */
    public void setReverseSort(final int index) {
        checkLocked();
        orderingBits.set(index);
    }

    
Number of Comparators in the current ComparatorChain.
Returns:
Comparator count/**
     * Number of Comparators in the current ComparatorChain.
     *
     * @return Comparator count
     */
    public int size() {
        return comparatorChain.size();
    }

    
Determine if modifications can still be made to the
ComparatorChain.  ComparatorChains cannot be modified
once they have performed a comparison.
Returns:
true = ComparatorChain cannot be modified; false =
        ComparatorChain can still be modified./**
     * Determine if modifications can still be made to the
     * ComparatorChain.  ComparatorChains cannot be modified
     * once they have performed a comparison.
     *
     * @return true = ComparatorChain cannot be modified; false =
     *         ComparatorChain can still be modified.
     */
    public boolean isLocked() {
        return isLocked;
    }

    
Throws an exception if the ComparatorChain is locked. 
Throws:
UnsupportedOperationException – if the ComparatorChain is locked/**
     * Throws an exception if the {@link ComparatorChain} is locked.
     *
     * @throws UnsupportedOperationException if the {@link ComparatorChain} is locked
     */
    private void checkLocked() {
        if (isLocked == true) {
            throw new UnsupportedOperationException(
                    "Comparator ordering cannot be changed after the first comparison is performed");
        }
    }

    
Throws an exception if the ComparatorChain is empty. 
Throws:
UnsupportedOperationException – if the ComparatorChain is empty/**
     * Throws an exception if the {@link ComparatorChain} is empty.
     *
     * @throws UnsupportedOperationException if the {@link ComparatorChain} is empty
     */
    private void checkChainIntegrity() {
        if (comparatorChain.size() == 0) {
            throw new UnsupportedOperationException("ComparatorChains must contain at least one Comparator");
        }
    }

    //-----------------------------------------------------------------------
    
Perform comparisons on the Objects as per
Comparator.compare(o1,o2).
Params:
o1 –  the first object to compare
o2 –  the second object to compare
Throws:
UnsupportedOperationException – if the ComparatorChain does not contain at least one Comparator
Returns:
-1, 0, or 1/**
     * Perform comparisons on the Objects as per
     * Comparator.compare(o1,o2).
     *
     * @param o1  the first object to compare
     * @param o2  the second object to compare
     * @return -1, 0, or 1
     * @throws UnsupportedOperationException if the ComparatorChain does not contain at least one Comparator
     */
    @Override
    public int compare(final E o1, final E o2) throws UnsupportedOperationException {
        if (isLocked == false) {
            checkChainIntegrity();
            isLocked = true;
        }

        // iterate over all comparators in the chain
        final Iterator<Comparator<E>> comparators = comparatorChain.iterator();
        for (int comparatorIndex = 0; comparators.hasNext(); ++comparatorIndex) {

            final Comparator<? super E> comparator = comparators.next();
            int retval = comparator.compare(o1,o2);
            if (retval != 0) {
                // invert the order if it is a reverse sort
                if (orderingBits.get(comparatorIndex) == true) {
                    if (retval > 0) {
                        retval = -1;
                    } else {
                        retval = 1;
                    }
                }
                return retval;
            }
        }

        // if comparators are exhausted, return 0
        return 0;
    }

    //-----------------------------------------------------------------------
    
Implement a hash code for this comparator that is consistent with equals. 
Returns:
a suitable hash code
Since:
3.0/**
     * Implement a hash code for this comparator that is consistent with
     * {@link #equals(Object) equals}.
     *
     * @return a suitable hash code
     * @since 3.0
     */
    @Override
    public int hashCode() {
        int hash = 0;
        if (null != comparatorChain) {
            hash ^= comparatorChain.hashCode();
        }
        if (null != orderingBits) {
            hash ^= orderingBits.hashCode();
        }
        return hash;
    }

    
Returns true iff that Object is is a Comparator whose ordering is known to be equivalent to mine. 

This implementation returns true
iff object.getClass()
equals this.getClass(), and the underlying comparators and order bits are equal. Subclasses may want to override this behavior to remain consistent with the Comparator.equals(Object) contract. 
Params:
object –  the object to compare with
Returns:
true if equal
Since:
3.0/**
     * Returns <code>true</code> iff <i>that</i> Object is
     * is a {@link Comparator} whose ordering is known to be
     * equivalent to mine.
     * <p>
     * This implementation returns <code>true</code>
     * iff <code><i>object</i>.{@link Object#getClass() getClass()}</code>
     * equals <code>this.getClass()</code>, and the underlying
     * comparators and order bits are equal.
     * Subclasses may want to override this behavior to remain consistent
     * with the {@link Comparator#equals(Object)} contract.
     *
     * @param object  the object to compare with
     * @return true if equal
     * @since 3.0
     */
    @Override
    public boolean equals(final Object object) {
        if (this == object) {
            return true;
        }
        if (null == object) {
            return false;
        }
        if (object.getClass().equals(this.getClass())) {
            final ComparatorChain<?> chain = (ComparatorChain<?>) object;
            return (null == orderingBits ? null == chain.orderingBits : orderingBits.equals(chain.orderingBits)) &&
                   (null == comparatorChain ? null == chain.comparatorChain :
                                              comparatorChain.equals(chain.comparatorChain));
        }
        return false;
    }

}