/**
 * Copyright (c) 2005 by Kevin Bierhoff
 */
package edu.cmu.cs.l3.trace;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Set;
import java.util.Vector;

import java.io.Serializable;
import java.io.IOException;

import edu.cmu.cs.l3.canon.Block;
import edu.cmu.cs.l3.canon.DominatorTree;
import edu.cmu.cs.l3.canon.Trace;
import edu.cmu.cs.l3.temp.Label;
import edu.cmu.cs.l3.tree.IRJump;
import edu.cmu.cs.l3.tree.IRLabel;

/**
 * Implements a graph for the purposes of discriminating paths of a function. It follows the presentation
 * in a T. Ball & J. Larus paper on "efficient path profiling". One distinctive feature of this graph is
 * that multiple edges can connect the same pair of vertexes. In particular, loops are replaced with
 * dummy edges connecting function entry to loop header and loop end to function exit. 
 * 
 * @author Kevin
 * @see PathGraphVertex
 * @see PathGraphEdge
 */
public class PathGraph implements Serializable {
	
	/** The blocks the graph is based on */
	private Vector blocks;
	/** Dominator tree to find loops */
	private DominatorTree domTree;
	
	/** Vertices in identical order to {@link #blocks}. */
	private PathGraphVertex vertices[];
	/** Edges (set of {@link PathGraphEdge}). */
	private HashSet edges;
	/** Keep track of back edges in loops (set of {@link BackEdge}). */
	private HashSet backEdges;

	/**
	 * Initializes the path graph fully.
	 * @param blocks
	 */
	public PathGraph(Vector blocks) {
		super();
		this.blocks = blocks;
		this.domTree = new DominatorTree(blocks);
		initializeGraph();
		computeEdgeValues();
		findSpanningTree();
		computeEdgeIncrements();
		//System.out.println(this.toString());
		/*for(int i = 0; i < getPathCount(); i++) {
			Trace t = getPath(i);
			System.out.print(i + " :");
			for(Iterator it = t.getBlocks().iterator(); it.hasNext(); ) {
				System.out.print(" " + ((Block) it.next()).getLabel());
			}
			System.out.println();
		}*/
	}
	
	public PathGraph(Vector blocks, boolean incremental) {
		super();
		this.blocks = blocks;
		this.domTree = new DominatorTree(blocks);

		if(incremental) {
			initializeIncrementalGraph();
		}
		else {
			initializeGraph();
		}
		computeEdgeValues();
		findSpanningTree();
		computeEdgeIncrements();
	}
	
	/** 
	 * Initialize the graph structure by populating vertex and edge fields. 
	 * Initializes vertices and edges with {@link #initializeVertex(int)}.
	 * Adds cycle edge from exit to entry vertex. 
	 */
	protected void initializeGraph() {
		vertices = new PathGraphVertex[domTree.getBlockCount()+1];
		edges = new HashSet();
		backEdges = new HashSet();
		
		Block exitBlock = new Block(new IRLabel(new Label("return")));
		PathGraphVertex exitVertex = new PathGraphVertex(this, exitBlock);
		vertices[blocks.size()] = exitVertex;
		
		initializeVertex(0);
		
		// add cycle edge from EXIT to ENTRY node
		PathGraphEdge cycleEdge = createDummyEdge(getExitVertex(), getEntryVertex());
		edges.add(cycleEdge);
	}
	
