BKNodePlacement.java 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222
  1. package bk;
  2. import javax.swing.JTree;
  3. import codeline.CodeLine;
  4. import codeline.DeclareVariable;
  5. import codeline.FunctionCall;
  6. import codeline.FunctionDefinition;
  7. import codeline.Comment;
  8. import codeline.SetVariable;
  9. import graph.LayeredGraphNode;
  10. import lib.TextLayoutHelper;
  11. import processor.ControlFlow;
  12. import processor.Memory;
  13. import processor.PseudoCodeNode;
  14. import processor.Memory.ReadOnlyMemory;
  15. import processor.Memory.Visibility;
  16. /**
  17. * The BK node placement algorithm.
  18. * @author kolja
  19. *
  20. */
  21. public class BKNodePlacement {
  22. /**
  23. * A stage of the BK node placement algorithm.
  24. * @author kolja
  25. *
  26. */
  27. public enum Stage
  28. {
  29. CONFLICT_DETECTION,
  30. LEFTMOST_UPPER,
  31. RIGHTMOST_UPPER,
  32. LEFTMOST_LOWER,
  33. RIGHTMOST_LOWER,
  34. COMBINE
  35. }
  36. private Stage stage;
  37. public BKNodePlacement() {
  38. stage = Stage.CONFLICT_DETECTION;
  39. }
  40. public Stage getAlgorithmState()
  41. {
  42. return stage;
  43. }
  44. /**
  45. * creates the pseudo code for the whole bk node placement algorithm
  46. * @param tree the tree where the code will be shown
  47. * @return the root/starting point of the pseudo code
  48. */
  49. public PseudoCodeNode createPseudocodeTree( JTree tree )
  50. {
  51. // Liste mit Variablen die eine andere Farbe im Code bekommen sollen
  52. String[] vars = { "layout", "graph" };
  53. // Die Mainfunktion des BK Node Placement Algorithmus
  54. PseudoCodeNode mainFunction = new PseudoCodeNode( "function bkNodePlacement( graph )", vars, tree, new FunctionDefinition( new String[]{"graph"} ) );
  55. PseudoCodeNode root = new PseudoCodeNode( "-- BK Node Placement Algorithm --", vars, tree, new CodeLine() {
  56. @Override
  57. public ControlFlow runForward(Memory m) {
  58. if( m.isDefined( "Called", Visibility.GLOBAL ) )
  59. {
  60. actions.push( (Memory mem) -> {} );
  61. return new ControlFlow( ControlFlow.STEP_OVER );
  62. }
  63. m.declare( "param1", m.read( "graph", Visibility.GLOBAL ), Visibility.GLOBAL ); // schreibe den Graph in die Globalen Parameter Register des Speichers
  64. m.declare( "Called", true, Visibility.GLOBAL );
  65. actions.push( (Memory mem) -> {
  66. m.undeclare( "param1", Visibility.GLOBAL );
  67. m.undeclare( "Called", Visibility.GLOBAL );
  68. } );
  69. return new ControlFlow( mainFunction ); // Rufe die Hauptfunktion von BK auf (Jump to mainFunction)
  70. // Diese lädt den Graph selbstständig aus dem globalen Speicher in ihr neues Stack Frame
  71. }
  72. } );
  73. root.setSelected( true );
  74. // Erzeuge die Conflict Detection Function
  75. PseudoCodeNode conflictDetectionFunction = ConflictDetection.mark_conflicts( tree );
  76. // Funktion zum Berechnen der Layouts
  77. PseudoCodeNode calcLayout = new PseudoCodeNode( "function calcLayout( layout, graph )", vars, tree, new FunctionDefinition( vars ) );
  78. // Erzeuge die Funktion zum Kombinieren der LKayouts
  79. PseudoCodeNode combine = Balancing.combine( tree );
  80. root.add( mainFunction );
  81. // Ruft die Konflikt Detection Funktion auf
  82. mainFunction.add( new PseudoCodeNode( "call detectConflicts( graph )", vars, tree, new FunctionCall( conflictDetectionFunction, new String[]{ "graph" } ) ) );
  83. // Setze das aktuelle Layout
  84. mainFunction.add( new PseudoCodeNode( "layout = 'RIGHTMOST_LOWER'", vars, tree, new DeclareVariable<String>( "layout" ) {
  85. @Override
  86. protected String value(ReadOnlyMemory m) {
  87. return "RIGHTMOST_LOWER";
  88. }
  89. }) );
  90. // Rufe die Funktion zum Berechnen des Layouts auf
  91. mainFunction.add( new PseudoCodeNode( "call calcLayout( layout, graph )", vars, tree, new FunctionCall( calcLayout, new String[]{ "layout", "graph" } ) ) );
  92. mainFunction.add( new PseudoCodeNode( "layout = 'LEFTMOST_LOWER'", vars, tree, new SetVariable<String>( "layout" ) {
  93. @Override
  94. protected String value(ReadOnlyMemory m) {
  95. return "LEFTMOST_LOWER";
  96. }
  97. }));
  98. mainFunction.add( new PseudoCodeNode( "call calcLayout( layout, graph )", vars, tree, new FunctionCall( calcLayout, new String[]{ "layout", "graph" } ) ) );
  99. mainFunction.add( new PseudoCodeNode( "layout = 'RIGHTMOST_UPPER'", vars, tree, new SetVariable<String>( "layout" ) {
  100. @Override
  101. protected String value(ReadOnlyMemory m) {
  102. return "RIGHTMOST_UPPER";
  103. }
  104. }) );
  105. mainFunction.add( new PseudoCodeNode( "call calcLayout( layout, graph )", vars, tree, new FunctionCall( calcLayout, new String[]{ "layout", "graph" } ) ) );
  106. mainFunction.add( new PseudoCodeNode( "layout = 'LEFTMOST_UPPER'", vars, tree, new SetVariable<String>( "layout" ) {
  107. @Override
  108. protected String value(ReadOnlyMemory m) {
  109. return "LEFTMOST_UPPER";
  110. }
  111. }) );
  112. mainFunction.add( new PseudoCodeNode( "call calcLayout( layout, graph )", vars, tree, new FunctionCall( calcLayout, new String[]{ "layout", "graph" } ) ) );
  113. // Rufe die Funktion zum Berechnen des Kombinierten Layouts auf
  114. mainFunction.add( new PseudoCodeNode( "call combine( graph )", vars, tree, new FunctionCall( combine, new String[]{ "graph" } ) ) );
  115. PseudoCodeNode conflictsStage = new PseudoCodeNode( "-- mark type 1 conflicts --", vars, tree, new Comment() ) {
  116. private static final long serialVersionUID = 1041941539437672704L;
  117. @Override
  118. public String getDebugOutput( Memory m ) {
  119. stage = Stage.CONFLICT_DETECTION;
  120. return ConflictDetection.buildDebugString( m );
  121. }
  122. };
  123. root.add( conflictsStage );
  124. conflictsStage.add( conflictDetectionFunction );
  125. // Erzeuge die Funktion zum berechnen der Blöcke
  126. PseudoCodeNode blockCalc = VerticalAligment.calculateBlockGraph( tree, calcLayout );
  127. // Erzeuge die Placeblock Function
  128. PseudoCodeNode placeBlock = PlaceBlock.place_block( tree );
  129. // Erzeuge die Funktion zum zuweisen der Positionen
  130. PseudoCodeNode horizontalCompaction = HorizontalCompaction.horizontalCompaction( tree, placeBlock );
  131. calcLayout.add( new PseudoCodeNode( "call calculateBlockGraph( layout, graph )", vars, tree, new FunctionCall( blockCalc, vars ) ) );
  132. calcLayout.add( new PseudoCodeNode( "call horizontalCompaction( layout, graph )", vars, tree, new FunctionCall( horizontalCompaction, vars ) ) );
  133. PseudoCodeNode extremalLayoutStage = new PseudoCodeNode( "-- Compute an extremal layout --", vars, tree, new Comment() ) {
  134. private static final long serialVersionUID = 4141215748809071958L;
  135. @Override
  136. public String getDebugOutput( Memory m ) { // Debug Text für die Layout Berechnungs Phase
  137. if( !m.isSomewhereDefined( "graph", Visibility.COMPLETE_STACK ) || !m.isSomewhereDefined( "layout", Visibility.COMPLETE_STACK ) )
  138. return "";
  139. String info = "| Node | Shift | Sink | Root | Align | x | xDef |\n";
  140. info += "|------|-------|------|------|-------|-----|--------|\n";
  141. LayeredGraphNode graph = m.read( "graph", Visibility.COMPLETE_STACK );
  142. LayoutType type = LayoutType.fromString( m.read( "layout", Visibility.COMPLETE_STACK ) );
  143. switch( type ) { // Aktualisierung des aktuellen Zustandes des Algorithmus (Wird zum Zeichnen des richtigen Layouts benötigt)
  144. case LEFTMOST_UPPER:
  145. stage = Stage.LEFTMOST_UPPER;
  146. break;
  147. case RIGHTMOST_UPPER:
  148. stage = Stage.RIGHTMOST_UPPER;
  149. break;
  150. case LEFTMOST_LOWER:
  151. stage = Stage.LEFTMOST_LOWER;
  152. break;
  153. case RIGHTMOST_LOWER:
  154. stage = Stage.RIGHTMOST_LOWER;
  155. break;
  156. case COMBINED: // this will never happen here
  157. assert false;
  158. break;
  159. default:
  160. assert false;
  161. break;
  162. }
  163. for( LayeredGraphNode n : graph.getContainedNodes() )
  164. {
  165. info += "|" + TextLayoutHelper.strToLen( n.toString(), 6 ) +
  166. "|" + TextLayoutHelper.strToLen( n.getShift( type ) + "", 7 ) +
  167. "|" + TextLayoutHelper.strToLen( n.getSink( type ).toString(), 6 ) +
  168. "|" + TextLayoutHelper.strToLen( n.getRoot( type ).toString(), 6 ) +
  169. "|" + TextLayoutHelper.strToLen( n.getAlign( type ).toString(), 7 ) +
  170. "|" + TextLayoutHelper.strToLen( n.getX( type ) + "", 5 ) +
  171. "|" + TextLayoutHelper.strToLen( !n.isXUndefined( type ) + "", 8 ) + "|\n";
  172. }
  173. return info;
  174. }
  175. };
  176. root.add( extremalLayoutStage );
  177. extremalLayoutStage.add( calcLayout );
  178. extremalLayoutStage.add( new PseudoCodeNode( "-- vertical alignment --", vars, tree, new Comment() ) );
  179. extremalLayoutStage.add( blockCalc );
  180. extremalLayoutStage.add( new PseudoCodeNode( "-- horizontal compaction --", vars, tree, new Comment() ) );
  181. extremalLayoutStage.add( horizontalCompaction );
  182. extremalLayoutStage.add( placeBlock );
  183. PseudoCodeNode balancingStage = new PseudoCodeNode( "-- balancing --", vars, tree, new Comment() ) {
  184. private static final long serialVersionUID = 4212377075998840086L;
  185. @Override
  186. public String getDebugOutput( Memory m ) { // Debug Text für die Berechnung des kombinierten Layouts
  187. stage = Stage.COMBINE;
  188. if( !m.isSomewhereDefined( "graph", Visibility.COMPLETE_STACK ) )
  189. return "";
  190. String info = "| Node | x BR | x BL | x UR | x UL | x CO |\n";
  191. info += "|------|------|------|------|------|------|\n";
  192. LayeredGraphNode graph = m.read( "graph", Visibility.COMPLETE_STACK );
  193. for( LayeredGraphNode n : graph.getContainedNodes() )
  194. {
  195. info += "|" + TextLayoutHelper.strToLen( n.toString(), 6 ) +
  196. "|" + TextLayoutHelper.strToLen( n.getX( LayoutType.LEFTMOST_UPPER ) + "", 6 ) +
  197. "|" + TextLayoutHelper.strToLen( n.getX( LayoutType.RIGHTMOST_UPPER ) + "", 6 ) +
  198. "|" + TextLayoutHelper.strToLen( n.getX( LayoutType.LEFTMOST_LOWER ) + "", 6 ) +
  199. "|" + TextLayoutHelper.strToLen( n.getX( LayoutType.RIGHTMOST_LOWER ) + "", 6 ) +
  200. "|" + TextLayoutHelper.strToLen( n.getX( LayoutType.COMBINED ) + "", 6 ) + "|\n";
  201. }
  202. return info;
  203. }
  204. };
  205. root.add( balancingStage );
  206. balancingStage.add( combine );
  207. return root;
  208. }
  209. }