Mercurial > dive4elements > river

comparison flys-artifacts/src/main/java/org/dive4elements/river/artifacts/model/QRangeTree.java @ 5831:bd047b71ab37

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Repaired internal references
author Sascha L. Teichmann <teichmann@intevation.de>
date Thu, 25 Apr 2013 12:06:39 +0200
parents flys-artifacts/src/main/java/de/intevation/flys/artifacts/model/QRangeTree.java@f4fd64a4d502
children
comparison
equal deleted inserted replaced
5830:160f53ee0870 5831:bd047b71ab37
1 package org.dive4elements.river.artifacts.model;
2
3 import java.io.Serializable;
4
5 import java.util.List;
6 import java.util.ArrayList;
7
8 import org.apache.log4j.Logger;
9
10 public class QRangeTree
11 implements Serializable
12 {
13 private static Logger log = Logger.getLogger(QRangeTree.class);
14
15 public static final double EPSILON = 1e-4;
16
17 public static class Node
18 implements Serializable
19 {
20 Node left;
21 Node right;
22 Node prev;
23 Node next;
24
25 double a;
26 double b;
27 double q;
28
29 public Node() {
30 }
31
32 public Node(double a, double b, double q) {
33 this.a = a;
34 this.b = b;
35 this.q = q;
36 }
37
38 protected final double interpolatePrev(double pos) {
39 /*
40 f(prev.b) = prev.q
41 f(a) = q
42
43 prev.q = m*prev.b + n
44 q = m*a + n <=> n = q - m*a
45
46 q - prev.q = m*(a - prev.b)
47
48 m = (q - prev.q)/(a - prev.b) # a != prev.b
49 */
50
51 if (a == prev.b) {
52 return 0.5*(q + prev.q);
53 }
54 double m = (q - prev.q)/(a - prev.b);
55 double n = q - m*a;
56 return m*pos + n;
57 }
58
59 protected final double interpolateNext(double pos) {
60 /*
61 f(next.a) = next.q
62 f(b) = q
63
64 next.q = m*next.a + n
65 q = m*b + n <=> n = q - m*b
66
67 q - next.q = m*(b - next.a)
68 m = (q - next.q)/(b - next.a) # b != next.a
69 */
70
71 if (b == next.a) {
72 return 0.5*(q + next.q);
73 }
74 double m = (q - next.q)/(b - next.a);
75 double n = q - m*b;
76 return m*pos + n;
77 }
78
79 public double findQ(double pos) {
80
81 Node current = this;
82 for (;;) {
83 if (pos < current.a) {
84 if (current.left != null) {
85 current = current.left;
86 continue;
87 }
88 return current.prev != null
89 ? current.interpolatePrev(pos)
90 : Double.NaN;
91 }
92 if (pos > current.b) {
93 if (current.right != null) {
94 current = current.right;
95 continue;
96 }
97 return current.next != null
98 ? current.interpolateNext(pos)
99 : Double.NaN;
100 }
101 return current.q;
102 }
103 }
104
105 public Node findNode(double pos) {
106 Node current = this;
107 while (current != null) {
108 if (pos < current.a) {
109 current = current.left;
110 }
111 else if (pos > current.b) {
112 current = current.right;
113 }
114 return current;
115 }
116 return null;
117 }
118
119 public boolean contains(double c) {
120 return c >= a && c <= b;
121 }
122 } // class Node
123
124 /** Class to cache the last found tree leaf in a search for Q.
125 * Its likely that a neighbored pos search
126 * results in using the same leaf node. So
127 * caching this leaf will minimize expensive
128 * tree traversals.
129 * Modeled as inner class because the QRangeTree
130 * itself is a shared data structure.
131 * Using this class omits interpolation between
132 * leaves.
133 */
134 public final class QuickQFinder {
135
136 private Node last;
137
138 public QuickQFinder() {
139 }
140
141 public double findQ(double pos) {
142 if (last != null && last.contains(pos)) {
143 return last.q;
144 }
145 last = QRangeTree.this.findNode(pos);
146 return last != null ? last.q : Double.NaN;
147 }
148
149 public double [] findQs(double [] kms, Calculation report) {
150 return findQs(kms, new double[kms.length], report);
151 }
152
153 public double [] findQs(
154 double [] kms,
155 double [] qs,
156 Calculation report
157 ) {
158 for (int i = 0; i < kms.length; ++i) {
159 if (Double.isNaN(qs[i] = findQ(kms[i]))) {
160 report.addProblem(kms[i], "cannot.find.q");
161 }
162 }
163 return qs;
164 }
165 } // class QuickQFinder
166
167 protected Node root;
168
169 public QRangeTree() {
170 }
171
172 public static final class AccessQAB {
173 private int startIndex;
174
175 public AccessQAB(int startIndex) {
176 this.startIndex = startIndex;
177 }
178
179 public Double getQ(Object [] row) {
180 return (Double)row[startIndex];
181 }
182
183 public Double getA(Object [] row) {
184 return (Double)row[startIndex+1];
185 }
186
187 public Double getB(Object [] row) {
188 return (Double)row[startIndex+2];
189 }
190 }
191
192 public static final AccessQAB WITH_COLUMN = new AccessQAB(1);
193 public static final AccessQAB WITHOUT_COLUMN = new AccessQAB(0);
194
195 /** wstQRanges need to be sorted by range.a */
196 public QRangeTree(List<Object []> qRanges, int start, int stop) {
197 this(qRanges, WITH_COLUMN, start, stop);
198 }
199
200 public QRangeTree(
201 List<Object []> qRanges,
202 AccessQAB accessQAB,
203 int start,
204 int stop
205 ) {
206 if (stop <= start) {
207 return;
208 }
209
210 int N = stop-start;
211
212 List<Node> nodes = new ArrayList<Node>(N);
213
214 Node last = null;
215
216 for (int i = 0; i < N; ++i) {
217 Object [] qRange = qRanges.get(start + i);
218 Double q = accessQAB.getQ(qRange);
219 Double a = accessQAB.getA(qRange);
220 Double b = accessQAB.getB(qRange);
221
222 double av = a != null ? a.doubleValue() : -Double.MAX_VALUE;
223 double bv = b != null ? b.doubleValue() : Double.MAX_VALUE;
224 double qv = q.doubleValue();
225
226 // If nodes are directly neighbored and Qs are the same
227 // join them.
228 if (last != null
229 && Math.abs(last.b - av) < EPSILON
230 && Math.abs(last.q - qv) < EPSILON) {
231 last.b = bv;
232 }
233 else {
234 nodes.add(last = new Node(av, bv, qv));
235 }
236 }
237
238 if (log.isDebugEnabled()) {
239 log.debug("Before/after nodes join: " +
240 N + "/" + nodes.size());
241 }
242
243 root = wireTree(nodes);
244 }
245
246 protected static Node wireTree(List<Node> nodes) {
247 int N = nodes.size();
248 for (int i = 0; i < N; ++i) {
249 Node node = nodes.get(i);
250 if (i > 0 ) node.prev = nodes.get(i-1);
251 if (i < N-1) node.next = nodes.get(i+1);
252 }
253
254 return buildTree(nodes, 0, N-1);
255 }
256
257 protected static Node buildTree(List<Node> nodes, int lo, int hi) {
258
259 if (lo > hi) {
260 return null;
261 }
262
263 int mid = (lo + hi) >> 1;
264 Node parent = nodes.get(mid);
265
266 parent.left = buildTree(nodes, lo, mid-1);
267 parent.right = buildTree(nodes, mid+1, hi);
268
269 return parent;
270 }
271
272 public double averageQ() {
273 double sum = 0d;
274 int n = 0;
275 for (Node node = head(); node != null; node = node.next) {
276 sum += node.q;
277 ++n;
278 }
279 return sum/n;
280 }
281
282 public double maxQ() {
283 double max = -Double.MAX_VALUE;
284 for (Node node = head(); node != null; node = node.next) {
285 if (node.q > max) {
286 max = node.q;
287 }
288 }
289 return max;
290 }
291
292 public double findQ(double pos) {
293 return root != null ? root.findQ(pos) : Double.NaN;
294 }
295
296 public Node findNode(double pos) {
297 return root != null ? root.findNode(pos) : null;
298 }
299
300 protected Node head() {
301 Node head = root;
302 while (head.left != null) {
303 head = head.left;
304 }
305 return head;
306 }
307
308 public boolean intersectsQRange(double qMin, double qMax) {
309 if (qMin > qMax) {
310 double t = qMin;
311 qMin = qMax;
312 qMax = t;
313 }
314 for (Node curr = head(); curr != null; curr = curr.next) {
315 if (curr.q >= qMin || curr.q <= qMax) {
316 return true;
317 }
318 }
319 return false;
320 }
321
322 public List<Range> findSegments(double a, double b) {
323 if (a > b) { double t = a; a = b; b = t; }
324 return findSegments(new Range(a, b));
325 }
326
327 public List<Range> findSegments(Range range) {
328 List<Range> segments = new ArrayList<Range>();
329
330 // Linear scan should be good enough here.
331 for (Node curr = head(); curr != null; curr = curr.next) {
332 if (!range.disjoint(curr.a, curr.b)) {
333 Range r = new Range(curr.a, curr.b);
334 if (r.clip(range)) {
335 segments.add(r);
336 }
337 }
338 }
339
340 return segments;
341 }
342
343 @Override
344 public String toString() {
345 StringBuilder sb = new StringBuilder();
346 inorder(root, sb);
347 return sb.toString();
348 }
349
350 protected static void inorder(Node node, StringBuilder sb) {
351 if (node != null) {
352 inorder(node.left, sb);
353 sb.append('[')
354 .append(node.a)
355 .append(", ")
356 .append(node.b)
357 .append(": ")
358 .append(node.q)
359 .append(']');
360 inorder(node.right, sb);
361 }
362 }
363
364 private static final String name(Object o) {
365 return String.valueOf(System.identityHashCode(o) & 0xffffffffL);
366 }
367
368 public String toGraph() {
369 StringBuilder sb = new StringBuilder();
370 sb.append("subgraph c");
371 sb.append(name(this));
372 sb.append(" {\n");
373 if (root != null) {
374 java.util.Deque<Node> stack = new java.util.ArrayDeque<Node>();
375 stack.push(root);
376 while (!stack.isEmpty()) {
377 Node current = stack.pop();
378 String name = "n" + name(current);
379 sb.append(name);
380 sb.append(" [label=\"");
381 sb.append(current.a).append(", ").append(current.b);
382 sb.append(": ").append(current.q).append("\"]\n");
383 if (current.left != null) {
384 String leftName = name(current.left);
385 sb.append(name).append(" -- n").append(leftName).append("\n");
386 stack.push(current.left);
387 }
388 if (current.right != null) {
389 String rightName = name(current.right);
390 sb.append(name).append(" -- n").append(rightName).append("\n");
391 stack.push(current.right);
392 }
393 }
394 }
395 sb.append("}\n");
396 return sb.toString();
397 }
398 }
399 // vim:set ts=4 sw=4 si et sta sts=4 fenc=utf8 :
http://dive4elements.wald.intevation.org