1 /*
2 * Copyright (C) 2016 Hobrasoft s.r.o.
3 *
4 * This program is free software: you can redistribute it and/or modify
5 * it under the terms of the GNU Affero General Public License as published by
6 * the Free Software Foundation, either version 3 of the License, or
7 * (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU Affero General Public License for more details.
13 *
14 * You should have received a copy of the GNU Affero General Public License
15 * along with this program. If not, see <http://www.gnu.org/licenses/>.
16 */
17 package cz.hobrasoft.pdfmu;
18
19 import java.util.Arrays;
20 import java.util.Comparator;
21 import java.util.Iterator;
22 import java.util.List;
23 import java.util.Map;
24 import java.util.SortedMap;
25 import java.util.TreeMap;
26 import org.apache.commons.collections.IteratorUtils;
27
28 /**
29 * Orders the items by a preference list.
30 *
31 * <p>
32 * The items at the start of the preference list are placed before (that is
33 * deemed smaller than) the other items. The items that appear in the preference
34 * list are placed before the items that do not appear in the preference list.
35 * The order of items that do not appear in the preference list is not specified
36 * (and is application specific in practice). Thus the induced order is not
37 * guaranteed to be linear.
38 *
39 * <p>
40 * Usage example:
41 * <pre>
42 * {@code
43 * import java.util.Comparator;
44 * import java.util.List;
45 * import java.util.Map;
46 * import java.util.SortedMap;
47 * import java.util.TreeMap;
48 * }
49 * </pre>
50 * <pre>
51 * {@code
52 * Map<K, V> unsorted;
53 * List<K> preferenceList;
54 * Comparator<K> comparator = new PreferenceListComparator<>(preferenceList);
55 * SortedMap<K, V> sorted = new TreeMap<>(comparator);
56 * sorted.putAll(unsorted);
57 * }
58 * </pre>
59 *
60 * @param <T> the type of objects that may be compared by this comparator
61 *
62 * @author <a href="mailto:filip.bartek@hobrasoft.cz">Filip Bartek</a>
63 */
64 public class PreferenceListComparator<T> implements Comparator<T>, MapSorter<T> {
65
66 private final List<T> preferred;
67
68 /**
69 * Creates a new comparator.
70 *
71 * @param preferred the preference list
72 */
73 public PreferenceListComparator(List<T> preferred) {
74 this.preferred = preferred;
75 }
76
77 /**
78 * Creates a new comparator.
79 *
80 * @param preferred the preference list specified by an array
81 */
82 public PreferenceListComparator(T[] preferred) {
83 this(Arrays.asList(preferred));
84 }
85
86 /**
87 * Creates a new comparator.
88 *
89 * @param preferredIterator an iterator that iterates over the items in the
90 * order of preference
91 */
92 public PreferenceListComparator(Iterator<T> preferredIterator) {
93 this(IteratorUtils.toList(preferredIterator));
94 }
95
96 /**
97 * Compares its two arguments for order. Returns a negative integer, zero,
98 * or a positive integer as the first argument is less than, equal to, or
99 * greater than the second.
100 *
101 * <p>
102 * Note that this implementation violates some of the requirements imposed
103 * by the {@link Comparator} interface, so care should be taken when using
104 * it. In practice, it at least allows a {@link TreeMap} initialized by a
105 * {@link Comparator} to be used for one-time ordering of elements of a
106 * {@link Map} (using the method {@link TreeMap#putAll(Map)}). Other uses of
107 * the comparator have not been tested.
108 *
109 * @param o1 the first object to be compared.
110 * @param o2 the second object to be compared.
111 * @return a negative integer, zero, or a positive integer as the first
112 * argument is less than, equal to, or greater than the second.
113 */
114 @Override
115 public int compare(T o1, T o2) {
116 if (o1.equals(o2)) {
117 return 0;
118 }
119
120 int i1 = preferred.indexOf(o1);
121 int i2 = preferred.indexOf(o2);
122
123 if (i1 == -1 && i2 != -1) {
124 // `o1` is not in `preferred` but `o2` is.
125 // "Prefer" `o2`, that is claim it smaller than `o1`.
126 return 1;
127 }
128 if (i2 == -1 && i1 != -1) {
129 return -1;
130 }
131 if (i1 == -1 && i2 == -1) {
132 // HACK:
133 // None of `o1` and `o2` is in `preferred`.
134 // Prefer `o1` (the former), preserving the order.
135 // With this hack, it may happen that `a < b` and `b < a`,
136 // so the comparator does not provide a <em>linear</em> order.
137 return -1;
138 }
139
140 // `i1 == i2` can only occur if `o1.equals(o1)`
141 // or when none of `o1` and `o2` is in `preferred`.
142 assert i1 != i2;
143
144 // If `o1` comes before `o1` in `preferred`, the result will be negative.
145 return i1 - i2;
146 }
147
148 /**
149 * Sorts a map by its keys using a comparator.
150 *
151 * @param <K> the type of keys
152 * @param <V> the type of values
153 * @param unsorted the original (unsorted) map
154 * @param comparator a comparator on K
155 * @return a sorted map
156 */
157 public static <K, V> SortedMap<K, V> sort(Map<K, V> unsorted, Comparator<K> comparator) {
158 SortedMap<K, V> sorted = new TreeMap<>(comparator);
159 sorted.putAll(unsorted);
160 return sorted;
161 }
162
163 @Override
164 public <V> SortedMap<T, V> sort(Map<T, V> unsorted) {
165 return sort(unsorted, this);
166 }
167 }