    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.Comparator;
    021import java.util.HashMap;
    022import java.util.List;
    023import java.util.Map;
    024
    025/**
    026 * A Comparator which imposes a specific order on a specific set of Objects.
    027 * Objects are presented to the FixedOrderComparator in a specified order and
    028 * subsequent calls to {@link #compare(Object, Object) compare} yield that order.
    029 * For example:
    030 * <pre>
    031 * String[] planets = {"Mercury", "Venus", "Earth", "Mars"};
    032 * FixedOrderComparator distanceFromSun = new FixedOrderComparator(planets);
    033 * Arrays.sort(planets);                     // Sort to alphabetical order
    034 * Arrays.sort(planets, distanceFromSun);    // Back to original order
    035 * </pre>
    036 * <p>
    037 * Once <code>compare</code> has been called, the FixedOrderComparator is locked
    038 * and attempts to modify it yield an UnsupportedOperationException.
    039 * <p>
    040 * Instances of FixedOrderComparator are not synchronized.  The class is not
    041 * thread-safe at construction time, but it is thread-safe to perform
    042 * multiple comparisons  after all the setup operations are complete.
    043 * <p>
    044 * This class is Serializable from Commons Collections 4.0.
    045 *
    046 * @param <T> the type of objects compared by this comparator
    047 * @since 3.0
    048 */
    049public class FixedOrderComparator<T> implements Comparator<T>, Serializable {
    050
    051    /** Serialization version from Collections 4.0. */
    052    private static final long serialVersionUID = 82794675842863201L;
    053
    054    /**
    055     * Unknown object behavior enum.
    056     * @since 4.0
    057     */
    058    public enum UnknownObjectBehavior {
    059        BEFORE, AFTER, EXCEPTION;
    060    }
    061
    062    /** Internal map of object to position */
    063    private final Map<T, Integer> map = new HashMap<>();
    064
    065    /** Counter used in determining the position in the map */
    066    private int counter = 0;
    067
    068    /** Is the comparator locked against further change */
    069    private boolean isLocked = false;
    070
    071    /** The behaviour in the case of an unknown object */
    072    private UnknownObjectBehavior unknownObjectBehavior = UnknownObjectBehavior.EXCEPTION;
    073
    074    // Constructors
    075    //-----------------------------------------------------------------------
    076    /**
    077     * Constructs an empty FixedOrderComparator.
    078     */
    079    public FixedOrderComparator() {
    080        super();
    081    }
    082
    083    /**
    084     * Constructs a FixedOrderComparator which uses the order of the given array
    085     * to compare the objects.
    086     * <p>
    087     * The array is copied, so later changes will not affect the comparator.
    088     *
    089     * @param items  the items that the comparator can compare in order
    090     * @throws NullPointerException if the array is null
    091     */
    092    public FixedOrderComparator(final T... items) {
    093        super();
    094        if (items == null) {
    095            throw new NullPointerException("The list of items must not be null");
    096        }
    097        for (final T item : items) {
    098            add(item);
    099        }
    100    }
    101
    102    /**
    103     * Constructs a FixedOrderComparator which uses the order of the given list
    104     * to compare the objects.
    105     * <p>
    106     * The list is copied, so later changes will not affect the comparator.
    107     *
    108     * @param items  the items that the comparator can compare in order
    109     * @throws NullPointerException if the list is null
    110     */
    111    public FixedOrderComparator(final List<T> items) {
    112        super();
    113        if (items == null) {
    114            throw new NullPointerException("The list of items must not be null");
    115        }
    116        for (final T t : items) {
    117            add(t);
    118        }
    119    }
    120
    121    // Bean methods / state querying methods
    122    //-----------------------------------------------------------------------
    123    /**
    124     * Returns true if modifications cannot be made to the FixedOrderComparator.
    125     * FixedOrderComparators cannot be modified once they have performed a comparison.
    126     *
    127     * @return true if attempts to change the FixedOrderComparator yield an
    128     *  UnsupportedOperationException, false if it can be changed.
    129     */
    130    public boolean isLocked() {
    131        return isLocked;
    132    }
    133
    134    /**
    135     * Checks to see whether the comparator is now locked against further changes.
    136     *
    137     * @throws UnsupportedOperationException if the comparator is locked
    138     */
    139    protected void checkLocked() {
    140        if (isLocked()) {
    141            throw new UnsupportedOperationException("Cannot modify a FixedOrderComparator after a comparison");
    142        }
    143    }
    144
    145    /**
    146     * Gets the behavior for comparing unknown objects.
    147     *
    148     * @return {@link UnknownObjectBehavior}
    149     */
    150    public UnknownObjectBehavior getUnknownObjectBehavior() {
    151        return unknownObjectBehavior;
    152    }
    153
    154    /**
    155     * Sets the behavior for comparing unknown objects.
    156     *
    157     * @param unknownObjectBehavior  the flag for unknown behaviour -
    158     * UNKNOWN_AFTER, UNKNOWN_BEFORE or UNKNOWN_THROW_EXCEPTION
    159     * @throws UnsupportedOperationException if a comparison has been performed
    160     * @throws NullPointerException if unknownObjectBehavior is null
    161     */
    162    public void setUnknownObjectBehavior(final UnknownObjectBehavior unknownObjectBehavior) {
    163        checkLocked();
    164        if (unknownObjectBehavior == null) {
    165            throw new NullPointerException("Unknown object behavior must not be null");
    166        }
    167        this.unknownObjectBehavior = unknownObjectBehavior;
    168    }
    169
    170    // Methods for adding items
    171    //-----------------------------------------------------------------------
    172    /**
    173     * Adds an item, which compares as after all items known to the Comparator.
    174     * If the item is already known to the Comparator, its old position is
    175     * replaced with the new position.
    176     *
    177     * @param obj  the item to be added to the Comparator.
    178     * @return true if obj has been added for the first time, false if
    179     *  it was already known to the Comparator.
    180     * @throws UnsupportedOperationException if a comparison has already been made
    181     */
    182    public boolean add(final T obj) {
    183        checkLocked();
    184        final Integer position = map.put(obj, Integer.valueOf(counter++));
    185        return position == null;
    186    }
    187
    188    /**
    189     * Adds a new item, which compares as equal to the given existing item.
    190     *
    191     * @param existingObj  an item already in the Comparator's set of
    192     *  known objects
    193     * @param newObj  an item to be added to the Comparator's set of
    194     *  known objects
    195     * @return true if newObj has been added for the first time, false if
    196     *  it was already known to the Comparator.
    197     * @throws IllegalArgumentException if existingObject is not in the
    198     *  Comparator's set of known objects.
    199     * @throws UnsupportedOperationException if a comparison has already been made
    200     */
    201    public boolean addAsEqual(final T existingObj, final T newObj) {
    202        checkLocked();
    203        final Integer position = map.get(existingObj);
    204        if (position == null) {
    205            throw new IllegalArgumentException(existingObj + " not known to " + this);
    206        }
    207        final Integer result = map.put(newObj, position);
    208        return result == null;
    209    }
    210
    211    // Comparator methods
    212    //-----------------------------------------------------------------------
    213    /**
    214     * Compares two objects according to the order of this Comparator.
    215     * <p>
    216     * It is important to note that this class will throw an IllegalArgumentException
    217     * in the case of an unrecognized object. This is not specified in the
    218     * Comparator interface, but is the most appropriate exception.
    219     *
    220     * @param obj1  the first object to compare
    221     * @param obj2  the second object to compare
    222     * @return negative if obj1 is less, positive if greater, zero if equal
    223     * @throws IllegalArgumentException if obj1 or obj2 are not known
    224     *  to this Comparator and an alternative behavior has not been set
    225     *  via {@link #setUnknownObjectBehavior(UnknownObjectBehavior)}.
    226     */
    227    @Override
    228    public int compare(final T obj1, final T obj2) {
    229        isLocked = true;
    230        final Integer position1 = map.get(obj1);
    231        final Integer position2 = map.get(obj2);
    232        if (position1 == null || position2 == null) {
    233            switch (unknownObjectBehavior) {
    234            case BEFORE:
    235                return position1 == null ? position2 == null ? 0 : -1 : 1;
    236            case AFTER:
    237                return position1 == null ? position2 == null ? 0 : 1 : -1;
    238            case EXCEPTION:
    239                final Object unknownObj = position1 == null ? obj1 : obj2;
    240                throw new IllegalArgumentException("Attempting to compare unknown object "
    241                        + unknownObj);
    242            default: //could be null
    243                throw new UnsupportedOperationException("Unknown unknownObjectBehavior: "
    244                        + unknownObjectBehavior);
    245            }
    246        }
    247        return position1.compareTo(position2);
    248    }
    249
    250    //-----------------------------------------------------------------------
    251    /**
    252     * Implement a hash code for this comparator that is consistent with
    253     * {@link #equals(Object) equals}.
    254     *
    255     * @return a hash code for this comparator.
    256     */
    257    @Override
    258    public int hashCode() {
    259        int total = 17;
    260        total = total*37 + (map == null ? 0 : map.hashCode());
    261        total = total*37 + (unknownObjectBehavior == null ? 0 : unknownObjectBehavior.hashCode());
    262        total = total*37 + counter;
    263        total = total*37 + (isLocked ? 0 : 1);
    264        return total;
    265    }
    266
    267    /**
    268     * Returns <code>true</code> iff <i>that</i> Object is
    269     * is a {@link Comparator} whose ordering is known to be
    270     * equivalent to mine.
    271     * <p>
    272     * This implementation returns <code>true</code>
    273     * iff <code><i>that</i></code> is a {@link FixedOrderComparator}
    274     * whose attributes are equal to mine.
    275     *
    276     * @param object  the object to compare to
    277     * @return true if equal
    278     */
    279    @Override
    280    public boolean equals(final Object object) {
    281        if (this == object) {
    282            return true;
    283        }
    284        if (null == object) {
    285            return false;
    286        }
    287        if (object.getClass().equals(this.getClass())) {
    288            final FixedOrderComparator<?> comp = (FixedOrderComparator<?>) object;
    289            return (null == map ? null == comp.map : map.equals(comp.map)) &&
    290                   (null == unknownObjectBehavior ? null == comp.unknownObjectBehavior :
    291                        unknownObjectBehavior == comp.unknownObjectBehavior &&
    292                        counter == comp.counter &&
    293                        isLocked == comp.isLocked &&
    294                        unknownObjectBehavior == comp.unknownObjectBehavior);
    295        }
    296        return false;
    297    }
    298
    299}