Source code: com/port80/graph/dot/impl/GridFactory.java
1 //
2 // Copyright(c) 2002, Chris Leung
3 //
4
5 package com.port80.graph.dot.impl;
6
7 import java.util.Arrays;
8
9 import com.port80.util.Debug;
10 import com.port80.util.msg;
11 import com.port80.util.sprint;
12 import com.port80.util.struct.IntList;
13
14 /**
15 * Grid factory for vertices in a given VirtualGraph.
16 * This class provide methods to create and manipulate Grid objects for the given VirtualGraph.
17 *
18 * To avoid allocation of lots of Grid object that are used only for
19 * a short time. The Grid factory maintains a pool of allocated Grid objects.
20 *
21 * @author chrisl
22 */
23 public class GridFactory {
24
25 ////////////////////////////////////////////////////////////////////////
26
27 private static final String NAME = "GridFactory";
28 private static final boolean DEBUG = false;
29 private static boolean CHECK = Debug.isCheck();
30
31 private static final int CAPACITY = 4196;
32 private static int fMAXSIZE = 0;
33
34 ////////////////////////////////////////////////////////////////////////
35
36 VirtualGraph fGraph;
37 Grid[] fPool;
38 Grid fSpare;
39 int fSize;
40 /** Space map. [0, left0, right0, left1, right1,..., maxx] for each rank. */
41 int[][] fSpaceTable;
42 /** Valid X coordinates in each rank. x0,x1, ... */
43 IntList[] fValidXTable;
44 /** Created grids in each rank. */
45 Grid[][] fGridTable;
46 int fMaxX;
47
48 VirtualVertex fSrc;
49 VirtualVertex fDest;
50
51 private int fXDIV_EDGES;
52 private int fXDIV_XEDGE;
53 private int fCELL_DISTFACTOR;
54
55 private int fXESpacing;
56 private int fESpacing;
57 private int fHalfESpacing;
58 private int fVVWidth;
59 private int fStep;
60
61 // Constructors ////////////////////////////////////////////////////////
62 //
63
64 /*
65 * Protected constructor for unit testing.
66 */
67 GridFactory() {}
68
69 public GridFactory(VirtualGraph graph, int griddiv) {
70 //
71 fGraph = graph;
72 //
73 fXDIV_EDGES = fGraph.fXDIV_EDGES;
74 fXDIV_XEDGE = fGraph.fXDIV_XEDGE;
75 fCELL_DISTFACTOR = fGraph.fCELL_DISTFACTOR;
76 //
77 int vspacing = graph.getVertexSpacing();
78 fXESpacing = vspacing / fXDIV_XEDGE;
79 fESpacing = vspacing / fXDIV_EDGES;
80 fHalfESpacing = fESpacing / 2;
81 fStep=fESpacing/griddiv;
82
83 fPool = new Grid[0];
84 growTo(CAPACITY);
85
86 /**
87 * Create the map from given VirtualGraph.
88 *
89 * Main data structure built are:
90 * <li>fVertexTable that maps the VirtualVertex into Grids.</li>
91 * <li>fSpaceTable for space interval lookup.</li>
92 */
93 //
94 int height = graph.maxRank + 1;
95 fSpaceTable = new int[height][];
96 fValidXTable = new IntList[height];
97 fGridTable = new Grid[height][];
98 initSpaceTable();
99 for (int r = graph.minRank; r <= graph.maxRank; ++r) {
100 fValidXTable[r] = new IntList(256);
101 }
102 }
103
104 ////////////////////////////////////////////////////////////////////////
105
106 void initSpaceTable() {
107 VirtualGraph.Rank rank, rank1;
108 VirtualVertex v;
109 int cn;
110 int maxvts = 0;
111 int maxx = 0;
112 int[] spaces;
113 for (int r = fGraph.minRank; r <= fGraph.maxRank; ++r) {
114 rank = fGraph.ranks[r];
115 if (r < fGraph.maxRank)
116 rank1 = fGraph.ranks[r + 1];
117 else
118 rank1 = null;
119 if (rank.nVts > maxvts)
120 maxvts = rank.nVts;
121 spaces = new int[rank.nVts * 2 + 2];
122 spaces[0] = 0;
123 cn = 0;
124 for (int i = 0; i < rank.nVts; ++i) {
125 v = rank.vts[i];
126 // A gap of fXESpacing is left for routing.
127 spaces[++cn] = leftBorder(v);
128 spaces[++cn] = rightBorder(v);
129 }
130 fSpaceTable[r] = spaces;
131 if (spaces[cn] > fMaxX)
132 fMaxX = spaces[cn];
133 }
134 fMaxX += fXESpacing * 2;
135 for (int r = fGraph.minRank; r <= fGraph.maxRank; ++r) {
136 spaces = fSpaceTable[r];
137 spaces[spaces.length - 1] = fMaxX;
138 if (CHECK)
139 TestUtil.checkMonotonic(spaces, "r=" + r);
140 }
141 }
142
143 public int leftBorder(VirtualVertex v) {
144 if (v.isReal()) {
145 int x = v.x - v.leftWidth - fXESpacing / 2;
146 VirtualGraph.Rank rank = fGraph.ranks[v.rank];
147 if (v.order > 0) {
148 x -= rank.vts[v.order - 1].padding;
149 }
150 return x;
151 } else
152 return v.x - v.leftWidth;
153 }
154
155 public int rightBorder(VirtualVertex v) {
156 if (v.isReal()) {
157 int x = v.x + v.rightWidth + fXESpacing / 2;
158 VirtualGraph.Rank rank = fGraph.ranks[v.rank];
159 if (v.order < rank.nVts - 1) {
160 x += rank.vts[v.order + 1].padding;
161 }
162 return x;
163 } else
164 return v.x + v.rightWidth;
165 }
166
167 /**
168 * Find all the grid points given the source and destination vertex.
169 */
170 public void initGrid(VirtualVertex src, VirtualVertex dest) {
171 fSrc = src;
172 fDest = (dest == null || dest.isBus()) ? null : dest;
173 clear();
174 VirtualVertex[] vts;
175 int erasedindex;
176 int[] spaces;
177 int[] forced;
178 //
179 // To avoid skipping one of the src/dest vertex when they are being crossed together,
180 // they need to be sorted.
181 if (fDest == null || fDest.x == fSrc.x) {
182 forced = new int[] { fSrc.x };
183 } else if (fSrc.x < fDest.x) {
184 forced = new int[] { fSrc.x, fDest.x };
185 } else {
186 forced = new int[] { fDest.x, fSrc.x };
187 }
188 if (DEBUG) {
189 msg.println(NAME + ".initGrid(): src.x=" + fSrc.x + ", dest.x=" + fDest.x);
190 msg.println("\tsrc=" + fSrc.getName());
191 msg.println("\tdest=" + ((fDest == null) ? "null" : fDest.getName()));
192 }
193 // Init only ranks used for routing: [src->dest)
194 // Init only the static information for fValidTable and fGridTable
195 // and should such information should not change with the given src and dest.
196 // Dynamic information in Grid are controlled by the mark value and can be invalidated
197 // by resetMarks().
198 int start = src.rank;
199 int end = dest.rank;
200 int dir = (end > start) ? 1 : -1;
201 for (int r = start + dir; r != end + dir; r += dir) {
202 IntList valids = fValidXTable[r];
203 valids.clear();
204 spaces = fSpaceTable[r];
205 vts = fGraph.ranks[r].vts;
206 // Mark the index for any erased vertex.
207 // There is at most one erased vertex. If none exists in this rank, erasedIndex=-1;
208 //FIXME: May not need to do linear search if erased path is available.
209 erasedindex = -1;
210 for (int i = 0; i < fGraph.ranks[r].nVts; ++i) {
211 if (vts[i].isErased()) {
212 erasedindex = i;
213 break;
214 }
215 }
216 ValidXIterator it = new ValidXIterator(spaces, forced, erasedindex, fSrc.x, fESpacing, fStep);
217 for (int i = it.first(); i < fMaxX; i = it.next()) {
218 valids.add(i);
219 }
220 if (fGridTable[r] == null || valids.size() > fGridTable[r].length)
221 fGridTable[r] = new Grid[valids.size()];
222 else
223 Arrays.fill(fGridTable[r], null);
224 if (DEBUG) {
225 msg.println(NAME + ": r=" + r + ", validx=\n" + valids);
226 msg.println(NAME + ": r=" + r + ", spaces=\n", fSpaceTable[r]);
227 }
228 }
229 }
230
231 /**
232 * Update space table values for the given vertex in case vertex.x is changed.
233 */
234 public void updateSpaceTable(VirtualVertex v) {
235 int[] spaces = fSpaceTable[v.rank];
236 int index = v.order * 2 + 1;
237 spaces[index] = leftBorder(v);
238 spaces[index + 1] = rightBorder(v);
239 }
240
241 /**
242 * Adjust SpaceTable orders when vertex has moved from index 'from' to 'to'.
243 */
244 void moveVertex(VirtualVertex v, int from, int to) {
245 if (to == from)
246 return;
247 int[] spaces = fSpaceTable[v.rank];
248 from = from * 2 + 1; // from is now index for the vertex left border coordinate.
249 to = to * 2 + 1;
250 if (to > from)
251 ++to;
252 else
253 ++from;
254 msg.move(spaces, from, to);
255 msg.move(spaces, from, to);
256 }
257
258 int[][] getSpaceTable() {
259 return fSpaceTable;
260 }
261
262 ////////////////////////////////////////////////////////////////////////
263
264 /** Get an uninitialized Grid from allocated pool. */
265 public Grid get() {
266 if (fSpare != null) {
267 Grid ret = fSpare;
268 fSpare = null;
269 return ret;
270 }
271 if (fSize >= fPool.length)
272 growTo(fPool.length * 2 + 1);
273 return fPool[fSize++];
274 }
275
276 /** Get an initialized vertex Grid. */
277 public Grid get(VirtualVertex v) {
278 Grid ret = get();
279 ret.rank = v.rank;
280 ret.x = v.x;
281 ret.vertex = v;
282 ret.leftVertex = v;
283 return ret;
284 }
285
286 /**
287 * Unfornately, since Grid object are put into the fGridTable once it is created,
288 * it would be expensive to unget the Grid object.
289 */
290 public void unget(Grid a) {
291 if (fSpare == null)
292 fSpare = a;
293 }
294
295 public int size() {
296 return fSize;
297 }
298
299 public int getMaxSize() {
300 if (fSize > fMAXSIZE)
301 fMAXSIZE = fSize;
302 return fMAXSIZE;
303 }
304
305 public void clear() {
306 if (fSize > fMAXSIZE)
307 fMAXSIZE = fSize;
308 fSize = 0;
309 }
310
311 ////////////////////////////////////////////////////////////////////////
312
313 private void growTo(int n) {
314 Grid[] a = new Grid[n];
315 System.arraycopy(fPool, 0, a, 0, fPool.length);
316 for (int i = fPool.length; i < a.length; ++i)
317 a[i] = new Grid();
318 fPool = a;
319 }
320
321 ////////////////////////////////////////////////////////////////////////
322
323 /**
324 * Check integerity of data structures.
325 * <li>Check that vertices are inside the left and right bounds specified in the fSpaceTable.</li>
326 *
327 * @enter fSpaceTable must be initialized.
328 */
329 public boolean sanityCheck() {
330 // Check spacetable and vertex.x are consistent.
331 VirtualGraph.Rank rank;
332 VirtualVertex v;
333 int x, left, right;
334 int[] spaces;
335 boolean ret = true;
336 for (int r = fGraph.minRank; r < fGraph.maxRank; ++r) {
337 rank = fGraph.ranks[r];
338 spaces = fSpaceTable[r];
339 for (int i = 0, index = 1; i < rank.nVts; ++i, index += 2) {
340 x = rank.vts[i].x;
341 left = spaces[index];
342 right = spaces[index + 1];
343 if (left < x && x < right)
344 continue;
345 msg.err(
346 NAME
347 + ".sanityCheck(): vertex out of bounds: r="
348 + r
349 + ", left="
350 + left
351 + ", right="
352 + right
353 + ", x="
354 + x
355 + "\nv="
356 + rank.vts[i]
357 + ", spaces[r]:"
358 + sprint.array("", "%6d ", spaces));
359
360 ret = false;
361 }
362 }
363 msg.println(NAME + ".sanityCheck(): pool size=" + fSize + ", OK");
364 return ret;
365 }
366
367 ////////////////////////////////////////////////////////////////////////
368
369 /**
370 * Iterate over Grids in a rank.
371 *
372 * GridIterator use the given path cost to determine the range of
373 * valid locations that Grid object need to be created. All created Grid object are then keep
374 * in a table with (rank,x) as key for lookup when the location (rank,x) is referenced again.
375 */
376 class GridIterator {
377
378 /** Rank. */
379 int fR;
380 /** Start x. */
381 int fX;
382 int[] fSpaces;
383 /** Created Grids in this rank. */
384 Grid[] fGrids;
385 /** Valid X for this rank. */
386 IntList fValidX;
387 int fIndex;
388 VirtualVertex[] fVts;
389
390 /**
391 * @return The Grid with smallest x-coordinates with the given distance cost from
392 * the given Grid.
393 */
394 public GridIterator(int r, int x, float distcost) {
395 //
396 fR = r;
397 fX = x;
398 //
399 int dx = Grid.distCostToX(distcost);
400 dx = x - dx;
401 if (dx <= 0)
402 dx = 0;
403 fSpaces = fSpaceTable[r];
404 fGrids = fGridTable[r];
405 fValidX = fValidXTable[r];
406 fIndex = fValidX.insertionIndex(dx);
407 fVts = fGraph.ranks[r].vts;
408 if (DEBUG) {
409 msg.println("r=" + r + ", validx=" + fValidX);
410 msg.println("r=" + r + ", x=" + x + ", index=" + fIndex);
411 }
412 }
413
414 boolean hasNext() {
415 return fIndex<fValidX.size();
416 }
417
418 /**
419 * Get next Grid on the right of the given 'grid'.
420 * @return Modified 'grid' or null.
421 */
422 Grid next() {
423 if (fIndex >= fValidX.size())
424 return null;
425 Grid ret = fGrids[fIndex];
426 if (ret != null) {
427 ++fIndex;
428 return ret;
429 }
430 //
431 // Create Grid object.
432 //
433 int x = fValidX.get(fIndex);
434 int index = msg.insertionIndex(fSpaces, x);
435 VirtualVertex v = null;
436 if (index > 1)
437 v = fVts[index / 2 - 1];
438 else
439 v = null;
440 ret = get();
441 ret.init();
442 if (v == null) {
443 ret.vertex = null;
444 ret.leftVertex = null;
445 } else if (x < v.x) {
446 ret.vertex = null;
447 if (v.order > 0)
448 ret.leftVertex = fVts[v.order - 1];
449 else
450 ret.leftVertex = null;
451 } else if (x > v.x) {
452 ret.vertex = null;
453 ret.leftVertex = v;
454 } else {
455 ret.vertex = v;
456 ret.leftVertex = v;
457 }
458 ret.rank = fR;
459 ret.x = x;
460 fGrids[fIndex] = ret;
461 ++fIndex;
462 return ret;
463 }
464 }
465
466 ////////////////////////////////////////////////////////////////////////
467
468 /**
469 * ValidXIterator find all the valid x-coordinates that a Grid point can be created for each rank.
470 * Grid objects are not created since only a fraction of the valid x-coordinates would be used
471 * depend on the path cost. GridIterator is responsible for creating and maintaining Grid objects.
472 *
473 * @see GridIterator
474 */
475 static final class ValidXIterator {
476 //
477 private static final String NAME = "ValidXIterator";
478 private static final boolean DEBUG = false;
479 //
480 int[] fSpaces;
481 int[] fForced;
482 int fErasedIndex;
483 int fESpacing;
484 int fStep;
485 //
486 int fX;
487 int fPrevX;
488 int fOffset;
489 int fHalfESpacing;
490 int fMaxX;
491
492 /**
493 * @param spaces The space table for this rank.
494 * @param forced Forced grid at src or dest x in ascending order.
495 * @param erasedindex The vertex.order for the erased vertex, -1 if none.
496 * @param srcx The src.x that grid should be aligned to.
497 * @param espacing The edge-edge spacing.
498 * @param step The grid spacing.
499 */
500 ValidXIterator(int[] spaces, int[] forced, int erasedindex, int srcx, int espacing, int step) {
501
502 fSpaces = spaces;
503 fErasedIndex = (erasedindex>=0) ? (erasedindex * 2 + 2): -1;
504 fForced = forced;
505 fESpacing = espacing;
506 fHalfESpacing = espacing / 2;
507 fMaxX = spaces[spaces.length - 1];
508 fStep=step;
509 //
510 fOffset = srcx % fStep;
511 fX = fESpacing + fOffset;
512 fPrevX = 0;
513 }
514
515 int first() {
516 int left, right;
517 int index;
518 while (fX < fMaxX) {
519 index = msg.insertionIndex(fSpaces, fX);
520 if (index % 2 == 1) {
521 // Hit space between index-1 and index. Check if space is enough.
522 if (index - 1 == fErasedIndex)
523 left = fSpaces[index - 2];
524 else
525 left = fSpaces[index - 1];
526 if (index + 1 == fErasedIndex)
527 right = fSpaces[index + 1];
528 else
529 right = fSpaces[index];
530 if (fitBetween(left, right))
531 break;
532 } else if (index == fErasedIndex) {
533 // Hit erased vertex.
534 if (fitBetween(fSpaces[index - 2], fSpaces[index + 1]))
535 break;
536 }
537 nextX();
538 }
539 return fX;
540 }
541
542 /**
543 * Get next Grid on the right of the given 'grid'.
544 * @return Modified 'grid' or null.
545 */
546 public int next() {
547 nextX();
548 return first();
549 }
550
551 ////////////////////////////////////////////////////////////////////////
552
553 /**
554 * Typically just an increment of fESpacing is fine. However, extra efforts
555 * are spent to have a Grid point at the source and destination x-coordinates
556 * so that straight routes from/to them are possible.
557 *
558 * To ensure vertically straight routes, grids are preferred to align vertically.
559 * To do that, we try to align to a basic grid of fESpacing away from src on both sides.
560 *
561 * Since each route only cross a rank once, there are no limit on spacing between
562 * Grid points themselves as long as they have enough spacings from non-erased
563 * vertices. So we simply add a Grid point if iterator go over the src and dest vertices.
564 *
565 * @return x-coordinate of next Grid point candidate.
566 */
567 //FIXME: To ensure a straight route whenever possible, grids exists in a rank
568 // should exists in all following ranks (may be discarded if not valid) when travelling
569 // from src to dest. The basic grid at fESpacing multiples from the src vertex should
570 // exists in all ranks (discarded if not valid).
571 int nextX() {
572 fPrevX = fX;
573 // Align to basic grid in case previous location has been skewed.
574 fX = fX - (fX % fStep) + fOffset;
575 if (fX <= fPrevX)
576 fX += fStep;
577 for (int i = 0; i < fForced.length; ++i) {
578 if ((fPrevX - fForced[i] < 0) && (fX - fForced[i] >= 0)) {
579 fX = fForced[i];
580 break;
581 }
582 }
583 if (fX <= fPrevX) {
584 msg.err(NAME + ".first(): fX<=fPrevX: fPrevX=" + fPrevX + ", fX=" + fX);
585 return fMaxX;
586 }
587 return fX;
588 }
589
590 boolean fitBetween(int left, int right) {
591 int x = fX;
592 if (x - left < fHalfESpacing)
593 x = left + fHalfESpacing;
594 if (right - x >= fHalfESpacing) {
595 fX = x;
596 return true;
597 } else if (right - left >= fESpacing && right<fMaxX) {
598 x = right-fHalfESpacing;
599 if (x > fPrevX ) {
600 fX = x;
601 return true;
602 }
603 }
604 return false;
605 }
606 }
607
608 }
609
610 ////////////////////////////////////////////////////////////////////////