NodeShuffler/src/bk/BlockCalc.java

package bk;

import java.awt.Color;
import java.util.ArrayList;
import java.util.Collections;

import javax.swing.JTree;

import animation.AlgorithmStage;
import animation.BackwardAction;
import animation.PseudoCodeNode;
import bk.ExtremalLayoutCalc.LayoutType;
import graph.LayeredGraphEdge;
import graph.LayeredGraphNode;

/**
 * The stage of the BK node placement algorithm where the blocks are computed.
 * @author kolja
 *
 */
public class BlockCalc implements AlgorithmStage {

    private int layerIndex;
    private int nodeIndex;
    private int r;
    private LayeredGraphNode graph;
    private ArrayList< ArrayList< PseudoCodeNode > > subgraphNodes;
    private ArrayList< ArrayList< ExtremalLayoutCalc > > subgraphAlgs;
    private ArrayList< BackwardAction > backwards; // TODO: evtl richtigen "Stack" benutzen
    private LayoutType layout;
    private PseudoCodeNode loopNode;
    private boolean inside;
    int step;

    public BlockCalc( LayeredGraphNode graph, LayoutType layout )
    {
        this.layout = layout;
        step = 0;
        this.graph = graph;
        layerIndex = 0;
        nodeIndex = 0;
        r = 0;
        subgraphNodes = new ArrayList<>();
        subgraphAlgs = new ArrayList<>();
        for( ArrayList<LayeredGraphNode> l : graph.getContainedLayers() )
        {
            ArrayList< PseudoCodeNode > nodes = new ArrayList<>();
            ArrayList< ExtremalLayoutCalc > algs = new ArrayList<>();
            for( int i = 0; i < l.size(); i++ )
            {
                nodes.add( null );
                algs.add( null );
            }
            subgraphAlgs.add( algs );
            subgraphNodes.add( nodes );
        }
        inside = false;
        backwards = new ArrayList<>();
    }

    private int calcLayerIndex()
    {
        if( layout == LayoutType.TOP_BOTTOM_LEFT || layout == LayoutType.TOP_BOTTOM_RIGHT )
            return layerIndex;
        if( layout == LayoutType.BOTTOM_TOP_LEFT || layout == LayoutType.BOTTOM_TOP_RIGHT )
            return graph.getContainedLayers().size() - layerIndex - 1;
        return -1;
    }

    private int calcBeforeLayerIndex()
    {
        if( layout == LayoutType.TOP_BOTTOM_LEFT || layout == LayoutType.TOP_BOTTOM_RIGHT )
            return layerIndex - 1;
        if( layout == LayoutType.BOTTOM_TOP_LEFT || layout == LayoutType.BOTTOM_TOP_RIGHT )
            return graph.getContainedLayers().size() - layerIndex;
        return -1;
    }

    private int calcNodeIndex( int index )
    {
        if( layout == LayoutType.TOP_BOTTOM_LEFT || layout == LayoutType.BOTTOM_TOP_LEFT )
            return index;
        if( layout == LayoutType.TOP_BOTTOM_RIGHT || layout == LayoutType.BOTTOM_TOP_RIGHT )
            return graph.getContainedLayers().get( calcLayerIndex() ).size() - index - 1;
        return index;
    }
    
    private int calcBeforeLayerNodeIndex( int index )
    {
        if( layout == LayoutType.TOP_BOTTOM_LEFT || layout == LayoutType.BOTTOM_TOP_LEFT )
            return index;
        if( layout == LayoutType.TOP_BOTTOM_RIGHT || layout == LayoutType.BOTTOM_TOP_RIGHT )
            return graph.getContainedLayers().get( calcBeforeLayerIndex() ).size() - index - 1;
        return index;
    }

