package graph;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

public class Node
{
    final private int value;
    /*
     * linked list as opposed to an array list because we treat it as
     * a queue more than an array.
     */
    final private List<Node> children = new LinkedList<Node>();
    public Node(int value)
    {
        this.value = value;
    }
    /**
     * Adds a link to the graph by exploring the children of
     * each possible new child. This is done with simple
     * implementation of Djikstra's algorithm, focusing on
     * finding each edge of the possible new child's children.
     * 
     * It was conscious choice not to throw an exception when the link
     * would make the graph cyclical. Exceptions in java can be expensive,
     * due to the nature of building the stack trace, and cyclical link
     * does not seem to be an exceptional case.
     * 
     * @param newChild
     * @returns boolean true is the link is successful, false if it is not.
     */
    public boolean link(Node newChild) 
    {
        /*
         * Again, a linked list because we are treating it as a queue.
         * No seeking is necessary here.
         */
        List<Node> next = new LinkedList<Node>(newChild.children);
        /*this will cut down on the coefficient runtime
         *by ensuring we do not process the same subtree twice.
         *the graph rules do allow for a Node to link to both a child and a descendant of
         *that child.
         */
        Set<Node> previous = new HashSet<Node>(); 
        while(!next.isEmpty())
        {
            Node current = next.remove(0);
            if (!previous.contains(current))
            {
                if (this.equals(current))
                    return false;
                for (Node child : current.children)
                    next.add(child);
            }
        }
        this.children.add(newChild);
        return true;
    }
    
    /*
     * Both the hash and the equals presume
     * that there will not be duplicate values
     * added to the graph, thus they only
     * consider the value during comparison and hashing. 
     */

    @Override
    public int hashCode()
    {
        final int prime = 31;
        int result = 1;
        result = prime * result + value;
        return result;
    }

    @Override
    public boolean equals(Object obj)
    {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (!(obj instanceof Node))
            return false;
        final Node other = (Node) obj;
        if (value != other.value)
            return false;
        return true;
    }
}