1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 package net.sf.collections15.comparators;
17
18 import java.io.Serializable;
19 import java.util.Comparator;
20 import java.util.HashMap;
21 import java.util.List;
22 import java.util.Map;
23
24 /***
25 * A Comparator which imposes a specific order on a specific set of objects.
26 * Objects are presented to the <code>FixedOrderComparator</code> in a specified
27 * order and the return values of subsequent calls to {@link #compare(Object,
28 * Object) compare} reflect that order.For example:
29 * <pre>
30 * String[] planets = {"Mercury", "Venus", "Earth", "Mars"};
31 * FixedOrderComparator<String> distanceFromSun = new
32 * FixedOrderComparator<String>(planets);
33 * Arrays.sort(planets); // Sort to alphabetical order
34 * Arrays.sort(planets, distanceFromSun); // Back to original order
35 * </pre>
36 * Once <code>compare</code> has been called, the <code>FixedOrderComparator</code>
37 * is locked and attempts to modify it yield an <code>UnsupportedOperationException</code>.
38 * <p/>
39 * Instances of FixedOrderComparator are not synchronized. The class is not
40 * thread-safe at construction time, but it is thread-safe to perform multiple
41 * comparisons after all the setup operations are complete.
42 *
43 * @author David Leppik
44 * @author Stephen Colebourne
45 * @author Janek Bogucki
46 * @author Chris Lambrou (port to Java 5.0)
47 * @since Collections15 1.0
48 */
49 public class FixedOrderComparator <E> implements Comparator<E>, Serializable
50 {
51
52 static final long serialVersionUID = 7131368585451649973L;
53
54 /***
55 * Enumeration class that defines constants representing the way in which a
56 * {@link FixedOrderComparator} handles the comparison of objects which
57 * aren't part of its known ordering.
58 */
59 public static enum UnknownObjectBehaviour
60 {
61 /***
62 * Behavior when comparing unknown objects: unknown objects compare as
63 * before known objects.
64 */
65 UNKNOWN_BEFORE,
66
67 /***
68 * Behavior when comparing unknown objects: unknown objects compare as
69 * after known objects.
70 */
71 UNKNOWN_AFTER,
72
73 /***
74 * Behavior when comparing unknown objects: unknown objects cause an
75 * <code>IllegalArgumentException</code> to be thrown. This is the
76 * default behavior for a newly created <code>FixedOrderComparator</code>.
77 */
78 UNKNOWN_THROW_EXCEPTION
79 }
80
81 /***
82 * Internal map of object to their position in the fixed order.
83 */
84 private final Map<E, Integer> map;
85
86 /***
87 * Counter used in determining the position in the order for the next object
88 * added to the fixed order.
89 */
90 private int counter = 0;
91
92 /***
93 * Flag indicating whether or not the comparator locked against further
94 * changes.
95 */
96 private boolean isLocked = false;
97
98 /***
99 * The comparison behaviour in the case of an unknown object - defaults to
100 * {@link FixedOrderComparator.UnknownObjectBehaviour#UNKNOWN_THROW_EXCEPTION}.
101 */
102 private UnknownObjectBehaviour unknownObjectBehavior = UnknownObjectBehaviour.UNKNOWN_THROW_EXCEPTION;
103
104 /***
105 * Constructs an empty <code>FixedOrderComparator</code>.
106 *
107 * @param initialCapacity The initial capacity. If the number of objects
108 * added to the fixed order does not exceed this
109 * value, then the internal map used to store the
110 * fixed order will not be rehashed. If negative, the
111 * default initial capacity of the underlying map us
112 * used.
113 */
114 protected FixedOrderComparator(int initialCapacity)
115 {
116 map = initialCapacity < 0
117 ? new HashMap<E, Integer>()
118 : new HashMap<E, Integer>((2 + (initialCapacity * 4)) / 3);
119
120 }
121
122 /***
123 * Returns an empty <code>FixedOrderComparator</code>.
124 */
125 public static <T> FixedOrderComparator<T> getInstance()
126 {
127 return new FixedOrderComparator<T>(-1);
128 }
129
130 /***
131 * Returns a <code>FixedOrderComparator</code> which uses the order of the
132 * given array to compare the objects.
133 * <p/>
134 * The array is copied, so later changes will not affect the comparator.
135 *
136 * @param items The items that the comparator can compare in order. If any
137 * items are duplicated in the array, the position of their
138 * first occurrence in the array is used to determine their
139 * position in the fixed order.
140 *
141 * @throws IllegalArgumentException Thrown if the array is <code>null</code>.
142 */
143 public static <T> FixedOrderComparator<T> getInstance(T[] items)
144 {
145 if (items == null) {
146 throw new IllegalArgumentException("The array of items must not be null");
147 }
148 FixedOrderComparator<T> comparator = new FixedOrderComparator<T>(items.length);
149 for (T item : items) {
150 Integer previousIndex = comparator.map.put(item, comparator.counter++);
151 if (previousIndex != null) {
152
153 comparator.map.put(item, previousIndex);
154 }
155 }
156 return comparator;
157 }
158
159 /***
160 * Returns a <code>FixedOrderComparator</code> which uses the order of the
161 * given list to compare the objects.
162 * <p/>
163 * The list is copied, so later changes will not affect the comparator.
164 *
165 * @param items The items that the comparator can compare in order. If any
166 * items are duplicated in the list, the position of their
167 * first occurrence in the list is used to determine their
168 * position in the fixed order.
169 *
170 * @throws IllegalArgumentException Thrown if the list is <code>null</code>.
171 */
172 public static <T> FixedOrderComparator<T> getInstance(List<? extends T> items)
173 {
174 if (items == null) {
175 throw new IllegalArgumentException("The list of items must not be null");
176 }
177 FixedOrderComparator<T> comparator = new FixedOrderComparator<T>(items.size());
178 for (T item : items) {
179 Integer previousIndex = comparator.map.put(item, comparator.counter++);
180 if (previousIndex != null) {
181 comparator.map.put(item, previousIndex);
182 }
183 }
184 return comparator;
185 }
186
187 /***
188 * Returns <code>true</code> if modifications cannot be made to the
189 * <code>FixedOrderComparator</code>. <code>FixedOrderComparator</code>s
190 * cannot be modified once they have performed their first comparison.
191 *
192 * @return <code>true</code> if attempts to change the <code>FixedOrderComparator</code>
193 * would yield an <code>UnsupportedOperationException</code>;
194 * <code>false</code> if it can be changed.
195 */
196 public boolean isLocked()
197 {
198 return isLocked;
199 }
200
201 /***
202 * Checks to see whether the comparator is now locked against further
203 * changes, invoked internally prior to executing a method which will modify
204 * this <code>Comparator</code>
205 *
206 * @throws UnsupportedOperationException Thrown if the comparator is
207 * locked.
208 */
209 private void checkLocked()
210 {
211 if (isLocked()) {
212 throw new UnsupportedOperationException("Cannot modify a FixedOrderComparator after a comparison");
213 }
214 }
215
216 /***
217 * Gets the comparison behaviour of the <code>Comparator</code> in the case
218 * of an unknown object being compared.
219 *
220 * @return An enumaration constant describing the comparison behaviour when
221 * handling objects not in the fixed ordering. Will be one of {@link
222 * UnknownObjectBehaviour#UNKNOWN_AFTER UNKNOWN_AFTER}, {@link
223 * UnknownObjectBehaviour#UNKNOWN_BEFORE UNKNOWN_BEFORE} or {@link
224 * UnknownObjectBehaviour#UNKNOWN_THROW_EXCEPTION
225 * UNKNOWN_THROW_EXCEPTION}.
226 */
227 public UnknownObjectBehaviour getUnknownObjectBehavior()
228 {
229 return unknownObjectBehavior;
230 }
231
232 /***
233 * Sets the comparison behaviour of the <code>Comparator</code> in the case
234 * of an unknown object being compared.
235 *
236 * @param unknownObjectBehavior An enumaration constant describing the
237 * comparison behaviour when handling objects
238 * not in the fixed ordering. Must be one of
239 * {@link UnknownObjectBehaviour#UNKNOWN_AFTER
240 * UNKNOWN_AFTER}, {@link UnknownObjectBehaviour#UNKNOWN_BEFORE
241 * UNKNOWN_BEFORE} or {@link UnknownObjectBehaviour#UNKNOWN_THROW_EXCEPTION
242 * UNKNOWN_THROW_EXCEPTION}.
243 *
244 * @throws UnsupportedOperationException Throw if this comparator is locked,
245 * after a comparison has been
246 * performed
247 */
248 public void setUnknownObjectBehavior(UnknownObjectBehaviour unknownObjectBehavior)
249 {
250 checkLocked();
251 if (unknownObjectBehavior == null) {
252 throw new IllegalArgumentException("Unrecognised value for unknown behaviour flag");
253 }
254 this.unknownObjectBehavior = unknownObjectBehavior;
255 }
256
257 /***
258 * Adds an item, which compares as after all items known to the
259 * <code>Comparator</code>. i.e. adds it to the end of the fixed order that
260 * has been defined so far. If the item is already known to the
261 * <code>Comparator</code>, its old position is replaced with the new
262 * position.
263 *
264 * @param obj The item to be added to the fixed order.
265 *
266 * @return <code>true</code> if <code>obj</code> has been added for the
267 * first time; <code>false</code> if it was already part of the
268 * fixed order.
269 *
270 * @throws UnsupportedOperationException Throw if this comparator is locked,
271 * after a comparison has been
272 * performed
273 */
274 public boolean add(E obj)
275 {
276 checkLocked();
277 Integer position = map.put(obj, counter++);
278 return (position == null);
279 }
280
281 /***
282 * Adds a new item to the fixed order, which compares as equal to the given
283 * existing item.
284 *
285 * @param existingObj An item already in the <code>Comparator</code>'s fixed
286 * order.
287 * @param newObj An item to be added to the <code>Comparator</code>'s
288 * fixed order in the equivalent position to the existing
289 * item.
290 *
291 * @return <code>true</code> if <code>obj</code> has been added for the
292 * first time; <code>false</code> if it was already part of the
293 * fixed order.
294 *
295 * @throws IllegalArgumentException Thrown if <code>existingObj</code>
296 * is not already in the <code>Comparator</code>'s
297 * fixed ordering.
298 * @throws UnsupportedOperationException Throw if this comparator is locked,
299 * after a comparison has been
300 * performed
301 */
302 public boolean addAsEqual(E existingObj, E newObj)
303 {
304 checkLocked();
305 Integer position = map.get(existingObj);
306 if (position == null) {
307 throw new IllegalArgumentException(existingObj + " not known to " + this);
308 }
309 Integer result = map.put(newObj, position);
310 return (result == null);
311 }
312
313 /***
314 * Compares two objects according to the order of this Comparator.
315 * <p/>
316 * It is important to note that this class will throw an
317 * IllegalArgumentException in the case of an unrecognised object. This is
318 * not specified in the Comparator interface, but is the most appropriate
319 * exception.
320 *
321 * @param obj1 the first object to compare
322 * @param obj2 the second object to compare
323 *
324 * @return negative if obj1 is less, positive if greater, zero if equal
325 *
326 * @throws IllegalArgumentException if obj1 or obj2 are not known to this
327 * Comparator and an alternative behavior
328 * has not been set via {@link
329 * #setUnknownObjectBehavior} )}.
330 */
331 public int compare(E obj1, E obj2)
332 {
333 isLocked = true;
334 Integer position1 = map.get(obj1);
335 Integer position2 = map.get(obj2);
336 if (position1 == null || position2 == null) {
337 switch (unknownObjectBehavior) {
338 case UNKNOWN_BEFORE:
339 if (position1 == null) {
340 return (position2 == null) ? 0 : -1;
341 }
342 else {
343 return 1;
344 }
345 case UNKNOWN_AFTER:
346 if (position1 == null) {
347 return (position2 == null) ? 0 : 1;
348 }
349 else {
350 return -1;
351 }
352 case UNKNOWN_THROW_EXCEPTION:
353 E unknownObj = (position1 == null) ? obj1 : obj2;
354 throw new IllegalArgumentException("Attempting to compare unknown object " + unknownObj);
355 default :
356 throw new UnsupportedOperationException("Unknown unknownObjectBehavior: " + unknownObjectBehavior);
357 }
358 }
359 else {
360 return position1.compareTo(position2);
361 }
362 }
363
364 }