/*
 * Copyright 2005-2010 the original author or authors.
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 * 
 *      http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */ 
package org.wamblee.system.graph;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

/**
 * Represents a graph consisting of nodes and edges.
 * 
 * @author Erik Brakkee
 */
public class Graph {
    private List<Node> nodes;

    private List<Edge> edges;

    /**
     * Constructs the graph.
     */
    public Graph() {
        nodes = new ArrayList<Node>();
        edges = new ArrayList<Edge>();
    }

    /**
     * Adds a node.
     * 
     * @param aNode
     *            Node to add.
     * 
     * @throws IllegalArgumentException
     *             In case the node already exists. Node equality is checked
     *             using <code>equals</code>.
     */
    public void addNode(Node aNode) {
        if (nodes.contains(aNode)) {
            throw new IllegalArgumentException("Node '" + aNode.getName() +
                "' already exists");
        }

        nodes.add(aNode);
    }

    /**
     * Finds a node with the given name.
     * 
     * @param aName
     *            Node name.
     * 
     * @return Node or null if not found.
     */
    public Node findNode(String aName) {
        for (Node node : nodes) {
            if (node.getName().equals(aName)) {
                return node;
            }
        }

        return null;
    }

    /**
     * Removes a node.
     * 
     * @param aNode
     *            Node to remove.
     * 
     * @return True iff the node was removed.
     * 
     * @throws IllegalArgumentException
     *             In case there are edges of which the node is a part.
     */
    public boolean removeNode(Node aNode) {
        if (!findOutgoing(aNode).isEmpty() || !findIncoming(aNode).isEmpty()) {
            throw new IllegalArgumentException("Cannot remove node '" +
                aNode.getName() +
                "' because it is connected to one or more edges");
        }

        return nodes.remove(aNode);
    }

    /**
     * Adds a list of nodes.
     * 
     * @param aNodes
     *            Nodes to add.
     * 
     * @see #addNode(Node)
     */
    public void addNodes(List<Node> aNodes) {
        for (Node node : aNodes) {
            addNode(node);
        }
    }

    /**
     * Adds an edge.
     * 
     * @param aEdge
     *            Edge to add.
     * 
     * @throws IllegalArgumentException
     *             In case one of the nodes of the edges is not part of the
     *             graph or if the same edge (as determined by
     *             {@link #equals(Object)} is already a part of the graph.
     */
    public void addEdge(Edge aEdge) {
        if (edges.contains(aEdge)) {
            throw new IllegalArgumentException("Edge '" + aEdge +
                "' already exists");
        }

        if (!nodes.contains(aEdge.getFrom())) {
            throw new IllegalArgumentException("From node '" + aEdge.getFrom() +
                "' from edge '" + aEdge + "' is not part of the graph");
        }

        if (!nodes.contains(aEdge.getTo())) {
            throw new IllegalArgumentException("To node '" + aEdge.getTo() +
                "' from edge '" + aEdge + "' is not part of the graph");
        }

        edges.add(aEdge);
    }

    /**
     * Removes an edge.
     * 
     * @param aEdge
     *            Edge to remove.
     * 
     * @return True if the edge was removed.
     */
    public boolean removeEdge(Edge aEdge) {
        return edges.remove(aEdge);
    }

    /**
     * Adds a number of edges.
     * 
     * @param aEdges
     *            Edges to add.
     */
    public void addEdges(List<Edge> aEdges) {
        for (Edge edge : aEdges) {
            addEdge(edge);
        }
    }

    /**
     * Gets the nodes.
     * 
     * @return Copy of the list of nodes of the graph.
     */
    public List<Node> getNodes() {
        return new ArrayList<Node>(nodes);
    }

    /**
     * Gets the edges.
     * 
     * @return Copy of the list of edges of the graph.
     */
    public List<Edge> getEdges() {
        return new ArrayList<Edge>(edges);
    }

    /**
     * Extends the graph with edges using an edge factory. All combinations of
     * nodes are passed to the factory which creates additional edges.
     * 
     * @param aFactory
     *            Edge factory.
     */
    public void extend(EdgeFactory aFactory) {
        for (Node from : nodes) {
            for (Node to : nodes) {
                edges.addAll(aFactory.create(from, to));
            }
        }
    }

    /**
     * Applies a filter to the graph for removing elements.
     * 
     * @param aFilter
     *            Filter to apply.
     */
    public void applyFilter(EdgeFilter aFilter) {
        for (Iterator<Edge> edge = edges.iterator(); edge.hasNext();) {
            if (aFilter.isViolated(edge.next())) {
                edge.remove();
            }
        }
    }

    /**
     * Finds all outgoing edges of a node. More specifically, finds all edges
     * <code>e</code> for which <code>e.getFrom().getName() =
     * aNode.getName()</code>.
     * 
     * @param aNode
     *            Node for which to find outgoing edges.
     * 
     * @return List of outgoing edges.
     */
    public List<Edge> findOutgoing(Node aNode) {
        List<Edge> result = new ArrayList<Edge>();

        for (Edge edge : edges) {
            if (edge.getFrom().getName().equals(aNode.getName())) {
                result.add(edge);
            }
        }

        return result;
    }

    /**
     * Finds all incoming edges of a node. More specifically, finds all edges
     * <code>e</code> for which <code>e.getTo().getName() =
     * aNode.getName()</code>.
     * 
     * @param aNode
     *            Node for which to find incoming edges.
     * 
     * @return List of incoming edges.
     */
    public List<Edge> findIncoming(Node aNode) {
        List<Edge> result = new ArrayList<Edge>();

        for (Edge edge : edges) {
            if (edge.getTo().getName().equals(aNode.getName())) {
                result.add(edge);
            }
        }

        return result;
    }

    /**
     * Implements a visitor design pattern. This loops over all nodes and all
     * edges and invokes the appropriate visit methods on the visitor.
     * 
     * @param aVisitor
     *            Visitor.
     */
    public void accept(Visitor aVisitor) {
        List<Node> allNodes = getNodes(); // copy to make sure the visitor can
        // modify the
        // list of nodes as part of the loop.

        List<Edge> allEdges = getEdges(); // copy ..... (see above).

        for (Node node : allNodes) {
            aVisitor.visitNode(node);
        }

        for (Edge edge : allEdges) {
            aVisitor.visitEdge(edge);
        }
    }
}