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}