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