	/**
	 * Initialize or find vertex for given block. Follows the Ball & Larus paper (section 4) 
	 * in handling loops with two dummy edges. Also replaces jumps to unknown blocks with 
	 * jumps to the synthetic exit vertex (simplifies handling of explicit returns).
	 * @param blockIndex
	 * @return Vertex representing given block.
	 */
	private PathGraphVertex initializeVertex(int blockIndex) {
		// block already processed
		if(vertices[blockIndex] != null)
			return vertices[blockIndex];
		
		// get the block
		Block b = domTree.getBlock(blockIndex);
		
		// this block has not beed initialized --> create vertex for it
		PathGraphVertex vertex = new PathGraphVertex(this, b);
		vertices[blockIndex] = vertex;
		
		// create edges for control flow from this block
		Set succs = domTree.getSuccs(b);
		for(Iterator it = succs.iterator(); it.hasNext(); ) {
			int succIndex = ((Integer) it.next()).intValue();
			if(domTree.dominates(succIndex, blockIndex)) {
				if(succIndex == blockIndex) {
					System.out.println("Self-loop ignored!");
					continue;
				}
				// handle back edges
				PathGraphVertex succVertex = initializeVertex(succIndex);
				PathGraphVertex entryVertex = initializeVertex(0);
				// dummy edge from entry to back edge target
				PathGraphEdge dummyIn = createDummyEdge(entryVertex, succVertex);
				edges.add(dummyIn);
				// dummy edge from back edge origin to exit (exit is guaranteed to exist)
				PathGraphEdge dummyOut = createDummyEdge(vertex, getExitVertex()); 
				edges.add(dummyOut);
				// take note of back edge
				backEdges.add(new BackEdge(this, vertex, succVertex, dummyIn, dummyOut));
			}
			else {
				// not a back edge
				PathGraphVertex succVertex = initializeVertex(succIndex);
				edges.add(createProgramEdge(vertex, succVertex));
			}
		}
		
		// check for returns (= unconditional jumps to unknown labels)
		if(b.getJump() instanceof IRJump && domTree.getBlockIndex(((IRJump) b.getJump()).getTarget().toString()) < 0) {
			edges.add(createExitEdge(vertex));
		}
		
		return vertex;
	}
	
	/**
	 * Implementation of an "algorithm for assigning values to edges in a DAG" from fig. 5
	 * of Ball & Larus. Rejects functions with more than 2 ^ 30 paths outright as they will cause
	 * out of memory errors at runtime.
	 */
	protected void computeEdgeValues() {
		// reset edge values
		for(int i = 0; i < vertices.length; i++) {
			if(vertices[i] != null)
				vertices[i].setNumPaths(-1);
		}
		computeEdgeValues(getEntryVertex());
	}
	
	/**
	 * Computes vertex and edge values in reverse topological order of vertices.
	 * @param cur
	 * @return The value of the visited vertex.
	 */
	private long computeEdgeValues(PathGraphVertex cur) {
		if(cur.getNumPaths() < 0) {
			// vertex has no value yet
			if(cur.isLeaf()) {
				cur.setNumPaths(1);
			}
			else {
				long numPaths = 0;
				for(Iterator outgoing = cur.getOutgoingEdges().iterator(); outgoing.hasNext(); ) {
					PathGraphEdge curEdge = (PathGraphEdge) outgoing.next();
					if(curEdge.isCycleEdge())
						// this shouldn't happen
						continue;
					curEdge.setValue(numPaths);
					long edgePaths = computeEdgeValues(curEdge.getTarget());
					numPaths += edgePaths;
	
					// 2^32 paths and more will incur problems....
					if(numPaths > ((long) Integer.MAX_VALUE) * 2) {
						throw new RuntimeException("Too many paths.");
					}
				}
				cur.setNumPaths(numPaths);
			}
		}
		return cur.getNumPaths();
	}
	
	/**
	 * Implementation of an "algorithm for assigning values to edges in a DAG" from fig. 5
	 * of Ball & Larus. Rejects functions with more than 2 ^ 30 paths outright as they will cause
	 * out of memory errors at runtime.
	 *
	 *
	 * Old implementation with reverseTopologicalVertices list.
	protected void computeEdgeValues() {
		for(Iterator it = reverseTopologicalVertices.iterator(); it.hasNext(); ) {
			PathGraphVertex cur = (PathGraphVertex) it.next();
			if(cur.isLeaf()) {
				cur.setNumPaths(1);
			}
			else {
				int numPaths = 0;
				for(Iterator outgoing = cur.getOutgoingEdges().iterator(); outgoing.hasNext(); ) {
					PathGraphEdge curEdge = (PathGraphEdge) outgoing.next();
					if(curEdge == cycleEdge)
						continue;
					curEdge.setValue(numPaths);
					int edgePaths = curEdge.getTarget().getNumPaths();
					// 2^30 paths and more will run out of memory and can also generate negative numPath values
					if(numPaths > Integer.MAX_VALUE / 2 || edgePaths > Integer.MAX_VALUE / 2) {
						throw new RuntimeException("Too many paths.");
					}
					numPaths += edgePaths;
					
				}
				cur.setNumPaths(numPaths);
			}
			
		}
	}*/
	
