NodeShuffler/src/Algorithms/Animated/BK/Compaction.java

package Algorithms.Animated.BK;

import java.util.ArrayList;

import Algorithms.Animated.AlgorithmStage;
import Algorithms.Animated.BackwardAction;
import Model.LayeredGraphNode;

/**
 * The stage of compacting the layout.
 * @author kolja
 *
 */
public class Compaction implements AlgorithmStage{

	private enum CompactionState
	{
		PLACE_BLOCKS,
		APPLY_SHIFT
	}
	
	private class StackFrame
	{
		public LayeredGraphNode v;
		public LayeredGraphNode u;
		public LayeredGraphNode w;
	}
	
	private CompactionState state;
	private LayeredGraphNode graph;
	private int vIndex;
	
	private ArrayList< StackFrame > stack;
	private ArrayList< BackwardAction > actions;
	
	public Compaction( LayeredGraphNode graph )
	{
		this.graph = graph;
		state = CompactionState.PLACE_BLOCKS;
		stack = new ArrayList<>();
		vIndex = 0;
		actions = new ArrayList<>();
	}
	
	public double calcSpacing()
	{
		double max = 0;
		for( LayeredGraphNode n : graph.getContainedNodes() )
			max = Math.max( max, n.getWidth() );
		return max + 50;
	}
	
	@Override
	public StageStatus forwardStep() {
		int acSize = actions.size();
		if( state == CompactionState.PLACE_BLOCKS )
		{
			if( stack.size() == 0 )
			{
				ArrayList< LayeredGraphNode > nodes = graph.getContainedNodes();
				boolean found = false;
				int oldVIndex = vIndex;
				for( ; vIndex < nodes.size(); vIndex++ )
				{
					if( nodes.get( vIndex ).isXUndefined() && nodes.get( vIndex ) == nodes.get( vIndex ).getRoot() )
					{
						found = true;
						break;
					}
				}
				if( !found )
				{
					state = CompactionState.APPLY_SHIFT;
					vIndex = 0;
					actions.add( 0, ()-> {
						vIndex = oldVIndex;
						state = CompactionState.PLACE_BLOCKS;
					} );
				}
				else
				{
					StackFrame f = new StackFrame();
					f.v = nodes.get( vIndex );
					double oldX = f.v.getX();
					f.v.setX( 0, true );
					f.v.setSelected();
					f.w = f.v;
					stack.add( 0, f );
					actions.add( 0, ()-> {
						stack.get( 0 ).v.setX( oldX, false );
						stack.get( 0 ).v.setSelected();
						stack.remove( 0 );
						vIndex = oldVIndex;
						state = CompactionState.PLACE_BLOCKS;
					});
				}
			}
			else
			{
				StackFrame sf = stack.get( 0 );
				if( sf.u == null )
				{
					if( graph.getContainedLayers().get( sf.w.getLayer() ).indexOf( sf.w ) >= 1 )
					{
						sf.u = graph.getContainedLayers().get( sf.w.getLayer() ).get( graph.getContainedLayers().get( sf.w.getLayer() ).indexOf( sf.w ) - 1 ).getRoot();
						if( sf.u.isXUndefined() )
						{
							StackFrame nsf = new StackFrame();
							nsf.v = sf.u;
							double oldX = nsf.v.getX();
							nsf.v.setX( 0, true );
							nsf.v.setSelected();
							nsf.w = nsf.v;
							stack.add( 0, nsf );
							actions.add( 0, ()-> {
								stack.get( 0 ).v.setX( oldX, false );
								stack.get( 0 ).v.setSelected();
								stack.remove( 0 );
								stack.get( 0 ).u = null;
							});
						}
						else
						{
							sf.u.setSelected();
							actions.add( 0, ()-> {
								stack.get( 0 ).u = null;
							});
						}
					}
					else
					{
						LayeredGraphNode oldW = sf.w;
						sf.v.setSelected();
						sf.w = sf.w.getAlignedTo();
						if( sf.w == sf.v )
						{
							stack.remove( 0 );
							actions.add( 0, ()-> {
								stack.add( 0, sf );
								sf.v.setSelected();
								sf.w = oldW;
							});
						}
						else
						{
							actions.add( 0, ()-> {
								sf.w = oldW;
								sf.v.setSelected();
							});
						}
					}	
				}
				else
				{
					LayeredGraphNode oldSink = sf.v.getSink();
					if( sf.v.getSink() == sf.v )
						sf.v.setSink( sf.u.getSink() );
					LayeredGraphNode sinkOfU = sf.u.getSink();
					double oldShift = sinkOfU.getShift();
					double oldX = sf.v.getX();
					boolean oldDef = !sf.v.isXUndefined();
					sf.v.setSelected();
					if( sf.v.getSink() != sf.u.getSink() )
						sf.u.getSink().setShift( Math.min( sf.u.getSink().getShift(), sf.v.getX() - sf.u.getX() - calcSpacing() ) );
					else
						sf.v.setX( Math.max( sf.v.getX(), sf.u.getX() + calcSpacing() ), true );
					LayeredGraphNode oldW = sf.w;
					sf.w = sf.w.getAlignedTo();
					LayeredGraphNode oldU = sf.u;
					sf.u = null;
					if( sf.w == sf.v )
					{
						stack.remove( 0 );
						actions.add( 0, ()-> {
							stack.add( 0, sf );
							stack.get( 0 ).v.setSink(  oldSink );
							sinkOfU.setShift( oldShift );
							sf.u = oldU;
							sf.v.setX( oldX, oldDef );
							sf.v.setSelected();
							sf.w = oldW;
						});
					}
					else
					{
						actions.add( 0, ()-> {
							stack.get( 0 ).v.setSink(  oldSink );
							sinkOfU.setShift( oldShift );
							sf.u = oldU;
							sf.v.setX( oldX, oldDef );
							sf.v.setSelected();
							sf.w = oldW;
						});
					}
				}
			}
		}
		else if( state == CompactionState.APPLY_SHIFT )
		{
			LayeredGraphNode v = graph.getContainedNodes().get( vIndex );
			double oldX = v.getX();
			boolean oldDef = !v.isXUndefined();
			v.setSelected();
			v.setX( v.getRoot().getX(), true );
			if( v == v.getRoot() && v.getSink().getShift() < Double.POSITIVE_INFINITY )
				v.setX( v.getX() + v.getSink().getShift(), true );
			actions.add( 0, ()-> {
				v.setX( oldX, oldDef );
				v.setSelected();
				vIndex--;
			} );
			vIndex++;
			if( vIndex >= graph.getContainedNodes().size() )
				return StageStatus.FINISHED;
		}
		if( actions.size() != acSize + 1 )
			System.out.println( "ERROR" );
		return StageStatus.UNFINISHED;
	}

	@Override
	public StageStatus backwardStep() {
		if( actions.size() == 0 )
			return StageStatus.FINISHED;
		actions.get( 0 ).reverse();
		actions.remove( 0 );
		return StageStatus.UNFINISHED;
	}

}