src/com/ibm/icu/dev/test/util/XEquivalenceClass.java

/*
 *******************************************************************************
 * Copyright (C) 1996-2005, International Business Machines Corporation and    *
 * others. All Rights Reserved.                                                *
 *******************************************************************************
 */
package com.ibm.icu.dev.test.util;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class XEquivalenceClass {
	
	// quick test
	static public void main(String[] args) {
		XEquivalenceClass foo1 = new XEquivalenceClass("NONE");
		String[][] tests = {{"b","a1"}, {"b", "c"}, {"a1", "c"}, {"d", "e"}, {"e", "f"}, {"c", "d"}};
		for (int i = 0; i < tests.length; ++i) {
			System.out.println("Adding: " + tests[i][0] + ", " + tests[i][1]);
			foo1.add(tests[i][0], tests[i][1], new Integer(i));
			for (Iterator it = foo1.getExplicitItems().iterator(); it.hasNext();) {
				Object item = it.next();
				System.out.println("\t" + item  + ";\t" + foo1.getSample(item) + ";\t" + foo1.getEquivalences(item));
				System.out.println("\t\t" + foo1.getReasons(item, foo1.getSample(item)));
			}
		}
	}
	
	private Map toPartitionSet = new HashMap();
	private Map obj_obj_reasons = new HashMap();
	private Object defaultReason;
	
	/**
	 * empty, as if just created
	 */
	public XEquivalenceClass clear(Object defaultReason) {
		toPartitionSet.clear();
		obj_obj_reasons.clear();
		this.defaultReason = defaultReason;
		return this;
	}
	
	/**
	 * Create class with comparator, and default reason.
	 *
	 */
	public XEquivalenceClass(Object defaultReason) {
		this.defaultReason = defaultReason;
	}
	
	/**
	 * Add two equivalent items, with NO_REASON for the reason.
	 */
	public XEquivalenceClass add(Object a, Object b) {
		return add(a,b,null);
	}
	
	/**
	 * Add two equivalent items, plus a reason. The reason is only used for getReasons
	 */
	public XEquivalenceClass add(Object a, Object b, Object reason) {
		if (a.equals(b)) return this;
		if (reason == null) reason = defaultReason;
		addReason(a,b,reason);
		addReason(b,a,reason);
		Set aPartitionSet = (Set) toPartitionSet.get(a);
		Set bPartitionSet = (Set) toPartitionSet.get(b);
		if (aPartitionSet == null) {
			if (bPartitionSet == null) { // both null, set up bSet
				bPartitionSet = new HashSet();
				bPartitionSet.add(b);
				toPartitionSet.put(b, bPartitionSet);				
			}
			bPartitionSet.add(a);
			toPartitionSet.put(a, bPartitionSet);				
		} else if (bPartitionSet == null) { // aSet is not null, bSet null
			aPartitionSet.add(b);
			toPartitionSet.put(b, aPartitionSet);							
		} else if (aPartitionSet != bPartitionSet) {  // both non-null, not equal, merge.  Equality check ok here
			aPartitionSet.addAll(bPartitionSet);
			// remap every x that had x => bPartitionSet
			for (Iterator it = bPartitionSet.iterator(); it.hasNext();) {
				toPartitionSet.put(it.next(), aPartitionSet);	
			}
		}
		return this;
	}
	
	/**
	 * Add all the information from the other class
	 *
	 */
	public XEquivalenceClass addAll(XEquivalenceClass other) {
		// For now, does the simple, not optimized version
		for (Iterator it = other.obj_obj_reasons.keySet().iterator(); it.hasNext();) {
			Object a = it.next();
			Map obj_reasons = (Map) other.obj_obj_reasons.get(a);
			for (Iterator it2 = obj_reasons.keySet().iterator(); it2.hasNext();) {
				Object b = it2.next();
				Set reasons = (Set) obj_reasons.get(b);
				for (Iterator it3 = reasons.iterator(); it3.hasNext();) {
					Object reason = it3.next();
					add(a, b, reason);
				}
			}
		}
		return this;
	}
	
	/**
	 * 
	 */
	private void addReason(Object a, Object b, Object reason) {
		Map obj_reasons = (Map) obj_obj_reasons.get(a);
		if (obj_reasons == null) obj_obj_reasons.put(a, obj_reasons = new HashMap());
		Set reasons = (Set) obj_reasons.get(b);
		if (reasons == null) obj_reasons.put(b, reasons = new HashSet());
		reasons.add(reason);
	}

	/**
	 * Returns a set of all the explicit items in the equivalence set. (Any non-explicit items only
	 * have themselves as equivalences.)
	 *
	 */
	public Set getExplicitItems() {
		return Collections.unmodifiableSet(toPartitionSet.keySet());
	}
	
	/**
	 * Returns an unmodifiable set of all the equivalent objects
	 *
	 */
	public Set getEquivalences(Object a) {
		Set aPartitionSet = (Set) toPartitionSet.get(a);
		if (aPartitionSet == null) { // manufacture an equivalence
			aPartitionSet = new HashSet();
			aPartitionSet.add(a); 
		}
		return Collections.unmodifiableSet(aPartitionSet);
	}
	
	public Set getEquivalenceSets() {
		Set result = new HashSet();
		for (Iterator it = toPartitionSet.keySet().iterator(); it.hasNext();) {
			Object item = it.next();
			Set partition = (Set) toPartitionSet.get(item);
			result.add(Collections.unmodifiableSet(partition));
		}
		return result;	
	}
	/**
	 * returns true iff a is equivalent to b (or a.equals b)
	 *
	 */
	public boolean isEquivalent(Object a, Object b) {
		if (a.equals(b)) return true;
		Set aPartitionSet = (Set) toPartitionSet.get(a);
		if (aPartitionSet == null) return false;
		return aPartitionSet.contains(b);
	}
	
	/**
	 * Gets a sample object in the equivalence set for a. 
	 *
	 */
	public Object getSample(Object a) {
		Set aPartitionSet = (Set) toPartitionSet.get(a);
		if (aPartitionSet == null) return a; // singleton
		return aPartitionSet.iterator().next();
	}
	
	public interface Filter {
		boolean matches(Object o);
	}
	
	public Object getSample(Object a, Filter f) {
		Set aPartitionSet = (Set) toPartitionSet.get(a);
		if (aPartitionSet == null) return a; // singleton
		for (Iterator it = aPartitionSet.iterator(); it.hasNext();) {
			Object obj = it.next();
			if (f.matches(obj)) return obj;
		}
		return a;
	}

	/**
	 * gets the set of all the samples, one from each equivalence class. 
	 *
	 */
	public Set getSamples() {
		Set seenAlready = new HashSet();
		Set result = new HashSet();
		for (Iterator it = toPartitionSet.keySet().iterator(); it.hasNext();) {
			Object item = it.next();
			if (seenAlready.contains(item)) continue;
			Set partition = (Set) toPartitionSet.get(item);
			result.add(partition.iterator().next());
			seenAlready.addAll(partition);
		}
		return result;
	}
	

	/**
	 * Returns a list of lists. Each sublist is in the form [reasons, obj, reasons, obj,..., reasons]
	 * where each reasons is a set of reasons to go from one obj to the next.<br>
	 * Returns null if there is no connection.
	 */
	public List getReasons(Object a, Object b) {
		// use dumb algorithm for getting shortest path
		// don't bother with optimization
		Set aPartitionSet = (Set) toPartitionSet.get(a);
		Set bPartitionSet = (Set) toPartitionSet.get(b);
		
		// see if they connect
		if (aPartitionSet == null || bPartitionSet == null || aPartitionSet != bPartitionSet || a.equals(b)) return null;
		
		ArrayList list = new ArrayList();
		list.add(a);
		ArrayList lists = new ArrayList();
		lists.add(list);

		// this will contain the results
		List foundLists = new ArrayList();
		Set sawLastTime = new HashSet();
		sawLastTime.add(a);
		
		// each time, we extend the lists by one (adding multiple other lists)
		while (foundLists.size() == 0) {
			ArrayList extendedList = new ArrayList();
			Set sawThisTime = new HashSet();
			for (Iterator it = lists.iterator(); it.hasNext();) {
				ArrayList lista = (ArrayList) it.next();
				Object last = lista.get(lista.size()-1);
				Map obj_reasons = (Map) obj_obj_reasons.get(last);
				for (Iterator it2 = obj_reasons.keySet().iterator(); it2.hasNext();) {
					Object item = it2.next();
					if (sawLastTime.contains(item)) {
						continue; // skip since we have shorter
					}
					sawThisTime.add(item);
					Set reasons = (Set) obj_reasons.get(item);
					ArrayList lista2 = (ArrayList)lista.clone();
					lista2.add(reasons);
					lista2.add(item);
					extendedList.add(lista2);
					if (item.equals(b)) {
						// remove first and last
						ArrayList found = (ArrayList)lista2.clone();
						found.remove(0);
						found.remove(found.size()-1);
						foundLists.add(found);
					}
				}
			}
			lists = extendedList;
			sawLastTime.addAll(sawThisTime);
		}
		return foundLists;
	}
}