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