import java.util.*;

import edu.mit.six825.bn.functiontable.*;
import edu.mit.six825.bn.bayesnet.*;

/**
 * An abstraction for representing BN-structure-search moves
 *
 * @author nocturne
 */
public class BNOp {
    public MoveType move;
    public BayesNetNode from;
    public BayesNetNode to;

    private boolean USE_SCORE_CACHE = true;
    private Double score = null;
    private int hashval;

    /*
     * Sole constructor.
     */
    public BNOp(MoveType _move, BayesNetNode _from, BayesNetNode _to) {
	move = _move;
	from = _from;
	to   = _to;

	hashval = (31*31*move.ord + 31*to.var.name.hashCode()
		   + from.var.name.hashCode());
    }

    /* Interfaces for caching a score in the BNOp object */
    public boolean hasScoreCache() {
	return(score != null);
    }
    public void setScoreCache(double _score) {
	if (USE_SCORE_CACHE) {score = new Double(_score); }
    }
    public double getScoreCache() {
	if (score == null) {
	    throw new IllegalArgumentException("Retrieved uncached score");
	}
	return (score.doubleValue());
    }

    public String toString() {
	return(move + " edge from " + from.var + " to " + to.var);
    }

    public int hashCode() {
	return (hashval);
    }

    public boolean equals(final Object obj) {
	if (obj instanceof BNOp) {
	    BNOp o = (BNOp) obj;
	    if ((move == o.move)
		&& from.var.toString().equals( o.from.var.toString() )
		&&   to.var.toString().equals( o.to.var.toString()   ) )
		{
		    return (true);
		}
	}
	return (false);
  }
	

    /**
     * Is this a valid structure-search move which also does not
     * create any directed cycles?
     */
     public boolean isValid() {
	 if (from.var.toString().equals(to.var.toString())) {
	     // can't have a move from a node to itself.
	     return false;
	 }

	if (move == MoveType.ADD) {
	    // [From --> To] valid so long as it doesn't already exist and
	    // so long as To isn't an ancestor of From
	    return ((!EdgeFromTo(from, to)) &&
		    (!IsAncestorOf(to, from)));
	} else if (move == MoveType.DELETE) {
	    // Deletions valid if the edge exists
	    return(EdgeFromTo(from, to));
	} else if (move == MoveType.REVERSE) {
	    /*    C
	     *   ^ \
	     *  /   v
	     * A --> B
	     * In the above graph, reverse(a, b) is invalid because it
	     * creates a directed cycle
	     */

	    // I *think* Reverse is valid if the edge already exists
	    // and the parent is not also a grand-ancestor of the
	    // child. This criterion is clearly necessary, but I'm not
	    // certain it's also sufficient.
	    return (EdgeFromTo(from, to) && !IsGrandAncestorOf(from, to));
	} else {
	    throw new IllegalArgumentException("Unknown move type " + move);
	}
    }

    /**
     * Random syntactic-sugar utility function.
     */
    public static boolean EdgeFromTo (BayesNetNode from, BayesNetNode to) {
	return(to.parents.contains(from));
    }

    /**
     * Regardless of whether Elder is a direct parent of Youth, is
     * Elder an indirect ancestor of Youth? (Expressed differently, is
     * there a directed route from Elder to Youth which contains more
     * than one edge?)
     * 
     * e.g. in B-->C-->D-->E:
     *
     *  B is a grandAncestor of E regardless of whether B is also a
     *  parent of E
     *
     *  B is NOT a grandAncestor of C (unless there are other chains
     *  of ancestry not show in the above graph)
     */
    public static boolean IsGrandAncestorOf (BayesNetNode elder,
					     BayesNetNode youth) {
	for (Iterator it = youth.parents.iterator(); it.hasNext();) {
	    if (IsAncestorOf(elder, (BayesNetNode)it.next())) {
		return (true);
	    }
	}
	return (false);
    }

    /**
     * Is Elder an ancestor of Youth?
     */
    public static boolean IsAncestorOf (BayesNetNode elder,
					BayesNetNode youth) {
	if (youth.parents.contains(elder)) {
	    return (true);
	} else {
	    return (IsGrandAncestorOf(elder, youth));
	}
    }

    /**
     * An iterator class which, given a BayesNet, will iterate over
     * all the valid BNOps which could be applied to the current
     * configuration of the BayesNet.
     *
     * Instantiation of this iterator has a moderate amount of
     * overhead, as it begins by enumerating all legal BNOps and then
     * storing them all in an array. As such, use of this iterator is
     * only appropriate when one desires to exhaustively try all
     * possible BNOps. If one merely needs a fixed number of random
     * BNOps, BNStructure.getRandomOp() is more appropriate.
     */
    public static class BNOpRandIterator implements Iterator {

