Continue to enhance the layout algorithm

git-svn-id: http://svn.us.apache.org/repos/asf/tuscany@1174318 13f79535-47bb-0310-9956-ffa450edef68

5 files changed, 178 insertions, 34 deletions

diff --git a/sca-java-2.x/trunk/modules/composite-diagram/src/main/java/org/apache/tuscany/sca/diagram/generator/DiagramGenerator.java b/sca-java-2.x/trunk/modules/composite-diagram/src/main/java/org/apache/tuscany/sca/diagram/generator/DiagramGenerator.java
index 9b20e97f83..ccedac5451 100755
--- a/sca-java-2.x/trunk/modules/composite-diagram/src/main/java/org/apache/tuscany/sca/diagram/generator/DiagramGenerator.java
+++ b/sca-java-2.x/trunk/modules/composite-diagram/src/main/java/org/apache/tuscany/sca/diagram/generator/DiagramGenerator.java
@@ -63,7 +63,7 @@ public class DiagramGenerator {
     private int lastUsedChangingFactor = 0;
 
     enum ChangingFactor {
-        a(20), b(25), c(30), d(35), e(40), f(15);
+        a(20), b(40), c(60), d(80), e(100), f(120), g(140), h(160);
 
         private final int val;
 
@@ -387,14 +387,8 @@ public class DiagramGenerator {
                 if (ent.getName().equals(eName)) {
                     for (String s : sers) {
                         for (String s1 : ent.getServices()) {
-                            //System.err.println("XXXXX "+ s1 +" ::: "+s);
                             if (s1.equals(s) || s.equals(ent.getName())) {
-                                //System.err.println("|||||||| "+ sers.size()+ " ||| " + refs.size()+"|| "+orderedRefs.length);
                                 if (orderedRefs[ent.getLevel()] == null) {
-                                    //System.err.println("XXXXX "+ sers.get(1)+ " ::::::: "+refs.get(1));
-                                    //									System.err.println("XXXXX "+ sers.get(2)+ " ::::::: "+refs.get(2));
-                                    //									System.err.println("XXXXX "+ sers.get(3)+ " ::::::: "+refs.get(3));
-                                    //System.err.println("XXXXX "+ refs.get(sers.indexOf(s))+" ::: "+ent.getLevel()+" ::: "+ent.getName());
                                     orderedRefs[ent.getLevel()] = refs.get(sers.indexOf(s));
                                     break;
                                 } else {
@@ -404,10 +398,6 @@ public class DiagramGenerator {
                                             orderedRefs[i] = refs.get(sers.indexOf(s));
                                             break;
                                         }
-                                        //										else{
-                                        //											if(i==orderedRefs.length)
-                                        //												System.out.println("GRRR");
-                                        //										}
                                     }
                                 }
                             }
diff --git a/sca-java-2.x/trunk/modules/composite-diagram/src/main/java/org/apache/tuscany/sca/diagram/layout/Entity.java b/sca-java-2.x/trunk/modules/composite-diagram/src/main/java/org/apache/tuscany/sca/diagram/layout/Entity.java
index 5adf11d5c7..cd9f1b8133 100755
--- a/sca-java-2.x/trunk/modules/composite-diagram/src/main/java/org/apache/tuscany/sca/diagram/layout/Entity.java
+++ b/sca-java-2.x/trunk/modules/composite-diagram/src/main/java/org/apache/tuscany/sca/diagram/layout/Entity.java
@@ -61,16 +61,16 @@ public abstract class Entity {
         return x;
     }
 
-    public void setX(int init) {
-        this.x = init + getWidth() * spaceFactor * lane;
+    public void setX(int x) {
+        this.x = x;
     }
 
     public int getY() {
         return y;
     }
 
-    public void setY(int init) {
-        this.y = init + getHeight() * spaceFactor * level;
+    public void setY(int y) {
+        this.y = y;
     }
 
     public int getLevel() {
diff --git a/sca-java-2.x/trunk/modules/composite-diagram/src/main/java/org/apache/tuscany/sca/diagram/layout/LayoutBuilder.java b/sca-java-2.x/trunk/modules/composite-diagram/src/main/java/org/apache/tuscany/sca/diagram/layout/LayoutBuilder.java
index 5b4ffa427d..a34e9e83b0 100755
--- a/sca-java-2.x/trunk/modules/composite-diagram/src/main/java/org/apache/tuscany/sca/diagram/layout/LayoutBuilder.java
+++ b/sca-java-2.x/trunk/modules/composite-diagram/src/main/java/org/apache/tuscany/sca/diagram/layout/LayoutBuilder.java
@@ -20,21 +20,45 @@
 package org.apache.tuscany.sca.diagram.layout;
 
 import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Comparator;
 import java.util.List;
 
+import org.apache.tuscany.sca.diagram.artifacts.Constant;
+
 public class LayoutBuilder {
 
-    private Entity[] elts = null;
-    private int[][] conns = null;
+    private Entity[] elts;
+    private int[][] conns;
     private int maxLevels = 8;
 
+    private int totalLevel;
+    private int totalLane;
+
+    private Entity[][] grid;
+
+    private int[][] graph;
+
     /**
      * Constructor which takes set of entities and their connection matrix
-     * @param maxLevels TODO
+     *
+     * @param entities
+     * @param connections
+     * @param maxLevels
      */
     public LayoutBuilder(Entity[] entities, int[][] connections, int maxLevels) {
         elts = entities;
-        conns = connections.clone();
+        graph = connections; // Keep the original connections
+
+        // Clone the connections
+        int len = connections.length;
+        conns = new int[len][];
+        for (int i = 0; i < len; i++) {
+            conns[i] = new int[len];
+            for (int j = 0; j < len; j++) {
+                conns[i][j] = connections[i][j];
+            }
+        }
         this.maxLevels = maxLevels;
     }
 
@@ -69,18 +93,43 @@ public class LayoutBuilder {
 
         sortEntities();
 
-        assignCoordinates();
+        // Build the grid for entities
+        grid = new Entity[totalLane + 1][totalLevel + 1];
+        int[] height = new int[totalLevel + 1];
+        int[] width = new int[totalLane + 1];
 
-        return elts;
+        for (Entity e : elts) {
+            grid[e.getLane()][e.getLevel()] = e;
+            if (height[e.getLevel()] < e.getHeight() + Constant.COMPONENT_DEFAULT_HEIGHT) {
+                height[e.getLevel()] = e.getHeight() + Constant.COMPONENT_DEFAULT_HEIGHT;
+            }
+            if (width[e.getLane()] < e.getWidth() + Constant.COMPONENT_DEFAULT_WIDTH) {
+                width[e.getLane()] = e.getWidth() + Constant.COMPONENT_DEFAULT_WIDTH;
+            }
+        }
 
-    }
+        for (int i = 1; i < totalLane + 1; i++) {
+            width[i] += width[i - 1];
+        }
 
-    private void assignCoordinates() {
+        for (int j = 1; j < totalLevel + 1; j++) {
+            height[j] += height[j - 1];
+        }
 
-        for (Entity ent : elts) {
-            ent.setX(ent.getParent().getX() + ent.getStartPosition());
-            ent.setY(ent.getParent().getY() + ent.getStartPosition() / 2);
+        for (int i = 0; i < totalLane + 1; i++) {
+            for (int j = 0; j < totalLevel + 1; j++) {
+                Entity ent = grid[i][j];
+                if (ent != null) {
+                    int w = ent.getLane() == 0 ? 0 : width[i - 1];
+                    ent.setX(ent.getParent().getX() + ent.getStartPosition() + w);
+                    int h = ent.getLevel() == 0 ? 0 : height[j - 1];
+                    ent.setY(ent.getParent().getY() + ent.getStartPosition() / 2 + h);
+                }
+            }
         }
+
+        return elts;
+
     }
 
     private Entity findEntity(int i) {
@@ -94,16 +143,75 @@ public class LayoutBuilder {
     }
 
     private void setPosition(Entity ent, int level, int lane) {
+        if (totalLane < lane) {
+            totalLane = lane;
+        }
+        if (totalLevel < level) {
+            totalLevel = level;
+        }
         ent.setLevel(level);
         ent.setLane(lane);
         ent.setPositionSet(true);
     }
 
     /**
+     * http://en.wikipedia.org/wiki/Coffman%E2%80%93Graham_algorithm#The_algorithm
+     * @param sorted
+     * @param e1
+     * @param e2
+     * @return
+     */
+    private int compareEntities(List<Integer> sorted, int e1, int e2) {
+        List<Integer> neighbors1 = findIncomingNeighbors(e1);
+        List<Integer> neighbors2 = findIncomingNeighbors(e2);
+
+        if (neighbors1.isEmpty() && neighbors2.isEmpty()) {
+            return 0;
+        } else if (neighbors1.isEmpty()) {
+            return -1;
+        } else if (neighbors2.isEmpty()) {
+            return 1;
+        }
+
+        int max = graph.length + 1;
+        int n1 = max;
+        int n2 = max;
+        for (int i = sorted.size() - 1; i >= 0; i--) {
+            if (neighbors1.contains(sorted.get(i))) {
+                n1 = i;
+            }
+            if (neighbors2.contains(sorted.get(i))) {
+                n2 = i;
+            }
+            if (n1 == n2) {
+                // Need to try the 2nd most recently added incoming neighbor
+                // Reset the indexes and continue
+                n1 = max;
+                n2 = max;
+                continue;
+            }
+        }
+        return n1 - n2;
+    }
+
+    private List<Integer> findIncomingNeighbors(int e1) {
+        // Get all the inbound connections for a given entity 
+        List<Integer> ins = new ArrayList<Integer>();
+        for (int i = 0; i < graph.length; i++) {
+            if (graph[i][e1] == 1) {
+                ins.add(i);
+            }
+        }
+        return ins;
+    }
+
+    /**
      * Perform a topological sort on the graph so that we can place the entities into level/lane grids
+     * http://en.wikipedia.org/wiki/Coffman%E2%80%93Graham_algorithm#The_algorithm
      */
-    private void sortEntities() {
+    List<Integer> sortEntities() {
         int lane = 0;
+        final List<Integer> sorted = new ArrayList<Integer>();
         while (true) {
             List<Integer> ids = new ArrayList<Integer>();
             for (int i = 0; i < conns.length; i++) {
@@ -135,16 +243,27 @@ public class LayoutBuilder {
                     }
                 }
                 if (end) {
-                    return;
+                    return sorted;
                 }
             }
             int level = 0;
+            Collections.sort(ids, new Comparator<Integer>() {
+
+                @Override
+                public int compare(Integer e1, Integer e2) {
+                    return compareEntities(sorted, e1, e2);
+                }
+            });
             for (int i : ids) {
-                setPosition(findEntity(i), level++, lane);
-                if (maxLevels > 0 && (level % maxLevels == 0)) {
+                sorted.add(i);
+
+                if (maxLevels > 0 && level > 0 && (level % maxLevels == 0)) {
+                    // Overflow to the next lane
                     level = 0;
                     lane++;
                 }
+
+                setPosition(findEntity(i), level++, lane);
                 for (int j = 0; j < conns.length; j++) {
                     // Remove the connections from i
                     conns[i][j] = 0;
diff --git a/sca-java-2.x/trunk/modules/composite-diagram/src/test/java/org/apache/tuscany/sca/diagram/layout/LayoutBuilderTestCase.java b/sca-java-2.x/trunk/modules/composite-diagram/src/test/java/org/apache/tuscany/sca/diagram/layout/LayoutBuilderTestCase.java
index 542de3de00..17e690ca71 100755
--- a/sca-java-2.x/trunk/modules/composite-diagram/src/test/java/org/apache/tuscany/sca/diagram/layout/LayoutBuilderTestCase.java
+++ b/sca-java-2.x/trunk/modules/composite-diagram/src/test/java/org/apache/tuscany/sca/diagram/layout/LayoutBuilderTestCase.java
@@ -18,6 +18,9 @@
  */
 package org.apache.tuscany.sca.diagram.layout;
 
+import java.util.Arrays;
+import java.util.List;
+
 import junit.framework.Assert;
 
 import org.junit.Before;
@@ -149,4 +152,25 @@ public class LayoutBuilderTestCase {
         Assert.assertEquals(2, ents[4].getLane());
 
     }
+
+    @Test
+    public void testPlaceEntities3() throws Exception {
+
+        /*
+         * 0----1---2
+         *  |   |    
+         *  +---3---4
+         */
+        conns = new int[5][5];
+        conns[0][1] = 1;
+        conns[0][3] = 1;
+        conns[1][2] = 1;
+        conns[1][3] = 1;
+        conns[2][4] = 1;
+
+        lb = new LayoutBuilder(ents, conns, 4);
+        List<Integer> sorted = lb.sortEntities();
+        Assert.assertEquals(Arrays.asList(0, 1, 3, 2, 4), sorted);
+
+    }
 }
diff --git a/sca-java-2.x/trunk/modules/composite-diagram/src/test/resources/input/Calculator2.xml b/sca-java-2.x/trunk/modules/composite-diagram/src/test/resources/input/Calculator2.xml
index 81384ef840..c3240bec3e 100755
--- a/sca-java-2.x/trunk/modules/composite-diagram/src/test/resources/input/Calculator2.xml
+++ b/sca-java-2.x/trunk/modules/composite-diagram/src/test/resources/input/Calculator2.xml
@@ -22,6 +22,7 @@
 
     <component name="CalculatorServiceComponent">
         <implementation.java class="calculator.CalculatorServiceImpl" />
+
         <reference name="addService" target="AddServiceComponent" />
         <reference name="subtractService" target="SubtractServiceComponent" />
         <reference name="multiplyService" target="MultiplyServiceComponent" />
@@ -32,13 +33,19 @@
         <reference name="multiplyService2" target="MultiplyServiceComponent2" />
         <reference name="divideService2" target="DivideServiceComponent2" />
 
-        <reference name="addService3" target="AddServiceComponent3" />
-        <reference name="subtractService3" target="SubtractServiceComponent3" />
-        <reference name="multiplyService3" target="MultiplyServiceComponent3" />
-        <reference name="divideService3" target="DivideServiceComponent3" />
+        <reference name="delegate" target="CalculatorServiceComponent2" />
+
+    </component>
 
+    <component name="CalculatorServiceComponent2">
+        <implementation.java class="calculator.CalculatorServiceImpl" />
+        <reference name="addService" target="AddServiceComponent3" />
+        <reference name="subtractService" target="SubtractServiceComponent3" />
+        <reference name="multiplyService" target="MultiplyServiceComponent3" />
+        <reference name="divideService" target="DivideServiceComponent3" />
     </component>
 
+
     <component name="AddServiceComponent">
         <implementation.java class="calculator.AddServiceImpl" />
     </component>
@@ -87,4 +94,8 @@
         <implementation.java class="calculator.DivideServiceImpl" />
     </component>
 
+    <component name="AddServiceComponent4">
+        <implementation.java class="calculator.AddServiceImpl" />
+    </component>
+
 </composite>
\ No newline at end of file