package causation.lab;

// Sun packages
import java.util.*;

// our packages
import tetrad.graph.*;

/**
 * This class determines and holds all of the D-separation facts 
 * implied by a TetradGraph.
 *
 * @version	1.0	July 20, 1999
 * @author	David Danks
 */

public class DSeparationFacts {

/////////////////// Instance Variables ///////////////////
	private TetradGraph tg;
	private String[][] dsep;
	private int numDSep = 0;
	private int nvert = 0;
	private Node[] allNodes;
	private String[] returnFacts = null;

/////////////////// Constructors ///////////////////
/**
 * This constructor reads in a TetradGraph and determines the D-separation
 * facts implied by that TetradGraph.
 *
 * @param	tgraph	The TetradGraph to be analyzed
 */
	public DSeparationFacts(TetradGraph tgraph) {
		this(tgraph, true);
	}
	
/**
 * This constructor reads in a TetradGraph and, depending on the value of
 * <code>analyze</code>, possibly determines the D-separation facts.
 * This constructor is provided since computing D-separation facts can
 * be computationally expensive, and so the user might want to wait.
 *
 * @param	tgraph	The TetradGraph to be analyzed
 * @param	analyze	<code>true</code>, to determine the D-separation 
 *							facts immediately;
 *							<code>false</code>, to wait.
 */
	public DSeparationFacts(TetradGraph tgraph, boolean analyze) {
		tg = tgraph;
		nvert = tg.getNumNodes();
		// lots of things are easier if we have the Nodes in an array
		Iterator nodeIter = tg.nodeIterator();
		allNodes = new Node[nvert];
		int n=0;
		while (nodeIter.hasNext()) {
			allNodes[n] = (Node)nodeIter.next();
			n++;
		}
		// allocate for dsep
		dsep = new String[nvert*(nvert-1)/2][10];
		if (analyze) computeDSepFacts();
	}
	
/////////////////// Instance Methods ///////////////////
/**
 * Computes the D-separation facts for the stored TetradGraph.  Note: This
 * procedure involves a significant combinatoric explosion, so it can
 * be quite computationally expensive.
 */
	public void computeDSepFacts() {
		for (int i=0; i<allNodes.length; i++) {
			for (int j=i+1; j<allNodes.length; j++) {
				// check the null conditioning set
				int curr = 0;
				if (tg.isDSeparatedFrom(allNodes[i], allNodes[j], 
					new HashSet())) {
					dsep[code(i,j)][curr] = "";
					curr++; numDSep++; 
				}
				// now check all of the actual conditioning sets.  It's easier
				// to determine the cond sets if we build them as Vectors, so
				// we do that, and then wrap them in HashSets to pass to the
				// isDSeparatedFrom() method.
				for (int n=1; n<=allNodes.length-2; n++) {
					Vector[] cond = 
						createCondSets(n, allNodes[i], allNodes[j]);
					for (int c=0; c<cond.length; c++) {
						if (tg.isDSeparatedFrom(allNodes[i], allNodes[j], 
							new HashSet(cond[c]))) {
							// figure out the String for the cond set
							String condSet = "";
							Enumeration nodeEnum = cond[c].elements();
							while (nodeEnum.hasMoreElements()) {
								condSet += ((Node)nodeEnum.nextElement()).getName();
								condSet += ",";
							}
							condSet= condSet.substring(0, condSet.length()-1);
							dsep[code(i,j)][curr] = condSet;
							curr++; numDSep++;
						}
					}
				}
			}
		}
	}
	
/**
 * Creates all of the conditioning sets of size n, for nodes x and y.
 *
 * @param	n	The number of nodes to be in the conditioning set
 * @param	X	One of the nodes to be tested
 * @param	Y	The other node to be tested
 * @return		An array of Vectors that contains all of the conditioning
 *					sets
 */
	private Vector[] createCondSets(int n, Node X, Node Y) {
		if (n < 0) return null;
		if (n == 0) return new Vector[] { new Vector() };
		// create the initial list
		Vector[] expand = new Vector[allNodes.length-n-1];
		int cnt = 0;
		for (int i=0; i<allNodes.length-n+1; i++) {
			if (allNodes[i] == X || allNodes[i] == Y) continue;
			expand[cnt] = new Vector();
			expand[cnt].add(allNodes[i]);
			cnt++;
			// this line is needed for n>1, and X or Y in the "not used"
			// part of allNodes
			if (cnt == expand.length) break;
		}
		// now, iterate through for the others
		for (int i=1; i<n; i++) {
			// get the new Vectors
			Vector[][] hold = new Vector[expand.length][];
			int size = 0;
			for (int j=0; j<expand.length; j++) {
				hold[j] = addToList(expand[j], X, Y);
				size += hold[j].length;
			}
			// transfer them back to expand
			expand = new Vector[size];
			int index = 0;
			for (int j=0; j<hold.length; j++) {
				System.arraycopy(hold[j], 0, 
					expand, index, hold[j].length);
				index += hold[j].length;
			}
		}
		return expand;
	}

/**
 * This method returns a Vector[] that uses start as an initial 
 * segment for the Vectors to be returned, and then adds one more 
 * element to each Vector.  X and Y are the nodes that should not
 * be added.
 *
 * @param	start	A Vector containing the elements that all of the
 *						Vectors to be constructed should share
 * @param	X		One node not to add
 * @param	Y		The other node not to add
 * @return	An array of Vectors with one more element added to each
 */
	private Vector[] addToList(Vector start, Node X, Node Y) {
		int index = -1;
		if (start.size() != 0) {	// if something's there, advance index
			Node last = (Node)start.lastElement();
			// now figure out the index of this Node
			for (index=0; index<allNodes.length; index++) {
				if (allNodes[index] == last) break;
			}
		}
		// advance past X and Y, if either is next
		index++;
		while (allNodes[index] == X || allNodes[index] == Y) index++;
		
		// find out how many Vectors we're going to have to create
		int offset = 2;
		for (int i=0; i<index; i++) {
			if (allNodes[i] == X) offset--;
			if (allNodes[i] == Y) offset--;
		}
		Vector[] ret = new Vector[nvert-index-offset];
		
		// now fill the Vectors
		for (int i=0; i<ret.length; i++) {
			while (allNodes[index] == X || allNodes[index] == Y) index++;
			ret[i] = new Vector(start);
			// add the new element
			ret[i].add(allNodes[index]);
			index++;
		}
		return ret;
	}
	
/**
 * Returns a String array with all of the D-separation facts.  A
 * 0-length array is returned if there are no D-separation facts.  Each 
 * fact is returned as:
 *		nodeX|nodeY|condSet (where condSet is comma-delimited)
 * so that you can easily separate out the components.
 *
 * @return	A String array of D-separation facts.
 */
	public String[] getDSepFacts() {
		if (returnFacts != null) return returnFacts;
		if (numDSep == 0) return new String[0];
		String[] facts = new String[numDSep];
		int index = 0;
		FIRST: for (int i=0; i<nvert; i++) {
			SECOND: for (int j=i+1; j<nvert; j++) {
				for (int k=0; k<dsep[0].length; k++) {
					if (dsep[code(i,j)][k] == null) continue SECOND;
					facts[index] = allNodes[i]+"|"+allNodes[j]+"|";
					facts[index] += dsep[code(i,j)][k];
					index++;
				}
			}
		}
		returnFacts = facts;
		return facts;
	}
	
/**
 * This method filters the DSeparationFacts to ensure that only those 
 * variables in the filter are returned to the user.  If the filter is set to
 * <code>null</code>, then all of the DSeparationFacts are returned.
 *
 * @param	filter	The filter listing the variables to be shown
 * @return	An array of filtered d-separation facts
 */
	private void filterFacts(String[] filter) {
		// first, clear out the returnFacts array, so we can re-set it
		returnFacts = null;
		String[] fullFacts = getDSepFacts();
		// if there's no filter, just set returnFacts to fullFacts
		if (filter == null) {
			returnFacts = fullFacts;
			return;
		}
		int numRemoved = 0;
		FACTS: for (int i=0; i<fullFacts.length; i++) {
			StringTokenizer st = new StringTokenizer(fullFacts[i], "|");
			// check the first variable
			String token = st.nextToken();
			int j; for (j=0; j<filter.length; j++) {
				if (token.equals(filter[j])) break;
			}
			if (j == filter.length) {
				fullFacts[i] = null;
				numRemoved++;
				continue FACTS;
			}
			// check the second variable
			token = st.nextToken();
			for (j=0; j<filter.length; j++) {
				if (token.equals(filter[j])) break;
			}
			if (j == filter.length) {
				fullFacts[i] = null;
				numRemoved++;
				continue FACTS;
			}
			// if there are conditioners, check each of them
			if (st.hasMoreTokens()) {
				token = st.nextToken();
				StringTokenizer cond = new StringTokenizer(token, ",");
				while (cond.hasMoreTokens()) {
					token = cond.nextToken();
					for (j=0; j<filter.length; j++) {
						if (token.equals(filter[j])) break;
					}
					if (j == filter.length) {
						fullFacts[i] = null;
						numRemoved++;
						continue FACTS;
					}
				}
			}
		}
		// now create a new facts array (possibly of length 0)
		String[] filtered = new String[fullFacts.length-numRemoved];
		int filtIndex = 0;
		for (int i=0; i<fullFacts.length; i++) {
			if (fullFacts[i] != null) {
				filtered[filtIndex] = fullFacts[i];
				filtIndex++;
			}
		}
		returnFacts = filtered;
	}
	
/**
 * This method (possibly) adds to the facts array.  Specifically, if 
 * X _||_ Y | Z, and all variables in Z are in locked, then it is also
 * true that X _||_ Y.
 *
 * @param	locked	The names of the locked variables
 */
	private void addLockFacts(String[] locked) {
		if (locked == null) return;
		if (locked.length == 0) return;
		Vector toAdd = new Vector();
		FACTS: for (int i=0; i<returnFacts.length; i++) {
			StringTokenizer st = new StringTokenizer(returnFacts[i], "|");
			String uncond = st.nextToken();
			uncond += "|"+st.nextToken()+"|";
			// if there are conditioners, check to see if all are locked
			if (st.hasMoreTokens()) {
				StringTokenizer cond = 
					new StringTokenizer(st.nextToken(), ",");
				while (cond.hasMoreTokens()) {
					String token = cond.nextToken();
					int j; for (j=0; j<locked.length; j++) {
						if (token.equals(locked[j])) break;
					}
					if (j == locked.length)	// unlocked conditioner
						continue FACTS;
				}
				// only gets here if all conditioners locked
				// check to see whether we already passed the unconditioned
				int j; for (j=0; j<i; j++)
					if (uncond.equals(returnFacts[j])) continue FACTS;
				// if (j == i), then we haven't passed the unconditioned fact
				if (j == i) toAdd.addElement(uncond);
			}
			else {	// check if this unconditioned fact matches any toAdds 
				for (int j=toAdd.size()-1; j>=0; j--) {
					if (uncond.equals((String)toAdd.elementAt(j))) {
						toAdd.removeElementAt(j);
						continue FACTS;
					}
				}
			}
		}
		// if there aren't any facts to add, just return initialFacts
		if (toAdd.size() == 0) return;
		// now create a new facts array
		String[] added = new String[returnFacts.length+toAdd.size()];
		System.arraycopy(returnFacts, 0, added, 0, returnFacts.length);
		for (int i=0; i<toAdd.size(); i++) {
			added[returnFacts.length+i] = (String)toAdd.elementAt(i);
		}
		returnFacts = added; added = null;
		return;
	}
	
/**
 * This allows us to set a filter that screens which variables appear in the
 * DSeparationFacts.  It also allows us to set which variables are locked,
 * since this can affect the d-separation facts.  If X _||_ Y | Z, and if all 
 * variables in Z are locked, then it is also true that X _||_ Y.
 *
 * @param	filter	The Strings that can appear on the screen
 * @param	locked	The names of the locked variables
 */
	public void setFilterAndLockedVars(String[] filter, String[] locked) { 
		filterFacts(filter); 
		addLockFacts(locked);
	}

/**
 * Computes the code for the dsep matrix, since it's not simple
 *
 * @param	x	index of one node
 * @param	y	index of other node
 * @return	Their code for the dsep matrix
 */
	private int code(int x, int y) {
		return (x*(nvert-1)-(x*(x+1)/2)+y-1);
	}
	
/**
 * @return	The stored TetradGraph
 */
	public TetradGraph getGraph() { return tg; }
/**
 * @return	The number of D-separation facts
 */
	public int getNumDSep() { return numDSep; }
/**
 * Compares this D-Separation facts object to another one to determine
 * whether they have the same facts.
 * @return	<code>true</code>, if the two objects have the same 
 *				D-separation facts; <code>false</code>, otherwise.
 */
	public boolean equals(DSeparationFacts compare) {
		String[] one = getDSepFacts();
		String[] comp = compare.getDSepFacts();
		
		// first, just check to make sure they're the same length
		if (one.length != comp.length) return false;
		// now, check the strings in comp, removing them from one, so that
		// we can easily check whether every string in one is also in comp
		COMP: for (int i=0; i<comp.length; i++) {
			for (int j=0; j<one.length; j++) {
				if (comp[i].equals(one[j])) {
					one[j] = "";
					continue COMP;
				}
			}
			// only gets here if there was no match to comp[i], so...
			return false;
		}
		// now, check to make sure that everything in one == ""
		for (int i=0; i<one.length; i++) {
			if (one[i].equals("")) { ; }
			else return false;
		}
		// only gets here if everything in one == "", so...
		return true;
	}
	
// end of DSeparationFrame
}