jars/icu4j-4_2_1-src/src/com/ibm/icu/dev/test/util/XEquivalenceClass.java

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