NodeShuffler/src/bk/ConflictDetection.java

package bk;

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

import javax.swing.JTree;

import bk.LayoutType;
import codeline.CodeLine;
import codeline.Comment;
import codeline.DeclareVariable;
import codeline.ForEachLoop;
import codeline.ForLoop;
import codeline.FunctionCall;
import codeline.FunctionDefinition;
import codeline.IfLoop;
import codeline.SetVariable;
import codeline.WhileLoop;
import graph.LayeredGraphEdge;
import graph.LayeredGraphNode;
import lib.TextLayoutHelper;
import processor.ControlFlow;
import processor.Memory;
import processor.PseudoCodeNode;
import processor.Memory.ReadOnlyMemory;
import processor.Memory.Visibility;

/**
 * the preprocessing stage of the bk node placement algorithm
 * 
 * @author kolja and eren
 *
 */
public class ConflictDetection {
    
    /**
     * return a debug string containing a table of variables and their values
     * @param m the memory which contains the variables
     * @return the table
     */
    public static String buildDebugString( Memory m ) {
        if( m.isSomewhereDefined( "l", Visibility.LOCAL ) && m.isSomewhereDefined( "i", Visibility.LOCAL ) &&
                m.<Integer>read( "l", Visibility.LOCAL ) < m.<LayeredGraphNode>read( "graph", Visibility.LOCAL).getContainedLayers().get( m.<Integer>read( "i", Visibility.LOCAL ) + 1 ).size() )
            m.<LayeredGraphNode>read( "graph", Visibility.LOCAL).getContainedLayers().get(m.<Integer>read( "i", Visibility.LOCAL ) + 1).get(m.<Integer>read( "l", Visibility.LOCAL )).setSelected(null);
        
        if( m.isSomewhereDefined( "i", Visibility.LOCAL ) && m.isSomewhereDefined( "l1", Visibility.LOCAL ) &&
                m.<Integer>read( "l1", Visibility.LOCAL ) < m.<LayeredGraphNode>read( "graph", Visibility.LOCAL).getContainedLayers().get(m.<Integer>read( "i", Visibility.LOCAL ) + 1).size() ) {
            m.<LayeredGraphNode>read( "graph", Visibility.LOCAL).getContainedLayers().get(m.<Integer>read( "i", Visibility.LOCAL ) + 1).get(m.<Integer>read( "l1", Visibility.LOCAL )).setSelected(null);
        }
        
        if( m.isSomewhereDefined( "i", Visibility.LOCAL ) && m.isSomewhereDefined( "k0", Visibility.LOCAL ) &&
                m.<Integer>read( "k0", Visibility.LOCAL ) <  m.<LayeredGraphNode>read( "graph", Visibility.LOCAL).getContainedLayers().get(m.read( "i", Visibility.LOCAL )).size()) {
            m.<LayeredGraphNode>read( "graph", Visibility.LOCAL).getContainedLayers().get(m.read( "i", Visibility.LOCAL )).get(m.<Integer>read( "k0", Visibility.LOCAL )).setSelected(null);
        }
        
        if( m.isSomewhereDefined( "i", Visibility.LOCAL ) && m.isSomewhereDefined( "k1", Visibility.LOCAL ) &&
                m.<Integer>read( "k1", Visibility.LOCAL ) < m.<LayeredGraphNode>read( "graph", Visibility.LOCAL).getContainedLayers().get(m.read( "i", Visibility.LOCAL )).size() ) {
            m.<LayeredGraphNode>read( "graph", Visibility.LOCAL).getContainedLayers().get(m.read( "i", Visibility.LOCAL )).get(m.<Integer>read( "k1", Visibility.LOCAL )).setSelected(null);
        }
        
        if( m.isSomewhereDefined( "n", Visibility.LOCAL ) )
        {
            m.<LayeredGraphNode>read( "n", Visibility.LOCAL ).setSelected( null );
        }
        String info = "| i  | l  | l1 | k0 | k1 |  v  |  n  |\n";
        info +=       "|----|----|----|----|----|-----|-----|\n";
        String i = "null";
        String l = "null";
        String l1 = "null";
        String k0 = "null";
        String k1 = "null";
        String v = "null";
        String n = "null";
        if( m.isSomewhereDefined( "i", Visibility.LOCAL ) )
            i = "" + m.<Integer>read( "i", Visibility.LOCAL );
        if( m.isSomewhereDefined( "l", Visibility.LOCAL ) )
            l = "" + m.<Integer>read( "l", Visibility.LOCAL );
        if( m.isSomewhereDefined( "l1", Visibility.LOCAL ) )
            l1 = "" + m.<Integer>read( "l1", Visibility.LOCAL );
        if( m.isSomewhereDefined( "k0", Visibility.LOCAL ) )
            k0 = "" + m.<Integer>read( "k0", Visibility.LOCAL );
        if( m.isSomewhereDefined( "k1", Visibility.LOCAL ) )
            k1 = "" + m.<Integer>read( "k1", Visibility.LOCAL );
        if( m.isSomewhereDefined( "v", Visibility.LOCAL ) && m.<LayeredGraphEdge>read( "v", Visibility.LOCAL ).getSources().get( 0 ).toString() != null )
            v = "" + m.<LayeredGraphEdge>read( "v", Visibility.LOCAL ).getSources().get( 0 ).toString();
        if( m.isSomewhereDefined( "n", Visibility.LOCAL ) && m.<LayeredGraphNode>read( "n", Visibility.LOCAL ).toString() != null )
            n = "" + m.<LayeredGraphNode>read( "n", Visibility.LOCAL ).toString();
        info += "|" + TextLayoutHelper.strToLen( i, 4 ) + 
                "|" + TextLayoutHelper.strToLen( l, 4 ) + 
                "|" + TextLayoutHelper.strToLen( l1, 4 ) + 
                "|" + TextLayoutHelper.strToLen( k0, 4 ) + 
                "|" + TextLayoutHelper.strToLen( k1, 4 ) + 
                "|" + TextLayoutHelper.strToLen( v, 5 ) + 
                "|" + TextLayoutHelper.strToLen( n, 5 ) + "|\n";
        return info;
    }
    
