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     */
017    package org.apache.commons.collections.comparators;
018    
019    import java.util.Comparator;
020    import java.util.HashMap;
021    import java.util.Iterator;
022    import java.util.List;
023    import 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     * Instances of FixedOrderComparator are not synchronized.  The class is not
041     * thread-safe at construction time, but it is thread-safe to perform
042     * multiple comparisons  after all the setup operations are complete.
043     * 
044     * @since Commons Collections 3.0
045     * @version $Revision: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $
046     *
047     * @author David Leppik
048     * @author Stephen Colebourne
049     * @author Janek Bogucki
050     */
051    public class FixedOrderComparator implements Comparator {
052    
053        /** 
054         * Behavior when comparing unknown Objects:
055         * unknown objects compare as before known Objects.
056         */
057        public static final int UNKNOWN_BEFORE = 0;
058    
059        /** 
060         * Behavior when comparing unknown Objects:
061         * unknown objects compare as after known Objects.
062         */
063        public static final int UNKNOWN_AFTER = 1;
064    
065        /** 
066         * Behavior when comparing unknown Objects:
067         * unknown objects cause a IllegalArgumentException to be thrown.
068         * This is the default behavior.
069         */
070        public static final int UNKNOWN_THROW_EXCEPTION = 2;
071    
072        /** Internal map of object to position */
073        private final Map map = new HashMap();
074        /** Counter used in determining the position in the map */
075        private int counter = 0;
076        /** Is the comparator locked against further change */
077        private boolean isLocked = false;
078        /** The behaviour in the case of an unknown object */
079        private int unknownObjectBehavior = UNKNOWN_THROW_EXCEPTION;
080    
081        // Constructors
082        //-----------------------------------------------------------------------
083        /** 
084         * Constructs an empty FixedOrderComparator.
085         */
086        public FixedOrderComparator() {
087            super();
088        }
089    
090        /** 
091         * Constructs a FixedOrderComparator which uses the order of the given array
092         * to compare the objects.
093         * <p>
094         * The array is copied, so later changes will not affect the comparator.
095         * 
096         * @param items  the items that the comparator can compare in order
097         * @throws IllegalArgumentException if the array is null
098         */
099        public FixedOrderComparator(Object[] items) {
100            super();
101            if (items == null) {
102                throw new IllegalArgumentException("The list of items must not be null");
103            }
104            for (int i = 0; i < items.length; i++) {
105                add(items[i]);
106            }
107        }
108    
109        /** 
110         * Constructs a FixedOrderComparator which uses the order of the given list
111         * to compare the objects.
112         * <p>
113         * The list is copied, so later changes will not affect the comparator.
114         * 
115         * @param items  the items that the comparator can compare in order
116         * @throws IllegalArgumentException if the list is null
117         */
118        public FixedOrderComparator(List items) {
119            super();
120            if (items == null) {
121                throw new IllegalArgumentException("The list of items must not be null");
122            }
123            for (Iterator it = items.iterator(); it.hasNext();) {
124                add(it.next());
125            }
126        }
127    
128        // Bean methods / state querying methods
129        //-----------------------------------------------------------------------
130        /**
131         * Returns true if modifications cannot be made to the FixedOrderComparator.
132         * FixedOrderComparators cannot be modified once they have performed a comparison.
133         * 
134         * @return true if attempts to change the FixedOrderComparator yield an
135         *  UnsupportedOperationException, false if it can be changed.
136         */
137        public boolean isLocked() {
138            return isLocked;
139        }
140    
141        /**
142         * Checks to see whether the comparator is now locked against further changes.
143         * 
144         * @throws UnsupportedOperationException if the comparator is locked
145         */
146        protected void checkLocked() {
147            if (isLocked()) {
148                throw new UnsupportedOperationException("Cannot modify a FixedOrderComparator after a comparison");
149            }
150        }
151    
152        /** 
153         * Gets the behavior for comparing unknown objects.
154         * 
155         * @return the flag for unknown behaviour - UNKNOWN_AFTER,
156         * UNKNOWN_BEFORE or UNKNOWN_THROW_EXCEPTION
157         */
158        public int getUnknownObjectBehavior() {
159            return unknownObjectBehavior;
160        }
161    
162        /** 
163         * Sets the behavior for comparing unknown objects.
164         * 
165         * @param unknownObjectBehavior  the flag for unknown behaviour -
166         * UNKNOWN_AFTER, UNKNOWN_BEFORE or UNKNOWN_THROW_EXCEPTION
167         * @throws UnsupportedOperationException if a comparison has been performed
168         * @throws IllegalArgumentException if the unknown flag is not valid
169         */
170        public void setUnknownObjectBehavior(int unknownObjectBehavior) {
171            checkLocked();
172            if (unknownObjectBehavior != UNKNOWN_AFTER 
173                && unknownObjectBehavior != UNKNOWN_BEFORE 
174                && unknownObjectBehavior != UNKNOWN_THROW_EXCEPTION) {
175                throw new IllegalArgumentException("Unrecognised value for unknown behaviour flag");    
176            }
177            this.unknownObjectBehavior = unknownObjectBehavior;
178        }
179    
180        // Methods for adding items
181        //-----------------------------------------------------------------------
182        /** 
183         * Adds an item, which compares as after all items known to the Comparator.
184         * If the item is already known to the Comparator, its old position is
185         * replaced with the new position.
186         * 
187         * @param obj  the item to be added to the Comparator.
188         * @return true if obj has been added for the first time, false if
189         *  it was already known to the Comparator.
190         * @throws UnsupportedOperationException if a comparison has already been made
191         */
192        public boolean add(Object obj) {
193            checkLocked();
194            Object position = map.put(obj, new Integer(counter++));
195            return (position == null);
196        }
197    
198        /**
199         * Adds a new item, which compares as equal to the given existing item.
200         * 
201         * @param existingObj  an item already in the Comparator's set of 
202         *  known objects
203         * @param newObj  an item to be added to the Comparator's set of
204         *  known objects
205         * @return true if newObj has been added for the first time, false if
206         *  it was already known to the Comparator.
207         * @throws IllegalArgumentException if existingObject is not in the 
208         *  Comparator's set of known objects.
209         * @throws UnsupportedOperationException if a comparison has already been made
210         */
211        public boolean addAsEqual(Object existingObj, Object newObj) {
212            checkLocked();
213            Integer position = (Integer) map.get(existingObj);
214            if (position == null) {
215                throw new IllegalArgumentException(existingObj + " not known to " + this);
216            }
217            Object result = map.put(newObj, position);
218            return (result == null);
219        }
220    
221        // Comparator methods
222        //-----------------------------------------------------------------------
223        /** 
224         * Compares two objects according to the order of this Comparator.
225         * <p>
226         * It is important to note that this class will throw an IllegalArgumentException
227         * in the case of an unrecognised object. This is not specified in the 
228         * Comparator interface, but is the most appropriate exception.
229         * 
230         * @param obj1  the first object to compare
231         * @param obj2  the second object to compare
232         * @return negative if obj1 is less, positive if greater, zero if equal
233         * @throws IllegalArgumentException if obj1 or obj2 are not known 
234         *  to this Comparator and an alternative behavior has not been set
235         *  via {@link #setUnknownObjectBehavior(int)}.
236         */
237        public int compare(Object obj1, Object obj2) {
238            isLocked = true;
239            Integer position1 = (Integer) map.get(obj1);
240            Integer position2 = (Integer) map.get(obj2);
241            if (position1 == null || position2 == null) {
242                switch (unknownObjectBehavior) {
243                    case UNKNOWN_BEFORE :
244                        if (position1 == null) {
245                            return (position2 == null) ? 0 : -1;
246                        } else {
247                            return 1;
248                        }
249                    case UNKNOWN_AFTER :
250                        if (position1 == null) {
251                            return (position2 == null) ? 0 : 1;
252                        } else {
253                            return -1;
254                        }
255                    case UNKNOWN_THROW_EXCEPTION :
256                        Object unknownObj = (position1 == null) ? obj1 : obj2;
257                        throw new IllegalArgumentException("Attempting to compare unknown object " + unknownObj);
258                    default :
259                        throw new UnsupportedOperationException("Unknown unknownObjectBehavior: " + unknownObjectBehavior);
260                }
261            } else {
262                return position1.compareTo(position2);
263            }
264        }
265    
266    }