--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/dwtx/draw2d/graph/HorizontalPlacement.d	Sun Aug 03 00:52:14 2008 +0200
@@ -0,0 +1,428 @@
+/*******************************************************************************
+ * Copyright (c) 2003, 2007 IBM Corporation and others.
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ *     IBM Corporation - initial API and implementation
+ * Port to the D programming language:
+ *     Frank Benoit <benoit@tionex.de>
+ *******************************************************************************/
+module dwtx.draw2d.graph.HorizontalPlacement;
+
+import dwt.dwthelper.utils;
+import dwtx.dwtxhelper.Collection;
+import dwtx.draw2d.graph.SpanningTreeVisitor;
+import dwtx.draw2d.graph.NodeCluster;
+import dwtx.draw2d.graph.NodePair;
+import dwtx.draw2d.graph.Node;
+import dwtx.draw2d.graph.Edge;
+import dwtx.draw2d.graph.DirectedGraph;
+import dwtx.draw2d.graph.RankList;
+import dwtx.draw2d.graph.CollapsedEdges;
+import dwtx.draw2d.graph.Rank;
+import dwtx.draw2d.graph.EdgeList;
+import dwtx.draw2d.graph.InitialRankSolver;
+import dwtx.draw2d.graph.TightSpanningTreeSolver;
+import dwtx.draw2d.graph.RankAssignmentSolver;
+
+/**
+ * Assigns the X and width values for nodes in a directed graph.
+ * @author Randy Hudson
+ * @since 2.1.2
+ */
+class HorizontalPlacement : SpanningTreeVisitor {
+
+class ClusterSet {
+    int freedom = Integer.MAX_VALUE;
+    bool isRight;
+    public List members;
+    int pullWeight = 0;
+    int rawPull = 0;
+
+    public this(){
+        members = new ArrayList();
+    }
+
+    bool addCluster (NodeCluster seed) {
+        members.add(seed);
+        seed.isSetMember = true;
+
+        rawPull += seed.weightedTotal;
+        pullWeight += seed.weightedDivisor;
+        if (isRight) {
+            freedom = Math.min(freedom, seed.rightNonzero);
+            if (freedom is 0 || rawPull <= 0)
+                return true;
+            addIncomingClusters(seed);
+            if (addOutgoingClusters(seed))
+                return true;
+        } else {
+            freedom = Math.min(freedom, seed.leftNonzero);
+            if (freedom is 0 || rawPull >= 0)
+                return true;
+            addOutgoingClusters(seed);
+            if (addIncomingClusters(seed))
+                return true;
+        }
+        return false;
+    }
+
+    bool addIncomingClusters(NodeCluster seed) {
+        for (int i = 0; i < seed.leftCount; i++) {
+            NodeCluster neighbor = seed.leftNeighbors[i];
+            if (neighbor.isSetMember)
+                continue;
+            CollapsedEdges edges = seed.leftLinks[i];
+            if (!edges.isTight())
+                continue;
+            if ((!isRight || neighbor.getPull() > 0) && addCluster (neighbor))
+                return true;
+        }
+        return false;
+    }
+
+    bool addOutgoingClusters(NodeCluster seed) {
+        for (int i = 0; i < seed.rightCount; i++) {
+            NodeCluster neighbor = seed.rightNeighbors[i];
+            if (neighbor.isSetMember)
+                continue;
+            CollapsedEdges edges = seed.rightLinks[i];
+            if (!edges.isTight())
+                continue;
+            if ((isRight || neighbor.getPull() < 0) && addCluster (neighbor))
+                    return true;
+        }
+        return false;
+    }
+
+    bool build(NodeCluster seed) {
+        isRight = seed.weightedTotal > 0;
+        if (!addCluster(seed)) {
+            int delta = rawPull / pullWeight;
+            if (delta < 0)
+                delta = Math.max(delta, -freedom);
+            else
+                delta = Math.min(delta, freedom);
+            if (delta !is 0) {
+                for (int i = 0; i < members.size(); i++) {
+                    NodeCluster c = cast(NodeCluster)members.get(i);
+                    c.adjustRank(delta, dirtyClusters);
+                }
+                refreshDirtyClusters();
+                reset();
+                return true;
+            }
+        }
+        reset();
+        return false;
+    }
+
+    void reset() {
+        rawPull = pullWeight = 0;
+        for (int i = 0; i < members.size(); i++)
+            (cast(NodeCluster)members.get(i)).isSetMember = false;
+        members.clear();
+        freedom = Integer.MAX_VALUE;
+    }
+}
+
+static int step;
+private List allClusters;
+private Map clusterMap;
+ClusterSet clusterset;
+Collection dirtyClusters;
+DirectedGraph graph;
+Map map_;
+DirectedGraph prime;
+Node graphRight;
+Node graphLeft;
+
+public this(){
+    clusterMap = new HashMap();
+    clusterset = new ClusterSet();
+    dirtyClusters = new HashSet();
+    map_ = new HashMap();
+}
+
+
+/**
+ * Inset the corresponding parts for the given 2 nodes along an edge E.  The weight value
+ * is a value by which to scale the edges specified weighting factor.
+ * @param u the source
+ * @param v the target
+ * @param e the edge along which u and v exist
+ * @param weight a scaling for the weight
+ */
+void addEdge(Node u, Node v, Edge e, int weight) {
+    Node ne = new Node(new NodePair(u, v));
+    prime.nodes.add(ne);
+
+    ne.y = (u.y + u.height + v.y) / 2;
+    Node uPrime = get(u);
+    Node vPrime = get(v);
+
+    int uOffset = e.getSourceOffset();
+
+    int vOffset = e.getTargetOffset();
+
+    Edge eu = new Edge(ne, uPrime, 0, e.weight * weight);
+    Edge ev = new Edge(ne, vPrime, 0, e.weight * weight);
+
+    int dw = uOffset - vOffset;
+    if (dw < 0)
+        eu.delta = -dw;
+    else
+        ev.delta = dw;
+
+    prime.edges.add(eu);
+    prime.edges.add(ev);
+}
+
+/**
+ * Adds all of the incoming edges to the graph.
+ * @param n the original node
+ * @param nPrime its corresponding node in the auxilary graph
+ */
+void addEdges(Node n) {
+    for (int i = 0; i < n.incoming.size(); i++) {
+        Edge e = n.incoming.getEdge(i);
+        addEdge(e.source, n, e, 1);
+    }
+}
+
+void applyGPrime() {
+    Node node;
+    for (int n = 0; n < prime.nodes.size(); n++) {
+        node = prime.nodes.getNode(n);
+        if (null !is cast(Node)node.data )
+            (cast(Node)node.data).x = node.rank;
+    }
+}
+
+private void balanceClusters() {
+    findAllClusters();
+
+    step = 0;
+    bool somethingMoved = false;
+
+    for (int i = 0; i < allClusters.size();) {
+
+        NodeCluster c = cast(NodeCluster)allClusters.get(i);
+        int delta = c.getPull();
+        if (delta < 0) {
+            if (c.leftFreedom > 0) {
+                c.adjustRank(Math.max(delta, -c.leftFreedom), dirtyClusters);
+                refreshDirtyClusters();
+                moveClusterForward(i, c);
+                somethingMoved = true;
+                step++;
+            } else if (clusterset.build(c)) {
+                step++;
+                moveClusterForward(i, c);
+                somethingMoved = true;
+            }
+        } else if (delta > 0) {
+            if (c.rightFreedom > 0) {
+                c.adjustRank(Math.min(delta, c.rightFreedom), dirtyClusters);
+                refreshDirtyClusters();
+                moveClusterForward(i, c);
+                somethingMoved = true;
+                step++;
+            } else if (clusterset.build(c)) {
+                step++;
+                moveClusterForward(i, c);
+                somethingMoved = true;
+            }
+        }
+        i++;
+        if (i is allClusters.size() && somethingMoved) {
+            i = 0;
+            somethingMoved = false;
+        }
+    }
+}
+
+//bool balanceClusterSets() {
+//  for (int i = 0; i < allClusters.size(); i++) {
+//      NodeCluster c = (NodeCluster)allClusters.get(i);
+//      if (c.weightedTotal < 0 && c.leftFreedom is 0) {
+//          if (clusterset.build(c)) {
+//              moveClusterForward(i, c);
+//              return true;
+//          }
+//      } else if (c.weightedTotal > 0 && c.rightFreedom is 0) {
+//          if (clusterset.build(c)) {
+//              moveClusterForward(i, c);
+//              return true;
+//          }
+//      }
+//  }
+//  return false;
+//}
+
+void buildGPrime() {
+    RankList ranks = graph.ranks;
+    buildRankSeparators(ranks);
+
+    Rank rank;
+    Node n;
+    for (int r = 1; r < ranks.size(); r++) {
+        rank = ranks.getRank(r);
+        for (int i = 0; i < rank.count(); i++) {
+            n = rank.getNode(i);
+            addEdges(n);
+        }
+    }
+}
+
+void buildRankSeparators(RankList ranks) {
+    Rank rank;
+    Node n, nPrime, prevNPrime;
+    Edge e;
+    for (int r = 0; r < ranks.size(); r++) {
+        rank = ranks.getRank(r);
+        prevNPrime = null;
+        for (int i = 0; i < rank.count(); i++) {
+            n = rank.getNode(i);
+            nPrime = new Node(n);
+            if (i is 0) {
+                e = new Edge(graphLeft, nPrime, 0, 0);
+                prime.edges.add(e);
+                e.delta = graph.getPadding(n).left + graph.getMargin().left;
+            } else {
+                e = new Edge(prevNPrime, nPrime);
+                e.weight = 0;
+                prime.edges.add(e);
+                rowSeparation(e);
+            }
+            prevNPrime = nPrime;
+            prime.nodes.add(nPrime);
+            map(n, nPrime);
+            if (i is rank.count() - 1) {
+                e = new Edge(nPrime, graphRight, 0, 0);
+                e.delta = n.width + graph.getPadding(n).right + graph.getMargin().right;
+                prime.edges.add(e);
+            }
+        }
+    }
+}
+
+private void calculateCellLocations() {
+    graph.cellLocations = new int[][](graph.ranks.size() + 1);
+    for (int row = 0; row < graph.ranks.size(); row++) {
+        Rank rank = graph.ranks.getRank(row);
+        int locations[] = graph.cellLocations[row] = new int[rank.size() + 1];
+        int cell;
+        Node node = null;
+        for (cell = 0; cell < rank.size(); cell++) {
+            node = rank.getNode(cell);
+            locations[cell] = node.x - graph.getPadding(node).left;
+        }
+        locations[cell] = node.x + node.width + graph.getPadding(node).right;
+    }
+}
+
+private void findAllClusters() {
+    Node root = prime.nodes.getNode(0);
+    NodeCluster cluster = new NodeCluster();
+    allClusters = new ArrayList();
+    allClusters.add(cluster);
+    growCluster(root, cluster);
+
+    for (int i = 0; i < prime.edges.size(); i++) {
+        Edge e = prime.edges.getEdge(i);
+        NodeCluster sourceCluster = cast(NodeCluster)clusterMap.get(e.source);
+        NodeCluster targetCluster = cast(NodeCluster)clusterMap.get(e.target);
+
+        //Ignore cluster internal edges
+        if (targetCluster is sourceCluster)
+            continue;
+
+        CollapsedEdges link = sourceCluster.getRightNeighbor(targetCluster);
+        if (link is null) {
+            link = new CollapsedEdges(e);
+            sourceCluster.addRightNeighbor(targetCluster, link);
+            targetCluster.addLeftNeighbor(sourceCluster, link);
+        } else {
+            prime.removeEdge(link.processEdge(e));
+            i--;
+        }
+    }
+    for (int i = 0; i < allClusters.size(); i++)
+        (cast(NodeCluster)allClusters.get(i)).initValues();
+}
+
+Node get(Node key) {
+    return cast(Node)map_.get(key);
+}
+
+void growCluster(Node root, NodeCluster cluster) {
+    cluster.add(root);
+    clusterMap.put(root, cluster);
+    EdgeList treeChildren = getSpanningTreeChildren(root);
+    for (int i = 0; i < treeChildren.size(); i++) {
+        Edge e = treeChildren.getEdge(i);
+        if (e.cut !is 0)
+            growCluster(getTreeTail(e), cluster);
+        else {
+            NodeCluster newCluster = new NodeCluster();
+            allClusters.add(newCluster);
+            growCluster(getTreeTail(e), newCluster);
+        }
+    }
+}
+
+void map(Node key, Node value) {
+    map_.put(key, value);
+}
+
+private void moveClusterForward(int i, NodeCluster c) {
+    if (i is 0)
+        return;
+    int swapIndex = i / 2;
+    Object temp = allClusters.get(swapIndex);
+    allClusters.set(swapIndex, c);
+    allClusters.set(i, temp);
+}
+
+void refreshDirtyClusters() {
+    for (Iterator iter = dirtyClusters.iterator(); iter.hasNext();)
+        (cast(NodeCluster)iter.next()).refreshValues();
+    dirtyClusters.clear();
+}
+
+void rowSeparation(Edge e) {
+    Node source = cast(Node)e.source.data;
+    Node target = cast(Node)e.target.data;
+    e.delta = source.width
+        + graph.getPadding(source).right
+        + graph.getPadding(target).left;
+}
+
+public void visit(DirectedGraph g) {
+    graph = g;
+    prime = new DirectedGraph();
+    prime.nodes.add(graphLeft = new Node(cast(Object)null));
+    prime.nodes.add(graphRight = new Node(cast(Object)null));
+    if (g.tensorStrength !is 0)
+        prime.edges.add(new Edge(graphLeft, graphRight, g.tensorSize, g.tensorStrength));
+    buildGPrime();
+    (new InitialRankSolver())
+        .visit(prime);
+    (new TightSpanningTreeSolver())
+        .visit(prime);
+
+    RankAssignmentSolver solver = new RankAssignmentSolver();
+    solver.visit(prime);
+    graph.size.width = graphRight.rank;
+    balanceClusters();
+
+    prime.nodes.adjustRank(-graphLeft.rank);
+    applyGPrime();
+    calculateCellLocations();
+}
+
+}