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