001: /*
002: *******************************************************************************
003: * Copyright (C) 1996-2006, International Business Machines Corporation and *
004: * others. All Rights Reserved. *
005: *******************************************************************************
006: */
007: package com.ibm.icu.dev.test.util;
008:
009: import java.util.ArrayList;
010: import java.util.Collections;
011: import java.util.HashMap;
012: import java.util.HashSet;
013: import java.util.Iterator;
014: import java.util.List;
015: import java.util.Map;
016: import java.util.Set;
017:
018: public class XEquivalenceClass {
019:
020: // quick test
021: static public void main(String[] args) {
022: XEquivalenceClass foo1 = new XEquivalenceClass("NONE");
023: String[][] tests = { { "b", "a1" }, { "b", "c" },
024: { "a1", "c" }, { "d", "e" }, { "e", "f" }, { "c", "d" } };
025: for (int i = 0; i < tests.length; ++i) {
026: System.out.println("Adding: " + tests[i][0] + ", "
027: + tests[i][1]);
028: foo1.add(tests[i][0], tests[i][1], new Integer(i));
029: for (Iterator it = foo1.getExplicitItems().iterator(); it
030: .hasNext();) {
031: Object item = it.next();
032: System.out.println("\t" + item + ";\t"
033: + foo1.getSample(item) + ";\t"
034: + foo1.getEquivalences(item));
035: System.out.println("\t\t"
036: + foo1.getReasons(item, foo1.getSample(item)));
037: }
038: }
039: }
040:
041: private Map toPartitionSet = new HashMap();
042: private Map obj_obj_reasons = new HashMap();
043: private Object defaultReason;
044:
045: /**
046: * empty, as if just created
047: */
048: public XEquivalenceClass clear(Object defaultReason) {
049: toPartitionSet.clear();
050: obj_obj_reasons.clear();
051: this .defaultReason = defaultReason;
052: return this ;
053: }
054:
055: /**
056: * Create class with comparator, and default reason.
057: *
058: */
059: public XEquivalenceClass(Object defaultReason) {
060: this .defaultReason = defaultReason;
061: }
062:
063: /**
064: * Add two equivalent items, with NO_REASON for the reason.
065: */
066: public XEquivalenceClass add(Object a, Object b) {
067: return add(a, b, null);
068: }
069:
070: /**
071: * Add two equivalent items, plus a reason. The reason is only used for getReasons
072: */
073: public XEquivalenceClass add(Object a, Object b, Object reason) {
074: if (a.equals(b))
075: return this ;
076: if (reason == null)
077: reason = defaultReason;
078: addReason(a, b, reason);
079: addReason(b, a, reason);
080: Set aPartitionSet = (Set) toPartitionSet.get(a);
081: Set bPartitionSet = (Set) toPartitionSet.get(b);
082: if (aPartitionSet == null) {
083: if (bPartitionSet == null) { // both null, set up bSet
084: bPartitionSet = new HashSet();
085: bPartitionSet.add(b);
086: toPartitionSet.put(b, bPartitionSet);
087: }
088: bPartitionSet.add(a);
089: toPartitionSet.put(a, bPartitionSet);
090: } else if (bPartitionSet == null) { // aSet is not null, bSet null
091: aPartitionSet.add(b);
092: toPartitionSet.put(b, aPartitionSet);
093: } else if (aPartitionSet != bPartitionSet) { // both non-null, not equal, merge. Equality check ok here
094: aPartitionSet.addAll(bPartitionSet);
095: // remap every x that had x => bPartitionSet
096: for (Iterator it = bPartitionSet.iterator(); it.hasNext();) {
097: toPartitionSet.put(it.next(), aPartitionSet);
098: }
099: }
100: return this ;
101: }
102:
103: /**
104: * Add all the information from the other class
105: *
106: */
107: public XEquivalenceClass addAll(XEquivalenceClass other) {
108: // For now, does the simple, not optimized version
109: for (Iterator it = other.obj_obj_reasons.keySet().iterator(); it
110: .hasNext();) {
111: Object a = it.next();
112: Map obj_reasons = (Map) other.obj_obj_reasons.get(a);
113: for (Iterator it2 = obj_reasons.keySet().iterator(); it2
114: .hasNext();) {
115: Object b = it2.next();
116: Set reasons = (Set) obj_reasons.get(b);
117: for (Iterator it3 = reasons.iterator(); it3.hasNext();) {
118: Object reason = it3.next();
119: add(a, b, reason);
120: }
121: }
122: }
123: return this ;
124: }
125:
126: /**
127: *
128: */
129: private void addReason(Object a, Object b, Object reason) {
130: Map obj_reasons = (Map) obj_obj_reasons.get(a);
131: if (obj_reasons == null)
132: obj_obj_reasons.put(a, obj_reasons = new HashMap());
133: Set reasons = (Set) obj_reasons.get(b);
134: if (reasons == null)
135: obj_reasons.put(b, reasons = new HashSet());
136: reasons.add(reason);
137: }
138:
139: /**
140: * Returns a set of all the explicit items in the equivalence set. (Any non-explicit items only
141: * have themselves as equivalences.)
142: *
143: */
144: public Set getExplicitItems() {
145: return Collections.unmodifiableSet(toPartitionSet.keySet());
146: }
147:
148: /**
149: * Returns an unmodifiable set of all the equivalent objects
150: *
151: */
152: public Set getEquivalences(Object a) {
153: Set aPartitionSet = (Set) toPartitionSet.get(a);
154: if (aPartitionSet == null) { // manufacture an equivalence
155: aPartitionSet = new HashSet();
156: aPartitionSet.add(a);
157: }
158: return Collections.unmodifiableSet(aPartitionSet);
159: }
160:
161: public Set getEquivalenceSets() {
162: Set result = new HashSet();
163: for (Iterator it = toPartitionSet.keySet().iterator(); it
164: .hasNext();) {
165: Object item = it.next();
166: Set partition = (Set) toPartitionSet.get(item);
167: result.add(Collections.unmodifiableSet(partition));
168: }
169: return result;
170: }
171:
172: /**
173: * returns true iff a is equivalent to b (or a.equals b)
174: *
175: */
176: public boolean isEquivalent(Object a, Object b) {
177: if (a.equals(b))
178: return true;
179: Set aPartitionSet = (Set) toPartitionSet.get(a);
180: if (aPartitionSet == null)
181: return false;
182: return aPartitionSet.contains(b);
183: }
184:
185: /**
186: * Gets a sample object in the equivalence set for a.
187: *
188: */
189: public Object getSample(Object a) {
190: Set aPartitionSet = (Set) toPartitionSet.get(a);
191: if (aPartitionSet == null)
192: return a; // singleton
193: return aPartitionSet.iterator().next();
194: }
195:
196: public interface Filter {
197: boolean matches(Object o);
198: }
199:
200: public Object getSample(Object a, Filter f) {
201: Set aPartitionSet = (Set) toPartitionSet.get(a);
202: if (aPartitionSet == null)
203: return a; // singleton
204: for (Iterator it = aPartitionSet.iterator(); it.hasNext();) {
205: Object obj = it.next();
206: if (f.matches(obj))
207: return obj;
208: }
209: return a;
210: }
211:
212: /**
213: * gets the set of all the samples, one from each equivalence class.
214: *
215: */
216: public Set getSamples() {
217: Set seenAlready = new HashSet();
218: Set result = new HashSet();
219: for (Iterator it = toPartitionSet.keySet().iterator(); it
220: .hasNext();) {
221: Object item = it.next();
222: if (seenAlready.contains(item))
223: continue;
224: Set partition = (Set) toPartitionSet.get(item);
225: result.add(partition.iterator().next());
226: seenAlready.addAll(partition);
227: }
228: return result;
229: }
230:
231: /**
232: * Returns a list of lists. Each sublist is in the form [reasons, obj, reasons, obj,..., reasons]
233: * where each reasons is a set of reasons to go from one obj to the next.<br>
234: * Returns null if there is no connection.
235: */
236: public List getReasons(Object a, Object b) {
237: // use dumb algorithm for getting shortest path
238: // don't bother with optimization
239: Set aPartitionSet = (Set) toPartitionSet.get(a);
240: Set bPartitionSet = (Set) toPartitionSet.get(b);
241:
242: // see if they connect
243: if (aPartitionSet == null || bPartitionSet == null
244: || aPartitionSet != bPartitionSet || a.equals(b))
245: return null;
246:
247: ArrayList list = new ArrayList();
248: list.add(a);
249: ArrayList lists = new ArrayList();
250: lists.add(list);
251:
252: // this will contain the results
253: List foundLists = new ArrayList();
254: Set sawLastTime = new HashSet();
255: sawLastTime.add(a);
256:
257: // each time, we extend the lists by one (adding multiple other lists)
258: while (foundLists.size() == 0) {
259: ArrayList extendedList = new ArrayList();
260: Set sawThisTime = new HashSet();
261: for (Iterator it = lists.iterator(); it.hasNext();) {
262: ArrayList lista = (ArrayList) it.next();
263: Object last = lista.get(lista.size() - 1);
264: Map obj_reasons = (Map) obj_obj_reasons.get(last);
265: for (Iterator it2 = obj_reasons.keySet().iterator(); it2
266: .hasNext();) {
267: Object item = it2.next();
268: if (sawLastTime.contains(item)) {
269: continue; // skip since we have shorter
270: }
271: sawThisTime.add(item);
272: Set reasons = (Set) obj_reasons.get(item);
273: ArrayList lista2 = (ArrayList) lista.clone();
274: lista2.add(reasons);
275: lista2.add(item);
276: extendedList.add(lista2);
277: if (item.equals(b)) {
278: // remove first and last
279: ArrayList found = (ArrayList) lista2.clone();
280: found.remove(0);
281: found.remove(found.size() - 1);
282: foundLists.add(found);
283: }
284: }
285: }
286: lists = extendedList;
287: sawLastTime.addAll(sawThisTime);
288: }
289: return foundLists;
290: }
291: }
|