	/**
	 * Implements the Prim-Dijkstra algorithm for finding a spanning tree.
	 */
	protected void findSpanningTree() {
		// this implementation assumes a connected graph
		
		// reset the spanning flag for all edges
		for(Iterator it = edges.iterator(); it.hasNext(); ) {
			PathGraphEdge e = (PathGraphEdge) it.next();
			e.setSpanning(false);
		}
		
		// bookkeeping
		HashSet covered = new HashSet();
		LinkedList worklist = new LinkedList();
		//PathGraphVertex v = (PathGraphVertex) reverseTopologicalVertices.get(0);
		PathGraphVertex v = getExitVertex();
		covered.add(v);
		worklist.addLast(v);
		while(worklist.isEmpty() == false) {
			v = (PathGraphVertex) worklist.removeFirst();
			for(Iterator eit = v.getOutgoingEdges().iterator(); eit.hasNext(); ) {
				PathGraphEdge curEdge = (PathGraphEdge) eit.next();
				PathGraphVertex otherEnd = curEdge.getTarget();
				if(covered.contains(otherEnd)) 
					continue;
				curEdge.setSpanning(true);
				covered.add(otherEnd);
				worklist.addLast(otherEnd);
			}
			for(Iterator it = v.getIncomingEdges().iterator(); it.hasNext(); ) {
				PathGraphEdge curEdge = (PathGraphEdge) it.next();
				PathGraphVertex otherEnd = curEdge.getOrigin();
				if(covered.contains(otherEnd)) 
					continue;
				curEdge.setSpanning(true);
				covered.add(otherEnd);
				worklist.addLast(otherEnd);
			}
		}
//		if(covered.size() < vertices.length) {
//			System.out.println("Spanning tree covers only " + covered.size() +
//					" out of " + vertices.length + " vertices.");
//		}
	}
	
	/**
	 * Computes increments of chord edges according to Ball & Larus section 3.3.
	 */
	protected void computeEdgeIncrements() {
		for(Iterator it = edges.iterator(); it.hasNext(); ) {
			PathGraphEdge cur = (PathGraphEdge) it.next();
			if(cur.isSpanning()) {
				// edges that are part of the spanning tree are not instrumented
				cur.setIncrement(0);
			}
			else {
				// chord edges are instrumented in such a way that spanning tree edges
				// need not be instrumented (by accumulating any values of spanning tree
				// edges into chord increments)
				Integer increment = spanningPath(cur.getTarget(), cur.getOrigin(), null);
				if(increment == null) {
					System.out.println("Couldn't find path through spanning tree around " + cur);
					cur.setIncrement(0);
				}
				else {
					cur.setIncrement(cur.getValue() + increment.intValue());
				}
			}
		}
	}
	
	
	/**
	 * Computes, if any, the sum of edge values passed on the way from <code>from<code> to <code>to</code>
	 * in the spanning tree.
	 * @param from
	 * @param to
	 * @param incoming The edge taken in the spanning tree to get to <code>from</code>. This edge is
	 * ignored in trying to find a path to <code>to</code>.
	 * @return Sum of the values of the passed edges or <code>null</code> if no path was found.
	 */
	private Integer spanningPath(PathGraphVertex from, PathGraphVertex to, PathGraphEdge incoming) {
		if(from.equals(to))
			return new Integer(0);
		for(Iterator it = from.getOutgoingEdges().iterator(); it.hasNext(); ) {
			PathGraphEdge cur = (PathGraphEdge) it.next();
			if(cur.isSpanning() && ! cur.equals(incoming)) {
				Integer val = spanningPath(cur.getTarget(), to, cur);
				if(val != null) return new Integer(cur.getValue() + val.intValue());
			}
		}
		for(Iterator it = from.getIncomingEdges().iterator(); it.hasNext(); ) {
			PathGraphEdge cur = (PathGraphEdge) it.next();
			if(cur.isSpanning() && ! cur.equals(incoming)) {
				Integer val = spanningPath(cur.getOrigin(), to, cur);
				if(val != null) return new Integer(val.intValue() - cur.getValue());
			}
		}
		return null;
	}

	
	protected PathGraphEdge createProgramEdge(PathGraphVertex origin, PathGraphVertex target) {
		return new PathGraphEdge(this, origin, target, true);
	}
	