	private BNOp[] _randomOrdering;
	private int    _nextOp;

	public BNOpRandIterator(BayesNet bn, Random rng) {

	    List ops = (List) new ArrayList();

	    Iterator opIt = (Iterator) new BNOp.BNOpIterator(bn);
	    for ( ; opIt.hasNext() ; ) {
		ops.add(opIt.next());
	    }

	    _randomOrdering = new BNOp[ops.size()];
	    for (int i=0; i < _randomOrdering.length; i++) {
		BNOp nextOp = (BNOp) ops.remove(rng.nextInt(ops.size()));
		_randomOrdering[i] =  nextOp;
	    }
	}

	public Object next() {
	    return(_randomOrdering[_nextOp++]);
	}

	public boolean hasNext() {
	    return(_nextOp < _randomOrdering.length);
	}

	public void remove() {
	    throw new UnsupportedOperationException("Meaningless.");
	}
    }

    /**
     * An iterator class which, given a BayesNet, will iterate over
     * all the valid BNOps which could be applied to the current
     * configuration of that BayesNet.
     *
     * Note, this Iterator tests operator validity on the fly.
     * Therefore, if you create an BNOpIterator object X and then
     * modify the structure of the BayesNet in question, be sure that
     * you unroll those modifications before applying methods to X.
     * (I.e. the BayesNet should be returned to the same structure it
     * had when X was created; if not, you will get inconsistent
     * results.)
     */
    public static class BNOpIterator implements Iterator {

	// A deterministically sorted array of the nodes we're using
	private BayesNetNode[] _nodes;

	/**
	 * You can think of this iterator as cycling through
	 * coordinates in a 3-D box, whose axes correspond to "from
	 * node", "to node", and "move type". This is the number of
	 * the next point we haven't tested for validity.
	 */
	private int  _nextUntestedPoint = 0;

	/**
	 * This is the next valid Operation to be returned. If it's
	 * set to null, either we haven't gone looking for one yet,
	 * or we've run out of points to test.
	 */
	private BNOp _nextOp = null;

	/**
	 * The ordinal index of the last point we will look at.
	 */
	private int  _maxPoint;

	public BNOpIterator(BayesNet bn) {
	    List tmplist = bn.nodes.getNodesWithTopologicalOrdering();
	    _nodes = (BayesNetNode[]) tmplist.toArray(new BayesNetNode[0]);

	    _maxPoint = (_nodes.length)*(_nodes.length)*(MoveType.size());
	}

	public Object next() {
	    BNOp op = _findNext();
	    if (op != null) {
		_nextOp = null; // Move on to the next op
		return ((Object) op);
	    } else {
		throw new NoSuchElementException("No next op");
	    }
	}

	public boolean hasNext() {
	    BNOp op = _findNext();
	    if (op != null) {
		return true;
	    } else {
		return false;
	    }
	}

	public void remove() {
	    throw new UnsupportedOperationException("Meaningless.");
	}



	private BNOp _findNext() {
	    if (_nextOp != null) {
		return _nextOp;
	    } else if (_nextUntestedPoint >= _maxPoint) {
		return null;
	    } else {
		for (int p = _nextUntestedPoint ; p < _maxPoint; p++) {
		    BNOp candidateOp = _pointToOp(p);
		    if (candidateOp.isValid()) {
			_nextOp = candidateOp;
			_nextUntestedPoint = p+1;
			return(_nextOp);
		    }
		}
		// If we reach here, there is no next point
		_nextOp = null;
		_nextUntestedPoint = _maxPoint;
		return null;
	    }
	}

	private BNOp _pointToOp(int point) {
	    /*
	     * point = fromnum*(# nodes)*(# moves)
	     *                   + tonum*(# moves)
	     *                           + movenum
	     */
	    int movenum, fromnum, tonum;

	    int decomp = point;

	    fromnum = decomp / (_nodes.length*MoveType.size());
	    decomp  = decomp - fromnum*(_nodes.length*MoveType.size());

	    tonum   = decomp / MoveType.size();
	    decomp  = decomp - tonum*MoveType.size();

	    movenum = decomp;

	    return(new BNOp(MoveType.get(movenum),
			    _nodes[fromnum],
			    _nodes[tonum]));
	}
    }

}