    @Override
    public StageStatus forwardStep() {
        LayeredGraphNode current = graph.getContainedLayers().get( calcLayerIndex() ).get( calcNodeIndex( nodeIndex ) );
        current.setSelected( layout );
        if( current.getContainedNodes().size() > 0 )
        {
            inside = true;
            boolean breakpoint = false;
            if( !subgraphNodes.get( calcLayerIndex() ).get( calcNodeIndex( nodeIndex ) ).isSelected() )
                breakpoint |= !subgraphNodes.get( calcLayerIndex() ).get( calcNodeIndex( nodeIndex ) ).setSelected( true );
            switch( subgraphAlgs.get( calcLayerIndex() ).get( calcNodeIndex( nodeIndex ) ).forwardStep() )
            {
            case BREAKPOINT:
                return StageStatus.BREAKPOINT;
            case UNFINISHED:
                if( breakpoint )
                    return StageStatus.BREAKPOINT;
                return StageStatus.UNFINISHED;
            case FINISHED:
                inside = false;
                subgraphNodes.get( calcLayerIndex() ).get( calcNodeIndex( nodeIndex ) ).setSelected( false );
                break;
            }
        }
        ArrayList< LayeredGraphEdge > incommingEdges = null;
        if( layout == LayoutType.TOP_BOTTOM_LEFT || layout == LayoutType.TOP_BOTTOM_RIGHT )
            incommingEdges = current.getSortedIncomingEdges();
        if( layout == LayoutType.BOTTOM_TOP_LEFT || layout == LayoutType.BOTTOM_TOP_RIGHT )
            incommingEdges = current.getSortedOutgoingEdges();
        if( layout == LayoutType.TOP_BOTTOM_RIGHT || layout == LayoutType.BOTTOM_TOP_RIGHT )
        Collections.reverse( incommingEdges );
        if( incommingEdges.size() == 0 )
        {
            backwards.add( 0, () -> {
                System.out.println( "Performing Empty Backwards Step..." );
            });
            return calcNextState();
        }
        int[] ms = {(incommingEdges.size() + 1) / 2, (int)( (incommingEdges.size() + 1) / 2.0 + 0.5 )};
        boolean backwardsAdded = false;
        for( int m : ms )
        {
            if( current.getAlign( layout ) == current )
            {
                LayeredGraphNode u = null;
                if( layout == LayoutType.TOP_BOTTOM_LEFT || layout == LayoutType.TOP_BOTTOM_RIGHT )
                    u = incommingEdges.get( m - 1 ).getSources().get( 0 );
                if( layout == LayoutType.BOTTOM_TOP_LEFT || layout == LayoutType.BOTTOM_TOP_RIGHT )
                    u = incommingEdges.get( m - 1 ).getTargets().get( 0 );
                ArrayList<LayeredGraphEdge> conflicts = incommingEdges.get( m - 1 ).calcEdgeCrossings();
                
                if( !incommingEdges.get( m - 1 ).isConflicted( layout ) && r < calcBeforeLayerNodeIndex( graph.getContainedLayers().get( calcBeforeLayerIndex() ).indexOf( u ) ) + 1 )
                {
                    System.out.println( "" );
                    ArrayList< Boolean > oldConflicts = new ArrayList<>();
                    for( LayeredGraphEdge e : conflicts )
                    {
                        oldConflicts.add( e.isConflicted( layout ) );
                        e.setConflicted( true, layout );
                    }
                    LayeredGraphNode oldAlignU = u.getAlign( layout );
                    Color oldColorCurrent = current.getColor( layout );
                    LayeredGraphNode oldRootCurrent = current.getRoot( layout );
                    LayeredGraphNode oldAlignCurrent = current.getAlign( layout );
                    int oldR = r;
                    u.setAlign( current, layout );
                    current.setColor( u.getRoot( layout ).getColor( layout ), layout );
                    current.setRoot( u.getRoot( layout ), layout );
                    current.setAlign( current.getRoot( layout ), layout );
                    r = calcBeforeLayerNodeIndex( graph.getContainedLayers().get( calcBeforeLayerIndex() ).indexOf( u ) ) + 1;
                    int oldStep = step++;
                    final LayeredGraphNode uf = u;
                    backwards.add( 0, () -> {
                        System.out.println( "Stepping Backwards... (Step " + oldStep + ")" );
                        for( int i = 0; i < conflicts.size(); i++ )
                            conflicts.get( i ).setConflicted( oldConflicts.get( i ), layout );
                        uf.setAlign( oldAlignU, layout );
                        current.setColor( oldColorCurrent, layout );
                        current.setRoot( oldRootCurrent, layout );
                        current.setAlign( oldAlignCurrent, layout );
                        r = oldR;
                    });
                    backwardsAdded = true;
                }
            }
        }
        if( !backwardsAdded )
        {
            backwards.add( 0, () -> {
                System.out.println( "Performing Empty Backwards Step..." );
            });
        }
        //current.update();
        return calcNextState();
    }

