NodeShuffler/src/bk/BlockCalc.java

package bk;

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

import javax.swing.JTree;

import animation.CodeLine;
import animation.ControlFlow;
import animation.Memory;
import animation.PseudoCodeNode;
import animation.Memory.MemoryType;
import animation.Memory.ReadOnlyMemory;
import codelines.AbstractForLoop;
import codelines.DeclareVariable;
import codelines.ForEachLoop;
import codelines.FunctionCall;
import codelines.FunctionDefinition;
import codelines.IfLoop;
import codelines.SetVariable;
import graph.LayeredGraphEdge;
import graph.LayeredGraphNode;

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

    public static PseudoCodeNode calculateBlockGraph( JTree tree, PseudoCodeNode claclLayout ) {
        String[] vars = { "graph", "L", "r", "neighbors", "layout", "m", "i", "k", "mids", "n" };
        @SuppressWarnings("serial")
        PseudoCodeNode root = new PseudoCodeNode( "function calculateBlockGraph( layout, graph )", vars, tree, new FunctionDefinition( new String[]{ "layout", "graph" } ) ) {
            @Override
            public String getDebugOutput( Memory m )
            {
                if( m.isSomewhereDefined( "n", MemoryType.LOCAL ) )
                    m.<LayeredGraphNode>read( "n", MemoryType.LOCAL).setSelected( LayoutType.fromString( m.read( "layout", MemoryType.LOCAL ) ) );
                return super.getDebugOutput( m );
            }
        };
        root.add( new PseudoCodeNode( "L = graph.getContainedLayers();", vars, tree, new DeclareVariable<ArrayList<ArrayList<LayeredGraphNode>>>( "L" ) {
            @Override
            protected ArrayList<ArrayList<LayeredGraphNode>> value(ReadOnlyMemory m) {
                return m.<LayeredGraphNode>read( "graph", MemoryType.LOCAL ).getContainedLayers();
            }
        } ) );
        PseudoCodeNode layerLoop = new PseudoCodeNode( "for i=layout.contains('DOWN') ? 0 : |L|-1 to layout.contains('DOWN') ? |L|-1 : 0 do", vars, tree, new AbstractForLoop<Integer>( "i" ) {
            @Override
            protected Integer begin(ReadOnlyMemory m) {
                if( m.<String>read( "layout", MemoryType.LOCAL ).contains( "DOWN" ) )
                    return 0;
                return m.<ArrayList<ArrayList<LayeredGraphNode>>>read( "L", MemoryType.LOCAL ).size() - 1;
            }
            @Override
            protected Integer step(ReadOnlyMemory m) {
                if( m.<String>read( "layout", MemoryType.LOCAL ).contains( "DOWN" ) )
                    return m.<Integer>read( "i", MemoryType.LOCAL ) + 1;
                return m.<Integer>read( "i", MemoryType.LOCAL ) - 1;
            }
            @Override
            protected boolean condition(ReadOnlyMemory m) {
                if( m.<String>read( "layout", MemoryType.LOCAL ).contains( "DOWN" ) )
                    return m.<Integer>read( "i", MemoryType.LOCAL ) <= m.<ArrayList<ArrayList<LayeredGraphNode>>>read( "L", MemoryType.LOCAL ).size() - 1;
                return m.<Integer>read( "i", MemoryType.LOCAL ) >= 0;
            }
        });
        root.add( layerLoop );
        layerLoop.add( new PseudoCodeNode( "r = layout.contains('RIGHT') ? -1 : INFINITY;", vars, tree, new DeclareVariable<Double>( "r" ) {
            @Override
            protected Double value(ReadOnlyMemory m) {
                if( m.<String>read( "layout", MemoryType.LOCAL ).contains( "RIGHT" ) )
                    return -1.0;
                return Double.POSITIVE_INFINITY;
            }
        } ) );
        PseudoCodeNode nodeLoop = new PseudoCodeNode( "for k=layout.contains('RIGHT') ? 0 : |L[i]|-1 to layout.contains('RIGHT') ? |L[i]|-1 : 0 do", vars, tree, new AbstractForLoop<Integer>( "k" ) {
            @Override
            protected Integer begin( ReadOnlyMemory m) {
                if( m.<String>read( "layout", MemoryType.LOCAL ).contains( "RIGHT" ) )
                    return 0;
                return m.<ArrayList<ArrayList<LayeredGraphNode>>>read( "L", MemoryType.LOCAL ).get( m.read( "i", MemoryType.LOCAL ) ).size() - 1;
            }
            @Override
            protected Integer step( ReadOnlyMemory m) {
                if( m.<String>read( "layout", MemoryType.LOCAL ).contains( "RIGHT" ) )
                    return m.<Integer>read( "k", MemoryType.LOCAL ) + 1;
                return m.<Integer>read( "k", MemoryType.LOCAL ) - 1;
            }
            @Override
            protected boolean condition( ReadOnlyMemory m) {
                if( m.<String>read( "layout", MemoryType.LOCAL ).contains( "RIGHT" ) )
                    return m.<Integer>read( "k", MemoryType.LOCAL ) <= m.<ArrayList<ArrayList<LayeredGraphNode>>>read( "L", MemoryType.LOCAL ).get( m.read( "i", MemoryType.LOCAL ) ).size() - 1;
                return m.<Integer>read( "k", MemoryType.LOCAL ) >= 0;
            }
        });
        nodeLoop.add( new PseudoCodeNode( "n = L[i][k];", vars, tree, new DeclareVariable<LayeredGraphNode>( "n" ) {
            @Override
            protected LayeredGraphNode value(ReadOnlyMemory m) {
                return m.<ArrayList<ArrayList<LayeredGraphNode>>>read( "L", MemoryType.LOCAL ).get( m.read( "i", MemoryType.LOCAL ) ).get( m.read( "k", MemoryType.LOCAL ) );
            }
        }));
        PseudoCodeNode ifNode = new PseudoCodeNode( "if n has subgraph then", vars, tree, new IfLoop() {
            @Override
            protected boolean condition(ReadOnlyMemory m) {
                return m.<LayeredGraphNode>read( "n", MemoryType.LOCAL ).getContainedNodes().size() > 0;
            }
        } );
        nodeLoop.add( ifNode );
        ifNode.add( new PseudoCodeNode( "call calcLayout( layout, n );", vars, tree, new FunctionCall( claclLayout, new String[]{ "layout", "n" } ) ) );
        nodeLoop.add( new PseudoCodeNode( "neighbors = layout.contains('DOWN') ? predecessors(n) : successors(n)", vars, tree, new DeclareVariable<ArrayList<LayeredGraphNode>>( "neighbors" ) {
            @Override
            protected ArrayList<LayeredGraphNode> value(ReadOnlyMemory m) {
                ArrayList<LayeredGraphEdge> list = m.<LayeredGraphNode>read( "n", MemoryType.LOCAL ).getSortedOutgoingEdges();
                if( m.<String>read( "layout", MemoryType.LOCAL ).contains( "DOWN" ) )
                    list = m.<LayeredGraphNode>read( "n", MemoryType.LOCAL ).getSortedIncomingEdges();
                ArrayList<LayeredGraphNode> result = new ArrayList<LayeredGraphNode>();
                for( LayeredGraphEdge e : list )
                {
                    if( m.<String>read( "layout", MemoryType.LOCAL ).contains( "DOWN" ) )
                        result.add( e.getSources().get( 0 ) );
                    else
                        result.add( e.getTargets().get( 0 ) );
                }
                return result;
            }
        } ) );
        layerLoop.add( nodeLoop );
        nodeLoop.add( new PseudoCodeNode( "neighbors = layout.contains('RIGHT') ? neighbors : reverse( neighbors )", vars, tree, new SetVariable<ArrayList<LayeredGraphNode>>( "neighbors" ) {
            @Override
            protected ArrayList<LayeredGraphNode> value(ReadOnlyMemory m) {
                ArrayList<LayeredGraphNode> list = m.read( "neighbors", MemoryType.LOCAL );
                if( m.<String>read( "layout", MemoryType.LOCAL ).contains( "RIGHT" ) )
                    return list;
                else
                {
                    ArrayList<LayeredGraphNode> result = new ArrayList<LayeredGraphNode>();
                    for( int i = list.size() - 1; i >= 0; i-- )
                        result.add( list.get( i ) );
                    return result;
                }
            }
        } ) );
        PseudoCodeNode ifNeighbors = new PseudoCodeNode( "if |neighbors| > 0 then", vars, tree, new IfLoop() {
            @Override
            protected boolean condition( ReadOnlyMemory m) {
                return m.<ArrayList<LayeredGraphNode>>read( "neighbors", MemoryType.LOCAL ).size() > 0;
            }
        });
        nodeLoop.add( ifNeighbors );
        ifNeighbors.add( new PseudoCodeNode( "mids = [roundDown((|neighbors|-1)/2),roundUp((|neighbors|-1)/2)]", vars, tree, new DeclareVariable<ArrayList<Integer>>( "mids" ) {
            @Override
            protected ArrayList<Integer> value(ReadOnlyMemory m) {
                int size = m.<ArrayList<LayeredGraphNode>>read( "neighbors", MemoryType.LOCAL ).size() - 1;
                int m1 = size / 2, m2 = (int)(size / 2.0 + 0.5);
                ArrayList<Integer> list = new ArrayList<Integer>();
                list.add( m1 );
                if( m1 != m2 )
                    list.add( m2 );
                return list;
            }
        } ) );
        PseudoCodeNode midLoop = new PseudoCodeNode( "foreach m in mids do", vars, tree, new ForEachLoop<Integer>( "m" ) {
            @Override
            protected List<Integer> list(ReadOnlyMemory m) {
                return m.read( "mids", MemoryType.LOCAL );
            }
        } );
        ifNeighbors.add( midLoop );
        PseudoCodeNode ifAlign = new PseudoCodeNode( "if align[n] == n then", vars, tree, new IfLoop() {
            @Override
            protected boolean condition(ReadOnlyMemory m) {
                LayeredGraphNode n = m.read( "n", MemoryType.LOCAL );
                return n.getAlign( LayoutType.fromString( m.read( "layout", MemoryType.LOCAL ) ) ) == n;
            }
        });
        midLoop.add( ifAlign );
        PseudoCodeNode ifMarked = new PseudoCodeNode( "if (neighbors[m],n) not conflicted and ((r < pos(neighbors[m]) and layout.contains('RIGHT')) or (r > pos(neighbors[m]) and layout.contains('LEFT'))) then", vars, tree, new IfLoop() {
            @Override
            protected boolean condition(ReadOnlyMemory m) {
                LayeredGraphEdge e = m.<LayeredGraphNode>read( "graph", MemoryType.LOCAL ).findEdgeBetween(
                        m.<ArrayList<LayeredGraphNode>>read( "neighbors", MemoryType.LOCAL ).get( m.read( "m", MemoryType.LOCAL ) ),
                        m.read( "n", MemoryType.LOCAL ) );
                if( e == null )
                    e = m.<LayeredGraphNode>read( "graph", MemoryType.LOCAL ).findEdgeBetween( m.read( "n", MemoryType.LOCAL ),
                            m.<ArrayList<LayeredGraphNode>>read( "neighbors", MemoryType.LOCAL ).get( m.read( "m", MemoryType.LOCAL ) ) );
                ArrayList<LayeredGraphNode> layerBefore;
                if( m.<String>read( "layout", MemoryType.LOCAL ).contains( "DOWN" ) )
                    layerBefore = m.<ArrayList<ArrayList<LayeredGraphNode>>>read( "L", MemoryType.LOCAL ).get( m.<Integer>read( "i", MemoryType.LOCAL ) - 1 );
                else
                    layerBefore = m.<ArrayList<ArrayList<LayeredGraphNode>>>read( "L", MemoryType.LOCAL ).get( m.<Integer>read( "i", MemoryType.LOCAL ) + 1 );
                int posU = layerBefore.indexOf( m.<ArrayList<LayeredGraphNode>>read( "neighbors", MemoryType.LOCAL ).get( m.read( "m", MemoryType.LOCAL ) ) );
                return !e.isConflicted( LayoutType.fromString( m.read( "layout", MemoryType.LOCAL ) ) ) &&
                        ( ( m.<Double>read( "r", MemoryType.LOCAL ) < posU && m.<String>read( "layout", MemoryType.LOCAL ).contains( "RIGHT" ) ) ||
                                ( m.<Double>read( "r", MemoryType.LOCAL ) > posU && m.<String>read( "layout", MemoryType.LOCAL ).contains( "LEFT" ) ) );
            }
        });
        ifAlign.add( ifMarked );
        ifMarked.add( new PseudoCodeNode( "align[neighbors[m]] = n;", vars, tree, new CodeLine() {
            @Override
            public ControlFlow runForward(Memory m) {
                LayeredGraphNode u = m.<ArrayList<LayeredGraphNode>>read( "neighbors", MemoryType.LOCAL ).get( m.read( "m", MemoryType.LOCAL ) );
                LayeredGraphNode v = m.read( "n", MemoryType.LOCAL );
                LayeredGraphNode old = u.getAlign( LayoutType.fromString( m.read( "layout", MemoryType.LOCAL ) ) );
                u.setAlign( v, LayoutType.fromString( m.read( "layout", MemoryType.LOCAL ) ) );
                actions.push( (Memory mem) -> {
                    u.setAlign( old, LayoutType.fromString( mem.read( "layout", MemoryType.LOCAL ) ) );
                });
                return new ControlFlow( ControlFlow.STEP_OVER );
            }
        }) );
        ifMarked.add( new PseudoCodeNode( "root[n] = root[neighbors[m]];", vars, tree, new CodeLine() {
            @Override
            public ControlFlow runForward(Memory m) {
                LayeredGraphNode u = m.<ArrayList<LayeredGraphNode>>read( "neighbors", MemoryType.LOCAL ).get( m.read( "m", MemoryType.LOCAL ) );
                LayeredGraphNode v = m.read( "n", MemoryType.LOCAL );
                LayeredGraphNode old = v.getRoot( LayoutType.fromString( m.read( "layout", MemoryType.LOCAL ) ) );
                v.setRoot( u.getRoot( LayoutType.fromString( m.read( "layout", MemoryType.LOCAL ) ) ), LayoutType.fromString( m.read( "layout", MemoryType.LOCAL ) ) );
                actions.push( (Memory mem) -> {
                    v.setRoot( old, LayoutType.fromString( m.read( "layout", MemoryType.LOCAL ) ) );
                });
                return new ControlFlow( ControlFlow.STEP_OVER );
            }
        }) );
        ifMarked.add( new PseudoCodeNode( "align[n] = root[n];", vars, tree, new CodeLine() {
            @Override
            public ControlFlow runForward(Memory m) {
                LayeredGraphNode v = m.read( "n", MemoryType.LOCAL );
                LayeredGraphNode old = v.getAlign( LayoutType.fromString( m.read( "layout", MemoryType.LOCAL ) ) );
                v.setAlign( v.getRoot( LayoutType.fromString( m.read( "layout", MemoryType.LOCAL ) ) ), LayoutType.fromString( m.read( "layout", MemoryType.LOCAL ) ) );
                actions.push( (Memory mem) -> {
                    v.setAlign( old, LayoutType.fromString( m.read( "layout", MemoryType.LOCAL ) ) );
                });
                return new ControlFlow( ControlFlow.STEP_OVER );
            }
        }) );
        ifMarked.add( new PseudoCodeNode( "r = pos(neighbors[m]);", vars, tree, new SetVariable<Double>( "r" ) {
            @Override
            protected Double value(ReadOnlyMemory m) {
                ArrayList<LayeredGraphNode> layerBefore;
                if( m.<String>read( "layout", MemoryType.LOCAL ).contains( "DOWN" ) )
                    layerBefore = m.<ArrayList<ArrayList<LayeredGraphNode>>>read( "L", MemoryType.LOCAL ).get( m.<Integer>read( "i", MemoryType.LOCAL ) - 1 );
                else
                    layerBefore = m.<ArrayList<ArrayList<LayeredGraphNode>>>read( "L", MemoryType.LOCAL ).get( m.<Integer>read( "i", MemoryType.LOCAL ) + 1 );
                LayeredGraphNode u = m.<ArrayList<LayeredGraphNode>>read( "neighbors", MemoryType.LOCAL ).get( m.read( "m", MemoryType.LOCAL ) );
                return (double)layerBefore.indexOf( u );
            }
        }) );
        return root;
    }
}