	protected PathGraphEdge createDummyEdge(PathGraphVertex origin, PathGraphVertex target) {
		return new PathGraphEdge(this, origin, target, false);
	}
	
	protected PathGraphEdge createExitEdge(PathGraphVertex origin) {
		return createProgramEdge(origin, getExitVertex());
	}
	
	public Trace getPath(int pathValue) {
	    //System.out.println("pathgraph.getpath, entry vertex is " + getEntryVertex() + " and exit vertex is " + getExitVertex());
		PathGraphVertex v = getEntryVertex();
		Trace result = new Trace();
		//result.addBlock(getEntryVertex().getBlock());
		while(v != getExitVertex()) {
		    //System.out.println("checkpoint 1");
			PathGraphEdge maxEdge = null;
			int maxValue = -1;
			for(Iterator it = v.getOutgoingEdges().iterator(); it.hasNext(); ) {
				PathGraphEdge cur = (PathGraphEdge) it.next();
				if(cur.getValue() <= pathValue && maxValue < cur.getValue()) {
					maxEdge = cur;
					maxValue = cur.getValue();
				}
			}
			if(maxValue < 0) return result;
			
			// let path start at entry only if first edge is program edge
			// otherwise path will start with loop header (first edge's target)
			//System.out.println("v: " + v);
			//System.err.println("max edge: " + maxEdge.isProgramEdge() + " and entry vertex " + (v == getEntryVertex()));
			if(v != getEntryVertex() || maxEdge.isProgramEdge())
				result.addBlock(v.getBlock());

			v = maxEdge.getTarget();
			pathValue -= maxValue;
			
			//System.out.println("new v: " + v);
			// add the next node unless this is a dummy edge from loop to exit --> let path end at end of loop
			//System.err.println("max edge: " + maxEdge.isProgramEdge() + " and EXIT vertex " + (v == getExitVertex()));
			//if(maxEdge.isProgramEdge() || v != getExitVertex())
				//result.addBlock(v.getBlock());
		}
		return result;
	}
	
	public boolean isComplete(int pathNumber) {
		ArrayList path = getVerticesOnPath(pathNumber);
		return path.get(path.size() - 1) == getExitVertex();
	}
	
	/** 
	 * Initialize the graph structure by populating vertex and edge fields. 
	 * Initializes vertices and edges with {@link #initializeVertex(int)}.
	 * Adds cycle edge from exit to entry vertex. 
	 */
	protected void initializeIncrementalGraph() {
		vertices = new PathGraphVertex[domTree.getBlockCount()+1];
		edges = new HashSet();
		backEdges = new HashSet();
		
		// initialize vertices for all blocks
		for(int i = 0; i < domTree.getBlockCount(); i++) {
			vertices[i] = new PathGraphVertex(this, domTree.getBlock(i));
		}
		
		// create pseudo EXIT block and vertex
		Block exitBlock = new Block(new IRLabel(new Label("return")));
		PathGraphVertex exitVertex = new PathGraphVertex(this, exitBlock);
		vertices[blocks.size()] = exitVertex;
		
		// create cycle edge from EXIT to ENTRY node
		PathGraphEdge cycleEdge = createDummyEdge(getExitVertex(), getEntryVertex());
		edges.add(cycleEdge);

		// see if there are any loops --> initializes backEdges and dummy edges to loop headers
		initializeLoops();
		if(backEdges.isEmpty()) {
			// no loops --> start with instrumenting a program branch
			// extend from entry over first branch
			System.out.println("No loops.");
			extendOneBranch(0);
		}
		else {
			// loops --> start with just seeing whether loops are taken
			// extend to first branch
			System.out.println("Loops.");
			extendToNextBranch(0, true);
		}
	}
	
