Mercurial > projects > dwt-addons

comparison dwtx/draw2d/graph/NodeCluster.d @ 98:95307ad235d9

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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) 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.NodeCluster;
14
15 import dwt.dwthelper.utils;
16 import dwtx.dwtxhelper.Collection;
17 import dwtx.draw2d.graph.NodeList;
18 import dwtx.draw2d.graph.CollapsedEdges;
19
20 /**
21 * A group of nodes which are interlocked and cannot be separately placed.
22 * @since 3.1
23 */
24 class NodeCluster : NodeList {
25
26 alias NodeList.adjustRank adjustRank;
27
28 int toHash_;
29
30 bool isSetMember;
31 bool isDirty;
32 bool leftDirty;
33 bool rightDirty;
34
35 int leftFreedom;
36 int rightFreedom;
37 int leftNonzero;
38 int rightNonzero;
39 int leftCount = 0;
40 int rightCount = 0;
41
42 CollapsedEdges[] leftLinks;
43 CollapsedEdges[] rightLinks;
44 NodeCluster[] leftNeighbors;
45 NodeCluster[] rightNeighbors;
46
47 int effectivePull;
48 int weightedTotal;
49 int weightedDivisor;
50 int unweightedTotal;
51 int unweightedDivisor;
52
53 public this(){
54 toHash_ = (new Object()).toHash();
55 leftLinks = new CollapsedEdges[10];
56 rightLinks = new CollapsedEdges[10];
57 leftNeighbors = new NodeCluster[10];
58 rightNeighbors = new NodeCluster[10];
59 }
60
61 void addLeftNeighbor(NodeCluster neighbor, CollapsedEdges link) {
62 //Need to grow array in the following case
63 if (leftNeighbors.length is leftCount) {
64 int newSize = leftNeighbors.length * 2;
65
66 NodeCluster newNeighbors[] = new NodeCluster[newSize];
67 CollapsedEdges newLinks[] = new CollapsedEdges[newSize];
68
69 System.arraycopy(leftNeighbors, 0, newNeighbors, 0, leftNeighbors.length);
70 System.arraycopy(leftLinks, 0, newLinks, 0, leftLinks.length);
71
72 leftNeighbors = newNeighbors;
73 leftLinks = newLinks;
74 }
75 leftNeighbors[leftCount] = neighbor;
76 leftLinks[leftCount++] = link;
77 }
78
79 void addRightNeighbor(NodeCluster neighbor, CollapsedEdges link) {
80 if (rightNeighbors.length is rightCount) {
81 int newSize = rightNeighbors.length * 2;
82
83 NodeCluster newNeighbors[] = new NodeCluster[newSize];
84 CollapsedEdges newLinks[] = new CollapsedEdges[newSize];
85
86 System.arraycopy(rightNeighbors, 0, newNeighbors, 0, rightNeighbors.length);
87 System.arraycopy(rightLinks, 0, newLinks, 0, rightLinks.length);
88
89 rightNeighbors = newNeighbors;
90 rightLinks = newLinks;
91 }
92 rightNeighbors[rightCount] = neighbor;
93 rightLinks[rightCount++] = link;
94 }
95
96 public void adjustRank(int delta, Collection affected) {
97 adjustRank(delta);
98 NodeCluster neighbor;
99 CollapsedEdges edges;
100 for (int i = 0; i < leftCount; i++) {
101 neighbor = leftNeighbors[i];
102 if (neighbor.isSetMember)
103 continue;
104 edges = leftLinks[i];
105
106 neighbor.weightedTotal += delta * edges.collapsedWeight;
107 neighbor.unweightedTotal += delta * edges.collapsedCount;
108
109 weightedTotal -= delta * edges.collapsedWeight;
110 unweightedTotal -= delta * edges.collapsedCount;
111
112 neighbor.rightDirty = leftDirty = true;
113 if (!neighbor.isDirty) {
114 neighbor.isDirty = true;
115 affected.add(neighbor);
116 }
117 }
118 for (int i = 0; i < rightCount; i++) {
119 neighbor = rightNeighbors[i];
120 if (neighbor.isSetMember)
121 continue;
122 edges = rightLinks[i];
123
124 neighbor.weightedTotal += delta * edges.collapsedWeight;
125 neighbor.unweightedTotal += delta * edges.collapsedCount;
126
127 weightedTotal -= delta * edges.collapsedWeight;
128 unweightedTotal -= delta * edges.collapsedCount;
129
130 neighbor.leftDirty = rightDirty = true;
131 if (!neighbor.isDirty) {
132 neighbor.isDirty = true;
133 affected.add(neighbor);
134 }
135 }
136 isDirty = true;
137 affected.add(this);
138 }
139
140 public override int opEquals(Object o) {
141 return o is this;
142 }
143
144 CollapsedEdges getLeftNeighbor(NodeCluster neighbor) {
145 for (int i = 0; i < leftCount; i++) {
146 if (leftNeighbors[i] is neighbor)
147 return leftLinks[i];
148 }
149 return null;
150 }
151
152 int getPull() {
153 return effectivePull;
154 }
155
156 CollapsedEdges getRightNeighbor(NodeCluster neighbor) {
157 for (int i = 0; i < rightCount; i++) {
158 if (rightNeighbors[i] is neighbor)
159 return rightLinks[i];
160 }
161 return null;
162 }
163
164 public override hash_t toHash() {
165 return toHash_;
166 }
167
168 /**
169 * Initializes pull and freedom values.
170 */
171 void initValues() {
172 weightedTotal = 0;
173 weightedDivisor = 0;
174 unweightedTotal = 0;
175 int slack;
176
177 leftNonzero = rightNonzero = leftFreedom = rightFreedom = Integer.MAX_VALUE;
178 for (int i = 0; i < leftCount; i++) {
179 CollapsedEdges edges = leftLinks[i];
180 weightedTotal -= edges.getWeightedPull();
181 unweightedTotal -= edges.tightestEdge.getSlack();
182 unweightedDivisor += edges.collapsedCount;
183 weightedDivisor += edges.collapsedWeight;
184 slack = edges.tightestEdge.getSlack();
185 leftFreedom = Math.min(slack, leftFreedom);
186 if (slack > 0)
187 leftNonzero = Math.min(slack, leftNonzero);
188 }
189 for (int i = 0; i < rightCount; i++) {
190 CollapsedEdges edges = rightLinks[i];
191 weightedTotal += edges.getWeightedPull();
192 unweightedDivisor += edges.collapsedCount;
193 unweightedTotal += edges.tightestEdge.getSlack();
194 weightedDivisor += edges.collapsedWeight;
195 slack = edges.tightestEdge.getSlack();
196 rightFreedom = Math.min(slack, rightFreedom);
197 if (slack > 0)
198 rightNonzero = Math.min(slack, rightNonzero);
199 }
200 updateEffectivePull();
201 }
202
203 /**
204 * Refreshes the left and right freedom.
205 */
206 void refreshValues() {
207 int slack;
208 isDirty = false;
209 if (leftDirty) {
210 leftDirty = false;
211 leftNonzero = leftFreedom = Integer.MAX_VALUE;
212 for (int i = 0; i < leftCount; i++) {
213 CollapsedEdges edges = leftLinks[i];
214 slack = edges.tightestEdge.getSlack();
215 leftFreedom = Math.min(slack, leftFreedom);
216 if (slack > 0)
217 leftNonzero = Math.min(slack, leftNonzero);
218 }
219 }
220 if (rightDirty) {
221 rightDirty = false;
222 rightNonzero = rightFreedom = Integer.MAX_VALUE;
223 for (int i = 0; i < rightCount; i++) {
224 CollapsedEdges edges = rightLinks[i];
225 slack = edges.tightestEdge.getSlack();
226 rightFreedom = Math.min(slack, rightFreedom);
227 if (slack > 0)
228 rightNonzero = Math.min(slack, rightNonzero);
229 }
230 }
231 updateEffectivePull();
232 }
233
234 private void updateEffectivePull() {
235 if (weightedDivisor !is 0)
236 effectivePull = weightedTotal / weightedDivisor;
237 else if (unweightedDivisor !is 0)
238 effectivePull = unweightedTotal / unweightedDivisor;
239 else
240 effectivePull = 0;
241 }
242
243 }