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(final 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        final 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}