	/**
	 * Initialize or find vertex for given block. Follows the Ball & Larus paper (section 4) 
	 * in handling loops with two dummy edges. Also replaces jumps to unknown blocks with 
	 * jumps to the synthetic exit vertex (simplifies handling of explicit returns).
	 * @param blockIndex
	 * @return Vertex representing given block.
	 */
	private void initializeLoops() {
		for(int blockIndex = 0; blockIndex < blocks.size(); blockIndex++) {
			PathGraphVertex vertex = getVertex(blockIndex);
			// get the block
			Block b = vertex.getBlock();
			
			// follow control flow from this block
			Set succs = domTree.getSuccs(b);
			for(Iterator it = succs.iterator(); it.hasNext(); ) {
				int succIndex = ((Integer) it.next()).intValue();
				if(succIndex == blockIndex || domTree.dominates(succIndex, blockIndex)) {
					// loop! --> handle back edge
					PathGraphVertex succVertex = getVertex(succIndex);
					// dummy edge from entry to back edge target
					PathGraphEdge dummyIn = createDummyEdge(getEntryVertex(), succVertex);
					edges.add(dummyIn);
					// dummy edges from loop end to exit incrementally added later
					// take note of back edge
					backEdges.add(new BackEdge(this, vertex, succVertex, dummyIn, null));
					
					// extend loop header to next branch
					extendToNextBranch(succIndex, true);
				}
				// else not a back edge
			}
		}
	}
	
	/**
	 * Extends a path in the graph with the next branch (resulting in more paths).
	 * @param pathToExtend The path to be extended (value >= 0).
	 */
	public void extendPath(int pathToExtend) {
		// extend the given path with the next branch
		ArrayList vertices = getVerticesOnPath(pathToExtend);
		if(vertices.get(vertices.size() - 1) == getExitVertex()) {
			System.out.println("Cannot extend path " + pathToExtend + "--already complete.");
			return;
		}
		
		// find the last vertex on the existing path
		PathGraphVertex vertex = (PathGraphVertex) vertices.get(vertices.size() - 1);
		int blockIndex = getIndex(vertex);
		
		// include next branch into the graph
		extendOneBranch(blockIndex);

		// recompute graph information
		computeEdgeValues();
		findSpanningTree();
		computeEdgeIncrements();
	}
		
	protected void extendOneBranch(int blockIndex) {
		PathGraphVertex vertex = getVertex(blockIndex);
		// cut existing edge to EXIT
		for(Iterator it = vertex.getOutgoingEdges().iterator(); it.hasNext(); ) {
			PathGraphEdge e = (PathGraphEdge) it.next();
			if(e.isSkipEdge()) {
				edges.remove(e);
				e.getTarget().getIncomingEdges().remove(e);
				it.remove();
			}
		}

		// find branch
		blockIndex = extendToNextBranch(blockIndex, false);
		if(blockIndex < 0) 
			// just needed to connect to next branch
			return;
		vertex = getVertex(blockIndex);
		
		// return node --> just finish up the path (shouldn't actually happen here)
		Set succs = domTree.getSuccs(domTree.getBlock(blockIndex));
		if(succs.isEmpty()) {
			edges.add(createExitEdge(vertex));
			return;
		}
		
		// create edges for control flow from this block
		for(Iterator it = succs.iterator(); it.hasNext(); ) {
			int succIndex = ((Integer) it.next()).intValue();
			if(succIndex == blockIndex || domTree.dominates(succIndex, blockIndex)) {
				// loop! assume BackEdge objects to be initialized with dummyIn edge only
				PathGraphVertex succVertex = getVertex(succIndex);
				// dummy edge from back edge origin to exit
				PathGraphEdge dummyOut = createDummyEdge(vertex, getExitVertex()); 
				edges.add(dummyOut);
				// take note of new dummy in back edge
				if(addDummyOutToBackEdge(vertex, succVertex, dummyOut) == null) {
					System.out.println("Couldn't find back edge " + vertex + "->" + succVertex);
				}
			}
			else {
				// not a back edge
				PathGraphVertex succVertex = getVertex(succIndex);
				edges.add(createProgramEdge(vertex, succVertex));
				extendToNextBranch(succIndex, true);
			}
		}
	}
	
	
	/**
	 * @param origin
	 * @param target
	 * @param dummyOut
	 * @return
	 */
	private BackEdge addDummyOutToBackEdge(PathGraphVertex origin, PathGraphVertex target, PathGraphEdge dummyOut) {
		for(Iterator it = backEdges.iterator(); it.hasNext(); ) {
			BackEdge backedge = (BackEdge) it.next();
			if(backedge.getOrigin() == origin && backedge.getTarget() == target) {
				backedge.setDummyOut(dummyOut);
				return backedge;
			}
		}
		return null;
	}

