123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222 |
- package bk;
- import javax.swing.JTree;
- import codeline.CodeLine;
- import codeline.DeclareVariable;
- import codeline.FunctionCall;
- import codeline.FunctionDefinition;
- import codeline.Comment;
- import codeline.SetVariable;
- import graph.LayeredGraphNode;
- import lib.TextLayoutHelper;
- import processor.ControlFlow;
- import processor.Memory;
- import processor.PseudoCodeNode;
- import processor.Memory.ReadOnlyMemory;
- import processor.Memory.Visibility;
- /**
- * The BK node placement algorithm.
- * @author kolja
- *
- */
- public class BKNodePlacement {
- /**
- * A stage of the BK node placement algorithm.
- * @author kolja
- *
- */
- public enum Stage
- {
- CONFLICT_DETECTION,
- LEFTMOST_UPPER,
- RIGHTMOST_UPPER,
- LEFTMOST_LOWER,
- RIGHTMOST_LOWER,
- COMBINE
- }
- private Stage stage;
-
- public BKNodePlacement() {
- stage = Stage.CONFLICT_DETECTION;
- }
-
- public Stage getAlgorithmState()
- {
- return stage;
- }
- /**
- * creates the pseudo code for the whole bk node placement algorithm
- * @param tree the tree where the code will be shown
- * @return the root/starting point of the pseudo code
- */
- public PseudoCodeNode createPseudocodeTree( JTree tree )
- {
- // Liste mit Variablen die eine andere Farbe im Code bekommen sollen
- String[] vars = { "layout", "graph" };
- // Die Mainfunktion des BK Node Placement Algorithmus
- PseudoCodeNode mainFunction = new PseudoCodeNode( "function bkNodePlacement( graph )", vars, tree, new FunctionDefinition( new String[]{"graph"} ) );
- PseudoCodeNode root = new PseudoCodeNode( "-- BK Node Placement Algorithm --", vars, tree, new CodeLine() {
- @Override
- public ControlFlow runForward(Memory m) {
- if( m.isDefined( "Called", Visibility.GLOBAL ) )
- {
- actions.push( (Memory mem) -> {} );
- return new ControlFlow( ControlFlow.STEP_OVER );
- }
- m.declare( "param1", m.read( "graph", Visibility.GLOBAL ), Visibility.GLOBAL ); // schreibe den Graph in die Globalen Parameter Register des Speichers
- m.declare( "Called", true, Visibility.GLOBAL );
- actions.push( (Memory mem) -> {
- m.undeclare( "param1", Visibility.GLOBAL );
- m.undeclare( "Called", Visibility.GLOBAL );
- } );
- return new ControlFlow( mainFunction ); // Rufe die Hauptfunktion von BK auf (Jump to mainFunction)
- // Diese lädt den Graph selbstständig aus dem globalen Speicher in ihr neues Stack Frame
- }
- } );
- root.setSelected( true );
- // Erzeuge die Conflict Detection Function
- PseudoCodeNode conflictDetectionFunction = ConflictDetection.mark_conflicts( tree );
- // Funktion zum Berechnen der Layouts
- PseudoCodeNode calcLayout = new PseudoCodeNode( "function calcLayout( layout, graph )", vars, tree, new FunctionDefinition( vars ) );
- // Erzeuge die Funktion zum Kombinieren der LKayouts
- PseudoCodeNode combine = Balancing.combine( tree );
- root.add( mainFunction );
- // Ruft die Konflikt Detection Funktion auf
- mainFunction.add( new PseudoCodeNode( "call detectConflicts( graph )", vars, tree, new FunctionCall( conflictDetectionFunction, new String[]{ "graph" } ) ) );
- // Setze das aktuelle Layout
- mainFunction.add( new PseudoCodeNode( "layout = 'RIGHTMOST_LOWER'", vars, tree, new DeclareVariable<String>( "layout" ) {
- @Override
- protected String value(ReadOnlyMemory m) {
- return "RIGHTMOST_LOWER";
- }
- }) );
- // Rufe die Funktion zum Berechnen des Layouts auf
- mainFunction.add( new PseudoCodeNode( "call calcLayout( layout, graph )", vars, tree, new FunctionCall( calcLayout, new String[]{ "layout", "graph" } ) ) );
- mainFunction.add( new PseudoCodeNode( "layout = 'LEFTMOST_LOWER'", vars, tree, new SetVariable<String>( "layout" ) {
- @Override
- protected String value(ReadOnlyMemory m) {
- return "LEFTMOST_LOWER";
- }
- }));
- mainFunction.add( new PseudoCodeNode( "call calcLayout( layout, graph )", vars, tree, new FunctionCall( calcLayout, new String[]{ "layout", "graph" } ) ) );
- mainFunction.add( new PseudoCodeNode( "layout = 'RIGHTMOST_UPPER'", vars, tree, new SetVariable<String>( "layout" ) {
- @Override
- protected String value(ReadOnlyMemory m) {
- return "RIGHTMOST_UPPER";
- }
- }) );
- mainFunction.add( new PseudoCodeNode( "call calcLayout( layout, graph )", vars, tree, new FunctionCall( calcLayout, new String[]{ "layout", "graph" } ) ) );
- mainFunction.add( new PseudoCodeNode( "layout = 'LEFTMOST_UPPER'", vars, tree, new SetVariable<String>( "layout" ) {
- @Override
- protected String value(ReadOnlyMemory m) {
- return "LEFTMOST_UPPER";
- }
- }) );
- mainFunction.add( new PseudoCodeNode( "call calcLayout( layout, graph )", vars, tree, new FunctionCall( calcLayout, new String[]{ "layout", "graph" } ) ) );
- // Rufe die Funktion zum Berechnen des Kombinierten Layouts auf
- mainFunction.add( new PseudoCodeNode( "call combine( graph )", vars, tree, new FunctionCall( combine, new String[]{ "graph" } ) ) );
- PseudoCodeNode conflictsStage = new PseudoCodeNode( "-- mark type 1 conflicts --", vars, tree, new Comment() ) {
- private static final long serialVersionUID = 1041941539437672704L;
- @Override
- public String getDebugOutput( Memory m ) {
- stage = Stage.CONFLICT_DETECTION;
- return ConflictDetection.buildDebugString( m );
- }
- };
- root.add( conflictsStage );
- conflictsStage.add( conflictDetectionFunction );
- // Erzeuge die Funktion zum berechnen der Blöcke
- PseudoCodeNode blockCalc = VerticalAligment.calculateBlockGraph( tree, calcLayout );
- // Erzeuge die Placeblock Function
- PseudoCodeNode placeBlock = PlaceBlock.place_block( tree );
- // Erzeuge die Funktion zum zuweisen der Positionen
- PseudoCodeNode horizontalCompaction = HorizontalCompaction.horizontalCompaction( tree, placeBlock );
- calcLayout.add( new PseudoCodeNode( "call calculateBlockGraph( layout, graph )", vars, tree, new FunctionCall( blockCalc, vars ) ) );
- calcLayout.add( new PseudoCodeNode( "call horizontalCompaction( layout, graph )", vars, tree, new FunctionCall( horizontalCompaction, vars ) ) );
- PseudoCodeNode extremalLayoutStage = new PseudoCodeNode( "-- Compute an extremal layout --", vars, tree, new Comment() ) {
- private static final long serialVersionUID = 4141215748809071958L;
- @Override
- public String getDebugOutput( Memory m ) { // Debug Text für die Layout Berechnungs Phase
- if( !m.isSomewhereDefined( "graph", Visibility.COMPLETE_STACK ) || !m.isSomewhereDefined( "layout", Visibility.COMPLETE_STACK ) )
- return "";
- String info = "| Node | Shift | Sink | Root | Align | x | xDef |\n";
- info += "|------|-------|------|------|-------|-----|--------|\n";
- LayeredGraphNode graph = m.read( "graph", Visibility.COMPLETE_STACK );
- LayoutType type = LayoutType.fromString( m.read( "layout", Visibility.COMPLETE_STACK ) );
- switch( type ) { // Aktualisierung des aktuellen Zustandes des Algorithmus (Wird zum Zeichnen des richtigen Layouts benötigt)
- case LEFTMOST_UPPER:
- stage = Stage.LEFTMOST_UPPER;
- break;
- case RIGHTMOST_UPPER:
- stage = Stage.RIGHTMOST_UPPER;
- break;
- case LEFTMOST_LOWER:
- stage = Stage.LEFTMOST_LOWER;
- break;
- case RIGHTMOST_LOWER:
- stage = Stage.RIGHTMOST_LOWER;
- break;
- case COMBINED: // this will never happen here
- assert false;
- break;
- default:
- assert false;
- break;
- }
- for( LayeredGraphNode n : graph.getContainedNodes() )
- {
- info += "|" + TextLayoutHelper.strToLen( n.toString(), 6 ) +
- "|" + TextLayoutHelper.strToLen( n.getShift( type ) + "", 7 ) +
- "|" + TextLayoutHelper.strToLen( n.getSink( type ).toString(), 6 ) +
- "|" + TextLayoutHelper.strToLen( n.getRoot( type ).toString(), 6 ) +
- "|" + TextLayoutHelper.strToLen( n.getAlign( type ).toString(), 7 ) +
- "|" + TextLayoutHelper.strToLen( n.getX( type ) + "", 5 ) +
- "|" + TextLayoutHelper.strToLen( !n.isXUndefined( type ) + "", 8 ) + "|\n";
- }
- return info;
- }
- };
- root.add( extremalLayoutStage );
- extremalLayoutStage.add( calcLayout );
- extremalLayoutStage.add( new PseudoCodeNode( "-- vertical alignment --", vars, tree, new Comment() ) );
- extremalLayoutStage.add( blockCalc );
- extremalLayoutStage.add( new PseudoCodeNode( "-- horizontal compaction --", vars, tree, new Comment() ) );
- extremalLayoutStage.add( horizontalCompaction );
- extremalLayoutStage.add( placeBlock );
- PseudoCodeNode balancingStage = new PseudoCodeNode( "-- balancing --", vars, tree, new Comment() ) {
- private static final long serialVersionUID = 4212377075998840086L;
- @Override
- public String getDebugOutput( Memory m ) { // Debug Text für die Berechnung des kombinierten Layouts
- stage = Stage.COMBINE;
- if( !m.isSomewhereDefined( "graph", Visibility.COMPLETE_STACK ) )
- return "";
- String info = "| Node | x BR | x BL | x UR | x UL | x CO |\n";
- info += "|------|------|------|------|------|------|\n";
- LayeredGraphNode graph = m.read( "graph", Visibility.COMPLETE_STACK );
- for( LayeredGraphNode n : graph.getContainedNodes() )
- {
- info += "|" + TextLayoutHelper.strToLen( n.toString(), 6 ) +
- "|" + TextLayoutHelper.strToLen( n.getX( LayoutType.LEFTMOST_UPPER ) + "", 6 ) +
- "|" + TextLayoutHelper.strToLen( n.getX( LayoutType.RIGHTMOST_UPPER ) + "", 6 ) +
- "|" + TextLayoutHelper.strToLen( n.getX( LayoutType.LEFTMOST_LOWER ) + "", 6 ) +
- "|" + TextLayoutHelper.strToLen( n.getX( LayoutType.RIGHTMOST_LOWER ) + "", 6 ) +
- "|" + TextLayoutHelper.strToLen( n.getX( LayoutType.COMBINED ) + "", 6 ) + "|\n";
- }
- return info;
- }
- };
- root.add( balancingStage );
- balancingStage.add( combine );
- return root;
- }
- }
|