package gd.module;


import java.util.ArrayList;
import java.util.List;
import java.util.Random;

import y.base.Node;
import y.layout.BufferedLayouter;
import y.layout.tree.TreeLayouter;
import y.module.YModule;
import y.option.OptionHandler;
import y.view.Graph2D;


/**
 * This class implements a module that generates
 * a decomposition tree of a series-parallel graph.
 */
public class SPDecompositionTreeGeneratorModule extends YModule
{
	public SPDecompositionTreeGeneratorModule()
	{
		super("SP Decomposition Generator",
			"Krists Boitmanis",
			"Generates a decomposition tree of a series-parallel graph.");
	}

	
	/**
	 * This method is the main entry point of this module.
	 */
	protected void mainrun()
	{
		Graph2D graph = this.getGraph2D();

		// Remove existing nodes and edges.
		graph.clear();

		// Create a random decomposition tree of an SP-graph.
		this.generateSPDecompositionTree();

		// Draw the graph.
		new BufferedLayouter(new TreeLayouter()).doLayout(graph);
		
		// Center the graph in the view.
		
		graph.updateViews();
		this.fitGraph2DView();
	}
	
	
	/**
	 * This method creates an option handler for interactive
	 * specification of the number of components in the
	 * SP-decomposition tree.
	 */
	public OptionHandler createOptionHandler()
	{
		OptionHandler handler = new OptionHandler(this.getModuleName());
		
		handler.addInt(NUMBER_OF_EDGES,
			DEFAULT_NUMBER_OF_EDGES,
			MIN_NUMBER_OF_EDGES,
			MAX_NUMBER_OF_EDGES);
		
		return handler;
	}
	
	
	/**
	 * This method generates the decomposition tree of a random SP-graph. 
	 */
	private void generateSPDecompositionTree()
	{
		Graph2D graph = this.getGraph2D();
		
		// Ask for the number of edges.
		
		int numberOfQNodes =
			this.getOptionHandler().getInt(NUMBER_OF_EDGES);
		
		// First create the structure of a complete binary tree with
		// numberOfQNodes leaves, i.e. 2 * numberOfQNodes - 1 nodes.
		
		int numberOfNodes = 2 * numberOfQNodes - 1;
		
		// Store the nodes in a list.
		List<Node> nodeList = new ArrayList<Node>();

		// Add the first node.
		nodeList.add(graph.createNode());

		while (graph.nodeCount() < numberOfNodes)
		{
			// Find a random leaf node.
			
			Node node;
			
			do
			{
				node = nodeList.get(this.random.nextInt(nodeList.size()));
			}
			while (node.outDegree() != 0);

			// Turn this node into an inner node.
			
			Node child1 = graph.createNode();
			Node child2 = graph.createNode();
			
			graph.createEdge(node, child1);
			graph.createEdge(node, child2);
			
			nodeList.add(child1);
			nodeList.add(child2);
		}
		
		// Now label the nodes with letters Q, P, and S.
		
		for (Node node : nodeList)
		{
			if (node.outDegree() == 0)
			{
				// Leaves are Q-nodes.
				graph.getRealizer(node).setLabelText("Q");
			}
			else
			{
				// Decide between P and S at random.
				
				graph.getRealizer(node).setLabelText("P");
				
				if (this.random.nextBoolean())
				{
					graph.getRealizer(node).setLabelText("S");
				}
			}
		}
	}
	
	
	private Random random = new Random();
	
	private static final String NUMBER_OF_EDGES = "Number of edges";
	private static final int DEFAULT_NUMBER_OF_EDGES = 10;
	private static final int MIN_NUMBER_OF_EDGES = 1;
	private static final int MAX_NUMBER_OF_EDGES = 100;
}