	/**
	 * @param blockIndex
	 * @return The last block to which we could expand (before EXIT) 
	 * or -1 if we hit an already extended node.
	 */
	private int extendToNextBranch(int blockIndex, boolean connectToExit) {
		PathGraphVertex vertex = getVertex(blockIndex);
		// node already extended --> skip
		if(isInitialized(vertex)) {
			return -1;
		}
		
		Set succs = domTree.getSuccs((Block) blocks.get(blockIndex));
		if(succs.size() == 1) {
			// straight-line code --> expand further
			int succIndex = ((Integer) succs.iterator().next()).intValue();
			if(succIndex == blockIndex || domTree.dominates(succIndex, blockIndex)) {
				// loop! assume BackEdge object to be initialized with dummyIn edge only
				PathGraphVertex succVertex = getVertex(succIndex);
				// dummy edge from back edge origin to exit
				PathGraphEdge dummyOut = createDummyEdge(vertex, getExitVertex()); 
				edges.add(dummyOut);
				// take note of new dummy in back edge
				if(addDummyOutToBackEdge(vertex, succVertex, dummyOut) == null) {
					System.out.println("Couldn't find back edge " + vertex + "->" + succVertex);
				}
				// continue with loop header -- should be initialized already, so this will return -1
				return extendToNextBranch(succIndex, connectToExit);
			}
			else {
				// not a back edge
				PathGraphVertex succVertex = getVertex(succIndex);
				edges.add(createProgramEdge(vertex, succVertex));
				return extendToNextBranch(succIndex, connectToExit);
			}
		}
		else {
			// branch --> stop and connect to exit
			if(connectToExit) {
				if(succs.isEmpty()) {
					edges.add(createExitEdge(vertex));
				}
				else {
					edges.add(createSkipEdge(vertex));
				}
			}
			return blockIndex;
		}
	}

	protected PathGraphEdge createSkipEdge(PathGraphVertex origin) {
		return new PathGraphEdge(this, origin, getExitVertex(), false);
	}
	
	/**
	 * @param vertex
	 * @return
	 */
	private boolean isInitialized(PathGraphVertex vertex) {
		// EXIT is always initialized
		if(vertex == getExitVertex()) return true;
		// initialized nodes always have edges
		if(vertex.getOutgoingEdges().isEmpty()) return false;
		if(vertex == getEntryVertex()) {
			// ENTRY is not initialized if there are only dummy edges to loop headers
			for(Iterator it = vertex.getOutgoingEdges().iterator(); it.hasNext(); ) {
				PathGraphEdge e = (PathGraphEdge) it.next();
				if(e.isLoopEdge() == false)
					return true;
			}
			return false;
		}
		else
			// other nodes are initialized as soon as they have any edges
			return true;
	}

	/**
	 * @param pathToExtend
	 * @return
	 */
	private ArrayList getVerticesOnPath(int pathToExtend) {
	    //System.out.println("pathgraph.getpath, entry vertex is " + getEntryVertex() + " and exit vertex is " + getExitVertex());
		PathGraphVertex v = getEntryVertex();
		ArrayList result = new ArrayList();
		
		// entry is always on the path
		result.add(v);
		while(v != getExitVertex()) {
		    //System.out.println("checkpoint 1");
			PathGraphEdge maxEdge = null;
			int maxValue = -1;
			for(Iterator it = v.getOutgoingEdges().iterator(); it.hasNext(); ) {
				PathGraphEdge cur = (PathGraphEdge) it.next();
				if(cur.getValue() <= pathToExtend && maxValue < cur.getValue()) {
					maxEdge = cur;
					maxValue = cur.getValue();
				}
			}
			if(maxValue < 0) return result;
			
			// advance one node
			v = maxEdge.getTarget();
			pathToExtend-= maxValue;
			
			// only include node if we didn't just take a skip edge
			if(maxEdge.isSkipEdge() == false) {
				result.add(v);
			}
			
			//System.out.println("new v: " + v);
			//System.err.println("max edge: " + maxEdge.isProgramEdge() + " and EXIT vertex " + (v == getExitVertex()));
		}
		return result;
	}

