Mercurial > projects > dwt-addons
comparison dwtx/draw2d/graph/RankSorter.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, 2005 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.RankSorter; | |
14 | |
15 import dwt.dwthelper.utils; | |
16 import dwtx.dwtxhelper.Collection; | |
17 import dwtx.dwtxhelper.Random; | |
18 import dwtx.draw2d.graph.Node; | |
19 import dwtx.draw2d.graph.Rank; | |
20 import dwtx.draw2d.graph.DirectedGraph; | |
21 import dwtx.draw2d.graph.EdgeList; | |
22 import dwtx.draw2d.graph.Edge; | |
23 import dwtx.draw2d.graph.GraphUtilities; | |
24 | |
25 /** | |
26 * Sorts Ranks during the up and down sweeps of the MinCross visitor. | |
27 * @author Randy Hudson | |
28 * @since 2.1.2 | |
29 */ | |
30 class RankSorter { | |
31 | |
32 Random flipflop; | |
33 Node node; | |
34 double rankSize, prevRankSize, nextRankSize; | |
35 int currentRow; | |
36 Rank rank; | |
37 double progress; | |
38 DirectedGraph g; | |
39 | |
40 public this(){ | |
41 flipflop = new Random(3); | |
42 } | |
43 | |
44 protected void assignIncomingSortValues() { | |
45 rankSize = rank.total; | |
46 prevRankSize = g.ranks.getRank(currentRow - 1).total; | |
47 if (currentRow < g.ranks.size() - 1) | |
48 nextRankSize = g.ranks.getRank(currentRow + 1).total; | |
49 for (int n = 0; n < rank.count(); n++) { | |
50 node = rank.getNode(n); | |
51 sortValueIncoming(); | |
52 } | |
53 } | |
54 | |
55 protected void assignOutgoingSortValues() { | |
56 rankSize = rank.total; | |
57 prevRankSize = g.ranks.getRank(currentRow + 1).total; | |
58 if (currentRow > 1) | |
59 nextRankSize = g.ranks.getRank(currentRow - 1).total; | |
60 | |
61 for (int n = 0; n < rank.count(); n++) { | |
62 node = rank.getNode(n); | |
63 sortValueOutgoing(); | |
64 } | |
65 } | |
66 | |
67 double evaluateNodeIncoming() { | |
68 bool change = false; | |
69 EdgeList incoming = node.incoming; | |
70 do { | |
71 change = false; | |
72 for (int i = 0; i < incoming.size() - 1; i++) { | |
73 if (incoming.getSourceIndex(i) > incoming.getSourceIndex(i + 1)) { | |
74 Edge e = incoming.getEdge(i); | |
75 incoming.set(i, incoming.get(i + 1)); | |
76 incoming.set(i + 1, e); | |
77 change = true; | |
78 } | |
79 } | |
80 } while (change); | |
81 | |
82 int n = incoming.size(); | |
83 if (n is 0) { | |
84 return node.index * prevRankSize / rankSize; | |
85 } | |
86 if (n % 2 is 1) | |
87 return incoming.getSourceIndex(n / 2); | |
88 | |
89 int l = incoming.getSourceIndex(n / 2 - 1); | |
90 int r = incoming.getSourceIndex(n / 2); | |
91 if (progress >= 0.8 && n > 2) { | |
92 int dl = l - incoming.getSourceIndex(0); | |
93 int dr = incoming.getSourceIndex(n - 1) - r; | |
94 if (dl < dr) | |
95 return l; | |
96 if (dl > dr) | |
97 return r; | |
98 } | |
99 if (progress > 0.25 && progress < 0.75) { | |
100 if (flipflop.nextBoolean()) | |
101 return (l + l + r) / 3.0; | |
102 else | |
103 return (r + r + l) / 3.0; | |
104 } | |
105 return (l + r) / 2.0; | |
106 } | |
107 | |
108 double evaluateNodeOutgoing() { | |
109 bool change = false; | |
110 EdgeList outgoing = node.outgoing; | |
111 do { | |
112 change = false; | |
113 for (int i = 0; i < outgoing.size() - 1; i++) { | |
114 if (outgoing.getTargetIndex(i) > outgoing.getTargetIndex(i + 1)) { | |
115 Edge e = outgoing.getEdge(i); | |
116 outgoing.set(i, outgoing.get(i + 1)); | |
117 outgoing.set(i + 1, e); | |
118 change = true; | |
119 } | |
120 } | |
121 } while (change); | |
122 | |
123 int n = outgoing.size(); | |
124 if (n is 0) | |
125 return node.index * prevRankSize / rankSize; | |
126 if (n % 2 is 1) | |
127 return outgoing.getTargetIndex(n / 2); | |
128 int l = outgoing.getTargetIndex(n / 2 - 1); | |
129 int r = outgoing.getTargetIndex(n / 2); | |
130 if (progress >= 0.8 && n > 2) { | |
131 int dl = l - outgoing.getTargetIndex(0); | |
132 int dr = outgoing.getTargetIndex(n - 1) - r; | |
133 if (dl < dr) | |
134 return l; | |
135 if (dl > dr) | |
136 return r; | |
137 } | |
138 if (progress > 0.25 && progress < 0.75) { | |
139 if (flipflop.nextBoolean()) | |
140 return (l + l + r) / 3.0; | |
141 else | |
142 return (r + r + l) / 3.0; | |
143 } | |
144 return (l + r) / 2.0; | |
145 } | |
146 | |
147 public void sortRankIncoming(DirectedGraph g, Rank rank, int row, double progress) { | |
148 this.currentRow = row; | |
149 this.rank = rank; | |
150 this.progress = progress; | |
151 assignIncomingSortValues(); | |
152 sort(); | |
153 postSort(); | |
154 } | |
155 | |
156 public void init(DirectedGraph g) { | |
157 this.g = g; | |
158 for (int i = 0; i < g.ranks.size(); i++) { | |
159 rank = g.ranks.getRank(i); | |
160 | |
161 //Sort the ranks based on their constraints. Constraints are preserved throughout. | |
162 Collections.sort(rank, new class() Comparator { | |
163 public int compare(Object left, Object right) { | |
164 return (cast(Node)left).rowOrder - (cast(Node)right).rowOrder; | |
165 } | |
166 }); | |
167 postSort(); | |
168 } | |
169 } | |
170 | |
171 void optimize(DirectedGraph g) { | |
172 } | |
173 | |
174 protected void postSort() { | |
175 rank.assignIndices(); | |
176 } | |
177 | |
178 void sort() { | |
179 bool change; | |
180 do { | |
181 change = false; | |
182 for (int i = 0; i < rank.size() - 1; i++) | |
183 change |= swap(i); | |
184 if (!change) | |
185 break; | |
186 change = false; | |
187 for (int i = rank.size() - 2; i >= 0; i--) | |
188 change |= swap(i); | |
189 } while (change); | |
190 } | |
191 | |
192 bool swap(int i) { | |
193 Node left = rank.getNode(i); | |
194 Node right = rank.getNode(i + 1); | |
195 if (GraphUtilities.isConstrained(left, right)) | |
196 return false; | |
197 if (left.sortValue <= right.sortValue) | |
198 return false; | |
199 rank.set(i, right); | |
200 rank.set(i + 1, left); | |
201 return true; | |
202 } | |
203 | |
204 public void sortRankOutgoing(DirectedGraph g, Rank rank, int row, double progress) { | |
205 this.currentRow = row; | |
206 this.rank = rank; | |
207 this.progress = progress; | |
208 assignOutgoingSortValues(); | |
209 sort(); | |
210 postSort(); | |
211 } | |
212 | |
213 void sortValueIncoming() { | |
214 node.sortValue = evaluateNodeIncoming(); | |
215 //$TODO restore this optimization | |
216 // if (progress is 0.0 && !(node instanceof VirtualNode)) | |
217 // node.sortValue = -1; | |
218 double value = evaluateNodeOutgoing(); | |
219 if (value < 0) | |
220 value = node.index * nextRankSize / rankSize; | |
221 node.sortValue += value * progress; | |
222 // if (progress < 0.7 && node.sortValue !is -1) | |
223 // node.sortValue += Math.random() * rankSize / (5 + 8 * progress); | |
224 } | |
225 | |
226 void sortValueOutgoing() { | |
227 node.sortValue = evaluateNodeOutgoing(); | |
228 //$TODO restore this optimization | |
229 // if (progress is 0.0 && !(node instanceof VirtualNode)) | |
230 // node.sortValue = -1; | |
231 double value = evaluateNodeIncoming(); | |
232 if (value < 0) | |
233 value = node.index * nextRankSize / rankSize; | |
234 node.sortValue += value * progress; | |
235 // if (progress < 0.7 && node.sortValue !is -1) | |
236 // node.sortValue += Math.random() * rankSize / (5 + 8 * progress); | |
237 } | |
238 | |
239 } |