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
10 * VTT Technical Research Centre of Finland - initial API and implementation
\r
11 *******************************************************************************/
\r
12 package org.simantics.g2d.routing.algorithm1;
\r
14 import gnu.trove.list.array.TIntArrayList;
\r
16 import java.util.Arrays;
\r
17 import java.util.Collection;
\r
18 import java.util.Comparator;
\r
20 public class StopSet {
\r
21 public static class Line {
\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
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
34 * Penalty of crossing the stop (null, if no penalty)
\r
36 public Penalty[] penalty;
\r
38 * Next line of stop with positive penalty
\r
42 * Index of the first interval in the nextLine[i]
\r
43 * that blocks fronts from this interval.
\r
45 int[] nextPosition;
\r
47 public Line(double[] xs, double y, Penalty[] penalty, Line[] nextLine, int[] nextPosition) {
\r
50 this.penalty = penalty;
\r
51 this.nextLine = nextLine;
\r
52 this.nextPosition = nextPosition;
\r
58 public static class Stop {
\r
63 public Stop(Penalty penalty, double x0, double x1, double y) {
\r
64 this.penalty = penalty;
\r
71 public static final Comparator<Stop> stopComparator = new Comparator<Stop>() {
\r
74 public int compare(Stop o1, Stop o2) {
\r
77 else if(o1.y > o2.y)
\r
79 else if(o1.x0 < o2.x0)
\r
81 else if(o1.x0 > o2.x0)
\r
89 public StopSet(Collection<Stop> _stops) {
\r
90 if(_stops.isEmpty())
\r
92 Stop[] stops = _stops.toArray(new Stop[_stops.size()]);
\r
93 Arrays.sort(stops, stopComparator);
\r
95 TIntArrayList lineBegins = new TIntArrayList();
\r
97 for(int i=1;i<stops.length;++i)
\r
98 if(stops[i-1].y < stops[i].y)
\r
101 lines = new Line[lineBegins.size()];
\r
103 int from = stops.length;
\r
104 for(int i=lineBegins.size()-1;i>=0;--i) {
\r
106 from = lineBegins.get(i);
\r
108 // Calculate xs and penalty
\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
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
126 if(stop.x0 == xs[pointCount-1]) {
\r
127 penalty[pointCount] = stop.penalty;
\r
128 xs[pointCount++] = stop.x1;
\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
135 xs[pointCount-1] = stop.x0;
\r
137 penalty[pointCount] = stop.penalty;
\r
138 xs[pointCount++] = stop.x1;
\r
140 else if(stop.penalty.penalty > penalty[pointCount-1].penalty) {
\r
141 // FIXME Not correct if more than two intersecting stops
\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
151 // Calculate nextLine and nextPosition
\r
153 Line[] nextLine = new Line[pointCount + 1];
\r
154 int[] nextPosition = new int[pointCount + 1];
\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
162 while(prevI < prevXs.length && prevXs[prevI] <= min)
\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
174 prevXs2 = prev2.xs;
\r
175 while(prevI2 < prevXs2.length && prevXs2[prevI2] <= min)
\r
178 nextLine[j] = prev2;
\r
179 nextPosition[j] = prevI2;
\r
182 lines[i] = prev = new Line(xs, stops[from].y, penalty, nextLine, nextPosition);
\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
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
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
203 else if(middleY > y)
\r
206 minJ = maxJ = middleJ;
\r
211 if(maxJ == lines.length)
\r
212 proc.blockEnd(Double.POSITIVE_INFINITY);
\r
214 double[] xs = lines[maxJ].xs;
\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
222 else if(middleX > min)
\r
225 minI = maxI = middleI;
\r
228 findStops(maxI, lines[maxJ], min, max, y, proc);
\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
242 while(pos < xs.length && xs[pos] <= min)
\r
246 proc.blockEnd(Double.POSITIVE_INFINITY);
\r
249 proc.blockEnd(line.y);
\r
250 if(pos==xs.length || xs[pos] >= max)
\r
251 proc.continuation(min, max, pos, line);
\r
253 proc.continuation(min, xs[pos], pos, line);
\r
254 while(pos+1 < xs.length && xs[pos+1] < max) {
\r
256 proc.continuation(xs[pos-1], xs[pos], pos, line);
\r
258 proc.continuation(xs[pos], max, pos+1, line);
\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
268 int newPos = line.nextPosition[pos];
\r
269 double[] xs = newLine.xs;
\r
270 while(newPos < xs.length && xs[newPos] <= min)
\r
272 findStops(newPos, newLine, min, max, line.y, proc);
\r