Source code: com/port80/graph/dot/impl/Route.java
1 //
2 // Copyright(c) 2002, Chris Leung
3 //
4
5 package com.port80.graph.dot.impl;
6
7 import java.awt.*;
8 import java.util.*;
9 import com.port80.util.*;
10 import com.port80.graph.*;
11
12 /** Draw splines for VirtualGraph.
13 *
14 */
15 public class Route {
16
17 // Static fields ///////////////////////////////////////////////////////
18 //
19
20 private static final String NAME = "Route";
21 private static final boolean DEBUG = false;
22 private static boolean CHECK = Debug.isCheck();
23 private static boolean VERBOSE = Debug.isVerbose();
24
25 private static final double EPSILON = 1e-6;
26 private static final int DELTA_STRAIGHT = 1;
27
28 private static final double ARROW_GAP_MIN = 1.0;
29 private static final double ARROW_GAP_MAX = 1.5;
30
31 /** Sides of boxes for SHAPE path. */
32 public static final int BOTTOM = 0x01;
33 public static final int RIGHT = 0x02;
34 public static final int TOP = 0x04;
35 public static final int LEFT = 0x08;
36
37 public static final int BOXBOTTOM = 0;
38 public static final int BOXRIGHT = 1;
39 public static final int BOXTOP = 2;
40 public static final int BOXLEFT = 3;
41
42 public static final int UL = 0x00;
43 public static final int LL = 0x01;
44 public static final int LR = 0x02;
45 public static final int UR = 0x03;
46
47 ////////////////////////////////////////
48
49 /* number of subdivisions, re-aiming splines */
50 private static final int MAXSUB = 16;
51 private static final int YSUB = 4;
52 private static final int STRAIGHT_SHORT = 75;
53 private static final int STRAIGHT_LONG = 200;
54 /* in building list of edges */
55 private static final int CHUNK = 128;
56
57 private static final int REGULAREDGE = 0x01;
58 private static final int FLATEDGE = 0x02;
59 private static final int SELFWPEDGE = 0x04;
60 private static final int SELFNPEDGE = 0x08;
61 private static final int SELFEDGE = 0x08;
62 private static final int EDGETYPEMASK = 0x0f; /* the OR of the above */
63 private static final int FWDEDGE = 0x10;
64 private static final int BWDEDGE = 0x20;
65 private static final int EDGEDIRMASK = 0x30; /* the OR of the above */
66 private static final int MAINGRAPH = 0x40;
67 private static final int AUXGRAPH = 0x80;
68 private static final int GRAPHTYPEMASK = 0xc0; /* the OR of the above */
69
70 private static final int CCW = -1; /* counter clock-wise */
71 private static final int CW = 1; /* clock-wise */
72 private static final int ANYW = 0; /* could go either way */
73
74 private static final int BINC = 300;
75 private static final int PINC = 300;
76
77 private static final int ARR_NONE = 0;
78 private static final int ARR_NORM = 1;
79 private static final int ARR_INV = 2;
80 private static final int ARR_DOT = 3;
81 private static final int ARR_ODOT = 4;
82 private static final int ARR_INVDOT = 5;
83 private static final int ARR_INVODOT = 6;
84
85 ////////////////////////////////////////////////////////////////////////
86
87 private static final String[] arrowDirNames = { "forward", "back", "both", "none" };
88 private static final String[] arrowHeadNames = { "none", "normal", "inv", "dot", "odot", "invdot", "invodot" };
89 private static final int[] dir_sflag = { ARR_NONE, ARR_NORM, ARR_NORM, ARR_NONE };
90 private static final int[] dir_eflag = { ARR_NORM, ARR_NONE, ARR_NORM, ARR_NONE };
91 private static final int[] arr_type =
92 { ARR_NONE, ARR_NORM, ARR_INV, ARR_DOT, ARR_ODOT, ARR_INVDOT, ARR_INVODOT };
93
94 private static final int[][] selfSideMap = { { BOTTOM, BOTTOM, ANYW }, {
95 TOP, TOP, ANYW }, {
96 RIGHT, RIGHT, ANYW }, {
97 LEFT, LEFT, ANYW }, {
98 BOTTOM, LEFT, CCW }, {
99 LEFT, BOTTOM, CW }, {
100 TOP, RIGHT, CW }, {
101 RIGHT, TOP, CCW }, {
102 TOP, LEFT, CCW }, {
103 LEFT, TOP, CW }, {
104 BOTTOM, RIGHT, CCW }, {
105 RIGHT, BOTTOM, CW }, {
106 BOTTOM, TOP, CCW }, {
107 TOP, BOTTOM, CW }, {
108 LEFT, RIGHT, CCW }, {
109 RIGHT, LEFT, CW }, };
110
111 private static final int[][] flatSideMap = { { BOTTOM, BOTTOM, BOTTOM, CCW, CCW, 0 }, {
112 TOP, TOP, TOP, CW, CW, 0 }, {
113 RIGHT, LEFT, BOTTOM, CW, CW, 1 }, {
114 BOTTOM, TOP, RIGHT, CCW, CW, 1 }, {
115 TOP, BOTTOM, RIGHT, CW, CCW, 1 }, {
116 RIGHT, TOP, RIGHT, CCW, CW, 1 }, {
117 RIGHT, BOTTOM, RIGHT, CW, CCW, 1 }, {
118 TOP, LEFT, TOP, CW, CCW, 1 }, {
119 BOTTOM, LEFT, BOTTOM, CCW, CW, 1 }, {
120 RIGHT, RIGHT, BOTTOM, CW, CCW, 1 }, {
121 LEFT, LEFT, BOTTOM, CCW, CW, 1 }, {
122 LEFT, BOTTOM, BOTTOM, CCW, CCW, 0 }, {
123 TOP, RIGHT, TOP, CW, CW, 0 }, {
124 LEFT, TOP, TOP, CW, CW, 0 }, {
125 BOTTOM, RIGHT, BOTTOM, CCW, CCW, 0 }, {
126 LEFT, RIGHT, BOTTOM, CCW, CCW, 0 }, };
127
128 // Instance fields /////////////////////////////////////////////////////
129 //
130
131 private VirtualGraph fGraph;
132 private VirtualGraph.Rank[] fRanks;
133 private int fFlatHeight;
134 private int fESpacing;
135 private int fXSpacing;
136 private int fXESpacing;
137
138 /**
139 * VirtualEdge->Spline mapping for saving generated splines. The
140 * key is the chain head of the edge chain that the spline
141 * represent.
142 */
143 private Map fSplineMap = new HashMap();
144 private int fLeftBound, fRightBound, fTopBound, fBottomBound;
145 /**
146 * Inter-rank spacing. interRankBoxes[0] is the space between rank[0]
147 * and rank[1].
148 */
149 private DotBox[] fInterRankBoxes;
150 private RouteSpline fRouter;
151 /**
152 * Bounding polygon for routing. An initialized array of
153 * DotPoint which can be reused without allocating DotPoint each
154 * time. (replace 'polypoints' in original 'routespl.c' code)
155 */
156 private DotPolyline fPolyBound = new DotPolyline(100);
157 private DotPolyline fSegment = new DotPolyline(100);
158 private DotPath fPath = new DotPath(100);
159 private DotSpline fSpline = new DotSpline(100);
160
161 /** Statistics */
162 private int fSplineCount = 0;
163 private int fBoxCount = 0;
164
165 //
166 // Layout parameters.
167 //
168 private int fXDIV_EDGES;
169 private int fXDIV_XEDGE;
170 private int fMERGE_OFFSET;
171 private int fBOX_MINOVERLAP;
172
173 // Static methods //////////////////////////////////////////////////////
174 //
175
176 public static void dot(VirtualGraph g) {
177 new Route().route(g);
178 }
179
180 public static void setVerbose(boolean yes) {
181 VERBOSE=yes;
182 }
183
184 // Instance methods ////////////////////////////////////////////////////
185 //
186
187 public void route(VirtualGraph g) {
188 StopWatch timer = null;
189 if (VERBOSE)
190 timer = new StopWatch().start();
191 //
192 fGraph = g;
193 fRanks = g.ranks;
194 fRouter = new RouteSpline();
195 //
196 SortedSet chaintails = init(g);
197 VirtualEdge e;
198 for (Iterator it = chaintails.iterator(); it.hasNext();) {
199 e = (VirtualEdge) it.next();
200 if (e.tail == e.head); //routeSelf(e);
201 else if (e.isFlat()); //routeFlat(e);
202 else
203 fSpline = routeRegular(e);
204 }
205
206 // Place edge labels.
207 // . Deferred this till saveResult().
208 if (false) {
209 VirtualVertex v;
210 VirtualVertex[] a = g.getVertices();
211 if (g.hasLabel()) {
212 for (int i = 0, max = a.length; i < max; ++i) {
213 v = a[i];
214 if (v.isLabel())
215 v.placeLabel();
216 }
217 }
218 }
219 // Place head and tail labels.
220 /*
221 if(g.hasHeadTailLabel()) {
222 for(int i=0; i<g.vertices.length; ++i) {
223 v=g.vertices[i];
224 for(int j=0; j<v.outs.length; ++j) {
225 e=v.outs[j];
226 placeHeadTailLabel(e,false); // tail label
227 placeHeadTailLabel(e,true); // head label
228 }
229 }
230 }
231 */
232
233 fRouter = null;
234 if (VERBOSE)
235 msg.println(
236 NAME
237 + ": "
238 + chaintails.size()
239 + " edges, "
240 + fSplineCount
241 + " splines: "
242 + timer.stop().toString());
243
244 // Save results:
245 g.getOriginal().setAttr("bb", g.getBounds());
246 }
247
248 /**
249 * @return The SortedSet of chain tails for all the edge chains to be routed.
250 */
251 private SortedSet init(VirtualGraph g) {
252 final String METHOD = NAME + ".init(): ";
253 StopWatch timer=null;
254
255 if (VERBOSE)
256 timer = new StopWatch().start();
257 //mark_lowclusters(g);
258 //routeSplinesinit();
259 //P=NEW(path);
260
261 fXDIV_EDGES = g.fXDIV_EDGES;
262 fXDIV_XEDGE = g.fXDIV_XEDGE;
263 fBOX_MINOVERLAP = g.fBOX_MINOVERLAP;
264 fMERGE_OFFSET = g.fMERGE_OFFSET;
265 //NOTE: rank and vertex separation is uniform across the whole
266 // graph (including clusters), only the top level graph
267 // ranksep and nodesep attribute is used.
268 fXSpacing = g.getVertexSpacing();
269 fXESpacing = fXSpacing / fXDIV_XEDGE;
270 fESpacing = fXSpacing / fXDIV_EDGES;
271 fFlatHeight = 2 * fXSpacing;
272
273 // Compute boundaries and list of edge chains to be routed.
274 SortedSet ret = initChain();
275 initInterRankBoxes();
276
277 if (VERBOSE)
278 msg.println(METHOD + ret.size() + " edges: elapsed=" + timer.stop().toString());
279 return ret;
280 }
281
282 private SortedSet initChain() {
283 final String METHOD = NAME + ".initChain(): ";
284
285 VirtualEdge e;
286 VirtualVertex v;
287 VirtualGraph.Rank rank;
288 // Sort edges in drawing order.
289 SortedSet edgeSet = new TreeSet(new VirtualEdge.EdgeChainComparator());
290 fLeftBound = Integer.MAX_VALUE;
291 fRightBound = 0;
292 if (CHECK)
293 fGraph.sanityCheck();
294 for (int x, r = fGraph.minRank; r <= fGraph.maxRank; ++r) {
295 rank = fRanks[r];
296 if (rank.nVts <= 0) {
297 msg.err(METHOD + "rank.nVts<=0: r=" + r);
298 continue;
299 }
300 // Bounds for the rank.
301 v = rank.vts[0];
302 x = v.x - v.leftWidth;
303 if (x < fLeftBound)
304 fLeftBound = x;
305 v = rank.vts[rank.nVts - 1];
306 x = v.x + v.rightWidth;
307 if (x > fRightBound)
308 fRightBound = x;
309
310 for (int nv = 0; nv < rank.nVts; ++nv) {
311 v = rank.vts[nv];
312 if (v.isReal()) {
313 v.shape = (IGraphShape) ((IVertex) v.getOriginal()).getAttr("-shape");
314 }
315 if (v.isEdge())
316 continue;
317 //
318 for (int i = 0; i < v.outs.length; ++i) {
319 e = v.outs[i];
320 // Queue only head of a chain.
321 if (e.prev != null)
322 e = e.prev;
323 if (e.isAux())
324 continue;
325 edgeSet.add(e);
326 }
327 for (int i = 0; i < v.flatOuts.length; ++i) {
328 e = v.flatOuts[i];
329 if (!e.isFlat())
330 msg.err(METHOD + "expected flat edge: " + e);
331 if (e.prev != null)
332 e = e.prev;
333 if (e.isAux())
334 continue;
335 edgeSet.add(e);
336 }
337 for (int i = 0; i < v.selves.length; ++i) {
338 e = v.selves[i];
339 if (e.isAux())
340 continue;
341 edgeSet.add(e);
342 }
343 }
344 }
345 if (fLeftBound > fRightBound)
346 fLeftBound = fRightBound;
347 if (DEBUG) {
348 msg.println(METHOD + "leftBound=" + fLeftBound + ", rightBound=" + fRightBound);
349 msg.println(METHOD + "Edges:");
350 for (Iterator it = edgeSet.iterator(); it.hasNext();) {
351 e = (VirtualEdge) it.next();
352 msg.println(e.toString() + " (" + e.chainLength() + ")");
353 }
354 }
355 return edgeSet;
356 }
357
358 private void initInterRankBoxes() {
359 VirtualVertex v;
360 VirtualGraph.Rank rank;
361 // Init. inter rank boxes.
362 fTopBound = Integer.MAX_VALUE;
363 fBottomBound = 0;
364 fInterRankBoxes = new DotBox[fGraph.maxRank + 1];
365 //
366 VirtualVertex v1;
367 VirtualGraph.Rank rank1;
368 rank = fRanks[fGraph.minRank];
369 if (rank.nVts > 0) {
370 v = rank.vts[0];
371 fTopBound = v.y - rank.top;
372 for (int r = fGraph.minRank; r < fGraph.maxRank; ++r) {
373 rank1 = fRanks[r + 1];
374 if (rank.nVts <= 0)
375 msg.err(NAME + ".initInterRankBoxes(): rank1.nVts<=0: r1=" + (r + 1));
376 v1 = rank1.vts[0];
377 fInterRankBoxes[r] =
378 new DotBox(fLeftBound, v1.y - rank1.top, fRightBound, v.y + rank.bottom);
379 rank = rank1;
380 v = v1;
381 if (DEBUG)
382 msg.println(
383 NAME
384 + ".initInterRankBoxes(): r="
385 + r
386 + ", boxes="
387 + fInterRankBoxes[r].toString());
388 }
389 fBottomBound = v.y + rank.bottom;
390 }
391 if (fTopBound > fBottomBound)
392 fTopBound = fBottomBound;
393 fGraph.updateBoundBox(fLeftBound, fTopBound, fRightBound - fLeftBound, fBottomBound - fTopBound);
394 }
395
396 // Regular edge ////////////////////////////////////////////////////////
397 //
398
399 /**
400 * Compute the spline points for edge chain starting at edge 'e'.
401 * @param e The starting edge of an edge chain.
402 */
403 private DotSpline routeRegular(VirtualEdge chaintail) {
404 final String METHOD = NAME + ".routeRegular(): ";
405
406 if (DEBUG) {
407 IEdge[] a = chaintail.getOriginals();
408 if (a != null && a.length > 0)
409 msg.println("### Edge: chaintail.original=" + a[0] + ", chaintail=" + chaintail);
410 else
411 msg.println("### Edge: chaintail=" + chaintail);
412 }
413
414 VirtualEdge start = chaintail;
415 VirtualEdge e = chaintail;
416 VirtualVertex tail = e.tail;
417 VirtualVertex head = e.head;
418
419 fSpline.reset(); // The result spline.
420
421 // Maximal bounding box at the chain tail, ie. the rank box
422 // bounding by neighbour vertices.
423 fPath.beginPath(e);
424 maximalBoxes(BOTTOM, tail, null, e, fPath);
425 int nboxes = boundTailBoxes(e, fInterRankBoxes[tail.rank], fPath);
426 //int nboxes=1;
427 //fPath.addInterRank(fInterRankBoxes[tail.rank]);
428
429 boolean straightmode = false;
430 int chainlen = e.getChainHead().y - tail.y;
431 int slen = 0;
432 int skip = 0;
433 while (e.next != null) {
434 if (slen >= 0 && !straightmode) {
435 // Length of straight segments after 'e' (not include 'e').
436 slen = straightLength(e, chainlen);
437 if (slen > 0) {
438 straightmode = true;
439 //slen--;
440 // Reserve the first and last straight segment for
441 // smooth turns.
442 // . However, if the first/last straight segment is
443 // long, this result in a long slightly oblique
444 // line that looks bad.
445 //
446 //skip = 1;
447 //slen -= 2;
448 }
449 }
450 if (slen < 0)
451 slen++;
452 if (!straightmode || skip > 0) {
453 if (skip > 0)
454 --skip;
455 maximalBoxes(TOP | BOTTOM, head, e, e.next, fPath);
456 fPath.addInterRank(fInterRankBoxes[head.rank]);
457 nboxes = 1;
458 e = e.next;
459 tail = e.tail;
460 head = e.head;
461 continue;
462 }
463 //
464 // Route the segments before the straight section to
465 // provide a smooth turn into the straight section.
466 //
467 fPath.endPath(e);
468 maximalBoxes(TOP, head, e, e.next, fPath);
469 fPath.fEnd.theta = -Math.PI / 2;
470 fPath.fEnd.constrained = true;
471 //fPath.completeRegularPath(start, e);
472 if (routePath(fPath, fSegment.reset()) == 0)
473 return fSpline;
474 fSpline.add(fSegment);
475 //
476 // Straight section
477 //
478 e = straightPath(e.next, slen, fSpline);
479 //
480 // Continue after the straight section.
481 //
482 start = e;
483 tail = e.tail;
484 head = e.head;
485 fPath.beginPath(e);
486 fPath.fStart.theta = Math.PI / 2;
487 fPath.fStart.constrained = true;
488 maximalBoxes(BOTTOM, tail, e.prev, e, fPath);
489 fPath.addInterRank(fInterRankBoxes[tail.rank]);
490 nboxes = 1;
491 straightmode = false;
492 }
493 boundHeadBoxes(e, nboxes, fPath);
494 fPath.endPath(e);
495 maximalBoxes(TOP, head, e, null, fPath);
496 //fPath.completeRegularPath(start, e);
497 if (DEBUG)
498 msg.println(METHOD + "chaintail=" + chaintail.getName() + "\n\tpath=" + fPath.toGeneralPath());
499 if (routePath(fPath, fSegment.reset()) == 0)
500 return fSpline;
501 fSpline.add(fSegment);
502 adjustChain(fGraph, chaintail, fSpline, fPath);
503 IEdge[] ies = chaintail.getOriginals();
504 if (ies.length > 0) {
505 if (DEBUG || chaintail.isDebug)
506 msg.println(METHOD + "original=" + ies[0] + ", theSpline=\n" + fSpline.toGeneralPath());
507 DotPoint p0 = fSpline.pts[0];
508 DotPoint p1 = fSpline.pts[fSpline.size - 1];
509 double scale = 1.0;
510 if (ies.length > 1) {
511 scale = 1.0 / Math.sin(Math.atan2(p1.y - p0.y, p1.x - p0.x));
512 if (DEBUG)
513 msg.println(METHOD + "scale=" + scale);
514 }
515 for (int i = 0; i < ies.length; ++i) {
516 int offset = (int) ((fMERGE_OFFSET) * scale * (2 * i - ies.length + 1) / 2);
517 clipInstall(chaintail, ies[i], fSpline, offset);
518 }
519 } else {
520 //FIXME: install Bus->Vertex->Bus routes.
521 // Stub (Bus-Vertex) routes.
522 if (DEBUG || chaintail.isDebug)
523 msg.println(
524 METHOD + "chaintail=" + chaintail + ", theSpline=\n" + fSpline.toGeneralPath());
525 clipInstall(chaintail, null, fSpline, 0);
526 }
527 return fSpline;
528 }
529
530 /**
531 * Move virtual vertices to routed locations so that other routing
532 * can take advantage of the spare spaces.
533 */
534 private void adjustChain(VirtualGraph graph, VirtualEdge chaintail, DotSpline spline, DotPath path) {
535 VirtualGraph.Rank rank;
536 VirtualVertex head, v;
537 IntPoint pp;
538 for (; chaintail.next != null; chaintail = chaintail.next) {
539 head = chaintail.head;
540 pp = spline.bezierAtY(head.y);
541 if (pp.x == head.x)
542 continue;
543 // VirtualGraph.Rank rank;
544 // VirtualVertex left, right;
545 // int dx, order;
546 // rank = graph.ranks[head.rank];
547 // order = head.order;
548 // left = null;
549 // right = null;
550 // if (order > 0) {
551 // left = rank.vts[order - 1];
552 // dx = (left.x + left.rightWidth) - (x - head.leftWidth);
553 // if (dx > 0)
554 // x += dx;
555 // }
556 // if (order < rank.nVts - 1) {
557 // right = rank.vts[order + 1];
558 // dx = (x + head.rightWidth) - (right.x - right.leftWidth);
559 // if (dx > 0)
560 // x -= dx;
561 // }
562 // + ", leftWidth="
563 // + head.leftWidth
564 // + ", rightWidth="
565 // + head.rightWidth);
566 // + ((left == null) ? "" : ", left.x=" + left.x)
567 // + ((right == null) ? "" : ", right.x=" + right.x));
568 rank = graph.ranks[head.rank];
569 v = rank.vts[rank.nVts - 1];
570 int neworder = findOrder(pp.x, rank);
571 if (DEBUG) {
572 int leftx = 0;
573 int rightx = Integer.MAX_VALUE;
574 if (head.order > 0) {
575 v = rank.vts[head.order - 1];
576 leftx = v.x + v.rightWidth;
577 }
578 if (head.order < rank.nVts - 1) {
579 v = rank.vts[head.order + 1];
580 rightx = v.x - v.leftWidth;
581 }
582 msg.println(
583 "\n"
584 + NAME
585 + ".adjustChain(): head="
586 + head.getName()
587 + ", old order="
588 + head.order
589 + ", new order="
590 + neworder
591 + ", nVts="
592 + rank.nVts
593 + ", y="
594 + head.y
595 + ", x="
596 + head.x
597 + ", newx="
598 + pp.x
599 + ", leftx="
600 + leftx
601 + ", rightx="
602 + rightx);
603 leftx = 0;
604 rightx = Integer.MAX_VALUE;
605 }
606 int leftx, rightx;
607 for (int iter = 0; neworder >= 0 && neworder <= rank.nVts; ++iter) {
608 if (neworder == head.order || neworder == head.order + 1)
609 break;
610 leftx = 0;
611 rightx = Integer.MAX_VALUE;
612 if (neworder > 0) {
613 v = rank.vts[neworder - 1];
614 leftx = v.x + v.rightWidth;
615 }
616 if (neworder < rank.nVts) {
617 v = rank.vts[neworder];
618 rightx = v.x - v.leftWidth;
619 }
620 if (DEBUG)
621 msg.println(
622 NAME
623 + ".adjustChain(): new x="
624 + pp.x
625 + ", new leftx="
626 + leftx
627 + ", new rightx="
628 + rightx
629 + ", new leftxx=");
630 if (rightx - leftx >= fESpacing)
631 break;
632 if (VERBOSE)
633 msg.warn(
634 NAME
635 + ".adjustChain(): not enough space to reorder: iter="
636 + iter
637 + "\n\tnewx="
638 + pp.x
639 + ", leftx="
640 + leftx
641 + ", rightx="
642 + rightx
643 + ", space required="
644 + (fESpacing));
645 if (neworder < head.order)
646 ++neworder;
647 else
648 --neworder;
649 }
650 adjustVertexWithReorder(neworder, pp.x, head, rank);
651 }
652 }
653
654 /**
655 * Find the new order for a vertex at the given x-coordinate 'x' such that
656 * vts[neworder-1].x <= x and vts[neworder].x > x
657 */
658 private int findOrder(int x, VirtualGraph.Rank rank) {
659 int low = 0;
660 int high = rank.nVts - 1;
661 VirtualVertex v;
662 while (low <= high) {
663 int mid = (low + high) >> 1;
664 v = rank.vts[mid];
665 if (v.x < x)
666 low = mid + 1;
667 else if (v.x > x)
668 high = mid - 1;
669 else
670 return mid + 1; // same x.
671 }
672 return low;
673 }
674
675 /**
676 * Move given vertex to location before the vertex vts[neworder] and
677 * adjust x coordinate to as close as possible to 'newx'.
678 */
679 private void adjustVertexWithReorder(int neworder, int newx, VirtualVertex head, VirtualGraph.Rank rank) {
680 if (neworder < head.order) {
681 System.arraycopy(rank.vts, neworder, rank.vts, neworder + 1, head.order - neworder);
682 rank.vts[neworder] = head;
683 for (int i = neworder, max = head.order; i <= max; ++i)
684 rank.vts[i].order = i;
685 } else if (neworder > head.order + 1) {
686 System.arraycopy(rank.vts, head.order + 1, rank.vts, head.order, neworder - 1 - head.order);
687 rank.vts[neworder - 1] = head;
688 for (int i = head.order; i < neworder; ++i)
689 rank.vts[i].order = i;
690 }
691 adjustVertexWithoutReorder(newx, head, rank);
692 return;
693 }
694
695 /**
696 * Adjust x coordinate of given vertex to as close as possible to newx while maintaining vertex orders.
697 */
698 private void adjustVertexWithoutReorder(int newx, VirtualVertex head, VirtualGraph.Rank rank) {
699 VirtualVertex v;
700 int order = head.order;
701 int left = 0;
702 if (order > 0) {
703 v = rank.vts[order - 1];
704 left = v.x + v.rightWidth + fESpacing / 2 + head.leftWidth;
705 }
706 int right = Integer.MAX_VALUE;
707 if (order < rank.nVts - 1) {
708 v = rank.vts[order + 1];
709 right = v.x - v.leftWidth - fESpacing / 2 - head.rightWidth;
710 }
711 if (VERBOSE)
712 msg.println(
713 NAME
714 + ".adjustVertexWithoutReorder(): newx="
715 + newx
716 + ", left="
717 + left
718 + ", right="
719 + right);
720 if (newx <= left) {
721 head.x = left;
722 return;
723 }
724 if (newx >= right) {
725 head.x = right;
726 return;
727 }
728 head.x = newx;
729 }
730
731 /**
732 * Bound the inter-rank spacing below the tail.
733 */
734 private int boundTailBoxes(VirtualEdge e, DotBox box, DotBoxList ret) {
735 if (DEBUG)
736 msg.println(NAME + ".boundTailBoxes(): box=" + box.toString());
737 if (e.tail.isVirtual()) {
738 fPath.add(box);
739 return 1;
740 }
741 // if(e.chainLength()<=1) {
742 // fPath.add(box);
743 // return 1;
744 // }
745 VirtualVertex head = e.head;
746 VirtualEdge left;
747 VirtualEdge right;
748 left = topLeftBound(e);
749 if (left != null && pathsCrossed(left.head, head, e, e.next))
750 left = null;
751 right = topRightBound(e);
752 if (right != null && pathsCrossed(right.head, head, e, e.next))
753 right = null;
754 if (left == null && right == null) {
755 fPath.add(box);
756 return 1;
757 }
758 // Need bounds.
759 int n = 0;
760 int dy = box.lly - box.ury;
761 int nsub = Math.min(MAXSUB, dy / YSUB);
762 if (nsub <= 0)
763 nsub = 1;
764 //
765 IntPoint up, lp;
766 DotBox above = ret.getLast();
767 DotBox below = new DotBox();
768 int llx, lly, urx, ury;
769 for (int sub = 0; sub < nsub; sub++) {
770 ury = box.ury + (dy * sub) / nsub;
771 lly = box.ury + (dy * (sub + 1)) / nsub;
772 if (DEBUG)
773 msg.println(
774 NAME
775 + ".boundTailBoxes(): tail="
776 + e.tail.getName()
777 + ", head="
778 + head.getName()
779 + ", ury="
780 + ury
781 + ", lly="
782 + lly);
783 if (left != null) {
784 up = left.getUnclipped().bezierAtY(ury);
785 lp = left.getUnclipped().bezierAtY(lly);
786 llx = Math.min(up.x, lp.x);
787 if (DEBUG)
788 msg.println(
789 NAME
790 + ".boundTailBoxes(): left: up.y="
791 + up.y
792 + ", up.x="
793 + up.x
794 + ", lp.y="
795 + lp.y
796 + ", lp.x="
797 + lp.x);
798 } else {
799 llx = box.llx;
800 }
801 if (right != null) {
802 up = right.getUnclipped().bezierAtY(ury);
803 lp = right.getUnclipped().bezierAtY(lly);
804 urx = Math.max(up.x, lp.x);
805 if (DEBUG)
806 msg.println(
807 NAME
808 + ".boundTailBoxes(): right: up.y="
809 + up.y
810 + ", up.x="
811 + up.x
812 + ", lp.y="
813 + lp.y
814 + ", lp.x="
815 + lp.x);
816 } else {
817 urx = box.urx;
818 }
819 below.set(llx, lly, urx, ury);
820 if (above != null)
821 ensureContact(above, below);
822 else
823 ensureBoxWidth(below);
824 above = fPath.add(below);
825 ++n;
826 }
827 return n;
828 }
829
830 /**
831 * Bound and replace the last 'nboxes' boxes in the given DotBoxList with bounding splines at head of 'e'.
832 *
833 * @param e The chainhead to be bounded where e.head should be a real vertex.
834 * @param chaintail The tail segment of the whole edge chain.
835 * @param ret DotBoxList whose last box is to be bounded and replaced.
836 */
837 private int boundHeadBoxes(VirtualEdge e, int nboxes, DotBoxList ret) {
838 if (e.head.isVirtual()) {
839 return 0;
840 }
841 VirtualEdge left;
842 VirtualEdge right;
843 VirtualVertex tail = e.tail;
844 left = bottomLeftBound(e);
845 right = bottomRightBound(e);
846 if (left != null && pathsCrossed(left.tail, tail, e.prev, e))
847 left = null;
848 if (right != null && pathsCrossed(right.tail, tail, e.prev, e))
849 right = null;
850 if (left == null && right == null) {
851 return 0;
852 }
853 // Need bounds.
854 DotBox[] boxes;
855 DotBox box;
856 int nsub;
857 if (nboxes == 1) {
858 // Subdivide the box.
859 box = ret.removeLast();
860 if (DEBUG)
861 msg.println(NAME + ".boundHeadBoxes(): box=" + box.toString());
862 // if(e.chainLength()<=1) {
863 // fPath.add(box);
864 // return 1;
865 // }
866 int dy = box.lly - box.ury;
867 nsub = Math.min(MAXSUB, dy / YSUB);
868 if (nsub <= 0)
869 nsub = 1;
870 boxes = new DotBox[nsub];
871 for (int sub = 0; sub < nsub; sub++) {
872 boxes[sub] = new DotBox(box);
873 boxes[sub].ury = box.ury + (dy * sub) / nsub;
874 boxes[sub].lly = box.ury + (dy * (sub + 1)) / nsub;
875 }
876 } else {
877 nsub = nboxes;
878 boxes = new DotBox[nboxes];
879 for (int i = 0; i < nboxes; ++i)
880 boxes[nboxes - 1 - i] = ret.removeLast();
881 }
882 int n = 0;
883 int llx, urx;
884 IntPoint up, lp;
885 if (left != null)
886 while (left.prev != null)
887 left = left.prev;
888 if (right != null)
889 while (right.prev != null)
890 right = right.prev;
891 DotBox above = ret.getLast();
892 for (int sub = 0; sub < nsub; sub++) {
893 box = boxes[sub];
894 if (DEBUG)
895 msg.println(
896 NAME
897 + ".boundHeadBoxes(): tail="
898 + tail.getName()
899 + ", head="
900 + e.head.getName()
901 + ", ury="
902 + box.ury
903 + ", lly="
904 + box.lly);
905 if (left != null) {
906 up = left.getUnclipped().bezierAtY(box.ury);
907 lp = left.getUnclipped().bezierAtY(box.lly);
908 llx = Math.min(up.x, lp.x);
909 if (llx > box.llx)
910 box.llx = llx;
911 if (DEBUG)
912 msg.println(
913 NAME
914 + ".boundHeadBoxes(): left: up.y="
915 + up.y
916 + ", up.x="
917 + up.x
918 + ", lp.y="
919 + lp.y
920 + ", lp.x="
921 + lp.x
922 + ", llx="
923 + llx);
924 }
925 if (right != null) {
926 up = right.getUnclipped().bezierAtY(box.ury);
927 lp = right.getUnclipped().bezierAtY(box.lly);
928 urx = Math.max(up.x, lp.x);
929 if (urx < box.urx)
930 box.urx = urx;
931 if (DEBUG)
932 msg.println(
933 NAME
934 + ".boundHeadBoxes(): right: up.y="
935 + up.y
936 + ", up.x="
937 + up.x
938 + ", lp.y="
939 + lp.y
940 + ", lp.x="
941 + lp.x
942 + ", urx="
943 + urx);
944 }
945 if (above != null)
946 ensureContact(above, box);
947 else
948 ensureBoxWidth(box);
949 above = fPath.add(box);
950 ++n;
951 }
952 return n - nboxes;
953 }
954
955 /**
956 * Ensure given box 'box' contact with box above.
957 */
958 private void ensureContact(DotBox above, DotBox box) {
959 int x;
960 if (box.urx < above.llx + fBOX_MINOVERLAP) {
961 x = (above.llx + box.urx) / 2;
962 above.llx = x - fBOX_MINOVERLAP / 2;
963 box.urx = x + fBOX_MINOVERLAP / 2;
964 if (VERBOSE)
965 msg.warn(NAME + ".ensureContact(): adjusted box.urx: old=" + box.urx + ", new=" + x);
966 }
967 if (box.llx > above.urx - fBOX_MINOVERLAP) {
968 x = (above.urx + box.llx) / 2;
969 above.urx = x + fBOX_MINOVERLAP / 2;
970 box.llx = x - fBOX_MINOVERLAP / 2;
971 if (VERBOSE)
972 msg.warn(NAME + ".ensureContact(): adjusted box.llx: old=" + box.llx + ", new=" + x);
973 }
974 }
975
976 private void ensureBoxWidth(DotBox box) {
977 if (box.urx - box.llx >= fBOX_MINOVERLAP)
978 return;
979 int x = (box.llx + box.urx) / 2;
980 box.llx = x - fBOX_MINOVERLAP / 2;
981 box.urx = x + fBOX_MINOVERLAP / 2;
982 }
983
984 /**
985 * Determine the maximal bounding box around 'v' available for
986 * routing edges 'ie' and 'oe'.
987 *
988 * @return Number of boxes added.
989 * @param side TOP/BOTTOM/both.
990 * @param v The vertex whose edges is to be routed.
991 * @param ie
992 * @param oe
993 * @param ret Added boxes to this list.
994 */
995 private int maximalBoxes(int side, VirtualVertex v, VirtualEdge ie, VirtualEdge oe, DotBoxList ret) {
996 int x;
997 VirtualGraph.Rank rank = fRanks[v.rank];
998 int llx, lly, urx, ury;
999 if ((side & BOTTOM) != 0)
1000 lly = v.y + rank.bottom;
1001 else
1002 lly = v.y;
1003 if ((side & TOP) != 0)
1004 ury = v.y - rank.top;
1005 else
1006 ury = v.y;
1007 int starty = ury;
1008 int dy = lly - ury;
1009 int nsub = Math.min(MAXSUB, dy / YSUB);
1010 if (nsub <= 0)
1011 nsub = 1;
1012 DotBox above = ret.getLast();
1013 DotBox box = new DotBox();
1014 for (int sub = 0; sub < nsub; ++sub) {
1015 ury = starty + (dy * sub) / nsub;
1016 lly = starty + (dy * (sub + 1)) / nsub;
1017 // Give this node all the available space up to its neighbours.
1018 int min = v.x - v.leftWidth;
1019 VirtualVertex left = neighbour(v, ie, oe, lly, ury, -1);
1020 if (false)
1021 if (ie != null && ie.isDebug || oe != null && oe.isDebug)
1022 msg.println(NAME + ".maximalBox(): left=" + left);
1023 if (left != null) {
1024 //FIXME: Ignore cluster stuffs for now.
1025 //
1026 //if((leftcluster=cl_bound(v,left)))
1027 //x=leftcluster.bb.urx+Splinesep;
1028 //else {
1029 x = left.x + left.rightWidth+v.padding;
1030 if (left.isVirtual())
1031 x += fESpacing / 2;
1032 else
1033 x += fESpacing; // More spacing in case spline overshoot.
1034 if (x < min)
1035 min = x;
1036 } else if (fLeftBound < min)
1037 min = fLeftBound;
1038 int max = v.x + v.rightWidth;
1039 VirtualVertex right = neighbour(v, ie, oe, lly, ury, 1);
1040 if (false)
1041 if (ie != null && ie.isDebug || oe != null && oe.isDebug)
1042 msg.println(NAME + ".maximalBox(): right=" + right);
1043 if (right != null) {
1044 //FIXME: Ignore cluster stuffs for now.
1045 //
1046 //if((rightcluster=cl_bound(v, right)))
1047 //x=rightcluster.bb.llx-Splinesep;
1048 //else {
1049 x = right.x - right.leftWidth-v.padding;
1050 if (right.isVirtual())
1051 x -= fESpacing / 2;
1052 else
1053 x -= fESpacing;
1054 if (x > max)
1055 max = x;
1056 } else if (fRightBound > max)
1057 max = fRightBound;
1058 //
1059 //FIXME: Need to make sure box size is valid.
1060 //FIXME: Triangulatoin error when nodesep is too small.
1061 llx = min;
1062 urx = max;
1063 // Make sure there are room for label.
1064 if (v.isLabel())
1065 urx -= v.leftWidth + v.rightWidth;
1066 box.set(llx, lly, urx, ury);
1067 if (above != null)
1068 ensureContact(above, box);
1069 else
1070 ensureBoxWidth(box);
1071 above = ret.add(box);
1072 }
1073 if (DEBUG)
1074 msg.println(NAME + ".maximalBox(): x=" + v.getName() + ", boxes=" + ret.toString());
1075 return nsub;
1076 }
1077
1078 /** Get neighbour on left (dir=-1) or right (dir=1).
1079 *
1080 * @param 'ie' is an in edge of 'v'.
1081 * @param 'oe' is an out edge of 'v'.
1082 */
1083 private VirtualVertex neighbour(VirtualVertex v, VirtualEdge ie, VirtualEdge oe, int lly, int ury, int dir) {
1084 VirtualVertex ret = null;
1085 VirtualGraph.Rank rank = fRanks[v.rank];
1086 for (int i = v.order + dir;((i >= 0) && (i < rank.nVts)); i += dir) {
1087 ret = rank.vts[i];
1088 //if(ret.type==VirtualVertex.EDGELABEL) return ret;
1089 if (ret.isReal()) {
1090 // Real vertex/graph.
1091 if ((lly < ret.y - ret.top - fESpacing) || (ury > ret.y + ret.bottom + fESpacing))
1092 continue;
1093 else
1094 return ret;
1095 }
1096 // If neighbour 'ret' is a real VirtualVertex and
1097 // there are crossings between the current edge chain and
1098 // the edge chain through 'ret', let current chain route
1099 // through the neighbour since they are going to cross
1100 // each other anyway.
1101 if (!pathsCrossed(ret, v, ie, oe)) {
1102 return ret;
1103 }
1104 if (false)
1105 if (ie != null && ie.isDebug || oe != null && oe.isDebug)
1106 msg.println(
1107 NAME
1108 + ".pathCross(): crossed: v="
1109 + v.getName()
1110 + ", dir="
1111 + dir
1112 + ", ret="
1113 + ret.getName());
1114 }
1115 return null;
1116 }
1117
1118 /** Check if edge chain 'ie1->v1->oe1' any cross edge chain through 'v0'.
1119 *
1120 * @param 'v0' is a VirtualVertex of type EDGE.
1121 * @return true if edge ie1 and oe1 through v1 can crossed edges in/out of v0.
1122 * In that case, neighbour() consider it is OK to use the space for v0.
1123 */
1124 private boolean pathsCrossed(VirtualVertex v0, VirtualVertex v1, VirtualEdge ie1, VirtualEdge oe1) {
1125 // Need to look for more levels in case there are a number of bus consecutive levels.
1126 final int NLEVEL = 4;
1127 VirtualEdge e0;
1128 VirtualVertex x0, x1;
1129 // Current vertices order.
1130 boolean order = (v0.x > v1.x);
1131 if (v0.outs.length == 1 && oe1 != null) {
1132 e0 = v0.outs[0];
1133 // Look ahead and see if they are crossed.
1134 for (int i = 0; i < NLEVEL; ++i) {
1135 x0 = e0.head;
1136 x1 = oe1.head;
1137 if (x0.equals(x1))
1138 break;
1139 // Order changed==crossed.
1140 if (order != (x0.x > x1.x))
1141 return true;
1142 // Reach a VirtualVertex.VERTEX.
1143 if (e0.next == null)
1144 break;
1145 if (oe1.next == null)
1146 break;
1147 e0 = e0.next;
1148 oe1 = oe1.next;
1149 }
1150 }
1151 if (v0.ins.length == 1 && ie1 != null) {
1152 e0 = v0.ins[0];
1153 for (int i = 0; i < NLEVEL; ++i) {
1154 x0 = e0.tail;
1155 x1 = ie1.tail;
1156 if (x0.equals(x1))
1157 break;
1158 if (order != (x0.x > x1.x))
1159 return true;
1160 if (e0.prev == null)
1161 break;
1162 if (ie1.prev == null)
1163 break;
1164 e0 = e0.prev;
1165 ie1 = ie1.prev;
1166 }
1167 }
1168 return false;
1169 }
1170
1171 /** Bound given boxes by the neighbour routed edges.
1172 *
1173 * @param istail 1 for tailend, -1 for headend.
1174 * @param ret boxes to be constrained and returned.
1175 */
1176 /*
1177 private void refineRegularEnds(
1178 DotBox[] ret,
1179 int nsub,
1180 VirtualEdge left,
1181 VirtualEdge right,
1182 DotPath path,
1183 DotPathEnd pathend,
1184 boolean istail) {
1185 if (left == null && right == null)
1186 return;
1187
1188 // If there are bounding edges(curves) on left/right,
1189 // refine the bounds of the boxes to avoid crossing them.
1190 // @see TSE93.pdf p.24.
1191 //
1192 DotSpline spline;
1193 IntPoint pp, cp;
1194 // IntPoint p0, p1;
1195 // double m0 = 0.0;
1196 // double m1 = 0.0;
1197 if (left != null) {
1198 spline = left.getSpline();
1199 // if (istail) {
1200 // p0 = new IntPoint(spline.pts[0]);
1201 // p1 = new IntPoint(spline.pts[1]);
1202 // } else {
1203 // p0 = new IntPoint(spline.pts[spline.size - 2]);
1204 // p1 = new IntPoint(spline.pts[spline.size - 1]);
1205 // }
1206 // if ((p1.x - p0.x) == 0)
1207 // m0 = Math.PI / 2;
1208 // else
1209 // m0 = Math.atan((p1.y - p0.y) / (p1.x - p0.x));
1210 pp = spline.bezierAtY(ret[0].ury);
1211 for (int i = 0; i < nsub; i++) {
1212 cp = spline.bezierAtY(ret[i].lly);
1213 //ret[i].llx=AVG (pp.x, cp.x);
1214 ret[i].llx = Math.max(pp.x, cp.x);
1215 pp = cp;
1216 }
1217 pp = spline.bezierAtY(istail ? pathend.boxes[1].ury : pathend.boxes[1].lly);
1218 for (int i = 1; i < pathend.nBox; i++) {
1219 cp = spline.bezierAtY(istail ? pathend.boxes[i].lly : pathend.boxes[i].ury);
1220 pathend.boxes[i].llx = Math.min(pathend.box.urx, Math.max(pp.x, cp.x));
1221 pp = cp;
1222 }
1223 int i = istail ? 0 : nsub - 1;
1224 if (ret[i].llx > pathend.boxes[pathend.nBox - 1].urx - fBOX_MINOVERLAP)
1225 ret[i].llx = pathend.boxes[pathend.nBox - 1].urx - fBOX_MINOVERLAP;
1226 }
1227 if (right != null) {
1228 spline = right.getSpline();
1229 // if (istail) {
1230 // p0 = new IntPoint(spline.pts[0]);
1231 // p1 = new IntPoint(spline.pts[1]);
1232 // } else {
1233 // p0 = new IntPoint(spline.pts[spline.size - 2]);
1234 // p1 = new IntPoint(spline.pts[spline.size - 1]);
1235 // }
1236 // if ((p1.x - p0.x) == 0)
1237 // m1 = Math.PI / 2;
1238 // else
1239 // m1 = Math.atan((p1.y - p0.y) / (p1.x - p0.x));
1240 pp = spline.bezierAtY(ret[0].ury);
1241 for (int i = 0; i < nsub; i++) {
1242 cp = spline.bezierAtY(ret[i].lly);
1243 //ret[i].urx=AVG (pp.x, cp.x);
1244 //
1245 //TELLME: Why this is different for left and right ?
1246 ret[i].urx = (pp.x + cp.x) / 2;
1247 pp = cp;
1248 }
1249 pp = spline.bezierAtY(istail ? pathend.boxes[1].ury : pathend.boxes[1].lly);
1250 for (int i = 1; i < pathend.nBox; i++) {
1251 cp = spline.bezierAtY(istail ? pathend.boxes[i].lly : pathend.boxes[i].ury);
1252 pathend.boxes[i].urx = Math.max(pathend.box.llx, (pp.x + cp.x) / 2);
1253 pp = cp;
1254 }
1255 int i = istail ? 0 : nsub - 1;
1256 if (ret[i].urx < pathend.boxes[pathend.nBox - 1].llx + fBOX_MINOVERLAP)
1257 ret[i].urx = pathend.boxes[pathend.nBox - 1].llx + fBOX_MINOVERLAP;
1258 }
1259 // Constrain the tangent if not already constrained.
1260 //
1261 // VirtualPort port = (istail) ? path.fStart : path.fEnd;
1262 // //if (!port.constrained) {
1263 // //FIXME: faster way to do this?
1264 // port.constrained = true;
1265 // if (left != null && right != null)
1266 // port.theta = (m0 + m1) / 2.0;
1267 // else if (left != null)
1268 // port.theta = m0;
1269 // else
1270 // port.theta = m1;
1271 // if (true)
1272 // msg.println("m0=" + m0 + ",m1=" + m1 + ", theta=" + port.theta);
1273 // }
1274 if (DEBUG) {
1275 msg.println(NAME + ".refineRegularEnd():");
1276 for (int i = 0; i < nsub; ++i)
1277 msg.println(ret[i].toString());
1278 }
1279 }
1280 */
1281
1282 private VirtualEdge topLeftBound(VirtualEdge e) {
1283 return topBound(e, -1);
1284 }
1285 private VirtualEdge topRightBound(VirtualEdge e) {
1286 return topBound(e, 1);
1287 }
1288 private VirtualEdge bottomLeftBound(VirtualEdge e) {
1289 return bottomBound(e, -1);
1290 }
1291 private VirtualEdge bottomRightBound(VirtualEdge e) {
1292 return bottomBound(e, 1);
1293 }
1294 /**
1295 * @param side > 0 means right. side < 0 means left.
1296 */
1297 private VirtualEdge topBound(VirtualEdge e, int side) {
1298 VirtualEdge ret = null;
1299 VirtualEdge[] outs = e.tail.outs;
1300 for (int i = 0; i < outs.length; ++i) {
1301 VirtualEdge f = outs[i];
1302 if (side * (f.head.order - e.head.order) <= 0)
1303 continue; // Not same side.
1304 if (f.getSpline() == null)
1305 continue;
1306 if (ret == null || side * (ret.head.order - f.head.order) > 0)
1307 ret = f;
1308 }
1309 if (DEBUG)
1310 msg.println(NAME + ".topBound(): side=" + side + ", e=" + e + ", ret=" + ret);
1311 return ret;
1312 }
1313
1314 /**
1315 * @return The first segment of the chain that bound the given edge on the given side.
1316 * @param side > 0 means right. side < 0 means left.
1317 */
1318 private VirtualEdge bottomBound(VirtualEdge e, int side) {
1319 VirtualEdge ret = null;
1320 VirtualEdge[] ins = e.head.ins;
1321 VirtualEdge chaintail;
1322 for (int i = 0; i < ins.length; ++i) {
1323 VirtualEdge f = ins[i];
1324 if (side * (f.tail.order - e.tail.order) <= 0)
1325 continue;
1326 chaintail = f;
1327 while (chaintail.prev != null)
1328 chaintail = chaintail.prev;
1329 if (chaintail.getSpline() == null)
1330 continue;
1331 if (ret == null || side * (ret.tail.order - f.tail.order) > 0)
1332 ret = f;
1333 }
1334 if (DEBUG)
1335 msg.println(NAME + ".bottomBound(): side=" + side + ", e=" + e + ", ret=" + ret);
1336 return ret;
1337 }
1338
1339 /** Make a box at bottom or top of an existing box.
1340 *
1341 * . For now, regular edges always go from top to bottom
1342 */
1343 private DotBox makeRegularBox(DotBox box, int side, int y) {
1344 DotBox ret = null;
1345 switch (side) {
1346 case BOTTOM :
1347 ret = new DotBox(box.llx, y, box.urx, box.lly);
1348 break;
1349 case TOP :
1350 ret = new DotBox(box.llx, box.ury, box.urx, y);
1351 break;
1352 }
1353 return ret;
1354 }
1355
1356 /**
1357 * Adjust boxes to meet MINWIDTH and ensure overlapped.
1358 */
1359 private void adjustRegularPath(DotPath path, int firstbox, int lastbox) {
1360 DotBox box1, box2;
1361 int x;
1362 for (int i = 0; i < path.fSize; ++i) {
1363 box1 = path.fBoxes[i];
1364 if ((i - firstbox) % 2 == 0) {
1365 // Why even and odd differ?
1366 // . This is different for rank box and inter-rank box.
1367 if (box1.llx >= box1.urx) {
1368 x = (box1.llx + box1.urx) / 2;
1369 box1.llx = x - fBOX_MINOVERLAP / 2;
1370 box1.urx = x + fBOX_MINOVERLAP / 2;
1371 }
1372 } else {
1373 if (box1.llx + fBOX_MINOVERLAP > box1.urx) {
1374 x = (box1.llx + box1.urx) / 2;
1375 box1.llx = x - fBOX_MINOVERLAP / 2;
1376 box1.urx = x + fBOX_MINOVERLAP / 2;
1377 }
1378 }
1379 }
1380 for (int i = 0; i < path.fSize - 1; ++i) {
1381 box1 = path.fBoxes[i];
1382 box2 = path.fBoxes[i + 1];
1383 if (i >= firstbox && i <= lastbox && (i - firstbox) % 2 == 0) {
1384 if (box1.llx + fBOX_MINOVERLAP > box2.urx)
1385 box2.urx = box1.llx + fBOX_MINOVERLAP;
1386 if (box1.urx - fBOX_MINOVERLAP < box2.llx)
1387 box2.llx = box1.urx - fBOX_MINOVERLAP;
1388 } else if (i + 1 >= firstbox &