    /**
     * creates the pseudo code for the conflict detection stage
     * @param tree the tree where the code will be displayed
     * @return the code
     */
    public static PseudoCodeNode mark_conflicts(JTree tree) {
        String[] vars = { "i", "L", "k0", "l", "l1", "k1", "v", "graph", "n" };
        String[] params = { "graph" };
        // Erstelle die mark Conflicts Funktion
        PseudoCodeNode root = new PseudoCodeNode( "function mark_conflicts( graph )", vars, tree, new FunctionDefinition( params ) );
        PseudoCodeNode text = new PseudoCodeNode( "-- mark conflicts in subgraphs --", vars, tree, new Comment() );
        root.add( text );
        // Für jeden Knoten im Graphen
        PseudoCodeNode foreach = new PseudoCodeNode( "foreach n in graph.getContainedNodes() do", vars, tree, new ForEachLoop<LayeredGraphNode>( "n" ) {
			@Override
			protected List<LayeredGraphNode> list(ReadOnlyMemory m) {
				return m.<LayeredGraphNode>read( "graph", Visibility.LOCAL ).getContainedNodes();
			}
        } );
        root.add( foreach );
        // Falls der Knoten einen Subgraphen hat
        PseudoCodeNode ifNode = new PseudoCodeNode( "if n has subgraph then", vars, tree, new IfLoop() {
			@Override
			protected boolean condition(ReadOnlyMemory m) {
				return m.<LayeredGraphNode>read( "n", Visibility.LOCAL ).getContainedLayers().size() > 0;
			}
        } );
        foreach.add( ifNode );
        // Rufe die Funktion rekursiv für den Subgraphen auf
        PseudoCodeNode call = new PseudoCodeNode( "call mark_conflicts( n );", vars, tree, new FunctionCall( root, new String[]{ "n" } ) );
        ifNode.add( call );
        text = new PseudoCodeNode( "-- mark conflicts in graph --", vars, tree, new Comment() );
        root.add( text );
        // Speichere die Layer in einer lokalen Variable
        PseudoCodeNode init = 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", Visibility.LOCAL ).getContainedLayers();
            }
        } );
        root.add( init );
        // Für jeden Layerindex vom 2. bis zum vorletzten (nur hier können innere Segmente auftreten)
        PseudoCodeNode outerLoop = new PseudoCodeNode( "for i=1 to |L|-2 do", vars, tree, new ForLoop( "i" ) {
			@Override
			protected int minimum( ReadOnlyMemory m ) {
				return 1;
			}
			@Override
			protected int maximum( ReadOnlyMemory m ) {
				return m.<ArrayList<ArrayList<LayeredGraphNode>>>read( "L", Visibility.LOCAL ).size() - 2;
			}
        } );
        root.add( outerLoop );
        // Initialisiere lokale Variablen
        PseudoCodeNode line = new PseudoCodeNode( "k0 = 0; l = 0;", vars, tree, new CodeLine() {
			@Override
			public ControlFlow runForward(Memory m) {
				m.declare( "k0", 0, Visibility.LOCAL ); // deklariere die Variablen im aktuellen Stack Frame
				m.declare( "l", 0, Visibility.LOCAL );
				actions.push( (Memory mem) -> { // Merkt sich die Rückgängig-mach-Aktion
					mem.undeclare( "k0", Visibility.LOCAL );
					mem.undeclare( "l", Visibility.LOCAL );
				} );
				return new ControlFlow( ControlFlow.STEP_OVER );
			}
        } );
        outerLoop.add( line );
        // Für eine genauere Beschreibung des Algoritmus zum markieren von Konflikten siehe Karstens Paper (link in Dokumentation)
        PseudoCodeNode innerLoop = new PseudoCodeNode( "for l1=0 to |L[i+1]|-1 do", vars, tree, new ForLoop( "l1" ) {
			@Override
			protected int minimum(ReadOnlyMemory m) {
				return 0;
			}
			@Override
			protected int maximum(ReadOnlyMemory m) {
				return m.<ArrayList<ArrayList<LayeredGraphNode>>>read( "L", Visibility.LOCAL ).get( m.<Integer>read( "i", Visibility.LOCAL ) + 1 ).size() - 1;
			}
        } );
        outerLoop.add( innerLoop );
        ifNode = new PseudoCodeNode( "if l1==|L[i+1]|-1 or L[i+1][l1] incident to inner segment between L[i+1] and L[i] then", vars, tree, new IfLoop() {
			@Override
			protected boolean condition(ReadOnlyMemory m) {
	            return m.<Integer>read( "l1", Visibility.LOCAL ) == m.<LayeredGraphNode>read( "graph", Visibility.LOCAL ).getContainedLayers().get( m.<Integer>read( "i", Visibility.LOCAL ) + 1).size() - 1 ||
	            		incidentToInnerSegmentBetweenLiPlusOneAndLi( m );
			}
        } );
        innerLoop.add( ifNode );
        line = new PseudoCodeNode( "k1 = |L[i]|-1;", vars, tree, new DeclareVariable<Integer>( "k1" ) {
			@Override
			protected Integer value(ReadOnlyMemory m) {
				return (int)m.<ArrayList<ArrayList<LayeredGraphNode>>>read( "L", Visibility.LOCAL ).get( m.read( "i", Visibility.LOCAL ) ).size() - 1;
			}
        } );
        ifNode.add( line );
        PseudoCodeNode innerIfNode = new PseudoCodeNode( "if L[i+1][l1] incident to inner segment between L[i+1] and L[i] then", vars, tree, new IfLoop() {
			@Override
			protected boolean condition(ReadOnlyMemory m) {
				return incidentToInnerSegmentBetweenLiPlusOneAndLi( m ); // Prüfe ob ein inneres Segment da ist
			}
		} );
        ifNode.add( innerIfNode );
        
        line = new PseudoCodeNode( "k1 = pos(pred(L[i+1][l1])[0]);", vars, tree, new SetVariable<Integer>( "k1" ) {
			@Override
			protected Integer value(ReadOnlyMemory m) {
				return (int)m.<LayeredGraphNode>read( "graph", Visibility.LOCAL ).getContainedLayers().get( m.read( "i", Visibility.LOCAL ) ).indexOf(
						m.<LayeredGraphNode>read( "graph", Visibility.LOCAL ).getContainedLayers().get( m.<Integer>read( "i", Visibility.LOCAL ) + 1 ).get( m.read( "l1", Visibility.LOCAL ) ).getSortedIncomingEdges().get( 0 ).getSources().get( 0 ) );
			}
        } );
        innerIfNode.add( line );
        PseudoCodeNode whileLoop = new PseudoCodeNode( "while l <= l1 do", vars, tree, new WhileLoop() {
			@Override
			protected boolean condition( ReadOnlyMemory m ) {
				return m.<Integer>read( "l", Visibility.LOCAL ) <= m.<Integer>read( "l1", Visibility.LOCAL );
			}
        } );
        ifNode.add( whileLoop );
        foreach = new PseudoCodeNode( "foreach v in pred(L[i+1][l]) do", vars, tree, new ForEachLoop<LayeredGraphEdge>( "v" ) {
			@Override
			protected List<LayeredGraphEdge> list(ReadOnlyMemory m) {
				return m.<LayeredGraphNode>read( "graph", Visibility.LOCAL ).getContainedLayers().get( m.<Integer>read( "i", Visibility.LOCAL ) + 1 ).get( m.read( "l", Visibility.LOCAL ) ).getIncomingEdges();
			}
        } );
        whileLoop.add( foreach );
        innerIfNode = new PseudoCodeNode( "if pos(v) < k0 or pos(v) > k1 then", vars, tree, new IfLoop() {
			@Override
			protected boolean condition(ReadOnlyMemory m) {
			    int k = m.<LayeredGraphNode>read( "graph", Visibility.LOCAL ).getContainedLayers().get( m.read( "i", Visibility.LOCAL ) ).indexOf( m.<LayeredGraphEdge>read( "v", Visibility.LOCAL ).getSources().get( 0 ) );
				return k < m.<Integer>read( "k0", Visibility.LOCAL ) || k > m.<Integer>read( "k1", Visibility.LOCAL );
			}
        } );
        foreach.add( innerIfNode );
        line = new PseudoCodeNode( "mark segment (v,L[i+1][l]);", vars, tree, new CodeLine() {
			@Override
			public ControlFlow runForward(Memory m) {
				LayeredGraphEdge e = m.read( "v", Visibility.LOCAL );
				boolean old = e.isConflicted( LayoutType.LEFTMOST_UPPER );
				e.setConflicted( true, null ); // Markiere die Kante als Konflicted
				actions.add( (Memory mem) -> {
					e.setConflicted( old, null ); // Rückwärts
				});
				return new ControlFlow( ControlFlow.STEP_OVER );
			}
        } );
        innerIfNode.add( line );
        line = new PseudoCodeNode( "l = l+1;", vars, tree, new SetVariable<Integer>( "l" ) {
			@Override
			protected Integer value(ReadOnlyMemory m) {
				return (int)m.<Integer>read( "l", Visibility.LOCAL ) + 1;
			}
        } );
        whileLoop.add( line );
        line = new PseudoCodeNode( "k0 = k1;", vars, tree, new SetVariable<Integer>( "k0" ) {
			@Override
			protected Integer value(ReadOnlyMemory m) {
				return (int)m.<Integer>read( "k1", Visibility.LOCAL );
			}
        } );
        ifNode.add( line );
        return root;
    }
    
    // Sucht nach Inneren Segmenten
    private static boolean incidentToInnerSegmentBetweenLiPlusOneAndLi( ReadOnlyMemory m ) {
        LayeredGraphNode curr = m.<LayeredGraphNode>read( "graph", Visibility.LOCAL ).getContainedLayers().get( m.<Integer>read( "i", Visibility.LOCAL ) + 1 ).get( m.read( "l1", Visibility.LOCAL ) );
        for (LayeredGraphEdge e : curr.getIncomingEdges()) {
            if (e.isDummyEdge()) {
                return true;
            }
        }
        return false;
    }
}