NodeShuffler/src/bk/Compaction.java

package bk;

import java.util.ArrayList;

import animation.AlgorithmStage;
import animation.BackwardAction;
import animation.PseudoCodeNode;
import bk.ExtremalLayoutCalc.LayoutType;
import graph.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; // TODO: evtl richtigen "Stack" benutzen
	private ArrayList< BackwardAction > actions; // TODO: evtl richtigen "Stack" benutzen
	private LayoutType layout;
	private PseudoCodeNode placeNode;
    private PseudoCodeNode placeLoopNode;
    private PseudoCodeNode applyNode;
    private PseudoCodeNode applyLoopNode;
    private boolean inside;
	
	
	public Compaction( LayeredGraphNode graph, LayoutType layout )
	{
	    this.layout = layout;
		this.graph = graph;
		state = CompactionState.PLACE_BLOCKS;
		stack = new ArrayList<>(); // der call-stack des rekursiven algorithmus
		vIndex = 0;
		actions = new ArrayList<>();
		inside = false;
	}
	
	/**
	 * calculates the minimum spacing needed between two left borders of nodes.
	 * @return the spacing
	 */
	public double calcSpacing()
	{
		double max = 0;
		for( LayeredGraphNode n : graph.getContainedNodes() )
			max = Math.max( max, n.getWidth( layout ) );
		//return max + 25;
		return max;
	}
	
	private LayeredGraphNode getNodeFromIndex( int index )
	{
	    for( ArrayList< LayeredGraphNode > l : graph.getContainedLayers() )
	    {
	        if( index >= l.size() )
	            index -= l.size();
	        else
	            return l.get( index );
	    }
	    return null;
	}
	
	@Override
	public StageStatus forwardStep() {
		int acSize = actions.size();
		if( state == CompactionState.PLACE_BLOCKS ) // blöcke platzieren
		{
		    inside = true;
		    placeNode.setSelected( true );
		    placeLoopNode.setSelected( true );
			if( stack.size() == 0 ) // äußere schleife, placeblocks bisher nicht aufgerufen
			{
				ArrayList< LayeredGraphNode > nodes = graph.getContainedNodes();
				boolean found = false; // knoten mit v = root[v] gefunden?
				int oldVIndex = vIndex; // nötig für "undo"
				
				// suche knoten mit v = root[v] und undefiniertem x-Wert
				for( ; vIndex < nodes.size(); vIndex++ )
				{
					if( getNodeFromIndex( vIndex ).isXUndefined( layout ) && getNodeFromIndex( vIndex ) == getNodeFromIndex( vIndex ).getRoot( layout ) )
					{
	                    found = true;
						break;
					}
				}
				
				// kein knoten gefunden
				if( !found )
				{
				    // wechsele in die phase des Blöckeshiftens
		            placeNode.setSelected( false );
		            placeLoopNode.setSelected( false );
		            applyNode.setSelected( true );
		            applyLoopNode.setSelected( true );
					state = CompactionState.APPLY_SHIFT;
					inside = false;
					vIndex = 0;
					actions.add( 0, ()-> {
	                    applyNode.setSelected( false );
	                    applyLoopNode.setSelected( false );
                        placeNode.setSelected( true );
                        placeLoopNode.setSelected( true );
						vIndex = oldVIndex;
						inside = false;
						state = CompactionState.PLACE_BLOCKS;
					} );
				}
				else // Knoten gefunden
				{
					StackFrame f = new StackFrame(); // enthält lokale variablen
					f.v = getNodeFromIndex( vIndex );
					double oldX = f.v.getX( layout ); // nötig für "undo"
					f.v.setX( 0, true, layout );
					f.w = f.v;
                    f.w.setSelected( layout ); // zeige knoten als aktiven knoten an
                    System.out.println( "call place_block( " + f.v + " )" );
					stack.add( 0, f );
					
					// die "undo"-action
					actions.add( 0, ()-> {
					    inside = true;
						stack.get( 0 ).v.setX( oldX, false, layout );
						stack.get( 0 ).v.setSelected( layout );
						stack.remove( 0 );
						vIndex = oldVIndex;
						state = CompactionState.PLACE_BLOCKS;
					});
				}
			}
			else // zurzeit innerhalb einer placeblock methode
			{
				StackFrame sf = stack.get( 0 );
				if( sf.u == null ) // zu beginn der placeblock methode
				{
                    int posW = graph.getContainedLayers().get( sf.w.getLayer() ).indexOf( sf.w );
					if( (posW >= 1 && (layout == LayoutType.BOTTOM_TOP_LEFT || layout == LayoutType.TOP_BOTTOM_LEFT)) || (posW < graph.getContainedLayers().get( sf.w.getLayer() ).size() - 1 && (layout == LayoutType.BOTTOM_TOP_RIGHT || layout == LayoutType.TOP_BOTTOM_RIGHT)) ) // if pos[w] > 1"
					{
					    int offset = -1;
					    if( layout == LayoutType.BOTTOM_TOP_RIGHT || layout == LayoutType.TOP_BOTTOM_RIGHT )
					        offset = 1;
                        sf.u = graph.getContainedLayers().get( sf.w.getLayer() ).get( posW + offset ).getRoot( layout );
						
						if( sf.u.isXUndefined( layout ) ) // nötig placeblock aufzurufen?
						{// ja
							StackFrame nsf = new StackFrame(); // enthält lokale variablen
							nsf.v = sf.u;
							double oldX = nsf.v.getX( layout ); // nötig für "undo"
							nsf.v.setX( 0, true, layout );
							nsf.w = nsf.v;
                            nsf.w.setSelected( layout ); // zeige knoten als aktiven knoten an
		                    System.out.println( "call place_block( " + nsf.v + " )" );
							stack.add( 0, nsf );
		                    
		                    // die "undo"-action
							actions.add( 0, ()-> {
							    inside = true;
								stack.get( 0 ).v.setX( oldX, false, layout );
								stack.get( 0 ).v.setSelected( layout );
								stack.remove( 0 );
								stack.get( 0 ).u = null;
							});
						}
						else // nein
						{
						    // tue nix
							sf.w.setSelected( layout );
							actions.add( 0, ()-> {
                                inside = true;
								stack.get( 0 ).u = null;
							});
						}
					}
					else 
					{ // w = align[w]
						LayeredGraphNode oldW = sf.w;
						sf.w = sf.w.getAlignedTo( layout );
						sf.w.setSelected( layout );
						if( sf.w == sf.v ) // schleifenabbruchbedingung
						{ //abbrechen, placeblock beendet
                            System.out.println( "return place_block( " + sf.v + " )" );
							stack.remove( 0 );
							actions.add( 0, ()-> {
                                inside = true;
								stack.add( 0, sf );
								sf.w = oldW;
                                sf.w.setSelected( layout );
							});
						}
						else
						{ //nur "undo aktion" hinzufügen
							actions.add( 0, ()-> {
                                inside = true;
								sf.w = oldW;
								sf.w.setSelected( layout );
							});
						}
					}	
				}
				else // ein "placeBlock(u)" aufruf hat gerade returned
				{
				    // alte Werte merken für undo
					LayeredGraphNode oldSink = sf.v.getSink( layout );	
					LayeredGraphNode sinkOfU = sf.u.getSink( layout );
					double oldShift = sinkOfU.getShift( layout );
					double oldX = sf.v.getX( layout );
					boolean oldDef = !sf.v.isXUndefined( layout );
					
					// v für visualisierung markieren
					sf.w.setSelected( layout );
                    
                    if( sf.v.getSink( layout ) == sf.v ) // sink[v] = v?
                        sf.v.setSink( sf.u.getSink( layout ), layout ); // sink[v] := sink[u]
                    int multiplyer = 1;
                    if( layout == LayoutType.BOTTOM_TOP_RIGHT || layout == LayoutType.TOP_BOTTOM_RIGHT )
                        multiplyer = -1;
                    
					if( sf.v.getSink( layout ) != sf.u.getSink( layout ) ) // sink[v] != sink [u]?
						sf.u.getSink( layout ).setShift( // shift[sink[u]] =
						  Math.min( sf.u.getSink( layout ).getShift( layout ),  // min(shift[sink[u]]
						          multiplyer * (Math.abs(sf.v.getX( layout )) - Math.abs(sf.u.getX( layout )) - calcSpacing()) ), layout ); // y_v - y_u - s
					else
					    // y_v = max {y_v, y_u + s}
						sf.v.setX( multiplyer * Math.max( Math.abs( sf.v.getX( layout ) ), Math.abs( sf.u.getX( layout ) ) + calcSpacing() ), true, layout );
					

                    // alte Werte merken für undo
					LayeredGraphNode oldW = sf.w;
                    LayeredGraphNode oldU = sf.u;
                    
					sf.w = sf.w.getAlignedTo( layout ); // w = align[w]
					sf.u = null; // u wird nächsten schleifendurchlauf neu gesetzt
					
					if( sf.w == sf.v ) // schleifenabbruchbedingung
					{ //abbrechen, placeblock beendet  
					    System.out.println( "return place_block( " + sf.v + " )" );
						stack.remove( 0 );
						actions.add( 0, ()-> {
                            inside = true;
							stack.add( 0, sf );
							stack.get( 0 ).v.setSink(  oldSink, layout );
							sinkOfU.setShift( oldShift, layout );
							sf.u = oldU;
							sf.v.setX( oldX, oldDef, layout );
							sf.w = oldW;
                            sf.w.setSelected( layout );
						});
					}
					else
					{ //nur "undo aktion" hinzufügen
						actions.add( 0, ()-> {
                            inside = true;
							stack.get( 0 ).v.setSink(  oldSink, layout );
							sinkOfU.setShift( oldShift, layout );
							sf.u = oldU;
							sf.v.setX( oldX, oldDef, layout );
							sf.w = oldW;
                            sf.w.setSelected( layout );
						});
					}
				}
			}
		}
		else if( state == CompactionState.APPLY_SHIFT )// "Compute absolute coordinates"
		{
            inside = true;
		    if( vIndex >= graph.getContainedNodes().size() )
		    {
                inside = false;
                applyNode.setSelected( false );
                applyLoopNode.setSelected( false );
                return StageStatus.FINISHED;
		    }
			LayeredGraphNode v = graph.getContainedNodes().get( vIndex );
			double oldX = v.getX( layout );
			boolean oldDef = !v.isXUndefined( layout );
			
			v.setSelected( layout );
			v.setX( v.getRoot( layout ).getX( layout ), true, layout ); // y_v = y_root[v]
			if( v == v.getRoot( layout ) && v.getSink( layout ).getShift( layout ) < Double.POSITIVE_INFINITY )
				v.setX( v.getX( layout ) + v.getSink( layout ).getShift( layout ), true, layout );
			actions.add( 0, ()-> {
                inside = true;
                applyNode.setSelected( true );
                applyLoopNode.setSelected( true );
				v.setX( oldX, oldDef, layout );
				v.setSelected( layout );
				vIndex--;
			} );
			vIndex++;
			if( vIndex >= graph.getContainedNodes().size() )
			{
                applyNode.setSelected( false );
                applyLoopNode.setSelected( false );
				return StageStatus.FINISHED;
			}
		}
		if( actions.size() != acSize + 1 )
			System.out.println( "ERROR" );
		return StageStatus.UNFINISHED;
	}

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

    @Override
    public PseudoCodeNode createPseudocodeTree() {
        PseudoCodeNode root = new PseudoCodeNode( "Horizontal compaction" );
        placeNode = new PseudoCodeNode( "Root coordinates relative to sink" );
        placeLoopNode = new PseudoCodeNode( "Loop through root nodes..." );
        placeNode.add( placeLoopNode );
        applyNode = new PseudoCodeNode( "Absolute coordinates" );
        applyLoopNode = new PseudoCodeNode( "Loop through all nodes..." );
        applyNode.add( applyLoopNode );
        root.add( placeNode );
        root.add( applyNode );
        return root;
    }

    @Override
    public StageStatus forwardStepOver() {
        if( !inside )
        {
            CompactionState oldState = state;
            StageStatus stage = StageStatus.UNFINISHED;
            while( state == oldState && stage != StageStatus.FINISHED )
                stage = forwardStep();
            return stage;
        }
        else
            return forwardStep();
    }

    @Override
    public StageStatus forwardStepOut() {
        if( !inside )
        {
            StageStatus status = StageStatus.UNFINISHED;
            while( status != StageStatus.FINISHED )
                status = forwardStep();
            return status;
        }
        else
        {
            CompactionState oldState = state;
            StageStatus stage = StageStatus.UNFINISHED;
            while( state == oldState && stage != StageStatus.FINISHED )
                stage = forwardStep();
            return stage;
        }
    }

    @Override
    public StageStatus backwardStepOver() {
        if( !inside )
        {
            CompactionState oldState = state;
            StageStatus stage = StageStatus.UNFINISHED;
            while( state == oldState && stage != StageStatus.FINISHED )
                stage = backwardStep();
            return stage;
        }
        else
            return backwardStep();
    }

    @Override
    public StageStatus backwardStepOut() {
        if( !inside )
        {
            StageStatus status = StageStatus.UNFINISHED;
            while( status != StageStatus.FINISHED )
                status = backwardStep();
            return status;
        }
        else
        {
            CompactionState oldState = state;
            StageStatus stage = StageStatus.UNFINISHED;
            while( state == oldState && stage != StageStatus.FINISHED )
                stage = backwardStep();
            return stage;
        }
    }
}