Enhance the layout using topological sorting of the entities

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

9 files changed, 116 insertions, 205 deletions

diff --git a/sca-java-2.x/trunk/modules/composite-diagram/src/main/java/org/apache/tuscany/sca/diagram/artifacts/Constant.java b/sca-java-2.x/trunk/modules/composite-diagram/src/main/java/org/apache/tuscany/sca/diagram/artifacts/Constant.java
index a5e3e91fbc..c27d82dd6d 100755
--- a/sca-java-2.x/trunk/modules/composite-diagram/src/main/java/org/apache/tuscany/sca/diagram/artifacts/Constant.java
+++ b/sca-java-2.x/trunk/modules/composite-diagram/src/main/java/org/apache/tuscany/sca/diagram/artifacts/Constant.java
@@ -41,4 +41,6 @@ public final class Constant {
 
     public static final int SPACING_FOR_TEXT = 2;
 
+    public static final int MAX_LEVELS = 8;
+
 }
diff --git a/sca-java-2.x/trunk/modules/composite-diagram/src/main/java/org/apache/tuscany/sca/diagram/artifacts/Style.java b/sca-java-2.x/trunk/modules/composite-diagram/src/main/java/org/apache/tuscany/sca/diagram/artifacts/Style.java
index 08554dcc61..012ca72f26 100644
--- a/sca-java-2.x/trunk/modules/composite-diagram/src/main/java/org/apache/tuscany/sca/diagram/artifacts/Style.java
+++ b/sca-java-2.x/trunk/modules/composite-diagram/src/main/java/org/apache/tuscany/sca/diagram/artifacts/Style.java
@@ -109,7 +109,10 @@ public class Style {
         }
         reader.close();
         String template = sw.toString();
-        // Remove the ASF license header
-        return template.replaceFirst("/\\*(?:.|[\\n\\r])*?\\*/", "");
+        // return template.replaceFirst("/\\*(?:.|[\\n\\r])*?\\*/", ""); // Unfortunately it causes StackOverFlow in Apache Jenkins build
+        int i1 = template.indexOf("/*");
+        int i2 = template.indexOf("*/", i1);
+        String result = template.substring(0, i1) + template.substring(i2 + 2, template.length());
+        return result;
     }
 }
