bundles/org.simantics.g2d/src/org/simantics/g2d/routing/algorithm1/StopSet.java

   1 /*******************************************************************************\r
   2  * Copyright (c) 2007, 2010 Association for Decentralized Information Management\r
   3  * in 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.g2d.routing.algorithm1;\r
  13 \r
  14 import gnu.trove.list.array.TIntArrayList;\r
  15 \r
  16 import java.util.Arrays;\r
  17 import java.util.Collection;\r
  18 import java.util.Comparator;\r
  19 \r
  20 public class StopSet {\r
  21         public static class Line {\r
  22                 /**\r
  23                  * The size of xs is even. The array is strictly ordered. \r
  24                  * For all n, (xs[2n], xs[2n+1]) is an obstacle. \r
  25                  */\r
  26                 double[] xs;\r
  27                 public double y;\r
  28                 \r
  29                 /* Following tables are indexed by intervals 0..xs.length such that\r
  30                    interval i is (xs[i-1],xs[i]), where xs[-1] = -INFINITY and\r
  31                    xs[xs.length] = INFINITY \r
  32                  */\r
  33                 /**\r
  34                  * Penalty of crossing the stop (null, if no penalty) \r
  35                  */\r
  36                 public Penalty[] penalty;\r
  37                 /**\r
  38                  * Next line of stop with positive penalty\r
  39                  */\r
  40                 Line[] nextLine; \r
  41                 /**\r
  42                  * Index of the first interval in the nextLine[i] \r
  43                  * that blocks fronts from this interval.\r
  44                  */\r
  45                 int[] nextPosition;  \r
  46                 \r
  47                 public Line(double[] xs, double y, Penalty[] penalty, Line[] nextLine, int[] nextPosition) {\r
  48                         this.xs = xs;\r
  49                         this.y = y;\r
  50                         this.penalty = penalty;\r
  51                         this.nextLine = nextLine;\r
  52                         this.nextPosition = nextPosition;\r
  53                 }                       \r
  54         }\r
  55         \r
  56         Line[] lines;\r
  57         \r
  58         public static class Stop {\r
  59                 double x0, x1;\r
  60                 double y;\r
  61                 Penalty penalty;\r
  62                 \r
  63                 public Stop(Penalty penalty, double x0, double x1, double y) {\r
  64                         this.penalty = penalty;\r
  65                         this.x0 = x0;\r
  66                         this.x1 = x1;\r
  67                         this.y = y;\r
  68                 }               \r
  69         }\r
  70 \r
  71         public static final Comparator<Stop> stopComparator = new Comparator<Stop>() {\r
  72 \r
  73                 @Override\r
  74                 public int compare(Stop o1, Stop o2) {\r
  75                         if(o1.y < o2.y)\r
  76                                 return -1;\r
  77                         else if(o1.y > o2.y)\r
  78                                 return 1;\r
  79                         else if(o1.x0 < o2.x0)\r
  80                                 return -1;\r
  81                         else if(o1.x0 > o2.x0)\r
  82                                 return 1;\r
  83                         else\r
  84                                 return 0;\r
  85                 }\r
  86                 \r
  87         };\r
  88         \r
  89         public StopSet(Collection<Stop> _stops) {\r
  90                 if(_stops.isEmpty())\r
  91                         return;\r
  92                 Stop[] stops = _stops.toArray(new Stop[_stops.size()]);\r
  93                 Arrays.sort(stops, stopComparator);\r
  94                 \r
  95                 TIntArrayList lineBegins = new TIntArrayList();\r
  96                 lineBegins.add(0);\r
  97                 for(int i=1;i<stops.length;++i)\r
  98                         if(stops[i-1].y < stops[i].y)\r
  99                                 lineBegins.add(i);\r
 100                 \r
 101                 lines = new Line[lineBegins.size()];\r
 102                 Line prev = null;\r
 103                 int from = stops.length;\r
 104                 for(int i=lineBegins.size()-1;i>=0;--i) {\r
 105                         int to = from;\r
 106                         from = lineBegins.get(i);\r
 107                         \r
 108                         // Calculate xs and penalty\r
 109                         \r
 110                         double[] xs = new double[(to-from)*2];\r
 111                         Penalty[] penalty = new Penalty[(to-from)*2+1];\r
 112                         int pointCount = 0;\r
 113                         for(int j=from;j<to;++j) {\r
 114                                 Stop stop = stops[j];\r
 115                                 if(pointCount == 0 || xs[pointCount-1] < stop.x0) {\r
 116                                         penalty[pointCount] = null;\r
 117                                         xs[pointCount++] = stop.x0;\r
 118                                         penalty[pointCount] = stop.penalty;\r
 119                                         xs[pointCount++] = stop.x1;                                     \r
 120                                 }\r
 121                                 else if(stop.penalty.equals(penalty[pointCount-1])) {\r
 122                                         if(stop.x1 > xs[pointCount-1])\r
 123                                                 xs[pointCount-1] = stop.x1;\r
 124                                 }\r
 125                                 else {\r
 126                                         if(stop.x0 == xs[pointCount-1]) {\r
 127                                                 penalty[pointCount] = stop.penalty;\r
 128                                                 xs[pointCount++] = stop.x1;\r
 129                                         }\r
 130                                         else if(stop.x1 > xs[pointCount-1]) {\r
 131                                                 if(stop.penalty.penalty > penalty[pointCount-1].penalty) {\r
 132                                                         if(xs[pointCount-2] == stop.x0)\r
 133                                                                 --pointCount;\r
 134                                                         else\r
 135                                                                 xs[pointCount-1] = stop.x0;\r
 136                                                 }\r
 137                                                 penalty[pointCount] = stop.penalty;\r
 138                                                 xs[pointCount++] = stop.x1;\r
 139                                         }\r
 140                                         else if(stop.penalty.penalty > penalty[pointCount-1].penalty) {\r
 141                                                 // FIXME Not correct if more than two intersecting stops                                                \r
 142                                         }\r
 143                                 }\r
 144                         }\r
 145                         penalty[pointCount] = null;\r
 146                         if(pointCount < xs.length) {\r
 147                                 xs = Arrays.copyOf(xs, pointCount);\r
 148                                 penalty = Arrays.copyOf(penalty, pointCount+1);\r
 149                         }\r
 150                         \r
 151                         // Calculate nextLine and nextPosition\r
 152                         \r
 153                         Line[] nextLine = new Line[pointCount + 1];\r
 154                         int[] nextPosition = new int[pointCount + 1];\r
 155                         if(prev != null) {\r
 156                                 int prevI = 0;\r
 157                                 double[] prevXs = prev.xs;\r
 158                                 for(int j=0;j<=pointCount;++j) {\r
 159                                         double min = j==0 ? Double.NEGATIVE_INFINITY : xs[j-1];\r
 160                                         double max = j==pointCount ? Double.POSITIVE_INFINITY : xs[j];\r
 161                                         \r
 162                                         while(prevI < prevXs.length && prevXs[prevI] <= min)\r
 163                                                 ++prevI;\r
 164                                         \r
 165                                         Line prev2 = prev;\r
 166                                         int prevI2 = prevI;\r
 167                                         double[] prevXs2 = prevXs;\r
 168                                         while(prev2.penalty[prevI2]==null && (prevI2==prevXs2.length || prevXs2[prevI2] >= max)) {\r
 169                                                 int temp = prev2.nextPosition[prevI2];\r
 170                                                 prev2 = prev2.nextLine[prevI2];\r
 171                                                 if(prev2 == null)\r
 172                                                         break;\r
 173                                                 prevI2 = temp;\r
 174                                                 prevXs2 = prev2.xs;             \r
 175                                                 while(prevI2 < prevXs2.length && prevXs2[prevI2] <= min)\r
 176                                                         ++prevI2;\r
 177                                         }\r
 178                                         nextLine[j] = prev2;\r
 179                                         nextPosition[j] = prevI2;                                       \r
 180                                 }\r
 181                         }\r
 182                         lines[i] = prev = new Line(xs, stops[from].y, penalty, nextLine, nextPosition); \r
 183                 }\r
 184         }\r
 185         \r
 186         public static interface IStopProcedure {\r
 187                 void blockEnd(double y);\r
 188                 void continuation(double min, double max, int pos, Line line);\r
 189         }\r
 190         \r
 191         public void findStops(double min, double max, double y, IStopProcedure proc) {\r
 192                 if(lines == null) {\r
 193                         proc.blockEnd(Double.POSITIVE_INFINITY);\r
 194                         return;\r
 195                 }\r
 196                 int minJ = -1;\r
 197                 int maxJ = lines.length;\r
 198                 while(maxJ > minJ+1) {\r
 199                         int middleJ = (minJ+maxJ) >>> 1;\r
 200                         double middleY = lines[middleJ].y;\r
 201                         if(middleY < y)\r
 202                                 minJ = middleJ;\r
 203                         else if(middleY > y)\r
 204                                 maxJ = middleJ;\r
 205                         else {\r
 206                                 minJ = maxJ = middleJ;\r
 207                                 break;\r
 208                         }\r
 209                 }\r
 210                 \r
 211                 if(maxJ == lines.length)\r
 212                         proc.blockEnd(Double.POSITIVE_INFINITY);\r
 213                 else {\r
 214                         double[] xs = lines[maxJ].xs;\r
 215                         int minI = -1;\r
 216                         int maxI = xs.length;\r
 217                         while(maxI > minI+1) {\r
 218                                 int middleI = (minI+maxI) >>> 1;\r
 219                                 double middleX = xs[middleI];\r
 220                                 if(middleX < min)\r
 221                                         minI = middleI;\r
 222                                 else if(middleX > min)\r
 223                                         maxI = middleI;\r
 224                                 else {\r
 225                                         minI = maxI = middleI;\r
 226                                 }\r
 227                         }\r
 228                         findStops(maxI, lines[maxJ], min, max, y, proc);\r
 229                 }\r
 230                 \r
 231         }\r
 232         \r
 233         static private void findStops(int pos, Line line, double min, double max, double y, IStopProcedure proc) {\r
 234                 double[] xs = line.xs;\r
 235                 while(line.penalty[pos]==null && (pos==xs.length || xs[pos] >= max)) {\r
 236                         int temp = line.nextPosition[pos];\r
 237                         line = line.nextLine[pos];\r
 238                         if(line == null)\r
 239                                 break;\r
 240                         xs = line.xs;                   \r
 241                         pos = temp;\r
 242                         while(pos < xs.length && xs[pos] <= min)\r
 243                                 ++pos;\r
 244                 }\r
 245                 if(line == null)\r
 246                         proc.blockEnd(Double.POSITIVE_INFINITY);\r
 247                 else {\r
 248                         if(line.y > y)\r
 249                                 proc.blockEnd(line.y);\r
 250                         if(pos==xs.length || xs[pos] >= max)\r
 251                                 proc.continuation(min, max, pos, line);\r
 252                         else {\r
 253                                 proc.continuation(min, xs[pos], pos, line);\r
 254                                 while(pos+1 < xs.length && xs[pos+1] < max) {\r
 255                                         ++pos;\r
 256                                         proc.continuation(xs[pos-1], xs[pos], pos, line);\r
 257                                 }\r
 258                                 proc.continuation(xs[pos], max, pos+1, line);\r
 259                         }\r
 260                 }\r
 261         }\r
 262         \r
 263         static public void continueStop(final int pos, final Line line, double min, double max, IStopProcedure proc) {\r
 264                 Line newLine = line.nextLine[pos];\r
 265                 if(newLine == null)\r
 266                         proc.blockEnd(Double.POSITIVE_INFINITY);\r
 267                 else {\r
 268                         int newPos = line.nextPosition[pos];\r
 269                         double[] xs = newLine.xs;\r
 270                         while(newPos < xs.length && xs[newPos] <= min)\r
 271                                 ++newPos;\r
 272                         findStops(newPos, newLine, min, max, line.y, proc);             \r
 273                 }\r
 274         }\r
 275 \r
 276 }\r