Source code: com/port80/graph/dot/impl/Cell.java
1 //
2 // Copyright(c) 2002, Chris Leung
3 //
4
5 package com.port80.graph.dot.impl;
6
7 import com.port80.util.msg;
8
9 /**
10 * @author chrisl
11 *
12 * To change this generated comment edit the template variable "typecomment":
13 * Window>Preferences>Java>Templates.
14 * To enable and disable the creation of type comments go to
15 * Window>Preferences>Java>Code Generation.
16 */
17 public class Cell {
18
19 ////////////////////////////////////////////////////////////////////////
20
21 private static final String NAME = "Cell";
22 private static final boolean DEBUG = false;
23 /** Mark cells occupied by vertex as BLOCKED instead of SPACE.*/
24 private static final boolean USEBLOCKED = true;
25
26 // Cell types.
27 //
28 /** Available for routing. */
29 public static final int SPACE = 0;
30 /** Margins of a vertex, not available for routing.*/
31 public static final int BLOCKED = 1;
32 /** Erased vertex cell for path being routed (not include BLOCKED cells).*/
33 public static final int ERASED = 2;
34 /** Vertex center, type>VERTEX are occupied by a VirtualVertex, not available for routing.*/
35 public static final int VERTEX = 3;
36 public static final int VIRTUAL = 4; /** Virtual vertex (EDGE,EDGELABEL) center.*/
37 public static final int BUS = 5; /** Bus vertex (BUS) center.*/
38
39 // accept() return codes.
40 //
41 public static final int REJECT = 0;
42 public static final int QUEUE = 1;
43 public static final int REQUEUE = 2;
44
45 ////////////////////////////////////////////////////////////////////////
46
47 /**
48 * fMarkCounter is used to validate several instance variables
49 * so that they don't need to be reset uneccesarily.
50 *
51 * These variables that are valid only if mark==fMarkCounter,
52 * otherwise, they should be initialized before use.
53 */
54 private static int fMARKCOUNTER = 0;
55
56 /** Mark that cell has been visited. Each routing increment a
57 * counter for the mark and thus no need to reset the mark
58 * after each routing.
59 */
60 private int mark;
61 /**
62 * The index in CellHeap. Used to remove this cell from the heap.
63 * If this cell is not in the a CellHeap, heapIndex==0.
64 */
65 int heapIndex;
66 /**
67 * Current total cost from src. to this cell.
68 */
69 int curCost;
70 /**
71 * Estimated total=curCost+est.
72 */
73 int estTotal;
74 /**
75 * Parent cell on the best path to this cell.
76 */
77 Cell parent;
78
79 ////////////////////////////////////////////////////////////////////////
80
81 // These variables are valid once the cell map is created
82 // and would always be kept updated.
83
84 int type;
85 /** rown is 0-based. row 0 represents graph.ranks[minRank]. */
86 int rown;
87 /** coln is x coordinate in map unit (eg. =xSpacing/XDIV). */
88 int coln;
89 /**
90 * The vertex at this cell. Note that BLOCKED cells are also
91 * label with vertex so that they can be erased properly.
92 * So to check for cell representing a vertex, use type>=VERTEX.
93 */
94 VirtualVertex vertex;
95
96 /** Sum of all xPenalty crossing this edge (but not yet multiplied by xPenalty of the edge).*/
97 int[] crossCost;
98 /** Saved copy of crossCost.*/
99 int[] crossSaved;
100 /** //DEBUG: sanity check.*/
101 boolean isCrossSaved;
102 /** The first VERTEX cell to the left of this.*/
103 Cell leftVertex;
104
105 ////////////
106
107 private static int fCELL_XDIV;
108 private static int fCELL_BASICCOST;
109 private static int fCELL_DISTCOST;
110 private static int fCELL_TURNCOST;
111 private static int fXSpacing;
112
113 ////////////////////////////////////////////////////////////////////////
114
115 static void configure(VirtualGraph graph) {
116 fCELL_XDIV = graph.fCELL_XDIV;
117 fCELL_BASICCOST = graph.fCELL_BASICFACTOR;
118 fCELL_DISTCOST = graph.fCELL_DISTFACTOR;
119 fCELL_TURNCOST = graph.fCELL_TURNFACTOR;
120 fXSpacing = graph.getVertexSpacing();
121 fMARKCOUNTER = 0;
122 }
123
124 static void resetMark() {
125 if (fMARKCOUNTER >= Integer.MAX_VALUE) {
126 msg.err("fMarkCounter>=Integer.MAX_VALUE");
127 fMARKCOUNTER = 0;
128 }
129 ++fMARKCOUNTER;
130 }
131
132 static Cell newVertexCell(int rn, int cn, VirtualVertex v) {
133 if (v.isReal())
134 return new Cell(VERTEX, rn, cn, v);
135 else if (v.isBus())
136 return new Cell(BUS, rn, cn, v);
137 else if (v.isEdge())
138 return new Cell(VIRTUAL, rn, cn, v);
139 else {
140 msg.err(
141 NAME
142 + ".newVertexCells(): Invalid type for VERTEX cell: v="
143 + v.getName()
144 + ", type="
145 + v.getType());
146 return new Cell(rn, cn);
147 }
148 }
149
150 static Cell newBlockedCell(int rn, int cn, VirtualVertex v) {
151 if (USEBLOCKED && v.isReal())
152 return new Cell(BLOCKED, rn, cn, v);
153 else
154 return new Cell(rn, cn);
155 }
156
157 static Cell newSpaceCell(int rn, int cn) {
158 return new Cell(rn, cn);
159 }
160
161 ////////////////////////////////////////////////////////////////////////
162
163 /** For CellHeap testing. */
164 Cell(int esttotal) {
165 this.estTotal = esttotal;
166 }
167
168 private Cell(int rn, int cn) {
169 this.type = SPACE;
170 this.rown = rn;
171 this.coln = cn;
172 }
173
174 private Cell(int type, int rn, int cn, VirtualVertex v) {
175 this.type = type;
176 this.rown = rn;
177 this.coln = cn;
178 this.vertex = v;
179 }
180
181 ////////////////////////////////////////////////////////////////////////
182
183 void init() {
184 heapIndex = 0;
185 curCost = 0;
186 estTotal = 0;
187 parent = null;
188 }
189
190 VirtualVertex getVertex() {
191 return vertex;
192 }
193 Cell save() {
194 return new Cell(type, rown, coln, vertex);
195
196 }
197 void saveCrossCost() {
198 if (crossSaved == null)
199 crossSaved = new int[crossCost.length];
200 System.arraycopy(crossCost, 0, crossSaved, 0, crossCost.length);
201 isCrossSaved = true;
202 }
203 void restoreCrossCost() {
204 if (!isCrossSaved) {
205 msg.err(NAME + ".restoreCrossCost(): !crossSaved");
206 return;
207 }
208 System.arraycopy(crossSaved, 0, crossCost, 0, crossCost.length);
209 isCrossSaved = false;
210 }
211 boolean checkSavedCrossCost() {
212 if (!isCrossSaved) {
213 msg.err(NAME + ".checkSavedCrossCost(): !crossSaved");
214 return false;
215 }
216 boolean ok=true;
217 for (int i = 0; i < crossCost.length; ++i) {
218 if (crossSaved[i] == crossCost[i])
219 continue;
220 msg.println(
221 NAME
222 + ".checkSavedCrossCost(): mismatch: cell="
223 + toString()
224 + ", i="
225 + i
226 + ", saved="
227 + crossSaved[i]
228 + ", current="
229 + crossCost[i]);
230 ok=false;
231 }
232 return ok;
233 }
234 /** Restore cell from previous save state.
235 * Only type and vertex may have changed.
236 */
237 void restore(Cell c) {
238 this.type = c.type;
239 this.vertex = c.vertex;
240 }
241
242 /** Set a cell to vertex 'v' and change cells within its width to be BLOCKED.*/
243 void setVertex(VirtualVertex v, Cell[][] map) {
244 if (v.isReal())
245 this.type = VERTEX;
246 else if (v.isBus())
247 this.type = BUS;
248 else if (v.isEdge())
249 this.type = VIRTUAL;
250 else {
251 msg.err(
252 NAME
253 + ".setVertex(): Invalid type for VERTEX cell: v="
254 + v.getName()
255 + ", type="
256 + v.getType());
257 this.type = VERTEX;
258 }
259 this.vertex = v;
260 if (USEBLOCKED) {
261 int left = fCELL_XDIV * (v.x - v.leftWidth) / fXSpacing;
262 int right = fCELL_XDIV * (v.x + v.rightWidth) / fXSpacing + 1;
263 Cell[] row = map[rown];
264 if (right >= row.length)
265 right = row.length - 1;
266 Cell c;
267 for (int i = coln - 1; i >= left; --i) {
268 c = row[i];
269 // Reserve a gap on both end.
270 if (c.type == SPACE && i > 0 && row[i - 1].type == SPACE) {
271 c.type = BLOCKED;
272 c.vertex = v;
273 } else
274 break;
275 }
276 for (int i = coln + 1; i <= right; ++i) {
277 c = row[i];
278 if (c.type == SPACE && i < right && row[i + 1].type == SPACE) {
279 c.type = BLOCKED;
280 c.vertex = v;
281 } else
282 break;
283 }
284 }
285 }
286 /** Estimate cost to destination.
287 */
288 int estimate(Cell dest) {
289 int dy=Math.abs(dest.rown-rown);
290 int cost = dy*fCELL_BASICCOST;
291 if (dest.vertex.isReal()) {
292 int dx=dest.coln-coln;
293 if(dy==0) return dx*dx/fCELL_DISTCOST;
294 cost += (dx*dx)/(dy*fCELL_DISTCOST);
295 }
296 return cost;
297 }
298
299 void setLeftVertex(Cell c) {
300 leftVertex = c;
301 }
302
303 /**
304 * @return First VERTEX/BUS/VIRTUAL cell to the left of this
305 * or this if this is a VERTEX/BUS/VIRTUAL.
306 */
307 Cell findLeftVertex(Cell[][] map) {
308 Cell[] r = map[rown];
309 Cell c;
310 for (int cn = coln; cn >= 0; --cn) {
311 c = r[cn];
312 if (c.type >= ERASED) {
313 leftVertex = c;
314 return leftVertex;
315 }
316 }
317 return null;
318 }
319 /**
320 * Convert this cell to ERASED and BLOCKED cells around it to SPACE.
321 * BLOCKED.vertex are cleared, but this.vertex stay since it is required
322 * for cross-cost calculation.
323 *
324 * @return Append clone of old cell states to 'ret' list.
325 */
326 void erase(CellList ret, Cell[][] map) {
327 if (vertex == null)
328 msg.err(NAME + ".erase(): vertex==null: cell=" + this);
329 if (USEBLOCKED && vertex != null) {
330 VirtualVertex v = vertex;
331 Cell[] r = map[rown];
332 Cell c;
333 for (int cn = coln - 1; cn >= 0; --cn) {
334 c = r[cn];
335 if (c.type != BLOCKED || c.vertex != v)
336 break;
337 ret.add(c.save());
338 c.type = SPACE;
339 c.vertex = null;
340 //NOTE: that c.crossCost is not cleared. If the
341 //cell got used again, it would be re-initialized.
342 }
343 for (int cn = coln + 1; cn < r.length; ++cn) {
344 c = r[cn];
345 if (c.type != BLOCKED || c.vertex != v)
346 break;
347 ret.add(c.save());
348 c.type = SPACE;
349 c.vertex = null;
350 }
351 }
352 ret.add(save());
353 type = ERASED;
354 }
355 /** Check if this cell is one of the destination.
356 *
357 * FIXME: For now, we always have line destination.
358 */
359 boolean reached(Cell dest) {
360 if (rown == dest.rown) {
361 if (DEBUG)
362 msg.println(NAME + ".reached(): dest=" + dest + ", this=" + this);
363 if (dest.vertex.isBus())
364 return true;
365 if (dest.vertex.isReal()) {
366 if (coln == dest.coln)
367 return true;
368 }
369 }
370 return false;
371 }
372
373 /**
374 * Calculate cost due to distance between this and the parent cell.
375 * Ignore turnings that are considered in travelCostFrom().
376 */
377 int distCostFrom(Cell parent) {
378 int cost = fCELL_BASICCOST;
379 // Distance cost.
380 //
381 // Linear proportional to dx keep path in straight lines.
382 // if (parent.coln > coln)
383 // cost += (parent.coln - coln) * fCELL_DISTCOST;
384 // else
385 // cost += (coln - parent.coln) * fCELL_DISTCOST;
386 //
387 // Proportional to square produce diagonal paths.
388 cost += (coln - parent.coln) * (coln - parent.coln) / fCELL_DISTCOST;
389 return cost;
390 }
391
392 /** Calculate cost for transversing from parent to this cell.
393 */
394 int travelCostFrom(Cell parent, Cell grandparent) {
395 int cost = fCELL_BASICCOST;
396 // Distance cost.
397 // Linear proportional to dx keep path in straight lines.
398 // Proportional to square produce diagonal paths.
399 if (parent.coln > coln)
400 cost += (parent.coln - coln) * (parent.coln - coln) / fCELL_DISTCOST;
401 else
402 cost += (coln - parent.coln) * (coln - parent.coln) / fCELL_DISTCOST;
403 if (false)
404 msg.println(
405 NAME
406 + ".traverlCostFrom(): distcost="
407 + (coln - parent.coln) * (coln - parent.coln) / fCELL_TURNCOST);
408 // Turning cost.
409 if (grandparent != null) {
410 int dx = (coln - parent.coln);
411 // Unfortunately, this cause path cost to be different when calculating from
412 // different direction and cause some edge to be routed the same way again and again.
413 // if (dx != 0 && dx != (parent.coln - grandparent.coln))
414 if (dx != (parent.coln - grandparent.coln))
415 cost += fCELL_TURNCOST;
416 /*
417 if(dx>=0) cost+=dx*TURNFACTOR;
418 else cost-=dx*TURNFACTOR;
419 */
420 if (false)
421 msg.println(NAME + ".traverlCostFrom(): turncost=" + dx * fCELL_TURNCOST);
422 }
423 return cost;
424 }
425
426 /**
427 * @return 1 if this is lower cost(higher priority) than given 'state', 0 if equal cost, else -1.
428 * */
429 public int lowerCostThan(Cell a) {
430 if (estTotal < a.estTotal)
431 return 1;
432 if (estTotal > a.estTotal)
433 return -1;
434 if (curCost > a.curCost)
435 return 1;
436 if (curCost < a.curCost)
437 return -1;
438 return 0;
439 }
440
441 /**
442 * Visit this cell from parent through the edge chain 'chain'.
443 *
444 * @return
445 * REJECT path have higher cost and should be discarded.
446 * QUEUE path have lower cost and should be queued.
447 * REQUEUEpath have been visited before but now have a lower cost and should be requeued.
448 */
449 public int accept(Cell parent, Cell dest, int cost) {
450 if (mark == fMARKCOUNTER) {
451 // Visited before.
452 if (cost < curCost) {
453 // The new visit have lower cost, requeue it.
454 curCost = cost;
455 estTotal = cost + estimate(dest);
456 this.parent = parent;
457 //if(estTotal>oldcost) return false;
458 return REQUEUE;
459 }
460 } else {
461 mark = fMARKCOUNTER;
462 heapIndex = 0;
463 curCost = cost;
464 estTotal = cost + estimate(dest);
465 this.parent = parent;
466 //if(estTotal>=oldcost) return false;
467 return QUEUE;
468 }
469 return REJECT;
470 }
471
472 /** Reset to init. state. */
473 public void reset() {}
474
475 ////////////////////////////////////////////////////////////////////////
476
477 public boolean equals(Object a) {
478 if (!(a instanceof Cell))
479 return false;
480 Cell ca = (Cell) a;
481 if (ca.rown != rown || ca.coln != coln || ca.type != type)
482 return false;
483 if (vertex == null && ca.vertex == null || vertex != null && vertex.equals(ca.vertex))
484 return true;
485 msg.err(NAME + ".equals(): vertex not equals:\n\tthis=" + toString() + "\n\ta=" + ca);
486 return false;
487 }
488
489 ////////////////////////////////////////////////////////////////////////
490
491 public String toString() {
492 String ret = "SPACE";
493 String order = "";
494 if (type == BLOCKED)
495 ret = "BLOCKED ";
496 else if (type == ERASED)
497 ret = "ERASED ";
498 if (vertex != null) {
499 ret = vertex.getName();
500 order = " " + vertex.order + " ";
501 }
502 return ret + " (" + rown + "," + coln + order + " cost=" + curCost + "/" + estTotal + ")";
503 }
504
505 public void toGeneralPath(StringBuffer buf, String fill) {
506 final int unit = 10;
507 int xx = coln * unit;
508 int yy = rown * unit;
509 if (fill == null) {
510 fill = "red";
511 if (type == SPACE)
512 fill = "lightgray";
513 else if (type == VERTEX)
514 fill = "black";
515 else if (type == BUS)
516 fill = "blue";
517 else if (type == VIRTUAL)
518 fill = "deepskyblue";
519 else if (type == BLOCKED)
520 fill = "white";
521 else if (type == ERASED)
522 fill = "pink";
523 }
524 buf.append("<rect color=\"white\" fill=\"" + fill + "\">" + xx + "," + yy);
525 buf.append(" " + unit + "," + unit);
526 buf.append("</rect>\n");
527 }
528
529 ////////////////////////////////////////////////////////////////////////
530
531 }