    private StageStatus calcNextState()
    {
        boolean breakpoint = !loopNode.setSelected( true );
        if( layerIndex >= graph.getContainedLayers().size() - 1 )
        {
            if( nodeIndex >= graph.getContainedLayers().get( calcLayerIndex() ).size() -1 )
            {
                loopNode.setSelected( false );
                return StageStatus.FINISHED;
            }
        }
        nodeIndex++;
        if( nodeIndex >= graph.getContainedLayers().get( calcLayerIndex() ).size() )
        {
            layerIndex++;
            nodeIndex = 0;
            int oldR = r;
            r = 0;
            backwards.add(0, ()->{
               this.r = oldR;
            });
        }
        if( breakpoint )
            return StageStatus.BREAKPOINT;
        return StageStatus.UNFINISHED;
    }

    @Override
    public StageStatus backwardStep() {
        if( subgraphAlgs.get( calcLayerIndex() ).get( calcNodeIndex( nodeIndex ) ) != null )
        {
            inside = true;
            boolean breakpoint = false;
            if( !subgraphNodes.get( calcLayerIndex() ).get( calcNodeIndex( nodeIndex ) ).isSelected() )
                breakpoint |= !subgraphNodes.get( calcLayerIndex() ).get( calcNodeIndex( nodeIndex ) ).setSelected( true );
            switch( subgraphAlgs.get( calcLayerIndex() ).get( calcNodeIndex( nodeIndex ) ).backwardStep() )
            {
            case BREAKPOINT:
                return StageStatus.BREAKPOINT;
            case UNFINISHED:
                LayeredGraphNode current = graph.getContainedLayers().get( calcLayerIndex() ).get( nodeIndex );
                current.setSelected( layout );
                if( breakpoint )
                    return StageStatus.BREAKPOINT;
                return StageStatus.UNFINISHED;
            case FINISHED:
                inside = false;
                subgraphNodes.get( calcLayerIndex() ).get( calcNodeIndex( nodeIndex ) ).setSelected( false );
                break;
            }
        }
        StageStatus status = calcBeforeState();
        if( status == StageStatus.FINISHED )
            return status;
        LayeredGraphNode current = graph.getContainedLayers().get( calcLayerIndex() ).get( calcNodeIndex( nodeIndex ) );
        current.setSelected( layout );
        //current.update();
        if( !backwards.isEmpty() )
        {
            backwards.get( 0 ).reverse();
            backwards.remove( 0 );
        }
        return status;
    }

    private StageStatus calcBeforeState()
    {
        boolean breakpoint = !loopNode.setSelected( true );
        if( layerIndex == 0 )
        {
            if( nodeIndex == 0 )
            {
                loopNode.setSelected( false );
                return StageStatus.FINISHED;
            }
        }
        nodeIndex--;
        if( nodeIndex < 0 )
        {
            layerIndex--;
            backwards.get( 0 ).reverse();
            backwards.remove( 0 );
            nodeIndex = graph.getContainedLayers().get( calcLayerIndex() ).size() - 1;
        }
        if( breakpoint )
            return StageStatus.BREAKPOINT;
        return StageStatus.UNFINISHED;
    }

    @Override
    public PseudoCodeNode createPseudocodeTree( JTree tree ) {
        PseudoCodeNode root = new PseudoCodeNode( "Vertical alignment", tree );
        loopNode = new PseudoCodeNode( "Loop through all nodes...", tree );
        do {
            LayeredGraphNode current = graph.getContainedLayers().get( calcLayerIndex() ).get( calcNodeIndex( nodeIndex ) );
            if( current.getContainedNodes().size() > 0 )
            {
                ExtremalLayoutCalc extcalc = new ExtremalLayoutCalc( layout, current );
                PseudoCodeNode subNode = extcalc.createPseudocodeTree( loopNode.getTree() );
                loopNode.add( subNode );
                subgraphAlgs.get( calcLayerIndex() ).set( calcNodeIndex( nodeIndex ), extcalc );
                subgraphNodes.get( calcLayerIndex() ).set( calcNodeIndex( nodeIndex ), subNode );
            }
        } while( calcNextState() != StageStatus.FINISHED );
        layerIndex = 0;
        nodeIndex = 0;
        backwards.clear();
        root.add( loopNode );
        return root;
    }

