/*
 * Copyright (c) 2003, the JUNG Project and the Regents of the University of
 * California All rights reserved.
 * 
 * This software is open-source under the BSD license; see either "license.txt"
 * or http://jung.sourceforge.net/license.txt for a description.
 */
package edu.uci.ics.jung.graph.filters;

import java.util.Iterator;
import java.util.Set;

import edu.uci.ics.jung.exceptions.FatalException;
import edu.uci.ics.jung.graph.*;
import edu.uci.ics.jung.utils.UserData;

/**
 * This class represents an unassembled graph. It does not implement Graph. It
 * represents the collection of vertices and edges that were generated by the
 * filter. VERTICES that are members of this DO NOT fulfill the vertex contract,
 * as they claim their graph is the source graph.
 * <p>
 * The filter process looks like this: <br>
 * 
 * <pre>
 * 
 *  		SOURCE GRAPH - [ Filter1 ] - UnassembledGraph - [Filter2] - UnassembledGraph  - [Assemble] - Graph
 *  
 * </pre>
 * 
 * @author danyelf
 */
public class UnassembledGraph {

    protected String name;

    /**
     * Holds a reference to the filter that generated this UnassembledGraph
     */
    protected Filter filter;

    // CONSTRAINT: all vertices in these sets are members of OriginalGraph
    /**
     * Holds a reference to the filter that generated this UnassembledGraph
     */
    protected Set vertexSet;

    protected Set edgeSet;

    // If there was a graph before this one, this is it
    protected UnassembledGraph previousGraph;

    // This is the last real graph in the sequence
    protected Graph originalGraph;

    public UnassembledGraph(Filter f, Set vertices, Set edges, Graph original) {
        this.filter = f;
        this.vertexSet = vertices;
        this.edgeSet = edges;
        this.previousGraph = null;
        this.originalGraph = original;
        this.name = filter.getName();
        checkData();
    }

    /**
     * A constructor that uses non-Filters (for example, GraphCluterers) to
     * build themselves.
     * 
     * @param name
     *            A name to refer to the caller (e.g.
     *            "EdgeBetweenessCluster(3)")
     * @param vertices
     *            The set of vertices in this UnassembledGraph
     * @param edges
     *            The set of edges in this UnassembledGraph
     * @param original
     *            The graph from which this data comes
     */
    public UnassembledGraph(String name, Set vertices, Set edges, Graph original) {
        this.filter = null;
        this.vertexSet = vertices;
        this.edgeSet = edges;
        this.previousGraph = null;
        this.originalGraph = original;
        this.name = name;
        checkData();
    }

    public UnassembledGraph(Filter f, Set vertices, Set edges,
            UnassembledGraph previous) {
        this.filter = f;
        this.vertexSet = vertices;
        this.edgeSet = edges;
        this.previousGraph = previous;
        this.originalGraph = previous.getOriginalGraph();
        this.name = filter.getName();
        checkData();
    }

    /**
     * Returns the name of the filter that generated this UnassembledGraph.
     */
    public String getFilterName() {
        String rv = name;
        if (previousGraph != null) {
            rv += ":" + previousGraph.getFilterName();
        }
        return rv;
    }

    private void checkData() {
        for (Iterator iter = vertexSet.iterator(); iter.hasNext();) {
            Vertex e = (Vertex) iter.next();
            if (e.getGraph() != originalGraph)
                    throw new FatalException("Vertex not in original");
        }

        for (Iterator iter = edgeSet.iterator(); iter.hasNext();) {
            Edge e = (Edge) iter.next();
            if (e.getGraph() != originalGraph)
                    throw new FatalException("Edge not in original");
        }
    }

    /**
     * Returns the original graph that was subsetted for this UnsassembledGraph.
     */
    public Graph getOriginalGraph() {
        return originalGraph;
    }

    /**
     * Returns the set of vertices (from <tt>getOriginalGraph()</tt>) that
     * passed the filter.
     */
    public Set getUntouchedVertices() {
        return vertexSet;
    }

    /**
     * Returns the set of edges (from <tt>getOriginalGraph()</tt>) that
     * passed the filter.
     */
    public Set getUntouchedEdges() {
        return edgeSet;
    }

    public String toString() {
        if (previousGraph == null) {
            return "UNASSEMBLED" + "<" + originalGraph + ">";
        } else {
            return "UNASSEMBLED" + "<" + previousGraph + ">";
        }
    }

    /**
     * Constructs a new graph based on the source graph. Assumes that edges
     * should only be copied if they contain all the original edge's vertices;
     * all vertices that pass the filter are copied.
     * <p>
     * Here's the general theory:
     * <ul>
     * <li>A Graph object of the appropriate type can be obtained by calling
     * <tt>{@link edu.uci.ics.jung.graph.ArchetypeGraph#newInstance() Graph.newInstance()}</tt>
     * on the original.</li>
     * <li>Then, the graph is populated with all vertices that the filters have
     * passed (that is, the vertices in
     * <tt>{@link #getUntouchedVertices() getUntouchedVertices()}</tt>.
     * Vertices are copied in with
     * <tt>{@link edu.uci.ics.jung.graph.ArchetypeVertex#copy( ArchetypeGraph ) copy(Graph)}</tt>.
     * </li>
     * <li>Last, the graph is populated with all edges that have both passed,
     * and have both ends in vertices that passed.</li>
     * </ul>
     */
    public Graph assemble(boolean shouldPreserveRecord) {
        // constructs AG from the various edges
        Graph subgraph = (Graph) originalGraph.newInstance();

        if (shouldPreserveRecord) {
            subgraph.addUserDatum(GraphAssemblyRecord.FILTER_GRAPH_KEY,
                    new GraphAssemblyRecord(this), UserData.REMOVE);
        }

        Set localVertices = getUntouchedVertices();

        // now, we scoop up vertices
        for (Iterator iter = localVertices.iterator(); iter.hasNext();) {
            ArchetypeVertex newV = (ArchetypeVertex) iter.next();
            newV.copy(subgraph);
        }

        // and only the edges that actually match
        for (Iterator iter = getUntouchedEdges().iterator(); iter.hasNext();) {
            ArchetypeEdge newE = (ArchetypeEdge) iter.next();
            if (localVertices.containsAll(newE.getIncidentVertices())) {
                newE.copy(subgraph);
            }
        }

        return subgraph;
    }

    public Graph assemble() {
        return assemble(false);
    }

}