gt: 			mxGraphHierarchyNode internalNode = startNodesCopy.get(i);
context: /*
   * $Id: mxGraphHierarchyModel.java,v 1.14 2012-06-26 10:59:34 david Exp $
   * Copyright (c) 2005-2012, JGraph Ltd
   */
  package com.mxgraph.layout.hierarchical.model;
  
  import java.util.ArrayList;
  import java.util.Arrays;
  import java.util.Collection;
  import java.util.HashSet;
  import java.util.Hashtable;
  import java.util.Iterator;
  import java.util.LinkedHashMap;
  import java.util.LinkedHashSet;
  import java.util.LinkedList;
  import java.util.List;
  import java.util.Map;
  import java.util.Set;
  
  import com.mxgraph.layout.hierarchical.mxHierarchicalLayout;
  import com.mxgraph.view.mxGraph;
  
  /**
   * Internal model of a hierarchical graph. This model stores nodes and edges
   * equivalent to the real graph nodes and edges, but also stores the rank of the
   * cells, the order within the ranks and the new candidate locations of cells.
   * The internal model also reverses edge direction were appropriate , ignores
   * self-loop and groups parallels together under one edge object.
   */
  public class mxGraphHierarchyModel
  {
  	/**
  	 * Stores the largest rank number allocated
  	 */
  	public int maxRank;
  
  	/**
  	 * Map from graph vertices to internal model nodes
  	 */
  	protected Map<Object, mxGraphHierarchyNode> vertexMapper = null;
  
  	/**
  	 * Map from graph edges to internal model edges
  	 */
  	protected Map<Object, mxGraphHierarchyEdge> edgeMapper = null;
  
  	/**
  	 * Mapping from rank number to actual rank
  	 */
  	public Map<Integer, mxGraphHierarchyRank> ranks = null;
  
  	/**
  	 * Store of roots of this hierarchy model, these are real graph cells, not
  	 * internal cells
  	 */
  	public List<Object> roots;
  
  	/**
  	 * The parent cell whose children are being laid out
  	 */
  	public Object parent = null;
  
  	/**
  	 * Count of the number of times the ancestor dfs has been used
  	 */
  	protected int dfsCount = 0;
  
  	/** High value to start source layering scan rank value from */
  	private final int SOURCESCANSTARTRANK = 100000000;
  
  	/**
  	 * Creates an internal ordered graph model using the vertices passed in. If
  	 * there are any, leftward edge need to be inverted in the internal model
  	 * 
  	 * @param layout
  	 *            the enclosing layout object
  	 * @param vertices
  	 *            the vertices for this hierarchy
  	 */
  	public mxGraphHierarchyModel(mxHierarchicalLayout layout,
  			Object[] vertices, List<Object> roots, Object parent)
  	{
  		mxGraph graph = layout.getGraph();
  		this.roots = roots;
  		this.parent = parent;
  
  		if (vertices == null)
  		{
  			vertices = graph.getChildVertices(parent);
  		}
  
  		// map of cells to internal cell needed for second run through
  		// to setup the sink of edges correctly. Guess size by number
  		// of edges is roughly same as number of vertices.
  		vertexMapper = new Hashtable<Object, mxGraphHierarchyNode>(
  				vertices.length);
  		edgeMapper = new Hashtable<Object, mxGraphHierarchyEdge>(
  				vertices.length);
  
  		maxRank = SOURCESCANSTARTRANK;
  
  		mxGraphHierarchyNode[] internalVertices = new mxGraphHierarchyNode[vertices.length];
  		createInternalCells(layout, vertices, internalVertices);
  
  		// Go through edges set their sink values. Also check the
  		// ordering if and invert edges if necessary
  		for (int i = 0; i < vertices.length; i++)
  		{
  			Collection<mxGraphHierarchyEdge> edges = internalVertices[i].connectsAsSource;
  			Iterator<mxGraphHierarchyEdge> iter = edges.iterator();
  
  			while (iter.hasNext())
  			{
  				mxGraphHierarchyEdge internalEdge = iter.next();
  				Collection<Object> realEdges = internalEdge.edges;
  				Iterator<Object> iter2 = realEdges.iterator();
  
  				// Only need to process the first real edge, since
  				// all the edges connect to the same other vertex
  				if (iter2.hasNext())
  				{
  					Object realEdge = iter2.next();
  					Object targetCell = graph.getView().getVisibleTerminal(
  							realEdge, false);
  					mxGraphHierarchyNode internalTargetCell = vertexMapper
  							.get(targetCell);
  
  					if (internalVertices[i] == internalTargetCell)
  					{
  						// The real edge is reversed relative to the internal edge
  						targetCell = graph.getView().getVisibleTerminal(
  								realEdge, true);
  						internalTargetCell = vertexMapper.get(targetCell);
  					}
  
  					if (internalTargetCell != null
  							&& internalVertices[i] != internalTargetCell)
  					{
  						internalEdge.target = internalTargetCell;
  
  						if (internalTargetCell.connectsAsTarget.size() == 0)
  						{
  							internalTargetCell.connectsAsTarget = new LinkedHashSet<mxGraphHierarchyEdge>(
  									4);
  						}
  
  						internalTargetCell.connectsAsTarget.add(internalEdge);
  					}
  				}
  			}
  
  			// Use the temp variable in the internal nodes to mark this
  			// internal vertex as having been visited.
  			internalVertices[i].temp[0] = 1;
  		}
  	}
  	
  	/**
  	 * Creates all edges in the internal model
  	 * 
  	 * @param layout
  	 *            reference to the layout algorithm
  	 * @param vertices
  	 *            the vertices whom are to have an internal representation
  	 *            created
  	 * @param internalVertices
  	 *            the blank internal vertices to have their information filled
  	 *            in using the real vertices
  	 */
  	protected void createInternalCells(mxHierarchicalLayout layout,
  			Object[] vertices, mxGraphHierarchyNode[] internalVertices)
  	{
  		mxGraph graph = layout.getGraph();
  
  		// Create internal edges
  		for (int i = 0; i < vertices.length; i++)
  		{
  			internalVertices[i] = new mxGraphHierarchyNode(vertices[i]);
  			vertexMapper.put(vertices[i], internalVertices[i]);
  
  			// If the layout is deterministic, order the cells
  			Object[] conns = layout.getEdges(vertices[i]);
  			List<Object> outgoingCells = Arrays.asList(graph.getOpposites(
  					conns, vertices[i]));
  			internalVertices[i].connectsAsSource = new LinkedHashSet<mxGraphHierarchyEdge>(
  					outgoingCells.size());
  
  			// Create internal edges, but don't do any rank assignment yet
  			// First use the information from the greedy cycle remover to
  			// invert the leftward edges internally
  			Iterator<Object> iter = outgoingCells.iterator();
  
  			while (iter.hasNext())
  			{
  				// Don't add self-loops
  				Object cell = iter.next();
  
  				if (cell != vertices[i] && graph.getModel().isVertex(cell)
  						&& !layout.isVertexIgnored(cell))
  				{
  					// We process all edge between this source and its targets
  					// If there are edges going both ways, we need to collect
  					// them all into one internal edges to avoid looping problems
  					// later. We assume this direction (source -> target) is the 
  					// natural direction if at least half the edges are going in
  					// that direction.
  
  					// The check below for edgeMapper.get(edges[0]) == null is
  					// in case we've processed this the other way around
  					// (target -> source) and the number of edges in each direction
  					// are the same. All the graph edges will have been assigned to
  					// an internal edge going the other way, so we don't want to 
  					// process them again
  					Object[] undirectEdges = graph.getEdgesBetween(vertices[i],
  							cell, false);
  					Object[] directedEdges = graph.getEdgesBetween(vertices[i],
  							cell, true);
  
  					if (undirectEdges != null
  							&& undirectEdges.length > 0
  							&& (edgeMapper.get(undirectEdges[0]) == null)
  							&& (directedEdges.length * 2 >= undirectEdges.length))
  					{
  
  						ArrayList<Object> listEdges = new ArrayList<Object>(
  								undirectEdges.length);
  
  						for (int j = 0; j < undirectEdges.length; j++)
  						{
  							listEdges.add(undirectEdges[j]);
  						}
  
  						mxGraphHierarchyEdge internalEdge = new mxGraphHierarchyEdge(
  								listEdges);
  						Iterator<Object> iter2 = listEdges.iterator();
  
  						while (iter2.hasNext())
  						{
  							Object edge = iter2.next();
  							edgeMapper.put(edge, internalEdge);
  
  							// Resets all point on the edge and disables the edge style
  							// without deleting it from the cell style
  							graph.resetEdge(edge);
  
  							if (layout.isDisableEdgeStyle())
  							{
  								layout.setEdgeStyleEnabled(edge, false);
  								layout.setOrthogonalEdge(edge, true);
  							}
  						}
  
  						internalEdge.source = internalVertices[i];
  						internalVertices[i].connectsAsSource.add(internalEdge);
  					}
  				}
  			}
  
  			// Ensure temp variable is cleared from any previous use
  			internalVertices[i].temp[0] = 0;
  		}
  	}
  
  	/**
  	 * Basic determination of minimum layer ranking by working from from sources
  	 * or sinks and working through each node in the relevant edge direction.
  	 * Starting at the sinks is basically a longest path layering algorithm.
  	 */
  	public void initialRank()
  	{
  		Collection<mxGraphHierarchyNode> internalNodes = vertexMapper.values();
  		LinkedList<mxGraphHierarchyNode> startNodes = new LinkedList<mxGraphHierarchyNode>();
  
  		if (roots != null)
  		{
  			Iterator<Object> iter = roots.iterator();
  
  			while (iter.hasNext())
  			{
  				mxGraphHierarchyNode internalNode = vertexMapper.get(iter
  						.next());
  
  				if (internalNode != null)
  				{
  					startNodes.add(internalNode);
  				}
  			}
  		}
  
  		Iterator<mxGraphHierarchyNode> iter = internalNodes.iterator();
  
  		while (iter.hasNext())
  		{
  			mxGraphHierarchyNode internalNode = iter.next();
  			// Mark the node as not having had a layer assigned
  			internalNode.temp[0] = -1;
  		}
  
  		List<mxGraphHierarchyNode> startNodesCopy = new ArrayList<mxGraphHierarchyNode>(
  				startNodes);
  
  		while (!startNodes.isEmpty())
  		{
  			mxGraphHierarchyNode internalNode = startNodes.getFirst();
  			Collection<mxGraphHierarchyEdge> layerDeterminingEdges;
  			Collection<mxGraphHierarchyEdge> edgesToBeMarked;
  
  			layerDeterminingEdges = internalNode.connectsAsTarget;
  			edgesToBeMarked = internalNode.connectsAsSource;
  
  			// flag to keep track of whether or not all layer determining
  			// edges have been scanned
  			boolean allEdgesScanned = true;
  
  			// Work out the layer of this node from the layer determining
  			// edges
  			Iterator<mxGraphHierarchyEdge> iter2 = layerDeterminingEdges
  					.iterator();
  
  			// The minimum layer number of any node connected by one of
  			// the layer determining edges variable. If we are starting
  			// from sources, need to start at some huge value and
  			// normalise down afterwards
  			int minimumLayer = SOURCESCANSTARTRANK;
  
  			while (allEdgesScanned && iter2.hasNext())
  			{
  				mxGraphHierarchyEdge internalEdge = iter2.next();
  
  				if (internalEdge.temp[0] == 5270620)
  				{
  					// This edge has been scanned, get the layer of the
  					// node on the other end
  					mxGraphHierarchyNode otherNode = internalEdge.source;
  					minimumLayer = Math.min(minimumLayer,
  								otherNode.temp[0] - 1);
  				}
  				else
  				{
  					allEdgesScanned = false;
  				}
  			}
  
  			// If all edge have been scanned, assign the layer, mark all
  			// edges in the other direction and remove from the nodes list
  			if (allEdgesScanned)
  			{
  				internalNode.temp[0] = minimumLayer;
  				maxRank = Math.min(maxRank, minimumLayer);
  
  				if (edgesToBeMarked != null)
  				{
  					Iterator<mxGraphHierarchyEdge> iter3 = edgesToBeMarked
  							.iterator();
  
  					while (iter3.hasNext())
  					{
  						mxGraphHierarchyEdge internalEdge = iter3.next();
  						// Assign unique stamp ( y/m/d/h )
  						internalEdge.temp[0] = 5270620;
  
  						// Add node on other end of edge to LinkedList of
  						// nodes to be analysed
  						mxGraphHierarchyNode otherNode = internalEdge.target;
  
  						// Only add node if it hasn't been assigned a layer
  						if (otherNode.temp[0] == -1)
  						{
  							startNodes.addLast(otherNode);
  
  							// Mark this other node as neither being
  							// unassigned nor assigned so it isn't
  							// added to this list again, but it's
  							// layer isn't used in any calculation.
  							otherNode.temp[0] = -2;
  						}
  					}
  				}
  
  				startNodes.removeFirst();
  			}
  			else
  			{
  				// Not all the edges have been scanned, get to the back of
  				// the class and put the dunces cap on
  				Object removedCell = startNodes.removeFirst();
  				startNodes.addLast(internalNode);
  
  				if (removedCell == internalNode && startNodes.size() == 1)
  				{
  					// This is an error condition, we can't get out of
  					// this loop. It could happen for more than one node
  					// but that's a lot harder to detect. Log the error
  					// TODO make log comment
  					break;
  				}
  			}
  		}
  
  		// Normalize the ranks down from their large starting value to place
  		// at least 1 sink on layer 0
  		iter = internalNodes.iterator();
  		while (iter.hasNext())
  		{
  			mxGraphHierarchyNode internalNode = iter.next();
  			// Mark the node as not having had a layer assigned
  			internalNode.temp[0] -= maxRank;
  		}
  		
  		// Tighten the roots as far as possible
  		for (int i = 0; i < startNodesCopy.size(); i++)
  		{
  