/**
 * Copyright (c) 2006-2015, JGraph Holdings Ltd
 * Copyright (c) 2006-2015, draw.io AG
 */
/**
 * Class: mxMinimumCycleRemover
 * 
 * An implementation of the first stage of the Sugiyama layout. Straightforward
 * longest path calculation of layer assignment
 * 
 * Constructor: mxMinimumCycleRemover
 *
 * Creates a cycle remover for the given internal model.
 */
function mxMinimumCycleRemover(layout)
{
	this.layout = layout;
};

/**
 * Extends mxHierarchicalLayoutStage.
 */
mxMinimumCycleRemover.prototype = new mxHierarchicalLayoutStage();
mxMinimumCycleRemover.prototype.constructor = mxMinimumCycleRemover;

/**
 * Variable: layout
 * 
 * Reference to the enclosing <mxHierarchicalLayout>.
 */
mxMinimumCycleRemover.prototype.layout = null;

/**
 * Function: execute
 * 
 * Takes the graph detail and configuration information within the facade
 * and creates the resulting laid out graph within that facade for further
 * use.
 */
mxMinimumCycleRemover.prototype.execute = function(parent)
{
	var model = this.layout.getModel();
	var seenNodes = new Object();
	var unseenNodesArray = model.vertexMapper.getValues();
	var unseenNodes = new Object();
	
	for (var i = 0; i < unseenNodesArray.length; i++)
	{
		unseenNodes[unseenNodesArray[i].id] = unseenNodesArray[i];
	}
	
	// Perform a dfs through the internal model. If a cycle is found,
	// reverse it.
	var rootsArray = null;
	
	if (model.roots != null)
	{
		var modelRoots = model.roots;
		rootsArray = [];
		
		for (var i = 0; i < modelRoots.length; i++)
		{
			rootsArray[i] = model.vertexMapper.get(modelRoots[i]);
		}
	}

	model.visit(function(parent, node, connectingEdge, layer, seen)
	{
		// Check if the cell is in it's own ancestor list, if so
		// invert the connecting edge and reverse the target/source
		// relationship to that edge in the parent and the cell
		if (node.isAncestor(parent))
		{
			connectingEdge.invert();
			mxUtils.remove(connectingEdge, parent.connectsAsSource);
			parent.connectsAsTarget.push(connectingEdge);
			mxUtils.remove(connectingEdge, node.connectsAsTarget);
			node.connectsAsSource.push(connectingEdge);
		}
		
		seenNodes[node.id] = node;
		delete unseenNodes[node.id];
	}, rootsArray, true, null);

	// If there are any nodes that should be nodes that the dfs can miss
	// these need to be processed with the dfs and the roots assigned
	// correctly to form a correct internal model
	var seenNodesCopy = mxUtils.clone(seenNodes, null, true);

	// Pick a random cell and dfs from it
	model.visit(function(parent, node, connectingEdge, layer, seen)
	{
		// Check if the cell is in it's own ancestor list, if so
		// invert the connecting edge and reverse the target/source
		// relationship to that edge in the parent and the cell
		if (node.isAncestor(parent))
		{
			connectingEdge.invert();
			mxUtils.remove(connectingEdge, parent.connectsAsSource);
			node.connectsAsSource.push(connectingEdge);
			parent.connectsAsTarget.push(connectingEdge);
			mxUtils.remove(connectingEdge, node.connectsAsTarget);
		}
		
		seenNodes[node.id] = node;
		delete unseenNodes[node.id];
	}, unseenNodes, true, seenNodesCopy);
};
