bundles/org.simantics.diagram.connection/src/org/simantics/diagram/connection/RouteGraph.java

   1 /*******************************************************************************
   2  * Copyright (c) 2011 Association for Decentralized Information Management in
   3  * Industry THTH ry.
   4  * All rights reserved. This program and the accompanying materials
   5  * are made available under the terms of the Eclipse Public License v1.0
   6  * which accompanies this distribution, and is available at
   7  * http://www.eclipse.org/legal/epl-v10.html
   8  *
   9  * Contributors:
  10  *     VTT Technical Research Centre of Finland - initial API and implementation
  11  *******************************************************************************/
  12 package org.simantics.diagram.connection;
  13
  14 import gnu.trove.list.array.TDoubleArrayList;
  15 import gnu.trove.map.hash.THashMap;
  16 import gnu.trove.map.hash.TObjectIntHashMap;
  17 import gnu.trove.set.hash.THashSet;
  18
  19 import java.awt.geom.Line2D;
  20 import java.awt.geom.Path2D;
  21 import java.awt.geom.Rectangle2D;
  22 import java.io.PrintStream;
  23 import java.io.Serializable;
  24 import java.util.ArrayList;
  25 import java.util.Collection;
  26 import java.util.Collections;
  27 import java.util.Iterator;
  28
  29 import org.simantics.diagram.connection.rendering.arrows.ILineEndStyle;
  30 import org.simantics.diagram.connection.rendering.arrows.PlainLineEndStyle;
  31 import org.simantics.diagram.connection.segments.Segment;
  32 import org.simantics.diagram.connection.splitting.SplittedRouteGraph;
  33
  34 public class RouteGraph implements Serializable {
  35
  36     private static final long serialVersionUID = 2004022454972623908L;
  37
  38     public static final boolean RETURN_UNMODIFIABLE_COLLECTIONS = false;
  39     public static final boolean CHECK_PARAMERS = true;
  40
  41     ArrayList<RouteLine> lines = new ArrayList<RouteLine>(4);
  42     ArrayList<RouteTerminal> terminals = new ArrayList<RouteTerminal>(4);
  43     ArrayList<RouteLine> transientLines = new ArrayList<RouteLine>(4);
  44     int caseId;
  45     boolean isSimpleConnection;
  46     boolean needsUpdate = false;
  47
  48     /**
  49      * Adds a route line to the graph.
  50      * @param isHorizontal true, if the line is horizontal
  51      * @param position y coordinate of the line if horizontal, x coordinate if vertical
  52      * @return The new line.
  53      */
  54     public RouteLine addLine(boolean isHorizontal, double position) {
  55         RouteLine line = new RouteLine(isHorizontal, position);
  56         lines.add(line);
  57         return line;
  58     }
  59
  60     /**
  61      * Adds a route terminal to the graph.
  62      * @param x The location of the terminal.
  63      * @param y
  64      * @param minX The avoidance area of the terminal.
  65      * @param minY
  66      * @param maxX
  67      * @param maxY
  68      * @param allowedDirections Allowed directions.
  69      *        First four bits tell with which directions
  70      *        a connection can leave the terminal. The
  71      *        Fifth bit indicates whether direct lines
  72      *        can be drawn to the terminal. Directions are
  73      * <pre>
  74      * 0 right (1,0)
  75      * 1 down  (0,1)
  76      * 2 left  (-1,0)
  77      * 3 up    (0,-1)
  78      * </pre>
  79      * @param style Tells what kind of line end is drawn
  80      *        to the connection.
  81      * @return The new terminal.
  82      */
  83     public RouteTerminal addTerminal(double x, double y,
  84             double minX, double minY,
  85             double maxX, double maxY,
  86             int allowedDirections,
  87             ILineEndStyle style) {
  88         return addTerminal(x, y, minX, minY, maxX, maxY, allowedDirections, style, null);
  89
  90     }
  91     public RouteTerminal addTerminal(double x, double y,
  92             double minX, double minY,
  93             double maxX, double maxY,
  94             int allowedDirections,
  95             ILineEndStyle style, ILineEndStyle dynamicStyle) {
  96         if(CHECK_PARAMERS) {
  97             if(allowedDirections > 0x1f)
  98                 throw new IllegalArgumentException("Illegal allowedDirection flags.");
  99             if(minX > x || x > maxX || minY > y || y > maxY)
 100                 throw new IllegalArgumentException("Illegal position attributes for a terminal, (" + x + ", " + y + ") is outside of (" + minX + ", " + minY + ")x(" + maxX + ", " + maxY + ").");
 101         }
 102         if(style == null)
 103             style = PlainLineEndStyle.INSTANCE;
 104         RouteTerminal terminal = new RouteTerminal(x, y, minX, minY,
 105                 maxX, maxY, allowedDirections, false, style);
 106         terminal.setDynamicStyle(dynamicStyle);
 107         terminals.add(terminal);
 108         return terminal;
 109     }
 110
 111     public RouteTerminal addBigTerminal(
 112             double minX, double minY,
 113             double maxX, double maxY,
 114             ILineEndStyle style) {
 115         return addBigTerminal(minX, minY, maxX, maxY, style, null);
 116     }
 117     public RouteTerminal addBigTerminal(
 118             double minX, double minY,
 119             double maxX, double maxY,
 120             ILineEndStyle style, ILineEndStyle dynamicStyle) {
 121         if(style == null)
 122             style = PlainLineEndStyle.INSTANCE;
 123         RouteTerminal terminal = new RouteTerminal(
 124                 0.5*(minX+maxX), 0.5*(minY+maxY),
 125                 minX, minY,
 126                 maxX, maxY,
 127                 0xf, true, style);
 128         terminal.setDynamicStyle(dynamicStyle);
 129
 130         terminals.add(terminal);
 131         return terminal;
 132     }
 133
 134     /**
 135      * Adds a route terminal to the graph. The avoidance
 136      * area is given as a rectangle.
 137      * @see RouteGraph#addTerminal(double, double, double, double, double, double, int, ILineEndStyle)
 138      */
 139     public RouteTerminal addTerminal(double x, double y,
 140             Rectangle2D bounds,
 141             int allowedDirections,
 142             ILineEndStyle style) {
 143         return addTerminal(x, y,
 144                 bounds.getMinX(), bounds.getMinY(), bounds.getMaxX(), bounds.getMaxY(),
 145                 allowedDirections, style);
 146     }
 147
 148     /**
 149      * Adds a copy of the given terminal to the graph.
 150      */
 151     public RouteTerminal addTerminal(RouteTerminal terminal) {
 152         RouteTerminal newTerminal = addTerminal(terminal.x, terminal.y,
 153                 terminal.getMinX(), terminal.getMinY(),
 154                 terminal.getMaxX(), terminal.getMaxY(),
 155                 terminal.getAllowedDirections(), terminal.getStyle(), terminal.getDynamicStyle());
 156         newTerminal.setData(terminal.getData());
 157         return terminal;
 158     }
 159
 160     /**
 161      * Adds a route terminal to the graph. A default line end style is used.
 162      * @see RouteGraph#addTerminal(double, double, double, double, double, double, int, ILineEndStyle)
 163      */
 164     public RouteTerminal addTerminal(double x, double y,
 165             double minX, double minY,
 166             double maxX, double maxY,
 167             int allowedDirections) {
 168         return addTerminal(x, y, minX, minY, maxX, maxY, allowedDirections,
 169                 PlainLineEndStyle.INSTANCE);
 170     }
 171
 172     /**
 173      * Links nodes.
 174      */
 175     public void link(RouteNode node1, RouteNode node2) {
 176         if(node1 instanceof RouteLine) {
 177             if(node2 instanceof RouteLine) {
 178                 link((RouteLine)node1, (RouteLine)node2);
 179             }
 180             else {
 181                 link((RouteLine)node1, (RouteTerminal)node2);
 182             }
 183         }
 184         else {
 185             if(node2 instanceof RouteLine) {
 186                 link((RouteTerminal)node1, (RouteLine)node2);
 187             }
 188             else {
 189                 link((RouteTerminal)node1, (RouteTerminal)node2);
 190             }
 191         }
 192     }
 193
 194     /**
 195      * Links nodes.
 196      */
 197     public void link(RouteNode ... nodes) {
 198         for(int i=1;i<nodes.length;++i)
 199             link(nodes[i-1], nodes[i]);
 200     }
 201
 202     /**
 203      * Links lines.
 204      */
 205     public void link(RouteLine node1, RouteLine node2) {
 206         new RouteLink(node1, node2);
 207         needsUpdate = true;
 208     }
 209
 210     /**
 211      * Links a terminal and a line.
 212      */
 213     public void link(RouteTerminal node1, RouteLine node2) {
 214         if(CHECK_PARAMERS) {
 215             if(node2 == null)
 216                 throw new NullPointerException();
 217             if(node1.line != null)
 218                 throw new IllegalStateException("Terminal is already connected.");
 219         }
 220         node1.line = node2;
 221         needsUpdate = true;
 222     }
 223
 224     /**
 225      * Links a line and a terminal.
 226      */
 227     public void link(RouteLine node1, RouteTerminal node2) {
 228         if(CHECK_PARAMERS) {
 229             if(node1 == null)
 230                 throw new NullPointerException();
 231             if(node2.line != null)
 232                 throw new IllegalStateException("Terminal is already connected.");
 233         }
 234         node2.line = node1;
 235         needsUpdate = true;
 236     }
 237
 238     /**
 239      * Links two terminals.
 240      */
 241     public void link(RouteTerminal node1, RouteTerminal node2) {
 242         if(CHECK_PARAMERS) {
 243             if(node1 == null)
 244                 throw new NullPointerException();
 245             if(node2 == null)
 246                 throw new NullPointerException();
 247         }
 248         isSimpleConnection = true;
 249         needsUpdate = true;
 250     }
 251
 252     void removeTransientRouteLines() {
 253         for(RouteLine line : transientLines)
 254             line.remove();
 255         transientLines.clear();
 256     }
 257
 258     /**
 259      * Rotates given terminal clockwise by given amount
 260      * (also negative numbers are allowed).
 261      */
 262     public void rotate(RouteTerminal terminal, int amount) {
 263         terminal.rotate(amount);
 264         needsUpdate = true;
 265     }
 266
 267     /**
 268      * Moves the given route line so that its position correspond
 269      * to given x or y depending on the orientation of the line.
 270      */
 271     public void setLocation(RouteLine line, double x, double y) {
 272         makePersistent(line);
 273         line.setLocation(x, y);
 274         needsUpdate = true;
 275     }
 276
 277     /**
 278      * Moves the terminal to given location.
 279      */
 280     public void setLocation(RouteTerminal terminal, double x, double y) {
 281         terminal.setLocation(x, y);
 282         needsUpdate = true;
 283     }
 284
 285     /**
 286      * Updates transient route lines, route link positions
 287      * and sorts route points of each route line.
 288      */
 289     public void update() {
 290         needsUpdate = false;
 291         removeTransientRouteLines();
 292
 293         //print();
 294
 295         for(RouteLine line : lines)
 296             line.hidden = false;
 297         for(RouteTerminal terminal : terminals)
 298             if(terminal.hasDirectConnection() && terminal.line != null)
 299                 terminal.line.hidden = true;
 300
 301         // Choose a strategy
 302         if(isSimpleConnection) {
 303             RouteTerminal a = terminals.get(0);
 304             RouteTerminal b = terminals.get(1);
 305             if(a.hasDirectConnection() || b.hasDirectConnection())
 306                 return;
 307             caseId = SimpleConnectionUtility.simpleConnectionCase(a, b);
 308             //System.out.println("caseId = " + caseId);
 309             switch(caseId) {
 310             case SimpleConnectionUtility.DIRECT_HORIZONTAL_CONNECTION:
 311             case SimpleConnectionUtility.DIRECT_VERTICAL_CONNECTION: {
 312                 boolean horiz = caseId==SimpleConnectionUtility.DIRECT_HORIZONTAL_CONNECTION;
 313                 RouteLine line = new RouteLine(horiz, horiz ? a.y : a.x);
 314                 line.addPoint(a);
 315                 line.addPoint(b);
 316                 line.terminal = a;
 317                 transientLines.add(line);
 318                 break;
 319             }
 320             case SimpleConnectionUtility.ONE_BEND_HORIZONTAL_VERTICAL: {
 321                 RouteLine line1 = new RouteLine(true, a.y);
 322                 RouteLine line2 = new RouteLine(false, b.x);
 323                 new RouteLink(line1, line2);
 324                 line1.addPoint(a);
 325                 line2.addPoint(b);
 326                 line1.terminal = a;
 327                 line2.terminal = b;
 328                 transientLines.add(line1);
 329                 transientLines.add(line2);
 330                 break;
 331             }
 332             case SimpleConnectionUtility.ONE_BEND_VERTICAL_HORIZONTAL: {
 333                 RouteLine line1 = new RouteLine(false, a.x);
 334                 RouteLine line2 = new RouteLine(true, b.y);
 335                 new RouteLink(line1, line2);
 336                 line1.addPoint(a);
 337                 line2.addPoint(b);
 338                 line1.terminal = a;
 339                 line2.terminal = b;
 340                 transientLines.add(line1);
 341                 transientLines.add(line2);
 342                 break;
 343             }
 344             case SimpleConnectionUtility.MORE_BENDS_BBS_DONT_INTERSECT:
 345             case SimpleConnectionUtility.MORE_BENDS_BBS_INTERSECT: {
 346                 RouteLine line =
 347                         SimpleConnectionUtility.findRouteLine(terminals.get(0), terminals.get(1),
 348                                 caseId == SimpleConnectionUtility.MORE_BENDS_BBS_INTERSECT )
 349                                 ;
 350                 terminals.get(0).line = line;
 351                 terminals.get(1).line = line;
 352                 transientLines.add(line);
 353                 routeFromTerminals(caseId==SimpleConnectionUtility.MORE_BENDS_BBS_INTERSECT);
 354                 break;
 355             }
 356             }
 357         }
 358         else {
 359             caseId = SimpleConnectionUtility.COMPLEX_CONNECTION;
 360             routeFromTerminals(false);
 361         }
 362
 363         // Find positions of route points
 364         for(RouteLine line : lines)
 365             line.setPointPositions();
 366         for(RouteLine line : transientLines)
 367             line.setPointPositions();
 368
 369         // Sort route points in route lines
 370         for(RouteLine line : lines) {
 371             line.sortPoints();
 372         }
 373         for(RouteLine line : transientLines) {
 374             line.sortPoints();
 375         }
 376     }
 377
 378     static class Interval {
 379         public final double min;
 380         public final double max;
 381         public Interval(double min, double max) {
 382             this.min = min;
 383             this.max = max;
 384         }
 385     }
 386
 387     class IntervalCache {
 388         THashMap<RouteLine, Interval> cache =
 389                 new THashMap<RouteLine, Interval>();
 390         public Interval get(RouteLine line) {
 391             Interval result = cache.get(line);
 392             if(result != null)
 393                 return result;
 394
 395             result = create(line);
 396             cache.put(line, result);
 397             return result;
 398         }
 399
 400         private Interval create(RouteLine line) {
 401             double min = Double.POSITIVE_INFINITY;
 402             double max = Double.NEGATIVE_INFINITY;
 403
 404             for(RoutePoint point : line.points) {
 405                 double temp;
 406                 if(point instanceof RouteLink) {
 407                     RouteLink link = (RouteLink)point;
 408                     if(link.a == line)
 409                         temp = link.b.position;
 410                     else
 411                         temp = link.a.position;
 412                 }
 413                 else {
 414                     RouteTerminal terminal = (RouteTerminal)point;
 415                     if(line.isHorizontal)
 416                         temp = terminal.x;
 417                     else
 418                         temp = terminal.y;
 419                 }
 420                 if(temp < min)
 421                     min = temp;
 422                 if(temp > max)
 423                     max = temp;
 424             }
 425             for(RouteTerminal terminal : terminals) {
 426                 if(terminal.line == line) {
 427                     double temp = terminal.approximatePositionToLine();
 428                     if(temp < min)
 429                         min = temp;
 430                     if(temp > max)
 431                         max = temp;
 432                 }
 433             }
 434
 435             return new Interval(min, max);
 436         }
 437     }
 438
 439     private void routeFromTerminals(boolean boundingBoxesIntersect) {
 440         IntervalCache cache = new IntervalCache();
 441         for(RouteTerminal terminal : terminals)
 442             if(terminal.line != null) {
 443                 if(!terminal.hasDirectConnection())
 444                     terminal.route(transientLines, cache, boundingBoxesIntersect);
 445             }
 446     }
 447
 448     /**
 449      * Returns a RouteLine near the given point (x,y) (within tolerance).
 450      */
 451     public RouteLine pickLine(double x, double y, double tolerance, int mask) {
 452         if(needsUpdate)
 453             update();
 454         if(isSimpleConnection && transientLines.isEmpty()) {
 455             if(terminals.size() == 2) {
 456                 if((mask & PICK_TRANSIENT_LINES) == 0)
 457                     return null;
 458                 RouteTerminal a = terminals.get(0);
 459                 RouteTerminal b = terminals.get(1);
 460                 if(a.hasDirectConnection() || b.hasDirectConnection()) {
 461                     if(Line2D.ptSegDistSq(a.x, a.y, b.x, b.y, x, y) <= tolerance*tolerance) {
 462                         RouteLine dummy = new RouteLine(false, y);
 463                         return dummy; // There are no lines to return
 464                     }
 465                     else
 466                         return null;
 467                 }
 468             }
 469         }
 470         if((mask & PICK_PERSISTENT_LINES) != 0)
 471             for(RouteLine line : lines)
 472                 if(line.isNear(x, y, tolerance))
 473                     return line;
 474         if((mask & PICK_TRANSIENT_LINES) != 0)
 475             for(RouteLine line : transientLines)
 476                 if(line.isNear(x, y, tolerance))
 477                     return line;
 478         if((mask & PICK_DIRECT_LINES) != 0) {
 479             RouteTerminal terminal = pickDirectLine(x, y, tolerance);
 480             if(terminal != null)
 481                 return terminal.line;
 482         }
 483         return null;
 484     }
 485
 486     public RouteLine pickLine(double x, double y, double tolerance) {
 487         return pickLine(x, y, tolerance, PICK_LINES);
 488     }
 489
 490     private RouteTerminal pickDirectLine(double x, double y, double tolerance) {
 491         double toleranceSq = tolerance * tolerance;
 492         for(RouteTerminal terminal : terminals)
 493             if((terminal.getAllowedDirections()&0x10) != 0) {
 494                 try {
 495                         RouteLine line = terminal.getLine();
 496                         if(line == null)
 497                                 continue;
 498                     RoutePoint b = line.getBegin();
 499                     double distSq = Line2D.ptSegDistSq(terminal.x, terminal.y, b.x, b.y, x, y);
 500                     if(distSq <= toleranceSq) {
 501                         //System.out.println("distSq = " + distSq + ", toleranceSq = " + toleranceSq);
 502                         return terminal;
 503                     }
 504                 } catch(NullPointerException e) {
 505                     //if terminal does not have a line
 506                     e.printStackTrace();
 507                 } catch(IndexOutOfBoundsException e) {
 508                     // if line does not contain points
 509                     e.printStackTrace();
 510                 }
 511             }
 512         return null;
 513     }
 514
 515     public RouteLineHalf pickLineHalf(double x, double y, double tolerance) {
 516         if(isSimpleConnection)
 517             return null;
 518         if(needsUpdate)
 519             update();
 520         RouteLine line = pickLine(x, y, tolerance);
 521         if(line == null)
 522             return null;
 523         RouteLink link = null;
 524         RoutePoint begin = line.getBegin();
 525         RoutePoint end = line.getEnd();
 526         if(line.isHorizontal) {
 527             double mx = 0.5*(begin.getX() + end.getX());
 528             if(x < mx) {
 529                 if(begin instanceof RouteLink)
 530                     link = (RouteLink)begin;
 531             }
 532             else {
 533                 if(end instanceof RouteLink)
 534                     link = (RouteLink)line.getEnd();
 535             }
 536         }
 537         else {
 538             double my = 0.5*(begin.getY() + end.getY());
 539             if(y < my) {
 540                 if(begin instanceof RouteLink)
 541                     link = (RouteLink)begin;
 542             }
 543             else {
 544                 if(end instanceof RouteLink)
 545                     link = (RouteLink)end;
 546             }
 547         }
 548         if(link == null)
 549             return null;
 550         if(link.getOther(line).isTransient())
 551             return null;
 552         return new RouteLineHalf(line, link);
 553     }
 554
 555     public Collection<RouteLineHalf> getLineHalves() {
 556         return getLineHalves(new ArrayList<RouteLineHalf>());
 557     }
 558
 559     public Collection<RouteLineHalf> getLineHalves(Collection<RouteLineHalf> result) {
 560         for(RouteLine line : getAllLines()) {
 561             {
 562                 RoutePoint p = line.getBegin();
 563                 if(p instanceof RouteLink) {
 564                     RouteLink link = (RouteLink)p;
 565                     if(!link.getOther(line).isTransient())
 566                         result.add(new RouteLineHalf(line, link));
 567                 }
 568             }
 569             {
 570                 RoutePoint p = line.getEnd();
 571                 if(p instanceof RouteLink) {
 572                     RouteLink link = (RouteLink)p;
 573                     if(!link.getOther(line).isTransient())
 574                         result.add(new RouteLineHalf(line, link));
 575                 }
 576             }
 577         }
 578         return result;
 579     }
 580
 581     /**
 582      * Returns a RoutePoint near the given point (x,y) (within tolerance).
 583      */
 584     public RoutePoint pickPoint(double x, double y, double tolerance, int mask) {
 585         if(needsUpdate)
 586             update();
 587         if((mask&PICK_TERMINALS) != 0)
 588             for(RouteTerminal terminal : terminals)
 589                 if(terminal.isNear(x, y))
 590                     return terminal;
 591         if((mask&PICK_INTERIOR_POINTS) != 0) {
 592             for(RouteLine line : lines) {
 593                 for(RoutePoint point : line.points)
 594                     if(point.isNear(x, y, tolerance))
 595                         return point;
 596             }
 597             for(RouteLine line : transientLines) {
 598                 for(RoutePoint point : line.points)
 599                     if(point.isNear(x, y, tolerance))
 600                         return point;
 601             }
 602         }
 603         return null;
 604     }
 605
 606     public RoutePoint pickPoint(double x, double y, double tolerance) {
 607         return pickPoint(x, y, tolerance, PICK_POINTS);
 608     }
 609
 610     public static final int PICK_INTERIOR_POINTS = 1;
 611     public static final int PICK_TERMINALS = 2;
 612     public static final int PICK_POINTS = PICK_INTERIOR_POINTS | PICK_TERMINALS;
 613
 614     public static final int PICK_PERSISTENT_LINES = 4;
 615     public static final int PICK_TRANSIENT_LINES = 8;
 616     public static final int PICK_DIRECT_LINES = 16;
 617     public static final int PICK_LINES = PICK_PERSISTENT_LINES | PICK_TRANSIENT_LINES | PICK_DIRECT_LINES;
 618
 619     public static final int PICK_ALL = PICK_POINTS | PICK_LINES;
 620
 621     /**
 622      * Returns RoutePoint or RouteLine near the given point (x,y) (within tolerance).
 623      */
 624     public Object pick(double x, double y, double tolerance, int mask) {
 625         if((mask & PICK_POINTS) != 0) {
 626             Object point = pickPoint(x, y, tolerance, mask);
 627             if(point != null)
 628                 return point;
 629         }
 630         /*if((mask & PICK_DIRECT_LINES) != 0) {
 631             RouteTerminal terminal = pickDirectLine(x, y, tolerance);
 632             if(terminal != null)
 633                 return terminal.line.getBegin();
 634         }*/
 635         if((mask & PICK_LINES) != 0)
 636             return pickLine(x, y, tolerance, mask);
 637         else
 638             return null;
 639     }
 640
 641     public Object pick(double x, double y, double tolerance) {
 642         return pick(x, y, tolerance, PICK_ALL);
 643     }
 644
 645     /**
 646      * Returns RoutePoint or RouteLine exactly under the given point (x,y).
 647      */
 648     public Object pick(double x, double y) {
 649         return pick(x, y, 0.0);
 650     }
 651
 652     /**
 653      * Prints the contents of the route graph to stdout.
 654      */
 655     public void print() {
 656         print(System.out);
 657     }
 658
 659     /**
 660      * Prints the contents of the route graph to given print stream.
 661      */
 662     public void print(PrintStream out) {
 663         if(needsUpdate)
 664             update();
 665         if(isSimpleConnection)
 666             out.println("=== SIMPLE CONNECTION ===");
 667         else
 668             out.println("=== COMPLEX CONNECTION ===");
 669         for(RouteLine line : lines) {
 670             out.print("perst");
 671             line.print(out);
 672         }
 673         for(RouteLine line : transientLines) {
 674             out.print("trans");
 675             line.print(out);
 676         }
 677         for(RouteTerminal terminal : terminals) {
 678             out.print("term");
 679             terminal.print(out);
 680         }
 681     }
 682
 683     public void makePersistent(RouteLine line) {
 684         prepareForModification();
 685         if(isSimpleConnection || line.isTransient()) {
 686             if(isSimpleConnection) {
 687                 isSimpleConnection = false;
 688                 for(RouteTerminal terminal : terminals)
 689                     terminal.line = line;
 690                 transientLines.remove(line);
 691                 lines.add(line);
 692                 Iterator<RoutePoint> it = line.points.iterator();
 693                 while(it.hasNext()) {
 694                     RoutePoint point = it.next();
 695                     if(point instanceof RouteTerminal)
 696                         it.remove();
 697                 }
 698                 line.terminal = null;
 699                 line.nextTransient = null;
 700             }
 701             else {
 702                 line.terminal.line = line;
 703                 do {
 704                     transientLines.remove(line);
 705                     lines.add(line);
 706                     Iterator<RoutePoint> it = line.points.iterator();
 707                     while(it.hasNext()) {
 708                         RoutePoint point = it.next();
 709                         if(point instanceof RouteTerminal)
 710                             it.remove();
 711                     }
 712                     line.terminal = null;
 713                     RouteLine temp = line.nextTransient;
 714                     line.nextTransient = null;
 715                     line = temp;
 716                 } while(line != null);
 717             }
 718             needsUpdate = true;
 719         }
 720     }
 721
 722     void prepareForModification() {
 723         if(caseId == 4) {
 724             RouteLine line = transientLines.remove(0);
 725             line.terminal = null;
 726             lines.add(line);
 727             for(RouteTerminal terminal : terminals)
 728                 terminal.line = line;
 729             isSimpleConnection = false;
 730             caseId = 6;
 731         }
 732     }
 733
 734     public double[] getLineLengths(RouteTerminal terminal) {
 735         if(needsUpdate)
 736             update();
 737         if(lines.size()==0 && transientLines.size()==1)
 738             return new double[] { transientLines.get(0).getLength() };
 739
 740         RouteLine line = null;
 741         fLoop:
 742         for(RouteLine l : transientLines)
 743             if(l.isTransient()) {
 744                 for(RoutePoint p : l.points)
 745                     if(!(p instanceof RouteLink)) {
 746                         line = l;
 747                         break fLoop;
 748                     }
 749             }
 750         TDoubleArrayList result = new TDoubleArrayList();
 751         THashSet<RouteLine> set = new THashSet<RouteLine>();
 752         set.add(line);
 753         loop:
 754         while(true) {
 755             result.add(line.getLength());
 756             for(RoutePoint point : line.points)
 757                 if(point instanceof RouteLink) {
 758                     RouteLink link = (RouteLink)point;
 759                     if(set.add(link.a)) {
 760                         line = link.a;
 761                         continue loop;
 762                     }
 763                     if(set.add(link.b)) {
 764                         line = link.b;
 765                         continue loop;
 766                     }
 767                 }
 768             break;
 769         }
 770         return result.toArray();
 771     }
 772
 773     public void split(RouteLine rl1, double splitPosition) {
 774         if(needsUpdate)
 775             update();
 776         boolean isHorizontal = rl1.isHorizontal();
 777         if(isSimpleConnection) {
 778             isSimpleConnection = false;
 779             if(caseId < 2) {
 780                 RouteLine sp = addLine(!isHorizontal, splitPosition);
 781                 for(RouteTerminal terminal : terminals)
 782                     terminal.line = sp;
 783                 update();
 784                 return;
 785             }
 786             else if(caseId < 4) {
 787                 RouteLine sp = addLine(!isHorizontal, splitPosition);
 788                 RouteLine l = addLine(isHorizontal, rl1.position);
 789                 link(l, sp);
 790                 rl1.terminal.line = sp;
 791                 for(RouteTerminal terminal : terminals)
 792                     if(terminal != rl1.terminal)
 793                         terminal.line = l;
 794                 update();
 795                 return;
 796             }
 797             else
 798                 prepareForModification();
 799         }
 800
 801         RouteLine rl2 = new RouteLine(isHorizontal, rl1.getPosition());
 802         RouteLine sp = new RouteLine(!isHorizontal, splitPosition);
 803
 804         ArrayList<RoutePoint> points = rl1.points;
 805
 806         int splitPos;
 807         {
 808             int minPos = 0;
 809             int maxPos = points.size();
 810             while(minPos != maxPos) {
 811                 int c = (minPos + maxPos)/2;
 812                 if(isHorizontal
 813                         ? points.get(c).getX() > splitPosition
 814                         : points.get(c).getY() > splitPosition)
 815                     maxPos = c;
 816                 else
 817                     minPos = c+1;
 818             }
 819             splitPos = minPos;
 820         }
 821
 822         for(int i=points.size()-1;i>=splitPos;--i) {
 823             RoutePoint point = points.remove(i);
 824             if(point instanceof RouteLink) {
 825                 RouteLink link = (RouteLink)point;
 826                 link.replace(rl1, rl2);
 827             }
 828         }
 829
 830         if(rl1.isTransient()) {
 831             boolean p1 = rl1.isConnectedToPeristentLine();
 832             boolean p2 = rl2.isConnectedToPeristentLine();
 833
 834             RouteTerminal terminal = rl1.terminal;
 835             if(p1) {
 836                 makePersistent(rl1);
 837                 transientLines.add(rl2);
 838             }
 839             else if(p2) {
 840                 lines.add(rl2);
 841             }
 842             else {
 843                 transientLines.add(rl2);
 844                 if(lines.isEmpty())
 845                     for(RouteTerminal t : terminals)
 846                         t.line = sp;
 847             }
 848             terminal.line = sp;
 849         }
 850         else
 851             lines.add(rl2);
 852
 853         new RouteLink(rl1, sp);
 854         new RouteLink(sp, rl2);
 855         lines.add(sp);
 856         update();
 857     }
 858
 859     public boolean merge(RouteLine line) {
 860         int count = 0;
 861         double sum = 0;
 862         for(RoutePoint point : line.points) {
 863             if(point instanceof RouteLink) {
 864                 RouteLink link = (RouteLink)point;
 865                 RouteLine other = link.getOther(line);
 866                 if(!other.isTransient()) {
 867                     sum += other.position;
 868                     ++count;
 869                 }
 870             }
 871         }
 872         return merge(line, sum / count);
 873     }
 874
 875     /**
 876      * Removes given route line and collapses all its neighbor
 877      * route lines into one line with given position.
 878      */
 879     public boolean merge(RouteLine line, double position) {
 880         if(needsUpdate)
 881             update();
 882         if(isSimpleConnection || line.isTransient())
 883             return false;
 884
 885         if(lines.size() == 1) {
 886             if(terminals.size() != 2)
 887                 return false;
 888             lines.remove(0);
 889             isSimpleConnection = true;
 890             for(RouteTerminal terminal : terminals)
 891                 terminal.line = null;
 892             update();
 893             return true;
 894         }
 895
 896         ArrayList<RouteLine> nLines = new ArrayList<RouteLine>();
 897         for(RoutePoint point : line.points) {
 898             /* Because line.terminal == null, there should be
 899              * not RouteTerminals
 900              *
 901              * Update 14.2.2014: With Sulca, there is a constant issue when line.terminal == null but point is RouteTerminal.
 902              */
 903                 if (point instanceof RouteLink) {
 904                     RouteLine l = ((RouteLink)point).getOther(line);
 905                     l.points.remove(point);
 906                     if(!l.isTransient())
 907                         nLines.add(l);
 908                 }
 909         }
 910
 911         if(nLines.isEmpty())
 912             return false;
 913         RouteLine merged = nLines.remove(nLines.size()-1);
 914         merged.position = position;
 915         for(RouteLine l : nLines) {
 916             for(RoutePoint point : l.points) {
 917                 /* Because l.terminal == null, there should be
 918                  * not RouteTerminals
 919                  *
 920                  * Update 16.10.2014: With Sulca, there is a constant issue when line.terminal == null but point is RouteTerminal.
 921                  */
 922                 if (point instanceof RouteLink) {
 923                         RouteLink link = (RouteLink)point;
 924                         link.replace(l, merged);
 925                 }
 926             }
 927         }
 928         THashSet<RouteLine> removedLines = new THashSet<RouteLine>();
 929         removedLines.addAll(nLines);
 930         lines.removeAll(removedLines);
 931         removedLines.add(line);
 932         lines.remove(line);
 933         for(RouteTerminal terminal : terminals)
 934             if(removedLines.contains(terminal.line))
 935                 terminal.line = merged;
 936         update();
 937         return true;
 938     }
 939
 940     public void deleteCorner(RouteLink link) {
 941         if(needsUpdate)
 942             update();
 943         RouteLine a = link.getA();
 944         RouteLine b = link.getB();
 945         if(a.isTransient() || b.isTransient()
 946                 || a.points.size() != 2 || b.points.size() != 2)
 947             return;
 948         RouteLine na=null, nb=null;
 949         for(RoutePoint p : a.points) {
 950             RouteLink l = (RouteLink)p;
 951             if(l.a == a && l.b != b) {
 952                 na = l.b;
 953                 break;
 954             }
 955             else if(l.b == a && l.a != b) {
 956                 na = l.a;
 957                 break;
 958             }
 959         }
 960         for(RoutePoint p : b.points) {
 961             RouteLink l = (RouteLink)p;
 962             if(l.a == b && l.b != a) {
 963                 nb = l.b;
 964                 break;
 965             }
 966             else if(l.b == b && l.a != a) {
 967                 nb = l.a;
 968                 break;
 969             }
 970         }
 971         if(na == null || nb == null) {
 972             System.err.println("Internal error in router.");
 973             return;
 974         }
 975         a.remove();
 976         b.remove();
 977         lines.remove(a);
 978         lines.remove(b);
 979         link(na, nb);
 980         if(na.terminal != null)
 981             na.terminal.line = nb;
 982         if(nb.terminal != null)
 983             nb.terminal.line = na;
 984         update();
 985     }
 986
 987     public boolean connectTerminal(RouteTerminal terminal, double x, double y, double tolerance) {
 988         Object target = pick(x, y, tolerance);
 989         if(target instanceof RouteLine) {
 990             RouteLine line = (RouteLine)target;
 991             RouteTerminal involvedTerminal =
 992                     line.isTransient() ? line.terminal : null;
 993             makePersistent(line);
 994             terminal.line = null; // TODO this is a workaround
 995
 996             int lineDir = line.isHorizontal
 997                     ? (line.position < terminal.y ? 3 : 1)
 998                     : (line.position < terminal.x ? 2 : 0)
 999                     ;
1000
1001             if(line.isHorizontal && Math.abs(x - terminal.x) > 30) {
1002                 RouteLine l2;
1003                 if(Directions.isAllowed(terminal.getAllowedDirections(), lineDir)) {
1004                     RouteLine l1 = addLine(true, 0.5*(y+terminal.y));
1005                     l2 = addLine(false, x);
1006                     link(terminal, l1, l2, line);
1007                 }
1008                 else {
1009                     l2 = addLine(false, x);
1010                     link(terminal, l2, line);
1011                 }
1012                 if(involvedTerminal != null)
1013                     involvedTerminal.line = l2;
1014             }
1015             else if(!line.isHorizontal && Math.abs(y - terminal.y) > 30) {
1016                 RouteLine l2;
1017                 if(Directions.isAllowed(terminal.getAllowedDirections(), lineDir)) {
1018                     RouteLine l1 = addLine(false, 0.5*(x+terminal.x));
1019                     l2 = addLine(true, y);
1020                     link(terminal, l1, l2, line);
1021                 }
1022                 else {
1023                     l2 = addLine(true, y);
1024                     link(terminal, l2, line);
1025                 }
1026                 if(involvedTerminal != null)
1027                     involvedTerminal.line = l2;
1028             }
1029             else {
1030                 link(terminal, line);
1031             }
1032             update();
1033             return true;
1034         }
1035         else
1036             return false;
1037     }
1038
1039     public boolean connectLine(RouteLine sLine, double x, double y, double tolerance) {
1040         Object target = pick(x, y, tolerance);
1041         if(target instanceof RouteLine) {
1042             RouteLine line = (RouteLine)target;
1043             RouteTerminal involvedTerminal =
1044                     line.isTransient() ? line.terminal : null;
1045             makePersistent(line);
1046             if(line.isHorizontal == sLine.isHorizontal) {
1047                 RouteLine l = addLine(!sLine.isHorizontal,
1048                         sLine.isHorizontal ? x : y);
1049                 link(sLine, l, line);
1050                 if(involvedTerminal != null)
1051                     involvedTerminal.line = l;
1052             }
1053             else {
1054                 link(sLine, line);
1055                 if(involvedTerminal != null)
1056                     involvedTerminal.line = sLine;
1057             }
1058             update();
1059             return true;
1060         }
1061         else
1062             return false;
1063     }
1064
1065     /**
1066      * Makes a deep copy of the route graph and stores
1067      * the correspondences between original and copied
1068      * objects into the given map.
1069      */
1070     public RouteGraph copy(THashMap<Object, Object> map) {
1071         RouteGraph copy = new RouteGraph();
1072         copy.isSimpleConnection = isSimpleConnection;
1073         copy.caseId = caseId;
1074         copy.needsUpdate = needsUpdate;
1075         for(RouteLine line : lines)
1076             copy.lines.add(line.copy(map));
1077         for(RouteLine line : transientLines)
1078             copy.transientLines.add(line.copy(map));
1079         for(RouteTerminal terminal : terminals)
1080             copy.terminals.add(terminal.copy(map));
1081         return copy;
1082     }
1083
1084     /**
1085      * Makes a deep copy of the route graph.
1086      */
1087     public RouteGraph copy() {
1088         THashMap<Object, Object> map = new THashMap<Object, Object>();
1089         return copy(map);
1090     }
1091
1092     /**
1093      * Removes route lines that are conneted to at most
1094      * one other route line or terminal.
1095      */
1096     public void removeExtraConnections() {
1097         TObjectIntHashMap<RouteLine> counts =
1098                 new TObjectIntHashMap<RouteLine>();
1099         removeTransientRouteLines();
1100         for(RouteLine line : lines) {
1101             int count = 0;
1102             for(RoutePoint point : line.points)
1103                 if(point instanceof RouteLink)
1104                     ++count;
1105             counts.put(line, count);
1106         }
1107         for(RouteTerminal terminal : terminals)
1108             counts.adjustOrPutValue(terminal.line, 1, 1);
1109         boolean removed;
1110         do {
1111             removed = false;
1112             Iterator<RouteLine> it = lines.iterator();
1113             while(it.hasNext()) {
1114                 RouteLine line = it.next();
1115                 if(counts.get(line) <= 1) {
1116                     for(RoutePoint point : line.points)
1117                         if(point instanceof RouteLink)
1118                             counts.adjustValue(((RouteLink)point).getOther(line), -1);
1119                     line.remove();
1120                     it.remove();
1121                     removed = true;
1122                 }
1123             }
1124         } while(removed);
1125         update();
1126     }
1127
1128     /**
1129      * Removes a terminal and all route lines that become degenerated by the removal.
1130      */
1131     public void remove(RouteTerminal terminal) {
1132         terminals.remove(terminal);
1133         removeExtraConnections();
1134     }
1135
1136     public void disconnect(RouteTerminal terminal) {
1137         terminal.line = null;
1138         removeExtraConnections();
1139     }
1140
1141     public void remove(RouteLink link) {
1142         link.a.points.remove(link);
1143         link.b.points.remove(link);
1144     }
1145
1146     public void toggleDirectLines(RouteTerminal terminal) {
1147         terminal.toggleDirectLines();
1148         needsUpdate = true;
1149     }
1150
1151     /**
1152      * Returns all persistent route lines of the route graph.
1153      */
1154     public Collection<RouteLine> getLines() {
1155         if(needsUpdate)
1156             update();
1157         if(RETURN_UNMODIFIABLE_COLLECTIONS)
1158             return Collections.unmodifiableList(lines);
1159         else
1160             return lines;
1161     }
1162
1163     /*
1164      * Returns all transient route lines of the route graph.
1165      */
1166     public Collection<RouteLine> getTransientLines() {
1167         if(needsUpdate)
1168             update();
1169         if(RETURN_UNMODIFIABLE_COLLECTIONS)
1170             return Collections.unmodifiableList(transientLines);
1171         else
1172             return transientLines;
1173     }
1174
1175     /**
1176      * Returns all terminals of the route graph.
1177      */
1178     public Collection<RouteTerminal> getTerminals() {
1179         if(RETURN_UNMODIFIABLE_COLLECTIONS)
1180             return Collections.unmodifiableList(terminals);
1181         else
1182             return terminals;
1183     }
1184
1185     /**
1186      * Returns all route lines, both persistent and transient,
1187      * of the route graph.
1188      */
1189     public Collection<RouteLine> getAllLines() {
1190         if(needsUpdate)
1191             update();
1192         ArrayList<RouteLine> allLines = new ArrayList<RouteLine>(lines.size() + transientLines.size());
1193         allLines.addAll(lines);
1194         allLines.addAll(transientLines);
1195         return allLines;
1196     }
1197
1198     /**
1199      * Returns all route lines, both persistent and transient, of the route
1200      * graph, added to the specified collection. Avoids allocation of new
1201      * {@link ArrayList} compared to {@link #getAllLines()}.
1202      */
1203     public Collection<RouteLine> getAllLines(Collection<RouteLine> result) {
1204         if (result == null)
1205             throw new NullPointerException("null result collection");
1206         if(needsUpdate)
1207             update();
1208         result.addAll(lines);
1209         result.addAll(transientLines);
1210         return result;
1211     }
1212
1213     /**
1214      * Returns true, if the route graph is connected and contains no cycles.
1215      */
1216     public boolean isTree() {
1217         if(isSimpleConnection)
1218             return true;
1219         for(RouteTerminal terminal : terminals)
1220             if(terminal.line == null)
1221                 return false;
1222         THashSet<RouteLine> visited = new THashSet<RouteLine>();
1223         ArrayList<RouteLine> stack = new ArrayList<RouteLine>();
1224         int linkCount = 0;
1225         visited.add(lines.get(0));
1226         stack.add(lines.get(0));
1227         while(!stack.isEmpty()) {
1228             RouteLine cur = stack.remove(stack.size()-1);
1229             for(RouteLine n : cur.getPersistentNeighbors()) {
1230                 ++linkCount;
1231                 if(visited.add(n))
1232                     stack.add(n);
1233             }
1234         }
1235         return visited.size() == lines.size() && linkCount == 2*(lines.size()-1);
1236     }
1237
1238     /**
1239      * Returns if the connection is simple. A connection is simple, if it has just
1240      * two terminals connected together directly without (persistent) route lines.
1241      */
1242     public boolean isSimpleConnection() {
1243         return isSimpleConnection;
1244     }
1245
1246     public void replaceBy(RouteGraph rg) {
1247         this.lines = rg.lines;
1248         this.terminals = rg.terminals;
1249         this.transientLines = rg.transientLines;
1250         this.caseId = rg.caseId;
1251         this.isSimpleConnection = rg.isSimpleConnection;
1252         this.needsUpdate = rg.needsUpdate;
1253         rg.reset();
1254     }
1255
1256     private void reset() {
1257         lines = new ArrayList<RouteLine>();
1258         terminals = new ArrayList<RouteTerminal>();
1259         transientLines = new ArrayList<RouteLine>();
1260         caseId = 0;
1261         isSimpleConnection = false;
1262         needsUpdate = false;
1263     }
1264
1265     public Rectangle2D getBounds() {
1266         Rectangle2D bounds = new Rectangle2D.Double();
1267         getBounds(bounds);
1268         return bounds;
1269     }
1270
1271     public void getBounds(Rectangle2D bounds) {
1272         if(needsUpdate)
1273             update();
1274         double minX = Double.POSITIVE_INFINITY;
1275         double maxX = Double.NEGATIVE_INFINITY;
1276         double minY = Double.POSITIVE_INFINITY;
1277         double maxY = Double.NEGATIVE_INFINITY;
1278         for(RouteLine line : lines) {
1279             double position = line.position;
1280             if(line.isHorizontal) {
1281                 minY = Math.min(minY, position);
1282                 maxY = Math.max(maxY, position);
1283             }
1284             else {
1285                 minX = Math.min(minX, position);
1286                 maxX = Math.max(maxX, position);
1287             }
1288         }
1289         for(RouteLine line : transientLines) {
1290             double position = line.position;
1291             if(line.isHorizontal) {
1292                 minY = Math.min(minY, position);
1293                 maxY = Math.max(maxY, position);
1294             }
1295             else {
1296                 minX = Math.min(minX, position);
1297                 maxX = Math.max(maxX, position);
1298             }
1299         }
1300         for(RouteTerminal terminal : terminals) {
1301             double x = terminal.x;
1302             double y = terminal.y;
1303             minX = Math.min(minX, x);
1304             maxX = Math.max(maxX, x);
1305             minY = Math.min(minY, y);
1306             maxY = Math.max(maxY, y);
1307         }
1308         bounds.setFrame(minX, minY, maxX-minX, maxY-minY);
1309     }
1310
1311     private static void addPathBegin(Path2D path, RoutePoint cur, RouteLine line) {
1312         double x = cur.x, y = cur.y;
1313         if(cur instanceof RouteTerminal) {
1314             ILineEndStyle style = ((RouteTerminal)cur).getRenderStyle();
1315             if(line.isHorizontal()) {
1316                 if(cur == line.getBegin())
1317                     x += style.getLineEndLength(0);
1318                 else
1319                     x -= style.getLineEndLength(2);
1320             }
1321             else {
1322                 if(cur == line.getBegin())
1323                     y += style.getLineEndLength(1);
1324                 else
1325                     y -= style.getLineEndLength(3);
1326             }
1327         }
1328         path.moveTo(x, y);
1329     }
1330
1331     private static void addPathEnd(Path2D path, RoutePoint cur, RouteLine line) {
1332         double x = cur.x, y = cur.y;
1333         if(cur instanceof RouteTerminal) {
1334             ILineEndStyle style = ((RouteTerminal)cur).getRenderStyle();
1335             if(line.isHorizontal()) {
1336                 if(cur == line.getBegin())
1337                     x += style.getLineEndLength(0);
1338                 else
1339                     x -= style.getLineEndLength(2);
1340             }
1341             else {
1342                 if(cur == line.getBegin())
1343                     y += style.getLineEndLength(1);
1344                 else
1345                     y -= style.getLineEndLength(3);
1346             }
1347         }
1348         path.lineTo(x, y);
1349     }
1350
1351     public void getPath2D(Path2D path) {
1352         if(needsUpdate)
1353             update();
1354
1355         if(isSimpleConnection && transientLines.isEmpty()) {
1356             if(terminals.size() == 2) {
1357                 RouteTerminal a = terminals.get(0);
1358                 RouteTerminal b = terminals.get(1);
1359                 if(a.hasDirectConnection() || b.hasDirectConnection()) {
1360                     path.moveTo(a.x, a.y);
1361                     path.lineTo(b.x, b.y);
1362                     return;
1363                 }
1364             }
1365         }
1366
1367         // Analyze graph
1368         THashMap<RoutePoint, RouteLine> begins =
1369                 new THashMap<RoutePoint, RouteLine>();
1370         for(RouteLine line : lines) {
1371             add(begins, line);
1372         }
1373         for(RouteLine line : transientLines) {
1374             add(begins, line);
1375         }
1376         for(RouteTerminal terminal : terminals)
1377             if((terminal.getAllowedDirections() & 0x10)!=0 && terminal.line != null) {
1378                 begins.remove(terminal.line.getBegin());
1379                 drawContinuousPath(path, begins, terminal, terminal.line);
1380             }
1381
1382         // Create paths
1383         for(RoutePoint begin : begins.keySet().toArray(new RoutePoint[begins.size()])) {
1384             RouteLine curLine = begins.remove(begin);
1385             drawContinuousPath(path, begins, begin, curLine);
1386         }
1387     }
1388
1389     private void drawContinuousPath(Path2D path, THashMap<RoutePoint, RouteLine> begins,
1390             RoutePoint cur, RouteLine curLine) {
1391         if(curLine == null)
1392             return;
1393         addPathBegin(path, cur, curLine);
1394
1395         while(true) {
1396             if(cur != curLine.getEnd())
1397                 cur = curLine.getEnd();
1398             else
1399                 cur = curLine.getBegin();
1400             if(begins.remove(cur) != null || !(cur instanceof RouteLink)) {
1401                 addPathEnd(path, cur, curLine);
1402                 return;
1403             }
1404             if(cur instanceof RouteLink) {
1405                 if(!curLine.isDegenerated() ||
1406                         path.getCurrentPoint().getX() != cur.x ||
1407                         path.getCurrentPoint().getY() != cur.y)
1408                     path.lineTo(cur.x, cur.y);
1409                 RouteLink link = (RouteLink)cur;
1410                 if(link.a != curLine)
1411                     curLine = link.a;
1412                 else
1413                     curLine = link.b;
1414             }
1415         }
1416     }
1417
1418     private static void add(THashMap<RoutePoint, RouteLine> begins,
1419             RouteLine line) {
1420         if(line.points.size() > 1) {
1421             {
1422                 RoutePoint p = line.getBegin();
1423                 if(begins.remove(p) == null)
1424                     begins.put(p, line);
1425             }
1426             {
1427                 RoutePoint p = line.getEnd();
1428                 if(begins.remove(p) == null)
1429                     begins.put(p, line);
1430             }
1431         }
1432     }
1433
1434     public Collection<Segment> getSegments() {
1435         if (needsUpdate)
1436             update();
1437         ArrayList<Segment> segments = new ArrayList<Segment>();
1438         for(RouteLine routeLine : lines)
1439             routeLine.collectSegments(segments);
1440         for(RouteLine routeLine : transientLines)
1441             routeLine.collectSegments(segments);
1442         return segments;
1443     }
1444
1445     public Path2D getPath2D() {
1446         Path2D result = new Path2D.Double();
1447         getPath2D(result);
1448         return result;
1449     }
1450
1451     public SplittedRouteGraph splitGraph(RouteLine splitLine, double position) {
1452         THashSet<RouteNode> interfaceNodes1 = new THashSet<RouteNode>();
1453         THashSet<RouteLine> lines1 = new THashSet<RouteLine>();
1454         THashSet<RouteTerminal> terminals1 = new THashSet<RouteTerminal>();
1455         THashSet<RouteNode> interfaceNodes2 = new THashSet<RouteNode>();
1456         THashSet<RouteLine> lines2 = new THashSet<RouteLine>();
1457         THashSet<RouteTerminal> terminals2 = new THashSet<RouteTerminal>();
1458
1459         if(splitLine.isTransient()) {
1460             RouteTerminal terminal = splitLine.terminal;
1461
1462             if(splitLine.beginsWithTerminal()) {
1463                 lines2.addAll(getLines());
1464                 terminals2.addAll(getTerminals());
1465                 terminals1.add(terminal);
1466                 terminals2.remove(terminal);
1467                 interfaceNodes1.add(terminal);
1468                 if(isSimpleConnection())
1469                     interfaceNodes2.addAll(terminals2);
1470                 else
1471                     interfaceNodes2.add(terminal.line);
1472             }
1473             else {
1474                 lines1.addAll(getLines());
1475                 terminals1.addAll(getTerminals());
1476                 terminals2.add(terminal);
1477                 terminals1.remove(terminal);
1478                 interfaceNodes2.add(terminal);
1479                 if(isSimpleConnection())
1480                     interfaceNodes1.addAll(terminals1);
1481                 else
1482                     interfaceNodes1.add(terminal.line);
1483             }
1484         }
1485         else {
1486             for(RoutePoint rp : splitLine.getPoints()) {
1487                 double p = splitLine.isHorizontal ? rp.x : rp.y;
1488                 if(rp instanceof RouteLink) {
1489                     RouteLink link = (RouteLink)rp;
1490                     RouteLine otherLine = link.getA() != splitLine ? link.getA()
1491                             : link.getB();
1492                     if(otherLine.isTransient()) {
1493                         if(p < position) {
1494                             interfaceNodes1.add(otherLine.terminal);
1495                             terminals1.add(otherLine.terminal);
1496                         }
1497                         else {
1498                             interfaceNodes2.add(otherLine.terminal);
1499                             terminals2.add(otherLine.terminal);
1500                         }
1501                         continue;
1502                     }
1503
1504                     if(p < position) {
1505                         interfaceNodes1.add(otherLine);
1506                         traverseGraph(link, otherLine, lines1);
1507                     }
1508                     else {
1509                         interfaceNodes2.add(otherLine);
1510                         traverseGraph(link, otherLine, lines2);
1511                     }
1512                 }
1513             }
1514
1515             for(RouteTerminal terminal : getTerminals())
1516                 if(lines1.contains(terminal.line))
1517                     terminals1.add(terminal);
1518                 else if(lines2.contains(terminal.line))
1519                     terminals2.add(terminal);
1520         }
1521
1522         return new SplittedRouteGraph(splitLine,
1523                 interfaceNodes1, lines1, terminals1,
1524                 interfaceNodes2, lines2, terminals2);
1525     }
1526
1527     private void traverseGraph(RoutePoint previousPoint, RouteLine line,
1528             THashSet<RouteLine> lines) {
1529         if(lines.add(line)) {
1530             for(RoutePoint rp : line.getPoints()) {
1531                 if(rp != previousPoint && rp instanceof RouteLink) {
1532                     RouteLink link = (RouteLink)rp;
1533                     RouteLine otherLine = line != link.getA()
1534                             ? link.getA() : link.getB();
1535                     if(otherLine.isTransient())
1536                         continue;
1537                     traverseGraph(rp, otherLine, lines);
1538                 }
1539             }
1540         }
1541     }
1542
1543     public void reclaimTransientMemory() {
1544         removeTransientRouteLines();
1545         needsUpdate = true;
1546     }
1547
1548 }