package nodebox.node;

import java.util.Collection;
import java.util.HashMap;
import java.util.Map;

/**
 * The CycleDetector finds cycles in a Directed Acyclic Graph structure. The detector gets run each time a new
 * connection gets established, or other changes to the network are made that might cause cycles.
 * <p/>
 * Explicit connections can only create new cycles when a new connection is made. Implicit connections (expression
 * dependencies) are a bit trickier: setting or changing an expression might cause a cycle, but also, renaming a node
 * might cause an expression somewhere to evaluate differently, which could cause a cycle.
 * <p/>
 * The constructor excepts a list of vertices, and a dictionary of edges,
 * keyed by the vertex, and the value a list of input, or destination
 * vertices.
 * <p/>
 * The cycle detector keeps its own state and doesn't modify the vertices or edge dict.
 * <p/>
 * A Cycle detector might work on a per-node or per-parameter basis.
 * Per-node means that parameters within different nodes cannot refer back to eachother, e.g.
 * rect1.x -> ellipse1.x and ellipse1.y -> rect1.y would cause a cycle, because on a node level this connection would be
 * cyclic. On a per-parameter basis, the example would not cause a cycle. This implementation works on a per-node basis.
 */
public class CycleDetector {

    private enum Color {
        WHITE, GRAY, BLACK
    }

    private Collection<Connection> connections;
    private Map<Node, Color> marks;

    public CycleDetector(Collection<Connection> connections) {
        this.connections = connections;

    }

    public boolean hasCycles() {
        marks = new HashMap<Node, Color>(connections.size());
        for (Connection c : connections) {
            marks.put(c.getOutputNode(), Color.WHITE);
        }
        for (Connection c : connections) {
            if (marks.get(c.getOutputNode()) == Color.WHITE) {
                if (visit(c.getOutputNode())) {
                    return true;
                }
            }
        }

        return false;
    }

    private boolean visit(Node node) {
        marks.put(node, Color.GRAY);
        for (Connection c : connections) {
            Node outputNode = c.getOutputNode();
            // Only use the ones I'm the input for (downstream connections for this node).
            if (c.getInputNode() != node) continue;
            if (!marks.containsKey(outputNode)) continue;
            if (marks.get(outputNode) == Color.GRAY) {
                return true;
            } else if (marks.get(outputNode) == Color.WHITE) {
                if (visit(outputNode)) {
                    return true;
                }
            } else {
                // Visiting black vertices is okay.
            }
        }
        marks.put(node, Color.BLACK);
        return false;
    }

}