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