1 /* 2 ******************************************************************************* 3 * Copyright (C) 1996-2013, International Business Machines Corporation and * 4 * others. All Rights Reserved. * 5 ******************************************************************************* 6 */ 7 package org.unicode.cldr.util; 8 9 import com.ibm.icu.text.Transform; 10 import java.util.ArrayList; 11 import java.util.Collections; 12 import java.util.HashMap; 13 import java.util.HashSet; 14 import java.util.Iterator; 15 import java.util.List; 16 import java.util.Map; 17 import java.util.Set; 18 19 public class XEquivalenceClass<T, R> implements Iterable<T> { 20 private static final String ARROW = "\u2192"; 21 getSetMaker()22 public SetMaker<T> getSetMaker() { 23 return setMaker; 24 } 25 26 // quick test main(String[] args)27 public static void main(String[] args) { 28 XEquivalenceClass<String, Integer> foo1 = new XEquivalenceClass<>(1); 29 String[][] tests = { 30 {"b", "a1"}, {"b", "c"}, {"a1", "c"}, {"d", "e"}, {"e", "f"}, {"c", "d"} 31 }; 32 for (int i = 0; i < tests.length; ++i) { 33 System.out.println("Adding: " + tests[i][0] + ", " + tests[i][1]); 34 foo1.add(tests[i][0], tests[i][1], i); 35 for (String item : foo1.getExplicitItems()) { 36 System.out.println( 37 "\t" 38 + item 39 + ";\t" 40 + foo1.getSample(item) 41 + ";\t" 42 + foo1.getEquivalences(item)); 43 List<Linkage<String, Integer>> reasons = 44 foo1.getReasons(item, foo1.getSample(item)); 45 if (reasons != null) { 46 System.out.println("\t\t" + XEquivalenceClass.toString(reasons, null)); 47 } 48 } 49 } 50 } 51 52 private Map<T, Set<T>> toPartitionSet = new HashMap(); 53 private Map<T, Map<T, Set<R>>> obj_obj_reasons = new HashMap(); 54 private R defaultReason; 55 private SetMaker setMaker; 56 57 public interface SetMaker<T> { make()58 Set<T> make(); 59 } 60 61 /** empty, as if just created */ clear(R defaultReasonArg)62 public XEquivalenceClass clear(R defaultReasonArg) { 63 toPartitionSet.clear(); 64 obj_obj_reasons.clear(); 65 this.defaultReason = defaultReasonArg; 66 return this; 67 } 68 69 /** Create class */ XEquivalenceClass()70 public XEquivalenceClass() {} 71 72 /** Create class with comparator, and default reason. */ XEquivalenceClass(R defaultReason)73 public XEquivalenceClass(R defaultReason) { 74 this.defaultReason = defaultReason; 75 } 76 77 /** Create class with comparator, and default reason. */ XEquivalenceClass(R defaultReason, SetMaker<T> setMaker)78 public XEquivalenceClass(R defaultReason, SetMaker<T> setMaker) { 79 this.defaultReason = defaultReason; 80 this.setMaker = setMaker; 81 } 82 83 /** Add two equivalent items, with NO_REASON for the reason. */ add(T a, T b)84 public XEquivalenceClass add(T a, T b) { 85 return add(a, b, null); 86 } 87 88 /** Add two equivalent items, with NO_REASON for the reason. */ add(T a, T b, R reason)89 public XEquivalenceClass add(T a, T b, R reason) { 90 return add(a, b, reason, reason); 91 } 92 93 /** Add two equivalent items, plus a reason. The reason is only used for getReasons */ add(T a, T b, R reasonAB, R reasonBA)94 public XEquivalenceClass add(T a, T b, R reasonAB, R reasonBA) { 95 if (a.equals(b)) return this; 96 if (reasonAB == null) reasonAB = defaultReason; 97 if (reasonBA == null) reasonBA = defaultReason; 98 addReason(a, b, reasonAB); 99 addReason(b, a, reasonBA); 100 Set<T> aPartitionSet = toPartitionSet.get(a); 101 Set<T> bPartitionSet = toPartitionSet.get(b); 102 if (aPartitionSet == null) { 103 if (bPartitionSet == null) { // both null, set up bSet 104 bPartitionSet = setMaker != null ? setMaker.make() : new HashSet(); 105 bPartitionSet.add(b); 106 toPartitionSet.put(b, bPartitionSet); 107 } 108 bPartitionSet.add(a); 109 toPartitionSet.put(a, bPartitionSet); 110 } else if (bPartitionSet == null) { // aSet is not null, bSet null 111 aPartitionSet.add(b); 112 toPartitionSet.put(b, aPartitionSet); 113 } else if (aPartitionSet 114 != bPartitionSet) { // both non-null, not equal, merge. Equality check ok here 115 aPartitionSet.addAll(bPartitionSet); 116 // remap every x that had x => bPartitionSet 117 for (T item : bPartitionSet) { 118 toPartitionSet.put(item, aPartitionSet); 119 } 120 } 121 return this; 122 } 123 124 /** Add all the information from the other class */ addAll(XEquivalenceClass<T, R> other)125 public XEquivalenceClass<T, R> addAll(XEquivalenceClass<T, R> other) { 126 // For now, does the simple, not optimized version 127 for (T a : other.obj_obj_reasons.keySet()) { 128 Map<T, Set<R>> obj_reasons = other.obj_obj_reasons.get(a); 129 for (T b : obj_reasons.keySet()) { 130 Set<R> reasons = obj_reasons.get(b); 131 for (R reason : reasons) { 132 add(a, b, reason); 133 } 134 } 135 } 136 return this; 137 } 138 139 /** */ addReason(T a, T b, R reason)140 private void addReason(T a, T b, R reason) { 141 Map<T, Set<R>> obj_reasons = obj_obj_reasons.get(a); 142 if (obj_reasons == null) obj_obj_reasons.put(a, obj_reasons = new HashMap()); 143 Set<R> reasons = obj_reasons.get(b); 144 if (reasons == null) obj_reasons.put(b, reasons = new HashSet()); 145 reasons.add(reason); 146 } 147 148 /** 149 * Returns a set of all the explicit items in the equivalence set. (Any non-explicit items only 150 * have themselves as equivalences.) 151 */ getExplicitItems()152 public Set<T> getExplicitItems() { 153 return Collections.unmodifiableSet(toPartitionSet.keySet()); 154 } 155 156 /** Returns an unmodifiable set of all the equivalent objects */ getEquivalences(T a)157 public Set<T> getEquivalences(T a) { 158 Set<T> aPartitionSet = toPartitionSet.get(a); 159 if (aPartitionSet == null) { // manufacture an equivalence 160 aPartitionSet = new HashSet<>(); 161 aPartitionSet.add(a); 162 } 163 return Collections.unmodifiableSet(aPartitionSet); 164 } 165 hasEquivalences(T a)166 public boolean hasEquivalences(T a) { 167 return toPartitionSet.get(a) != null; 168 } 169 getEquivalenceSets()170 public Set<Set<T>> getEquivalenceSets() { 171 Set<Set<T>> result = new HashSet<>(); 172 for (T item : toPartitionSet.keySet()) { 173 Set<T> partition = toPartitionSet.get(item); 174 result.add(Collections.unmodifiableSet(partition)); 175 } 176 return result; 177 } 178 179 /** returns true iff a is equivalent to b (or a.equals b) */ isEquivalent(T a, T b)180 public boolean isEquivalent(T a, T b) { 181 if (a.equals(b)) return true; 182 Set<T> aPartitionSet = toPartitionSet.get(a); 183 if (aPartitionSet == null) return false; 184 return aPartitionSet.contains(b); 185 } 186 187 /** Gets a sample object in the equivalence set for a. */ getSample(T a)188 public T getSample(T a) { 189 Set<T> aPartitionSet = toPartitionSet.get(a); 190 if (aPartitionSet == null) return a; // singleton 191 return aPartitionSet.iterator().next(); 192 } 193 194 public interface Filter<T> { matches(T o)195 boolean matches(T o); 196 } 197 getSample(T a, Filter<T> f)198 public T getSample(T a, Filter<T> f) { 199 Set<T> aPartitionSet = toPartitionSet.get(a); 200 if (aPartitionSet == null) return a; // singleton 201 for (T obj : aPartitionSet) { 202 if (f.matches(obj)) return obj; 203 } 204 return a; 205 } 206 207 /** gets the set of all the samples, one from each equivalence class. */ getSamples()208 public Set<T> getSamples() { 209 Set<T> seenAlready = new HashSet(); 210 Set<T> result = new HashSet(); 211 for (T item : toPartitionSet.keySet()) { 212 if (seenAlready.contains(item)) continue; 213 Set<T> partition = toPartitionSet.get(item); 214 result.add(partition.iterator().next()); 215 seenAlready.addAll(partition); 216 } 217 return result; 218 } 219 220 @Override iterator()221 public Iterator<T> iterator() { 222 return getSamples().iterator(); 223 } 224 225 public static class Linkage<T, R> { 226 public Set<R> reasons; 227 public T result; 228 Linkage(Set<R> reasons, T result)229 public Linkage(Set<R> reasons, T result) { 230 this.reasons = reasons; 231 this.result = result; 232 } 233 234 @Override toString()235 public String toString() { 236 return reasons + (result == null ? "" : ARROW + result); 237 } 238 } 239 toString( List<Linkage<T, R>> others, Transform<Linkage<T, R>, String> itemTransform)240 public static <T, R> String toString( 241 List<Linkage<T, R>> others, Transform<Linkage<T, R>, String> itemTransform) { 242 StringBuffer result = new StringBuffer(); 243 for (Linkage<T, R> item : others) { 244 result.append(itemTransform == null ? item.toString() : itemTransform.transform(item)); 245 } 246 return result.toString(); 247 } 248 249 /** 250 * Returns a list of linkages, where each set of reasons to go from one obj to the next. The 251 * list does not include a and b themselves. The last linkage has a null result.<br> 252 * Returns null if there is no connection. 253 */ getReasons(T a, T b)254 public List<Linkage<T, R>> getReasons(T a, T b) { 255 // use dumb algorithm for getting shortest path 256 // don't bother with optimization 257 Set<T> aPartitionSet = toPartitionSet.get(a); 258 Set<T> bPartitionSet = toPartitionSet.get(b); 259 260 // see if they connect 261 if (aPartitionSet == null 262 || bPartitionSet == null 263 || aPartitionSet != bPartitionSet 264 || a.equals(b)) return null; 265 266 ArrayList<Linkage<T, R>> list = new ArrayList<>(); 267 list.add(new Linkage(null, a)); 268 ArrayList<ArrayList<Linkage<T, R>>> lists = new ArrayList<>(); 269 lists.add(list); 270 271 // this will contain the results 272 Set<T> sawLastTime = new HashSet<>(); 273 sawLastTime.add(a); 274 275 // each time, we extend each lists by one (adding multiple other lists) 276 while (true) { // foundLists.size() == 0 277 ArrayList extendedList = new ArrayList(); 278 Set<T> sawThisTime = new HashSet(); 279 for (ArrayList<Linkage<T, R>> lista : lists) { 280 Linkage<T, R> last = lista.get(lista.size() - 1); 281 Map<T, Set<R>> obj_reasons = obj_obj_reasons.get(last.result); 282 for (T result : obj_reasons.keySet()) { 283 if (sawLastTime.contains(result)) { 284 continue; // skip since we have shorter 285 } 286 sawThisTime.add(result); 287 Set<R> reasons = obj_reasons.get(result); 288 ArrayList<Linkage<T, R>> lista2 = (ArrayList<Linkage<T, R>>) lista.clone(); 289 lista2.add(new Linkage(reasons, result)); 290 extendedList.add(lista2); 291 if (result.equals(b)) { 292 // remove first and last 293 ArrayList<Linkage<T, R>> found = (ArrayList<Linkage<T, R>>) lista2.clone(); 294 found.remove(0); 295 found.get(found.size() - 1).result = null; 296 return found; 297 } 298 } 299 } 300 lists = extendedList; 301 sawLastTime.addAll(sawThisTime); 302 } 303 // return foundLists; 304 } 305 306 /** For debugging. */ 307 @Override toString()308 public String toString() { 309 return getEquivalenceSets().toString(); 310 } 311 } 312