package se.chalmers.cs.gf.graph;

import java.util.*;

/**
 *  A weighted directed graph. Nodes have unique string keys.
 *  The class is parametrized over the types of data stored in the
 *  nodes and edges.
 *
 *  Type parameters: node value type, edge value type
 */
public class Graph<NV,EV> {

        private Map<String,Node> nodeMap;

        public Graph() {
                nodeMap = new HashMap<String,Node>();
        }

        public Node getNode(String key) {
                return nodeMap.get(key);
        }

        public void addNode(String key, NV value) {
                Node n = new Node(key, value);
                nodeMap.put(key, n);
        }

        public void addEdge(String from, String to, double weight, EV value) {
                addEdge(getNode(from), getNode(to), weight, value);
        }

        public void addEdge(Node from, Node to, double weight, EV value) {
                from.addEdge(new Edge(from, to, weight, value));
        }

        public int countNodes() {
                return nodeMap.size();
        }

        /**
         * Gets an unmodifiable collection containing all Nodes. The
         * nodes themselves may be modified.
         */
        public Collection<Node> nodes() {
                return Collections.unmodifiableCollection(nodeMap.values());
        }

        /**
         *  Copy this graph, changing the node values.
         *
         *  @param value The value to give each new node. Note that
         *  all nodes will share the same value object, pass null to avoid
         *  that.
         */
        public <A> Graph<A,EV> copyChangeNodeValues(A value) {
                Graph<A,EV> g = new Graph<A,EV>();
                for (Node n : nodeMap.values())
                        g.addNode(n.getKey(), value);
                for (Node n : nodeMap.values()) {
                        for (Edge e : n.adjacent()) {
                                Graph<A,EV>.Node from = g.getNode(e.getFrom().getKey());
                                Graph<A,EV>.Node to = g.getNode(e.getTo().getKey());
                                g.addEdge(from, to, e.getWeight(), e.getValue());
                        }
                }
                return g;
        }

        public class Node {
                private String key;
                private NV value;
                private List<Edge> edges = new LinkedList<Edge>();

                public Node(String key, NV value) {
                        this.key = key;
                        this.value = value;
                }

                public String getKey() { return key; }
                public NV getValue() { return value; }
                public void setValue(NV value) { this.value = value; }
                public void addEdge(Edge e) { edges.add(e); }
                /**
                 * Gets an unmodifiable list Edges containing all edges from this Node.
                 */
                public List<Edge> adjacent() { return Collections.unmodifiableList(edges); }
        }

        public class Edge {
                private Node from;
                private Node to;
                private double weight;
                private EV value;

                public Edge(Node from, Node to, double weight, EV value) {
                        this.from = from;
                        this.to = to;
                        this.weight = weight;
                        this.value = value;
                }

                public Node getFrom() { return from; }
                public Node getTo() { return to; }
                public double getWeight() { return weight; }
                public EV getValue() { return value; }
        }

}