jars/icu4j-4_4_2-src/main/tests/core/src/com/ibm/icu/dev/test/util/XEquivalenceClass.java

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