diff --git a/sca-java-2.x/trunk/modules/composite-diagram/src/main/java/org/apache/tuscany/sca/diagram/layout/CompositeEntity.java b/sca-java-2.x/trunk/modules/composite-diagram/src/main/java/org/apache/tuscany/sca/diagram/layout/CompositeEntity.java
index 02e98c56d5..bd0a71431f 100755
--- a/sca-java-2.x/trunk/modules/composite-diagram/src/main/java/org/apache/tuscany/sca/diagram/layout/CompositeEntity.java
+++ b/sca-java-2.x/trunk/modules/composite-diagram/src/main/java/org/apache/tuscany/sca/diagram/layout/CompositeEntity.java
@@ -68,26 +68,18 @@ public class CompositeEntity extends Entity {
         int h = 0;
         int w = 0;
 
-        int lastHeight = 0;
-        // int lastWidth = 0;
         for (ComponentEntity ent : componentList) {
 
             if (ent.getLevel() > maxInternalLevel) {
                 maxInternalLevel = ent.getLevel();
-                lastHeight = ent.getHeight();
-                h += ent.getHeight() * getSpaceFactor();
+                h += (ent.getHeight() + Constant.COMPONENT_DEFAULT_HEIGHT);
             }
             if (ent.getLane() > maxInternalLane) {
                 maxInternalLane = ent.getLane();
-                // lastWidth = ent.getWidth();
-                w += ent.getWidth() * getSpaceFactor();
+                w += (ent.getWidth() + Constant.COMPONENT_DEFAULT_WIDTH);
             }
         }
 
-        // For last level, no spacing is needed
-        h -= lastHeight * (getSpaceFactor() - 1);
-        // w -= lastWidth * (getSpaceFactor() - 1);
-
         // Find the services height
         int size1 = services.size();
         int total1 = size1 * serHeight + (size1 + 1) * Constant.SPACING_FOR_COMPOSITE_OF_SERVICE;
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 54becf82f2..5adf11d5c7 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
@@ -29,13 +29,13 @@ public abstract class Entity {
     protected int y; // y coordinate
     protected int level = -1; // corresponding row which this entity is placed
     protected int lane = -1; // corresponding column which this entity is placed
-    protected boolean isPossitionSet = false;
+    protected boolean positionSet = false;
     protected int height; // height of the entity
     protected int width; // width of the entity
     protected int refHeight; // height of a reference element
     protected int serHeight; // height of a service element
     protected int propWidth; // length of a property element
-    
+
     protected int startPosition = 0;
     protected Entity parent = null;
 
@@ -211,12 +211,12 @@ public abstract class Entity {
         return id;
     }
 
-    public void setPossitionSet(boolean isPossitionSet) {
-        this.isPossitionSet = isPossitionSet;
+    public void setPositionSet(boolean isPositionSet) {
+        this.positionSet = isPositionSet;
     }
 
-    public boolean isPossitionSet() {
-        return isPossitionSet;
+    public boolean isPositionSet() {
+        return positionSet;
     }
 
     public int getSpaceFactor() {
diff --git a/sca-java-2.x/trunk/modules/composite-diagram/src/main/java/org/apache/tuscany/sca/diagram/layout/EntityBuilder.java b/sca-java-2.x/trunk/modules/composite-diagram/src/main/java/org/apache/tuscany/sca/diagram/layout/EntityBuilder.java
index a936d83871..9e70781a08 100755
--- a/sca-java-2.x/trunk/modules/composite-diagram/src/main/java/org/apache/tuscany/sca/diagram/layout/EntityBuilder.java
+++ b/sca-java-2.x/trunk/modules/composite-diagram/src/main/java/org/apache/tuscany/sca/diagram/layout/EntityBuilder.java
@@ -22,6 +22,7 @@ package org.apache.tuscany.sca.diagram.layout;
 import java.util.ArrayList;
 import java.util.HashMap;
 
+import org.apache.tuscany.sca.diagram.artifacts.Constant;
 import org.w3c.dom.Document;
 import org.w3c.dom.Element;
 import org.w3c.dom.NodeList;
@@ -66,7 +67,7 @@ public class EntityBuilder {
         composite.setComponentList(comps);
         composite.setConnections(conns);
 
-        LayoutBuilder buildLayout = new LayoutBuilder(comps, conns);
+        LayoutBuilder buildLayout = new LayoutBuilder(comps, conns, Constant.MAX_LEVELS);
         buildLayout.placeEntities();
 
         //System.out.println("conns "+conns[0][0]);
@@ -207,70 +208,6 @@ public class EntityBuilder {
         int[][] connections = new int[comps.length][comps.length];
         connections = initConnections(connections);
 
-        //		//sec. 5.4 in the spec
-        //		NodeList nl = docEle.getElementsByTagName("wire");
-        //		//System.out.println("^^^^^^^^^ "+nl.getLength());
-        //		if(nl != null && nl.getLength() > 0 ) {
-        //			
-        //			for(int i = 0 ; i < nl.getLength();i++) {
-        //				
-        //				Element elt = (Element)nl.item(i);
-        //				
-        //				String source = elt.getAttribute("source");
-        //				String target = elt.getAttribute("target");
-        //				
-        //				String service, serviceComp, reference, referenceComp;
-        //				
-        //				String[] arr1 = extractComp(target);
-        //				serviceComp = arr1[0];
-        //				service = arr1[1];
-        //				
-        //				String[] arr2 = extractComp(source);
-        //				referenceComp = arr2[0];
-        //				reference = arr2[1];
-
-        //				//System.out.println("^^^^^^^^^ "+source+" ::: "+target);
-        //				if(target.contains("/")){
-        //					String[] arr = target.split("/");
-        //					serviceComp = arr[0];
-        //					service = arr[1];
-        //				}
-        //				else{
-        //					serviceComp = target;
-        //					service = null;
-        //				}
-        //				
-        //				if(source.contains("/")){
-        //					String[] arr = source.split("/");
-        //					referenceComp = arr[0];
-        //					reference = arr[1];
-        //				}
-        //				else{
-        //					referenceComp = source;
-        //					reference = null;
-        //				}
-        //				//sec. 5.4 in the spec
-        //		NodeList nl = docEle.getElementsByTagName("wire");
-        //		//System.out.println("^^^^^^^^^ "+nl.getLength());
-        //		if(nl != null && nl.getLength() > 0 ) {
-        //			
-        //			for(int i = 0 ; i < nl.getLength();i++) {
-        //				
-        //				Element elt = (Element)nl.item(i);
-        //				
-        //				String source = elt.getAttribute("source");
-        //				String target = elt.getAttribute("target");
-        //				
-        //				String service, serviceComp, reference, referenceComp;
-        //				
-        //				String[] arr1 = extractComp(target);
-        //				serviceComp = arr1[0];
-        //				service = arr1[1];
-        //				
-        //				String[] arr2 = extractComp(source);
-        //				referenceComp = arr2[0];
-        //				reference = arr2[1];
-
         for (Entity ent : comps) {
             for (String name : ent.getAdjacentEntities()) {
                 ComponentEntity e2 = findEntity(comps, name);
@@ -281,18 +218,7 @@ public class EntityBuilder {
             }
 
         }
-        //				ComponentEntity e1 = findEntity(comps, referenceComp);
-        //				ComponentEntity e2 = findEntity(comps, serviceComp);
-        //				
-        //				System.out.println("^^^^^^^^^ "+e1.getName());
-        //				if(e1 != null && e2 != null){
-        //					System.out.println("^^^^^^^^^ "+e1.getId());
-        //					connections[e1.getId()][e2.getId()] = 1;
-        //					createConnection(e1, reference, serviceComp, service);
-        //				}
-        //			}
-        //		}
-        //		
+
         return connections;
     }
 
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 87b358479a..5b4ffa427d 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
@@ -19,19 +19,23 @@
 
 package org.apache.tuscany.sca.diagram.layout;
 
+import java.util.ArrayList;
+import java.util.List;
+
 public class LayoutBuilder {
 
     private Entity[] elts = null;
     private int[][] conns = null;
-    private Entity startEnt = null;
-    private int currentMaxLevel = 0;
+    private int maxLevels = 8;
 
     /**
      * Constructor which takes set of entities and their connection matrix
+     * @param maxLevels TODO
      */
-    public LayoutBuilder(Entity[] entities, int[][] connections) {
+    public LayoutBuilder(Entity[] entities, int[][] connections, int maxLevels) {
         elts = entities;
-        conns = connections;
+        conns = connections.clone();
+        this.maxLevels = maxLevels;
     }
 
     /**
@@ -63,52 +67,14 @@ public class LayoutBuilder {
      */
     public Entity[] placeEntities() {
 
-        /**
-         * Finding the starting entity
-         */
-        for (int i = 0; i < elts.length; i++) {
-            //System.out.println("ELts "+elts.length);
-            Entity ent = elts[i];
-            if (isConnected(ent.getId())) {
-                setPosition(ent, 0, 0);
-                startEnt = ent;
-                //System.out.println("startEnt "+ent.getId());
-                break;
-            }
-
-        }
+        sortEntities();
 
-        if (startEnt != null) {
-            assignPositions(startEnt);
-        }
-
-        assignPositionsOfOtherConncetedEntities();//such as a different cluster of components
-        assignPositionsOfIdleEntities();
         assignCoordinates();
 
         return elts;
 
     }
 
-    private void assignPositionsOfIdleEntities() {
-
-        for (Entity ent : elts) {
-            if (!ent.isPossitionSet()) {
-
-                setPosition(ent, currentMaxLevel++, 0);
-            }
-        }
-    }
-
-    private void assignPositionsOfOtherConncetedEntities() {
-
-        for (Entity ent : elts) {
-            if (!ent.isPossitionSet() && isConnected(ent.getId())) {
-                assignPositions(ent);
-            }
-        }
-    }
-
     private void assignCoordinates() {
 
         for (Entity ent : elts) {
@@ -117,27 +83,6 @@ public class LayoutBuilder {
         }
     }
 
-    private void assignPositions(Entity ent) {
-        int id = ent.getId();
-        int[] entConns = conns[id];
-
-        for (int i = 0; i < entConns.length; i++) {
-            if (entConns[i] == 1) {
-                Entity nextEnt = findEntity(i);
-
-                //				if(nextEnt.isPossitionSet()){
-                //					currentMaxLevel = nextEnt.getLevel()+1; // for diagram clearness purpose
-                //				}
-                if (nextEnt != null && !nextEnt.isPossitionSet()) {
-                    setPosition(nextEnt, currentMaxLevel, ent.getLane() + 1);
-                    assignPositions(nextEnt);
-                }
-            }
-
-        }
-        currentMaxLevel = ent.getLevel() + 1;
-    }
-
     private Entity findEntity(int i) {
 
         for (Entity ent : elts) {
@@ -148,36 +93,65 @@ public class LayoutBuilder {
         return null;
     }
 
-    /**
-     * If there's at least 1 connection, this will return true
-     */
-    private boolean isConnected(int id) {
-        int[] entConns = conns[id];
-
-        //System.out.println("entConns "+entConns.length);
-        for (int i = 0; i < entConns.length; i++) {
-
-            if (entConns[i] == 1) {
-                return true;
-            }
-
-        }
-
-        return false;
-    }
-
     private void setPosition(Entity ent, int level, int lane) {
         ent.setLevel(level);
         ent.setLane(lane);
-        ent.setPossitionSet(true);
+        ent.setPositionSet(true);
     }
 
-    public Entity getStartEnt() {
-        return startEnt;
-    }
+    /**
+     * Perform a topological sort on the graph so that we can place the entities into level/lane grids
+     */
+    private void sortEntities() {
+        int lane = 0;
+        while (true) {
+            List<Integer> ids = new ArrayList<Integer>();
+            for (int i = 0; i < conns.length; i++) {
+                Entity ent = findEntity(i);
+                if (ent.isPositionSet()) {
+                    continue;
+                }
+                boolean beingConnected = false;
+                for (int j = 0; j < conns.length; j++) {
+                    if (conns[j][i] == 1) {
+                        beingConnected = true;
+                        break;
+                    }
+                }
+                if (!beingConnected) {
+                    ids.add(i);
+                }
+            }
 
-    public void setStartEnt(Entity startEnt) {
-        this.startEnt = startEnt;
+            if (ids.isEmpty()) {
+                boolean end = true;
+                // There might be circular dependencies
+                for (Entity e : elts) {
+                    if (!e.isPositionSet()) {
+                        // Pick the first one 
+                        ids.add(e.getId());
+                        end = false;
+                        break;
+                    }
+                }
+                if (end) {
+                    return;
+                }
+            }
+            int level = 0;
+            for (int i : ids) {
+                setPosition(findEntity(i), level++, lane);
+                if (maxLevels > 0 && (level % maxLevels == 0)) {
+                    level = 0;
+                    lane++;
+                }
+                for (int j = 0; j < conns.length; j++) {
+                    // Remove the connections from i
+                    conns[i][j] = 0;
+                }
+            }
+            lane++;
+        }
     }
 
 }
diff --git a/sca-java-2.x/trunk/modules/composite-diagram/src/main/java/org/apache/tuscany/sca/diagram/layout/TuscanyCompositeEntityBuilder.java b/sca-java-2.x/trunk/modules/composite-diagram/src/main/java/org/apache/tuscany/sca/diagram/layout/TuscanyCompositeEntityBuilder.java
index dc9d3be55b..9f6e7a6bda 100755
--- a/sca-java-2.x/trunk/modules/composite-diagram/src/main/java/org/apache/tuscany/sca/diagram/layout/TuscanyCompositeEntityBuilder.java
+++ b/sca-java-2.x/trunk/modules/composite-diagram/src/main/java/org/apache/tuscany/sca/diagram/layout/TuscanyCompositeEntityBuilder.java
@@ -37,6 +37,7 @@ import org.apache.tuscany.sca.assembly.Reference;
 import org.apache.tuscany.sca.assembly.Service;
 import org.apache.tuscany.sca.assembly.Wire;
 import org.apache.tuscany.sca.diagram.artifacts.Artifact;
+import org.apache.tuscany.sca.diagram.artifacts.Constant;
 
 public class TuscanyCompositeEntityBuilder {
 
@@ -77,7 +78,7 @@ public class TuscanyCompositeEntityBuilder {
         composite.setComponentList(comps);
         composite.setConnections(conns);
 
-        LayoutBuilder buildLayout = new LayoutBuilder(comps, conns);
+        LayoutBuilder buildLayout = new LayoutBuilder(comps, conns, Constant.MAX_LEVELS);
         buildLayout.placeEntities();
 
         // System.out.println("conns " + conns[0][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 8faaddfa19..542de3de00 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
@@ -20,10 +20,6 @@ package org.apache.tuscany.sca.diagram.layout;
 
 import junit.framework.Assert;
 
-import org.apache.tuscany.sca.diagram.layout.ComponentEntity;
-import org.apache.tuscany.sca.diagram.layout.CompositeEntity;
-import org.apache.tuscany.sca.diagram.layout.Entity;
-import org.apache.tuscany.sca.diagram.layout.LayoutBuilder;
 import org.junit.Before;
 import org.junit.Test;
 
@@ -66,12 +62,11 @@ public class LayoutBuilderTestCase {
             }
         }
 
-        lb = new LayoutBuilder(ents, conns);
+        lb = new LayoutBuilder(ents, conns, 4);
 
         ents = lb.placeEntities();
 
         Assert.assertEquals(5, ents.length);
-        Assert.assertEquals(0, lb.getStartEnt().getId());
 
         Assert.assertEquals(0, ents[0].getLevel());
         Assert.assertEquals(0, ents[1].getLevel());
@@ -102,12 +97,11 @@ public class LayoutBuilderTestCase {
         }
         conns[3][4] = 0;
 
-        lb = new LayoutBuilder(ents, conns);
+        lb = new LayoutBuilder(ents, conns, 4);
 
         ents = lb.placeEntities();
 
         Assert.assertEquals(5, ents.length);
-        Assert.assertEquals(0, lb.getStartEnt().getId());
 
         Assert.assertEquals(0, ents[0].getLevel());
         Assert.assertEquals(0, ents[1].getLevel());
@@ -136,24 +130,23 @@ public class LayoutBuilderTestCase {
             }
         }
 
-        lb = new LayoutBuilder(ents, conns);
+        lb = new LayoutBuilder(ents, conns, 4);
 
         ents = lb.placeEntities();
 
         Assert.assertEquals(5, ents.length);
-        Assert.assertEquals(1, lb.getStartEnt().getId());
 
-        Assert.assertEquals(1, ents[0].getLevel());
+        Assert.assertEquals(0, ents[0].getLevel());
         Assert.assertEquals(0, ents[1].getLevel());
         Assert.assertEquals(0, ents[2].getLevel());
         Assert.assertEquals(0, ents[3].getLevel());
-        Assert.assertEquals(1, ents[4].getLevel());
+        Assert.assertEquals(0, ents[4].getLevel());
 
         Assert.assertEquals(0, ents[0].getLane());
-        Assert.assertEquals(0, ents[1].getLane());
-        Assert.assertEquals(2, ents[2].getLane());
-        Assert.assertEquals(1, ents[3].getLane());
-        Assert.assertEquals(1, ents[4].getLane());
+        Assert.assertEquals(1, ents[1].getLane());
+        Assert.assertEquals(3, ents[2].getLane());
+        Assert.assertEquals(4, ents[3].getLane());
+        Assert.assertEquals(2, ents[4].getLane());
 
     }
 }
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 ff2723dac7..81384ef840 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
@@ -17,10 +17,8 @@
  * specific language governing permissions and limitations
  * under the License.    
 -->
-<composite xmlns="http://docs.oasis-open.org/ns/opencsa/sca/200912"
-           targetNamespace="http://sample"
-           xmlns:sample="http://sample"
-           name="Calculator2">
+<composite xmlns="http://docs.oasis-open.org/ns/opencsa/sca/200912" targetNamespace="http://sample"
+    xmlns:sample="http://sample" name="Calculator2">
 
     <component name="CalculatorServiceComponent">
         <implementation.java class="calculator.CalculatorServiceImpl" />
@@ -28,11 +26,17 @@
         <reference name="subtractService" target="SubtractServiceComponent" />
         <reference name="multiplyService" target="MultiplyServiceComponent" />
         <reference name="divideService" target="DivideServiceComponent" />
-        
+
         <reference name="addService2" target="AddServiceComponent2" />
         <reference name="subtractService2" target="SubtractServiceComponent2" />
         <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" />
+
     </component>
 
     <component name="AddServiceComponent">
@@ -67,4 +71,20 @@
         <implementation.java class="calculator.DivideServiceImpl" />
     </component>
 
+    <component name="AddServiceComponent3">
+        <implementation.java class="calculator.AddServiceImpl" />
+    </component>
+
+    <component name="SubtractServiceComponent3">
+        <implementation.java class="calculator.SubtractServiceImpl" />
+    </component>
+
+    <component name="MultiplyServiceComponent3">
+        <implementation.java class="calculator.MultiplyServiceImpl" />
+    </component>
+
+    <component name="DivideServiceComponent3">
+        <implementation.java class="calculator.DivideServiceImpl" />
+    </component>
+
 </composite>
\ No newline at end of file