1 package org.unicode.cldr.util; 2 3 import java.util.ArrayList; 4 import java.util.Collection; 5 import java.util.Comparator; 6 import java.util.HashMap; 7 import java.util.HashSet; 8 import java.util.LinkedHashMap; 9 import java.util.LinkedHashSet; 10 import java.util.LinkedList; 11 import java.util.List; 12 import java.util.Map; 13 import java.util.Set; 14 import java.util.TreeMap; 15 import java.util.TreeSet; 16 17 import com.ibm.icu.impl.Utility; 18 19 /** 20 * A comparator that can be built from a series of 'less than' relations. 21 * 22 * <pre> 23 * DiscreteComparator<String> comp = new Builder<String>(order).add("c", "d", "b", "a").add("m", "n", "d").get(); 24 * if (comp.compare("a", "m")) ... 25 * </pre> 26 * 27 * @author markdavis 28 * @param <T> 29 * any class 30 */ 31 public class DiscreteComparator<T> implements Comparator<T> { 32 /** 33 * The builder can take three different orders: input order, natural order 34 * (assumes T is Comparable<T>), and arbitrary. 35 */ 36 public enum Ordering { 37 CHRONOLOGICAL, NATURAL, ARBITRARY 38 } 39 40 private static final boolean DEBUG = false; 41 private static int debugIndent; 42 43 private Map<T, Integer> ordering; 44 private Comparator<T> backupOrdering; 45 DiscreteComparator(Map<T, Integer> ordering, Comparator<T> backupOrdering)46 private DiscreteComparator(Map<T, Integer> ordering, Comparator<T> backupOrdering) { 47 this.backupOrdering = backupOrdering; 48 this.ordering = ordering; 49 } 50 51 /** 52 * Compare the items. If there was a backup comparator, it will be used for 53 * items not specified explicitly. However, all explicit items will always 54 * come before all others, to preserve transitivity. 55 * 56 * @param o1 57 * first item 58 * @param o2 59 * second item 60 * @return integer representing the order 61 * @exception MissingItemException 62 * thrown if there is no backup comparator, and at least one of 63 * the items is not explicit in the collator. 64 */ compare(T o1, T o2)65 public int compare(T o1, T o2) { 66 // TODO add option for back ordering 67 Integer a = ordering.get(o1); 68 Integer b = ordering.get(o2); 69 if (a != null && b != null) { 70 } 71 if (a == null) { 72 if (backupOrdering != null) { 73 if (b == null) { 74 return backupOrdering.compare(o1, o2); 75 } else { 76 return 1; // b is in, so less 77 } 78 } 79 throw new MissingItemException("Item not in ordering:\t" + o1); 80 } else if (b == null) { 81 if (backupOrdering != null) { 82 return -1; // a is in, so less 83 } 84 throw new MissingItemException("Item not in ordering:\t" + o2); 85 } 86 return a.compareTo(b); 87 } 88 89 /** 90 * Get a list of the explicit items. 91 * 92 * @return a list 93 */ getOrdering()94 public List<T> getOrdering() { 95 return new ArrayList<T>(ordering.keySet()); 96 } 97 98 @Override toString()99 public String toString() { 100 return ordering.keySet().toString(); 101 } 102 103 /** 104 * Builder for DiscreteComparator 105 * 106 * @param <T> 107 * any class 108 */ 109 public static class Builder<T> { 110 111 // builds a topological sort from an input set of relations 112 // with O(n) algorithm 113 private Map<T, Node<T>> all; 114 private Comparator<T> backupOrdering; 115 private Ordering order; 116 117 /** 118 * Pass the order you want for the results. 119 * 120 * @param order 121 */ Builder(Ordering order)122 public Builder(Ordering order) { 123 this.order = order; 124 all = order == Ordering.CHRONOLOGICAL ? new LinkedHashMap<T, Node<T>>() 125 : order == Ordering.NATURAL ? new TreeMap<T, Node<T>>() 126 : new HashMap<T, Node<T>>(); 127 } 128 129 /** 130 * If there is a backup comparator, specify it here. 131 * 132 * @param backupOrdering 133 * @return this, for chaining 134 */ setFallbackComparator(Comparator<T> backupOrdering)135 public Builder<T> setFallbackComparator(Comparator<T> backupOrdering) { 136 this.backupOrdering = backupOrdering; 137 return this; 138 } 139 140 /** 141 * Add explicitly ordered items, from least to greatest 142 * 143 * @param items 144 * @return this, for chaining 145 */ add(Collection<T> items)146 public Builder<T> add(Collection<T> items) { 147 if (items.size() < 2) { 148 if (items.size() == 1) { 149 T item = items.iterator().next(); 150 if (!all.containsKey(item)) { 151 addNew(item); 152 } 153 } 154 return this; 155 } 156 T last = null; 157 boolean first = true; 158 for (T item : items) { 159 if (first) { 160 first = false; 161 } else { 162 add(last, item); 163 } 164 last = item; 165 } 166 return this; 167 } 168 169 /** 170 * Add explicitly ordered items, from least to greatest 171 * 172 * @param items 173 * @return this, for chaining 174 */ 175 @SuppressWarnings("unchecked") add(T... items)176 public Builder<T> add(T... items) { 177 if (items.length < 2) { 178 if (items.length == 1) { 179 T item = items[0]; 180 if (!all.containsKey(item)) { 181 addNew(item); 182 } 183 } 184 } 185 T last = null; 186 boolean first = true; 187 for (T item : items) { 188 if (first) { 189 first = false; 190 } else { 191 add(last, item); 192 } 193 last = item; 194 } 195 return this; 196 } 197 198 /** 199 * Add explicitly ordered items 200 * 201 * @param a 202 * lesser 203 * @param b 204 * greater 205 * @return this, for chaining 206 */ add(T a, T b)207 public Builder<T> add(T a, T b) { 208 // if (a.equals(b)) { 209 // throw new CycleException("Can't add equal items", a, a); 210 // } 211 Node<T> aNode = all.get(a); 212 if (aNode == null) { 213 aNode = addNew(a); 214 } 215 Node<T> bNode = all.get(b); 216 if (bNode == null) { 217 bNode = addNew(b); 218 } 219 addLink(aNode, bNode); 220 if (DEBUG) { 221 System.out.println(a + " + " + b + " => " + this); 222 } 223 return this; 224 } 225 226 /** 227 * Get the comparator you've been building. After this call, the builder is 228 * reset (if there is no error). 229 * 230 * @return comparator 231 * @exception CycleException 232 * throwing if there is (at least one) cycle, like a > b > c > 233 * a. If so, call getCycle to see the cycle that triggered the 234 * exception. 235 */ get()236 public DiscreteComparator<T> get() { 237 if (DEBUG) { 238 debugIndent = new Exception().getStackTrace().length; 239 } 240 Map<T, Integer> ordering = new LinkedHashMap<T, Integer>(); 241 for (Node<T> subNode : all.values()) { 242 if (!subNode.visited) { 243 try { 244 subNode.visit(ordering); 245 } catch (CycleException e) { 246 throw new CycleException( 247 "\n\tcycle:" + getCycle() 248 + "\n\tall:" + all 249 + "\n\tordering:" + ordering, 250 e); 251 } 252 } 253 } 254 // clean up, so another call doesn't mess things up 255 all.clear(); 256 return new DiscreteComparator<T>(ordering, backupOrdering); 257 } 258 259 /** 260 * Call only after getting a CycleException 261 * 262 * @return list of items that form a cycle, in order from least to greatest 263 */ getCycle()264 public List<T> getCycle() { 265 List<T> result = new LinkedList<T>(); 266 Collection<Node<T>> lesser = all.values(); 267 main: while (true) { 268 for (Node<T> item : lesser) { 269 if (item.chained) { 270 if (result.contains(item.me)) { 271 return result; 272 } 273 result.add(0, item.me); 274 lesser = item.less; 275 continue main; 276 } 277 } 278 throw new IllegalArgumentException("Must only be called after a CycleException"); 279 } 280 } 281 282 @Override toString()283 public String toString() { 284 return order + ":\t" + all.values().toString(); 285 } 286 addLink(Node<T> aNode, Node<T> bNode)287 private void addLink(Node<T> aNode, Node<T> bNode) { 288 bNode.less.add(aNode); 289 } 290 addNew(T a)291 private Node<T> addNew(T a) { 292 Node<T> aNode = new Node<T>(a, order); 293 all.put(a, aNode); 294 return aNode; 295 } 296 } 297 298 private static class Node<T> implements Comparable<Node<T>> { 299 private Set<Node<T>> less; 300 private T me; 301 private boolean visited = false; 302 private boolean chained = false; 303 Node(T a, Ordering order)304 public Node(T a, Ordering order) { 305 less = new LinkedHashSet<Node<T>>(); 306 less = order == Ordering.CHRONOLOGICAL ? new LinkedHashSet<Node<T>>() 307 : order == Ordering.NATURAL ? new TreeSet<Node<T>>() 308 : new HashSet<Node<T>>(); 309 310 me = a; 311 } 312 visit(Map<T, Integer> resultOrdering)313 private void visit(Map<T, Integer> resultOrdering) { 314 Node<T> currentNode = this; 315 if (DEBUG) { 316 String gap = Utility.repeat(" ", new Exception().getStackTrace().length - debugIndent); 317 System.out.println("Visiting:\t" + gap + currentNode + " => " + resultOrdering.keySet()); 318 } 319 currentNode.visited = true; 320 currentNode.chained = true; 321 for (Node<T> subNode : currentNode.less) { 322 if (subNode.chained) { 323 throw new CycleException("Cycle in input data: " + subNode.toString()); 324 } 325 if (subNode.visited) { 326 continue; 327 } 328 subNode.visit(resultOrdering); 329 } 330 currentNode.chained = false; 331 resultOrdering.put(currentNode.me, resultOrdering.size()); 332 } 333 toString()334 public String toString() { 335 StringBuilder result = new StringBuilder(); 336 result.append(me == null ? null : me.toString()).append(" >"); 337 for (Node<T> lesser : less) { 338 result.append(" ").append(lesser.me); 339 } 340 return result.toString(); 341 } 342 343 @SuppressWarnings({ "unchecked", "rawtypes" }) compareTo(Node<T> o)344 public int compareTo(Node<T> o) { 345 return ((Comparable) me).compareTo((Comparable) (o.me)); 346 } 347 } 348 349 /** 350 * Exception for indicating that a cycle was found. 351 */ 352 public static class CycleException extends RuntimeException { 353 private static final long serialVersionUID = 1L; 354 CycleException(String message)355 public <T> CycleException(String message) { 356 super(message); 357 } 358 CycleException(String message, Exception e)359 public <T> CycleException(String message, Exception e) { 360 super(message, e); 361 } 362 } 363 364 /** 365 * Exception indicating that there is no backup comparator, and at least one 366 * of the items compared is not explicitly set. 367 */ 368 public static class MissingItemException extends RuntimeException { 369 private static final long serialVersionUID = 1L; 370 MissingItemException(String message)371 public MissingItemException(String message) { 372 super(message); 373 } 374 } 375 } 376