    @Override
    public StageStatus forwardStepOver() {
        if( !inside )
            return forwardStep();
        else
        {
            boolean breakpoint = false;
            if( !subgraphNodes.get( calcLayerIndex() ).get( calcNodeIndex( nodeIndex ) ).isSelected() )
                breakpoint |= !subgraphNodes.get( calcLayerIndex() ).get( calcNodeIndex( nodeIndex ) ).setSelected( true );
            switch( subgraphAlgs.get( calcLayerIndex() ).get( calcNodeIndex( nodeIndex ) ).forwardStepOver() )
            {
            case BREAKPOINT:
                return StageStatus.BREAKPOINT;
            case UNFINISHED:
                if( breakpoint )
                    return StageStatus.BREAKPOINT;
                return StageStatus.UNFINISHED;
            case FINISHED:
                inside = false;
                subgraphNodes.get( calcLayerIndex() ).get( calcNodeIndex( nodeIndex ) ).setSelected( false );
                break;
            }
            return StageStatus.UNFINISHED;
        }
    }

    @Override
    public StageStatus forwardStepOut() {
        if( !inside )
        {
            StageStatus status = StageStatus.UNFINISHED;
            while( status == StageStatus.UNFINISHED )
                status = forwardStep();
            return status;
        }
        else
        {
            boolean breakpoint = false;
            if( !subgraphNodes.get( calcLayerIndex() ).get( calcNodeIndex( nodeIndex ) ).isSelected() )
                breakpoint |= !subgraphNodes.get( calcLayerIndex() ).get( calcNodeIndex( nodeIndex ) ).setSelected( true );
            switch( subgraphAlgs.get( calcLayerIndex() ).get( calcNodeIndex( nodeIndex ) ).forwardStepOut() )
            {
            case BREAKPOINT:
                return StageStatus.BREAKPOINT;
            case UNFINISHED:
                if( breakpoint )
                    return StageStatus.BREAKPOINT;
                return StageStatus.UNFINISHED;
            case FINISHED:
                inside = false;
                subgraphNodes.get( calcLayerIndex() ).get( calcNodeIndex( nodeIndex ) ).setSelected( false );
                break;
            }
            return StageStatus.UNFINISHED;
        }
    }

    @Override
    public StageStatus backwardStepOver() {
        if( !inside )
            return backwardStep();
        else
        {
            boolean breakpoint = false;
            if( !subgraphNodes.get( calcLayerIndex() ).get( calcNodeIndex( nodeIndex ) ).isSelected() )
                breakpoint |= !subgraphNodes.get( calcLayerIndex() ).get( calcNodeIndex( nodeIndex ) ).setSelected( true );
            switch( subgraphAlgs.get( calcLayerIndex() ).get( calcNodeIndex( nodeIndex ) ).backwardStepOver() )
            {
            case BREAKPOINT:
                return StageStatus.BREAKPOINT;
            case UNFINISHED:
                LayeredGraphNode current = graph.getContainedLayers().get( calcLayerIndex() ).get( nodeIndex );
                current.setSelected( layout );
                if( breakpoint )
                    return StageStatus.BREAKPOINT;
                return StageStatus.UNFINISHED;
            case FINISHED:
                inside = false;
                subgraphNodes.get( calcLayerIndex() ).get( calcNodeIndex( nodeIndex ) ).setSelected( false );
                break;
            }
            return StageStatus.UNFINISHED;
        }
    }

    @Override
    public StageStatus backwardStepOut() {
        if( !inside )
        {
            StageStatus status = StageStatus.UNFINISHED;
            while( status == StageStatus.UNFINISHED )
                status = backwardStep();
            return status;
        }
        else
        {
            boolean breakpoint = false;
            if( !subgraphNodes.get( calcLayerIndex() ).get( calcNodeIndex( nodeIndex ) ).isSelected() )
                breakpoint |= !subgraphNodes.get( calcLayerIndex() ).get( calcNodeIndex( nodeIndex ) ).setSelected( true );
            switch( subgraphAlgs.get( calcLayerIndex() ).get( calcNodeIndex( nodeIndex ) ).backwardStepOut() )
            {
            case BREAKPOINT:
                return StageStatus.BREAKPOINT;
            case UNFINISHED:
                LayeredGraphNode current = graph.getContainedLayers().get( calcLayerIndex() ).get( nodeIndex );
                current.setSelected( layout );
                if( breakpoint )
                    return StageStatus.BREAKPOINT;
                return StageStatus.UNFINISHED;
            case FINISHED:
                inside = false;
                subgraphNodes.get( calcLayerIndex() ).get( calcNodeIndex( nodeIndex ) ).setSelected( false );
                break;
            }
            return StageStatus.UNFINISHED;
        }
    }
}