Mercurial > projects > dwt-addons
comparison dwtx/draw2d/graph/PopulateRanks.d @ 98:95307ad235d9
Added Draw2d code, still work in progress
author | Frank Benoit <benoit@tionex.de> |
---|---|
date | Sun, 03 Aug 2008 00:52:14 +0200 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
96:b492ba44e44d | 98:95307ad235d9 |
---|---|
1 /******************************************************************************* | |
2 * Copyright (c) 2003, 2008 IBM Corporation and others. | |
3 * All rights reserved. This program and the accompanying materials | |
4 * are made available under the terms of the Eclipse Public License v1.0 | |
5 * which accompanies this distribution, and is available at | |
6 * http://www.eclipse.org/legal/epl-v10.html | |
7 * | |
8 * Contributors: | |
9 * IBM Corporation - initial API and implementation | |
10 * Port to the D programming language: | |
11 * Frank Benoit <benoit@tionex.de> | |
12 *******************************************************************************/ | |
13 module dwtx.draw2d.graph.PopulateRanks; | |
14 | |
15 import dwt.dwthelper.utils; | |
16 import dwtx.dwtxhelper.Collection; | |
17 import dwtx.draw2d.graph.RevertableChange; | |
18 import dwtx.draw2d.graph.GraphVisitor; | |
19 import dwtx.draw2d.graph.DirectedGraph; | |
20 import dwtx.draw2d.graph.RankList; | |
21 import dwtx.draw2d.graph.Rank; | |
22 import dwtx.draw2d.graph.Node; | |
23 import dwtx.draw2d.graph.Edge; | |
24 import dwtx.draw2d.graph.VirtualNodeCreation; | |
25 | |
26 /** | |
27 * This class takes a DirectedGraph with an optimal rank assignment and a spanning tree, | |
28 * and populates the ranks of the DirectedGraph. Virtual nodes are inserted for edges that | |
29 * span 1 or more ranks. | |
30 * <P> | |
31 * Ranks are populated using a pre-order depth-first traversal of the spanning tree. For | |
32 * each node, all edges requiring virtual nodes are added to the ranks. | |
33 * @author Randy Hudson | |
34 * @since 2.1.2 | |
35 */ | |
36 class PopulateRanks : GraphVisitor { | |
37 | |
38 private Stack changes; | |
39 | |
40 public this(){ | |
41 changes = new Stack(); | |
42 } | |
43 /** | |
44 * @see GraphVisitor#visit(DirectedGraph) | |
45 */ | |
46 public void visit(DirectedGraph g) { | |
47 if (g.forestRoot !is null) { | |
48 for (int i = g.forestRoot.outgoing.size() - 1; i >= 0; i--) | |
49 g.removeEdge(g.forestRoot.outgoing.getEdge(i)); | |
50 g.removeNode(g.forestRoot); | |
51 } | |
52 g.ranks = new RankList(); | |
53 for (int i = 0; i < g.nodes.size(); i++) { | |
54 Node node = g.nodes.getNode(i); | |
55 g.ranks.getRank(node.rank).add(node); | |
56 } | |
57 for (int i = 0; i < g.nodes.size(); i++) { | |
58 Node node = g.nodes.getNode(i); | |
59 for (int j = 0; j < node.outgoing.size();) { | |
60 Edge e = node.outgoing.getEdge(j); | |
61 if (e.getLength() > 1) | |
62 changes.push(new VirtualNodeCreation(e, g)); | |
63 else | |
64 j++; | |
65 } | |
66 } | |
67 } | |
68 | |
69 /** | |
70 * @see GraphVisitor#revisit(DirectedGraph) | |
71 */ | |
72 public void revisit(DirectedGraph g) { | |
73 for (int r = 0; r < g.ranks.size(); r++) { | |
74 Rank rank = g.ranks.getRank(r); | |
75 Node prev = null, cur; | |
76 for (int n = 0; n < rank.size(); n++) { | |
77 cur = rank.getNode(n); | |
78 cur.left = prev; | |
79 if (prev !is null) { | |
80 prev.right = cur; | |
81 } | |
82 prev = cur; | |
83 } | |
84 } | |
85 for (int i = 0; i < changes.size(); i++) { | |
86 RevertableChange change = cast(RevertableChange)changes.get(i); | |
87 change.revert(); | |
88 } | |
89 } | |
90 | |
91 } |