package graph;

import java.util.*;
import java.lang.*;

/**
 * Graph represents a mutable graph of interconnected Node objects. Nodes can be connected
 * via one-way edges, each with their own label. If an edge goes from Node A to Node B, A
 * is the parent while B is the child. All Nodes and edges are not null. No two Nodes can
 * have the same data/name. A Node can be a child and parent of itself. You can change the
 * setting for DEBUGGING to run additional tests to see if your graph is working properly.
 * If parent A has edge C to child B, there cannot be another edge C between them.
 */
public class Graph<E, F> {
    private Map<E, Node<E, F>> nodes;
    private int numNodes;
    private int numEdges;
    public static final boolean DEBUGGING = false; // if set to true, checkRep() runs more tests

    // Abstract Function:
    // Graph is a graph of Nodes. nodes represents all the Nodes in this Graph as well as their
    // name/data. When this is first constructed, there are no Nodes in the Graph so nodes is
    // an empty Map. Nodes and edges must be added in. All the added Nodes are attached to their
    // corresponding names in nodes. The number of Nodes and edges are recorded and can't be
    // below 0. See the Node class for more details.
    //
    // Representation Invariant:
    // nodes != null, numNodes > 0 && numEdges > 0, !nodes.containsKey(null),
    // !nodes.containsValue(null)

    /**
     * Constructs a Graph
     *
     * @spec.modifies this
     * @spec.effects Constructs a new Graph with no starting nodes
     */
    public Graph() {
        nodes = new HashMap<E, Node<E, F>>();
        numNodes = 0;
        numEdges = 0;
        checkRep();
    }

    /**
     * Adds a Node with the given data to the existing graph
     *
     * @param name the data to be given to the new Node
     * @spec.requires The node to be added can't be in the graph already
     * @spec.modifies this
     * @spec.effects adds Node name to the Graph
     * @throws IllegalArgumentException if name is null
     */
    public void addNode(E name) {
        if (name == null) {
            throw new IllegalArgumentException();
        }
        nodes.put(name, new Node<E, F>(name));
        numNodes++;
        checkRep();
    }

    /**
     * Returns the Node with the given data or null if it is not found
     *
     * @param name the data of the desired Node
     * @return the Node with the given name
     * @throws IllegalArgumentException if name is null or name is not in this graph
     */
    public Node<E, F> getNode(E name) {
        checkRep();
        if (name == null || !nodes.containsKey(name)) {
            throw new IllegalArgumentException();
        }
        return nodes.get(name);
    }

    /**
     * Connects node and node2 with an edge pointing from the former to the latter
     *
     * @param node the parent node's data
     * @param node2 the child node's data
     * @param label the name of the edge to be created
     * @spec.requires An edge between node and node2 with data label can't already exist
     * @spec.modifies this, Node of name node
     * @spec.effects Connects node and node2 in this Graph with an edge of data label
     * @throws IllegalArgumentException if node and node2 are not in this, or if any of
     *      the arguments are null
     */
    public void addEdge(E node, E node2, F label) {
        checkRep();
        if (node == null || node2 == null || label == null) {
            throw new IllegalArgumentException();
        }
        // getNode throws an IllegalArgumentException if the nodes aren't in this graph
        Node<E, F> parent = getNode(node);
        Node<E, F> child = getNode(node2);
        Map<F, List<Node<E, F>>> edges = parent.getEdges();
        if (!edges.containsKey(label)) {
            edges.put(label, new ArrayList<Node<E, F>>());
        }
        edges.get(label).add(child);
        numEdges++;
        checkRep();
    }

    /**
     * Disconnects node and node2, removing the associated edge
     *
     * @param node the parent node's data
     * @param node2 the child node's data
     * @param label the data of the edge to be removed
     * @spec.modifies this, Node of name node
     * @spec.effects Disconnects node and node2 in this Graph with edge label
     * @throws IllegalArgumentException if any of the arguments are null or if node or node2 are
     *      not in this graph
     */
    public void removeEdge(E node, E node2, F label) {
        checkRep();
        if (node == null || node2 == null || label == null) {
            throw new IllegalArgumentException();
        }
        // getNode throws an IllegalArgumentException if node is not in this graph
        Map<F, List<Node<E, F>>> edges = getNode(node).getEdges();
        Node child = getNode(node2);
        if (edges.containsKey(label) && edges.get(label).contains(child)) {
            edges.get(label).remove(child);
            if (edges.get(label).isEmpty()) {
                edges.remove(label);
            }
            this.numEdges--;
        }
        checkRep();
    }