	public int getPathCount() {
		return getEntryVertex().getNumPaths();
	}

	/**
	 * @return
	 */
	protected PathGraphVertex getExitVertex() {
		return vertices[vertices.length-1];
	}

	/**
	 * @return
	 */
	protected PathGraphVertex getEntryVertex() {
		return vertices[0];
	}

	/**
	 * @return Returns the cycleEdge.
	 *
	protected PathGraphEdge getCycleEdge() {
		return cycleEdge;
	}*/
	
	public String toString() {
		StringBuffer result = new StringBuffer();
		for(Iterator it = edges.iterator(); it.hasNext(); ) {
			PathGraphEdge cur = (PathGraphEdge) it.next();
			result.append(cur.toString());
			result.append(" val=" + cur.getValue());

			if(cur.isSpanning()) {
				result.append(" spans");
			}
			else {
				result.append(" chord inc=" + cur.getIncrement());
			}
			result.append('\n');
		}
		return result.toString();
	}

	/**
	 * @return
	 */
	public Set getEdges() {
		return edges;
	}

	/**
	 * @return Returns the backEdges.
	 */
	public HashSet getBackEdges() {
		return backEdges;
	}

    /** Serialization functions */

    private Vector edgesV, backEdgesV;
    private void writeObject(java.io.ObjectOutputStream out) throws IOException {
	//ignoring exitVertex because duplicate
	edgesV = new Vector(edges);
	backEdgesV = new Vector(backEdges);
	out.writeObject(vertices);
	out.writeObject(edgesV);
	out.writeObject(backEdgesV);
	//out.writeObject(exitVertex);
    }

    private void readObject(java.io.ObjectInputStream in) throws IOException, ClassNotFoundException {
	//tree and blocks null

	vertices = (PathGraphVertex []) in.readObject();
	edgesV = (Vector) in.readObject();
	backEdgesV = (Vector) in.readObject();
	//exitVertex = (PathGraphVertex) in.readObject();

	edges = new HashSet(edgesV);
	backEdges = new HashSet(backEdgesV);

	for(int i = 0; i < vertices.length; i++) {
	    vertices[i].setPathGraph(this);
	}

	for(Iterator it = edges.iterator(); it.hasNext(); ) {
	    PathGraphEdge e = (PathGraphEdge) it.next();
	    e.setPathGraph(this);
	}

	for(Iterator it = backEdges.iterator(); it.hasNext(); ) {
	    BackEdge e = (BackEdge) it.next();
	    e.setPathGraph(this);
	}

	//exitVertex.setPathGraph(this);
    }

    protected int getIndex(PathGraphVertex v) {
	for(int i = 0; i < vertices.length; i++) {
	    if(vertices[i] == v) return i;
	}
	System.err.println("can't find vertex!! baad.");
	return -1;
    }

    protected int getIndex(PathGraphEdge e) {
    	if(edgesV == null) edgesV = new Vector(edges);
    	return edgesV.indexOf(e);
    }

    protected PathGraphVertex getVertex(int i) {
	return vertices[i];
    }
    
    protected PathGraphEdge getEdge(int i) {
    	return (PathGraphEdge) edgesV.get(i);
    }

	/**
	 * @return Returns the blocks.
	 */
	protected Vector getBlocks() {
		return blocks;
	}

    /**
     * This method is not part of the public interface. Call this method to restore the
     * blocks after deserializing a path graph from a file.
     * @param blocks
     */
	public void setBlocks(Vector blocks) {
	this.blocks = blocks;
	this.domTree = new DominatorTree(blocks);

	for(int i = 0; i < vertices.length; i++) {
	    vertices[i].setBlock();
	}
    }

}

