• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 }