--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/dwtx/draw2d/graph/CompoundPopulateRanks.d	Sun Aug 03 00:52:14 2008 +0200
@@ -0,0 +1,86 @@
+/*******************************************************************************
+ * Copyright (c) 2003, 2005 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.CompoundPopulateRanks;
+
+import dwt.dwthelper.utils;
+import dwtx.dwtxhelper.Collection;
+import dwtx.draw2d.graph.PopulateRanks;
+import dwtx.draw2d.graph.DirectedGraph;
+import dwtx.draw2d.graph.Subgraph;
+import dwtx.draw2d.graph.CompoundDirectedGraph;
+import dwtx.draw2d.graph.Edge;
+import dwtx.draw2d.graph.NodeList;
+import dwtx.draw2d.graph.Node;
+
+/**
+ * Places nodes into ranks for a compound directed graph.  If a subgraph spans a rank
+ * without any nodes which belong to that rank, a bridge node is inserted to prevent nodes
+ * from violating the subgraph boundary.
+ * @author Randy Hudson
+ * @since 2.1.2
+ */
+class CompoundPopulateRanks : PopulateRanks {
+
+public void visit(DirectedGraph g) {
+    CompoundDirectedGraph graph = cast(CompoundDirectedGraph)g;
+
+    /**
+     * Remove long containment edges at this point so they don't affect MinCross.
+     */
+    Iterator containment = graph.containment.iterator();
+    while (containment.hasNext()) {
+        Edge e = cast(Edge)containment.next();
+        if (e.getSlack() > 0) {
+            graph.removeEdge(e);
+            containment.remove();
+        }
+    }
+
+    super.visit(g);
+    NodeList subgraphs = graph.subgraphs;
+    for (int i = 0; i < subgraphs.size(); i++) {
+        Subgraph subgraph = cast(Subgraph)subgraphs.get(i);
+        bridgeSubgraph(subgraph, graph);
+    }
+}
+
+/**
+ * @param subgraph
+ */
+private void bridgeSubgraph(Subgraph subgraph, CompoundDirectedGraph g) {
+    int offset = subgraph.head.rank;
+    bool occupied[] = new bool[subgraph.tail.rank - subgraph.head.rank + 1];
+    Node bridge[] = new Node[occupied.length];
+
+    for (int i = 0; i < subgraph.members.size(); i++) {
+        Node n = cast(Node)subgraph.members.get(i);
+        if (auto s = cast(Subgraph)n ) {
+            for (int r = s.head.rank; r <= s.tail.rank; r++)
+                occupied[r - offset] = true;
+        } else
+            occupied[n.rank - offset] = true;
+    }
+
+    for (int i = 0; i < bridge.length; i++) {
+        if (!occupied[i]) {
+            Node br = bridge[i] = new Node(stringcast("bridge"), subgraph); //$NON-NLS-1$
+            br.rank = i + offset;
+            br.height = br.width = 0;
+            br.nestingIndex = subgraph.nestingIndex;
+            g.ranks.getRank(br.rank).add(br);
+            g.nodes.add(br);
+        }
+    }
+}
+
+}