001/* 
002 * Copyright (C) 2016 Hobrasoft s.r.o.
003 *
004 * This program is free software: you can redistribute it and/or modify
005 * it under the terms of the GNU Affero General Public License as published by
006 * the Free Software Foundation, either version 3 of the License, or
007 * (at your option) any later version.
008 *
009 * This program is distributed in the hope that it will be useful,
010 * but WITHOUT ANY WARRANTY; without even the implied warranty of
011 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
012 * GNU Affero General Public License for more details.
013 *
014 * You should have received a copy of the GNU Affero General Public License
015 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
016 */
017package cz.hobrasoft.pdfmu;
018
019import java.util.Arrays;
020import java.util.Comparator;
021import java.util.Iterator;
022import java.util.List;
023import java.util.Map;
024import java.util.SortedMap;
025import java.util.TreeMap;
026import org.apache.commons.collections.IteratorUtils;
027
028/**
029 * Orders the items by a preference list.
030 *
031 * <p>
032 * The items at the start of the preference list are placed before (that is
033 * deemed smaller than) the other items. The items that appear in the preference
034 * list are placed before the items that do not appear in the preference list.
035 * The order of items that do not appear in the preference list is not specified
036 * (and is application specific in practice). Thus the induced order is not
037 * guaranteed to be linear.
038 *
039 * <p>
040 * Usage example:
041 * <pre>
042 * {@code
043 * import java.util.Comparator;
044 * import java.util.List;
045 * import java.util.Map;
046 * import java.util.SortedMap;
047 * import java.util.TreeMap;
048 * }
049 * </pre>
050 * <pre>
051 * {@code
052 * Map<K, V> unsorted;
053 * List<K> preferenceList;
054 * Comparator<K> comparator = new PreferenceListComparator<>(preferenceList);
055 * SortedMap<K, V> sorted = new TreeMap<>(comparator);
056 * sorted.putAll(unsorted);
057 * }
058 * </pre>
059 *
060 * @param <T> the type of objects that may be compared by this comparator
061 *
062 * @author <a href="mailto:filip.bartek@hobrasoft.cz">Filip Bartek</a>
063 */
064public class PreferenceListComparator<T> implements Comparator<T>, MapSorter<T> {
065
066    private final List<T> preferred;
067
068    /**
069     * Creates a new comparator.
070     *
071     * @param preferred the preference list
072     */
073    public PreferenceListComparator(List<T> preferred) {
074        this.preferred = preferred;
075    }
076
077    /**
078     * Creates a new comparator.
079     *
080     * @param preferred the preference list specified by an array
081     */
082    public PreferenceListComparator(T[] preferred) {
083        this(Arrays.asList(preferred));
084    }
085
086    /**
087     * Creates a new comparator.
088     *
089     * @param preferredIterator an iterator that iterates over the items in the
090     * order of preference
091     */
092    public PreferenceListComparator(Iterator<T> preferredIterator) {
093        this(IteratorUtils.toList(preferredIterator));
094    }
095
096    /**
097     * Compares its two arguments for order. Returns a negative integer, zero,
098     * or a positive integer as the first argument is less than, equal to, or
099     * 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}