    /**
     * Returns a String listing the node's children and the edge label connecting them, or a
     * String indicating that node is not in Graph
     * In the format "children of node: node1(label) node2(label2)"
     *
     * @param node the parent node's data
     * @return A String of node's children
     * @throws IllegalArgumentException if node is null
     */
    public String getChildren(E node) {
        if (node == null) {
            throw new IllegalArgumentException();
        }
        if (!nodes.containsKey(node)) {
            return node + " is not in this graph";
        }
        Node<E, F> parent = getNode(node);
        String result = "children of " + parent.getName() + ":";
        StringBuilder sb = new StringBuilder(result);
        Map<F, List<Node<E, F>>> edges = getNode(node).getEdges();
        Map<String, Node<E, F>> orderedChildren = new TreeMap<String, Node<E, F>>();
        for (List<Node<E, F>> listOfNodes : edges.values()) {
            for (Node<E, F> n : listOfNodes) {
                orderedChildren.put(n.toString(), n);
            }
        }
        for (String child : orderedChildren.keySet()) {
            List<F> edgesTo = parent.getEdgesTo(orderedChildren.get(child).getName());
            Set<String> orderedEdges = new TreeSet<String>();
            for (F edge : edgesTo) {
                orderedEdges.add(edge.toString());
            }
            for (String e : orderedEdges) {
                sb.append(" ");
                sb.append(child);
                sb.append("(");
                sb.append(e);
                sb.append(")");
            }
        }
        return sb.toString();
    }


    /**
     * Returns a set of the specified node's children
     *
     * @param node The parent whose children are desired
     * @return An ordered set of node's children, null if node is not in the graph
     * @throws IllegalArgumentException if node is null
     */
    public Set<Node<E, F>> getChildrenSet(E node) {
        if (node == null) {
            throw new IllegalArgumentException();
        }
        if (!nodes.containsKey(node)) {
            return null;
        }
        Set<Node<E, F>> result = new HashSet<Node<E, F>>();
        Map<F, List<Node<E, F>>> edges = getNode(node).getEdges();
        for (F label : edges.keySet()) {
            List<Node<E, F>> childrenWithLabel = edges.get(label);
            result.addAll(childrenWithLabel);
        }
        return result;
    }

    /**
     * Returns a String listing all the Nodes in this Graph. In the format
     * "graph contains: node1 node2"
     *
     * @return A String listing all Nodes in this Graph
     */
    public String contains() {
        checkRep();
        String contains = "graph contains:";
        Set<E> elements = nodes.keySet();
        Set<String> orderedNodes = new TreeSet<String>();
        for (E element : elements) {
            orderedNodes.add(element.toString());
        }
        StringBuilder sb = new StringBuilder(contains);
        for (String nodeName : orderedNodes) {
            sb.append(" ");
            sb.append(nodeName);
        }
        return sb.toString();
    }

    /**
     * Returns true if node name is in this graph but false if not
     *
     * @param name The node to check for
     * @throws IllegalArgumentException if name is null
     * @return True if the node is in this graph
     */
    public boolean containsNode(E name) {
        if (name == null) {
            throw new IllegalArgumentException();
        }
        return nodes.containsKey(name);
    }

    /**
     * Returns the number of Nodes in this
     *
     * @return Number of nodes
     */
    public int getNumNodes() {
        return numNodes;
    }

    /**
     * Returns the number of edges in this
     *
     * @return Number of edges
     */
    public int getNumEdges() {
        return numEdges;
    }

    /**
     * Clears the Graph
     *
     * @spec.modifies this
     * @spec.effects Disassociates all Nodes in this Graph
     */
    public void clear() {
        nodes.clear();
        numNodes -= numNodes;
        numEdges -= numEdges;
        checkRep();
    }

    /**
     * Returns a Map of the graph's node names and their associated nodes
     *
     * @return Map of node names to nodes
     */
    public Map<E, Node<E, F>> getNodes() {
        return nodes;
    }

    /**
     * Throws an exception if the representation invariant is violated.
     */
    private void checkRep() {
        assert nodes != null;
        assert numNodes >= 0 && numEdges >= 0;
        if (DEBUGGING) {
            if (!nodes.isEmpty()) {
                // containsKey and containsValue threw NullPointerExceptions when checked for
                // null so I looped through everything one-by-one
                for (E name : nodes.keySet()) {
                    assert name != null;
                }
                for (Node<E, F> n : nodes.values()) {
                    assert n != null;
                }
            }
        }
    }
}