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