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

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