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