Mercurial > dive4elements > river

annotate artifacts/src/main/java/org/dive4elements/river/artifacts/model/QRangeTree.java @ 5863:4897a58c8746

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
River artifacts: Added new copyright headers.
author Sascha L. Teichmann <teichmann@intevation.de>
date Sun, 28 Apr 2013 14:40:59 +0200
parents 5aa05a7a34b7
children af13ceeba52a
rev   line source
5863
4897a58c8746 River artifacts: Added new copyright headers.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 5838
diff changeset
1 /* Copyright (C) 2011, 2012, 2013 by Bundesanstalt für Gewässerkunde
4897a58c8746 River artifacts: Added new copyright headers.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 5838
diff changeset
2 * Software engineering by Intevation GmbH
4897a58c8746 River artifacts: Added new copyright headers.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 5838
diff changeset
3 *
4897a58c8746 River artifacts: Added new copyright headers.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 5838
diff changeset
4 * This file is Free Software under the GNU AGPL (>=v3)
4897a58c8746 River artifacts: Added new copyright headers.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 5838
diff changeset
5 * and comes with ABSOLUTELY NO WARRANTY! Check out the
4897a58c8746 River artifacts: Added new copyright headers.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 5838
diff changeset
6 * documentation coming with Dive4Elements River for details.
4897a58c8746 River artifacts: Added new copyright headers.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 5838
diff changeset
7 */
4897a58c8746 River artifacts: Added new copyright headers.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 5838
diff changeset
8
5831
bd047b71ab37 Repaired internal references
Sascha L. Teichmann <teichmann@intevation.de>
parents: 5423
diff changeset
9 package org.dive4elements.river.artifacts.model;
625
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
10
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
11 import java.io.Serializable;
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
12
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
13 import java.util.List;
2611
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2609
diff changeset
14 import java.util.ArrayList;
625
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
15
633
d08f77e7f7e8 WST value table: Qs are now stored in ranges for each column.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 632
diff changeset
16 import org.apache.log4j.Logger;
625
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
17
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
18 public class QRangeTree
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
19 implements Serializable
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
20 {
633
d08f77e7f7e8 WST value table: Qs are now stored in ranges for each column.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 632
diff changeset
21 private static Logger log = Logger.getLogger(QRangeTree.class);
d08f77e7f7e8 WST value table: Qs are now stored in ranges for each column.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 632
diff changeset
22
2611
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2609
diff changeset
23 public static final double EPSILON = 1e-4;
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2609
diff changeset
24
625
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
25 public static class Node
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
26 implements Serializable
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
27 {
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
28 Node left;
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
29 Node right;
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
30 Node prev;
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
31 Node next;
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
32
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
33 double a;
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
34 double b;
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
35 double q;
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
36
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
37 public Node() {
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
38 }
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
39
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
40 public Node(double a, double b, double q) {
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
41 this.a = a;
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
42 this.b = b;
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
43 this.q = q;
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
44 }
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
45
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
46 protected final double interpolatePrev(double pos) {
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
47 /*
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
48 f(prev.b) = prev.q
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
49 f(a) = q
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
50
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
51 prev.q = m*prev.b + n
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
52 q = m*a + n <=> n = q - m*a
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
53
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
54 q - prev.q = m*(a - prev.b)
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
55
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
56 m = (q - prev.q)/(a - prev.b) # a != prev.b
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
57 */
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
58
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
59 if (a == prev.b) {
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
60 return 0.5*(q + prev.q);
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
61 }
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
62 double m = (q - prev.q)/(a - prev.b);
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
63 double n = q - m*a;
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
64 return m*pos + n;
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
65 }
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
66
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
67 protected final double interpolateNext(double pos) {
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
68 /*
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
69 f(next.a) = next.q
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
70 f(b) = q
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
71
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
72 next.q = m*next.a + n
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
73 q = m*b + n <=> n = q - m*b
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
74
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
75 q - next.q = m*(b - next.a)
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
76 m = (q - next.q)/(b - next.a) # b != next.a
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
77 */
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
78
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
79 if (b == next.a) {
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
80 return 0.5*(q + next.q);
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
81 }
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
82 double m = (q - next.q)/(b - next.a);
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
83 double n = q - m*b;
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
84 return m*pos + n;
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
85 }
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
86
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
87 public double findQ(double pos) {
633
d08f77e7f7e8 WST value table: Qs are now stored in ranges for each column.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 632
diff changeset
88
625
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
89 Node current = this;
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
90 for (;;) {
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
91 if (pos < current.a) {
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
92 if (current.left != null) {
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
93 current = current.left;
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
94 continue;
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
95 }
633
d08f77e7f7e8 WST value table: Qs are now stored in ranges for each column.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 632
diff changeset
96 return current.prev != null
625
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
97 ? current.interpolatePrev(pos)
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
98 : Double.NaN;
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
99 }
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
100 if (pos > current.b) {
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
101 if (current.right != null) {
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
102 current = current.right;
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
103 continue;
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
104 }
633
d08f77e7f7e8 WST value table: Qs are now stored in ranges for each column.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 632
diff changeset
105 return current.next != null
625
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
106 ? current.interpolateNext(pos)
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
107 : Double.NaN;
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
108 }
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
109 return current.q;
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
110 }
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
111 }
4797
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4796
diff changeset
112
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4796
diff changeset
113 public Node findNode(double pos) {
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4796
diff changeset
114 Node current = this;
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4796
diff changeset
115 while (current != null) {
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4796
diff changeset
116 if (pos < current.a) {
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4796
diff changeset
117 current = current.left;
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4796
diff changeset
118 }
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4796
diff changeset
119 else if (pos > current.b) {
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4796
diff changeset
120 current = current.right;
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4796
diff changeset
121 }
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4796
diff changeset
122 return current;
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4796
diff changeset
123 }
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4796
diff changeset
124 return null;
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4796
diff changeset
125 }
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4796
diff changeset
126
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4796
diff changeset
127 public boolean contains(double c) {
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4796
diff changeset
128 return c >= a && c <= b;
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4796
diff changeset
129 }
625
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
130 } // class Node
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
131
4797
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4796
diff changeset
132 /** Class to cache the last found tree leaf in a search for Q.
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4796
diff changeset
133 * Its likely that a neighbored pos search
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4796
diff changeset
134 * results in using the same leaf node. So
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4796
diff changeset
135 * caching this leaf will minimize expensive
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4796
diff changeset
136 * tree traversals.
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4796
diff changeset
137 * Modeled as inner class because the QRangeTree
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4796
diff changeset
138 * itself is a shared data structure.
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4796
diff changeset
139 * Using this class omits interpolation between
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4796
diff changeset
140 * leaves.
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4796
diff changeset
141 */
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4796
diff changeset
142 public final class QuickQFinder {
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4796
diff changeset
143
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4796
diff changeset
144 private Node last;
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4796
diff changeset
145
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4796
diff changeset
146 public QuickQFinder() {
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4796
diff changeset
147 }
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4796
diff changeset
148
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4796
diff changeset
149 public double findQ(double pos) {
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4796
diff changeset
150 if (last != null && last.contains(pos)) {
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4796
diff changeset
151 return last.q;
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4796
diff changeset
152 }
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4796
diff changeset
153 last = QRangeTree.this.findNode(pos);
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4796
diff changeset
154 return last != null ? last.q : Double.NaN;
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4796
diff changeset
155 }
4821
bcf25d8c183e Moved NaN removal code from W to DoubleUtil. Create QKms when calculating the 'Umhuellende'.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4797
diff changeset
156
bcf25d8c183e Moved NaN removal code from W to DoubleUtil. Create QKms when calculating the 'Umhuellende'.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4797
diff changeset
157 public double [] findQs(double [] kms, Calculation report) {
bcf25d8c183e Moved NaN removal code from W to DoubleUtil. Create QKms when calculating the 'Umhuellende'.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4797
diff changeset
158 return findQs(kms, new double[kms.length], report);
bcf25d8c183e Moved NaN removal code from W to DoubleUtil. Create QKms when calculating the 'Umhuellende'.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4797
diff changeset
159 }
bcf25d8c183e Moved NaN removal code from W to DoubleUtil. Create QKms when calculating the 'Umhuellende'.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4797
diff changeset
160
bcf25d8c183e Moved NaN removal code from W to DoubleUtil. Create QKms when calculating the 'Umhuellende'.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4797
diff changeset
161 public double [] findQs(
5282
14db045d6368 Removed trailing whitespace.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4821
diff changeset
162 double [] kms,
14db045d6368 Removed trailing whitespace.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4821
diff changeset
163 double [] qs,
4821
bcf25d8c183e Moved NaN removal code from W to DoubleUtil. Create QKms when calculating the 'Umhuellende'.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4797
diff changeset
164 Calculation report
bcf25d8c183e Moved NaN removal code from W to DoubleUtil. Create QKms when calculating the 'Umhuellende'.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4797
diff changeset
165 ) {
bcf25d8c183e Moved NaN removal code from W to DoubleUtil. Create QKms when calculating the 'Umhuellende'.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4797
diff changeset
166 for (int i = 0; i < kms.length; ++i) {
bcf25d8c183e Moved NaN removal code from W to DoubleUtil. Create QKms when calculating the 'Umhuellende'.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4797
diff changeset
167 if (Double.isNaN(qs[i] = findQ(kms[i]))) {
bcf25d8c183e Moved NaN removal code from W to DoubleUtil. Create QKms when calculating the 'Umhuellende'.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4797
diff changeset
168 report.addProblem(kms[i], "cannot.find.q");
bcf25d8c183e Moved NaN removal code from W to DoubleUtil. Create QKms when calculating the 'Umhuellende'.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4797
diff changeset
169 }
bcf25d8c183e Moved NaN removal code from W to DoubleUtil. Create QKms when calculating the 'Umhuellende'.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4797
diff changeset
170 }
bcf25d8c183e Moved NaN removal code from W to DoubleUtil. Create QKms when calculating the 'Umhuellende'.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4797
diff changeset
171 return qs;
bcf25d8c183e Moved NaN removal code from W to DoubleUtil. Create QKms when calculating the 'Umhuellende'.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4797
diff changeset
172 }
4797
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4796
diff changeset
173 } // class QuickQFinder
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4796
diff changeset
174
625
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
175 protected Node root;
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
176
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
177 public QRangeTree() {
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
178 }
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
179
2609
ed550e325248 Little optimization when fetching q ranges for single columns of wsts.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1890
diff changeset
180 public static final class AccessQAB {
ed550e325248 Little optimization when fetching q ranges for single columns of wsts.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1890
diff changeset
181 private int startIndex;
ed550e325248 Little optimization when fetching q ranges for single columns of wsts.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1890
diff changeset
182
ed550e325248 Little optimization when fetching q ranges for single columns of wsts.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1890
diff changeset
183 public AccessQAB(int startIndex) {
ed550e325248 Little optimization when fetching q ranges for single columns of wsts.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1890
diff changeset
184 this.startIndex = startIndex;
ed550e325248 Little optimization when fetching q ranges for single columns of wsts.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1890
diff changeset
185 }
ed550e325248 Little optimization when fetching q ranges for single columns of wsts.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1890
diff changeset
186
ed550e325248 Little optimization when fetching q ranges for single columns of wsts.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1890
diff changeset
187 public Double getQ(Object [] row) {
ed550e325248 Little optimization when fetching q ranges for single columns of wsts.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1890
diff changeset
188 return (Double)row[startIndex];
ed550e325248 Little optimization when fetching q ranges for single columns of wsts.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1890
diff changeset
189 }
ed550e325248 Little optimization when fetching q ranges for single columns of wsts.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1890
diff changeset
190
ed550e325248 Little optimization when fetching q ranges for single columns of wsts.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1890
diff changeset
191 public Double getA(Object [] row) {
ed550e325248 Little optimization when fetching q ranges for single columns of wsts.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1890
diff changeset
192 return (Double)row[startIndex+1];
ed550e325248 Little optimization when fetching q ranges for single columns of wsts.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1890
diff changeset
193 }
ed550e325248 Little optimization when fetching q ranges for single columns of wsts.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1890
diff changeset
194
ed550e325248 Little optimization when fetching q ranges for single columns of wsts.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1890
diff changeset
195 public Double getB(Object [] row) {
ed550e325248 Little optimization when fetching q ranges for single columns of wsts.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1890
diff changeset
196 return (Double)row[startIndex+2];
ed550e325248 Little optimization when fetching q ranges for single columns of wsts.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1890
diff changeset
197 }
ed550e325248 Little optimization when fetching q ranges for single columns of wsts.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1890
diff changeset
198 }
ed550e325248 Little optimization when fetching q ranges for single columns of wsts.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1890
diff changeset
199
ed550e325248 Little optimization when fetching q ranges for single columns of wsts.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1890
diff changeset
200 public static final AccessQAB WITH_COLUMN = new AccessQAB(1);
ed550e325248 Little optimization when fetching q ranges for single columns of wsts.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1890
diff changeset
201 public static final AccessQAB WITHOUT_COLUMN = new AccessQAB(0);
ed550e325248 Little optimization when fetching q ranges for single columns of wsts.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1890
diff changeset
202
632
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
203 /** wstQRanges need to be sorted by range.a */
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
204 public QRangeTree(List<Object []> qRanges, int start, int stop) {
2609
ed550e325248 Little optimization when fetching q ranges for single columns of wsts.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1890
diff changeset
205 this(qRanges, WITH_COLUMN, start, stop);
ed550e325248 Little optimization when fetching q ranges for single columns of wsts.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1890
diff changeset
206 }
ed550e325248 Little optimization when fetching q ranges for single columns of wsts.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1890
diff changeset
207
ed550e325248 Little optimization when fetching q ranges for single columns of wsts.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1890
diff changeset
208 public QRangeTree(
ed550e325248 Little optimization when fetching q ranges for single columns of wsts.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1890
diff changeset
209 List<Object []> qRanges,
3076
5642a83420f2 FLYS artifacts: Removed trailing whitespace.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2792
diff changeset
210 AccessQAB accessQAB,
2609
ed550e325248 Little optimization when fetching q ranges for single columns of wsts.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1890
diff changeset
211 int start,
ed550e325248 Little optimization when fetching q ranges for single columns of wsts.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1890
diff changeset
212 int stop
ed550e325248 Little optimization when fetching q ranges for single columns of wsts.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1890
diff changeset
213 ) {
632
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
214 if (stop <= start) {
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
215 return;
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
216 }
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
217
2611
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2609
diff changeset
218 int N = stop-start;
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2609
diff changeset
219
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2609
diff changeset
220 List<Node> nodes = new ArrayList<Node>(N);
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2609
diff changeset
221
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2609
diff changeset
222 Node last = null;
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2609
diff changeset
223
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2609
diff changeset
224 for (int i = 0; i < N; ++i) {
1890
9144e5a5027b (Picky) cosmetics.
Felix Wolfsteller <felix.wolfsteller@intevation.de>
parents: 1020
diff changeset
225 Object [] qRange = qRanges.get(start + i);
2609
ed550e325248 Little optimization when fetching q ranges for single columns of wsts.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1890
diff changeset
226 Double q = accessQAB.getQ(qRange);
ed550e325248 Little optimization when fetching q ranges for single columns of wsts.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1890
diff changeset
227 Double a = accessQAB.getA(qRange);
ed550e325248 Little optimization when fetching q ranges for single columns of wsts.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1890
diff changeset
228 Double b = accessQAB.getB(qRange);
632
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
229
2611
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2609
diff changeset
230 double av = a != null ? a.doubleValue() : -Double.MAX_VALUE;
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2609
diff changeset
231 double bv = b != null ? b.doubleValue() : Double.MAX_VALUE;
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2609
diff changeset
232 double qv = q.doubleValue();
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2609
diff changeset
233
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2609
diff changeset
234 // If nodes are directly neighbored and Qs are the same
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2609
diff changeset
235 // join them.
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2609
diff changeset
236 if (last != null
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2609
diff changeset
237 && Math.abs(last.b - av) < EPSILON
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2609
diff changeset
238 && Math.abs(last.q - qv) < EPSILON) {
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2609
diff changeset
239 last.b = bv;
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2609
diff changeset
240 }
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2609
diff changeset
241 else {
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2609
diff changeset
242 nodes.add(last = new Node(av, bv, qv));
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2609
diff changeset
243 }
632
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
244 }
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
245
2612
49cfa5c66651 Squashed performance bug introduced in rev4070. Now CSV export is about 245 times faster.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2611
diff changeset
246 if (log.isDebugEnabled()) {
49cfa5c66651 Squashed performance bug introduced in rev4070. Now CSV export is about 245 times faster.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2611
diff changeset
247 log.debug("Before/after nodes join: " +
49cfa5c66651 Squashed performance bug introduced in rev4070. Now CSV export is about 245 times faster.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2611
diff changeset
248 N + "/" + nodes.size());
49cfa5c66651 Squashed performance bug introduced in rev4070. Now CSV export is about 245 times faster.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2611
diff changeset
249 }
49cfa5c66651 Squashed performance bug introduced in rev4070. Now CSV export is about 245 times faster.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2611
diff changeset
250
632
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
251 root = wireTree(nodes);
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
252 }
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
253
2611
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2609
diff changeset
254 protected static Node wireTree(List<Node> nodes) {
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2609
diff changeset
255 int N = nodes.size();
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2609
diff changeset
256 for (int i = 0; i < N; ++i) {
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2609
diff changeset
257 Node node = nodes.get(i);
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2609
diff changeset
258 if (i > 0 ) node.prev = nodes.get(i-1);
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2609
diff changeset
259 if (i < N-1) node.next = nodes.get(i+1);
625
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
260 }
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
261
2611
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2609
diff changeset
262 return buildTree(nodes, 0, N-1);
625
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
263 }
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
264
2611
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2609
diff changeset
265 protected static Node buildTree(List<Node> nodes, int lo, int hi) {
632
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
266
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
267 if (lo > hi) {
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
268 return null;
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
269 }
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
270
625
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
271 int mid = (lo + hi) >> 1;
2611
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2609
diff changeset
272 Node parent = nodes.get(mid);
625
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
273
632
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
274 parent.left = buildTree(nodes, lo, mid-1);
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
275 parent.right = buildTree(nodes, mid+1, hi);
625
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
276
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
277 return parent;
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
278 }
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
279
5423
f4fd64a4d502 Fix Wstcalculation for non monotonous values.
Andre Heinecke <aheinecke@intevation.de>
parents: 5282
diff changeset
280 public double averageQ() {
f4fd64a4d502 Fix Wstcalculation for non monotonous values.
Andre Heinecke <aheinecke@intevation.de>
parents: 5282
diff changeset
281 double sum = 0d;
f4fd64a4d502 Fix Wstcalculation for non monotonous values.
Andre Heinecke <aheinecke@intevation.de>
parents: 5282
diff changeset
282 int n = 0;
f4fd64a4d502 Fix Wstcalculation for non monotonous values.
Andre Heinecke <aheinecke@intevation.de>
parents: 5282
diff changeset
283 for (Node node = head(); node != null; node = node.next) {
f4fd64a4d502 Fix Wstcalculation for non monotonous values.
Andre Heinecke <aheinecke@intevation.de>
parents: 5282
diff changeset
284 sum += node.q;
f4fd64a4d502 Fix Wstcalculation for non monotonous values.
Andre Heinecke <aheinecke@intevation.de>
parents: 5282
diff changeset
285 ++n;
f4fd64a4d502 Fix Wstcalculation for non monotonous values.
Andre Heinecke <aheinecke@intevation.de>
parents: 5282
diff changeset
286 }
f4fd64a4d502 Fix Wstcalculation for non monotonous values.
Andre Heinecke <aheinecke@intevation.de>
parents: 5282
diff changeset
287 return sum/n;
f4fd64a4d502 Fix Wstcalculation for non monotonous values.
Andre Heinecke <aheinecke@intevation.de>
parents: 5282
diff changeset
288 }
f4fd64a4d502 Fix Wstcalculation for non monotonous values.
Andre Heinecke <aheinecke@intevation.de>
parents: 5282
diff changeset
289
f4fd64a4d502 Fix Wstcalculation for non monotonous values.
Andre Heinecke <aheinecke@intevation.de>
parents: 5282
diff changeset
290 public double maxQ() {
f4fd64a4d502 Fix Wstcalculation for non monotonous values.
Andre Heinecke <aheinecke@intevation.de>
parents: 5282
diff changeset
291 double max = -Double.MAX_VALUE;
f4fd64a4d502 Fix Wstcalculation for non monotonous values.
Andre Heinecke <aheinecke@intevation.de>
parents: 5282
diff changeset
292 for (Node node = head(); node != null; node = node.next) {
f4fd64a4d502 Fix Wstcalculation for non monotonous values.
Andre Heinecke <aheinecke@intevation.de>
parents: 5282
diff changeset
293 if (node.q > max) {
f4fd64a4d502 Fix Wstcalculation for non monotonous values.
Andre Heinecke <aheinecke@intevation.de>
parents: 5282
diff changeset
294 max = node.q;
f4fd64a4d502 Fix Wstcalculation for non monotonous values.
Andre Heinecke <aheinecke@intevation.de>
parents: 5282
diff changeset
295 }
f4fd64a4d502 Fix Wstcalculation for non monotonous values.
Andre Heinecke <aheinecke@intevation.de>
parents: 5282
diff changeset
296 }
f4fd64a4d502 Fix Wstcalculation for non monotonous values.
Andre Heinecke <aheinecke@intevation.de>
parents: 5282
diff changeset
297 return max;
f4fd64a4d502 Fix Wstcalculation for non monotonous values.
Andre Heinecke <aheinecke@intevation.de>
parents: 5282
diff changeset
298 }
f4fd64a4d502 Fix Wstcalculation for non monotonous values.
Andre Heinecke <aheinecke@intevation.de>
parents: 5282
diff changeset
299
625
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
300 public double findQ(double pos) {
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
301 return root != null ? root.findQ(pos) : Double.NaN;
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
302 }
632
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
303
4797
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4796
diff changeset
304 public Node findNode(double pos) {
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4796
diff changeset
305 return root != null ? root.findNode(pos) : null;
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4796
diff changeset
306 }
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4796
diff changeset
307
3743
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3076
diff changeset
308 protected Node head() {
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3076
diff changeset
309 Node head = root;
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3076
diff changeset
310 while (head.left != null) {
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3076
diff changeset
311 head = head.left;
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3076
diff changeset
312 }
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3076
diff changeset
313 return head;
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3076
diff changeset
314 }
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3076
diff changeset
315
4796
729a5edb0313 Added intersectsQRange to QRangeTree to check if a given Q range intersects the Qs of the tree. Useful for 'Umhuellende'. TODO make check depend on km range.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 3743
diff changeset
316 public boolean intersectsQRange(double qMin, double qMax) {
729a5edb0313 Added intersectsQRange to QRangeTree to check if a given Q range intersects the Qs of the tree. Useful for 'Umhuellende'. TODO make check depend on km range.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 3743
diff changeset
317 if (qMin > qMax) {
729a5edb0313 Added intersectsQRange to QRangeTree to check if a given Q range intersects the Qs of the tree. Useful for 'Umhuellende'. TODO make check depend on km range.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 3743
diff changeset
318 double t = qMin;
729a5edb0313 Added intersectsQRange to QRangeTree to check if a given Q range intersects the Qs of the tree. Useful for 'Umhuellende'. TODO make check depend on km range.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 3743
diff changeset
319 qMin = qMax;
729a5edb0313 Added intersectsQRange to QRangeTree to check if a given Q range intersects the Qs of the tree. Useful for 'Umhuellende'. TODO make check depend on km range.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 3743
diff changeset
320 qMax = t;
729a5edb0313 Added intersectsQRange to QRangeTree to check if a given Q range intersects the Qs of the tree. Useful for 'Umhuellende'. TODO make check depend on km range.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 3743
diff changeset
321 }
729a5edb0313 Added intersectsQRange to QRangeTree to check if a given Q range intersects the Qs of the tree. Useful for 'Umhuellende'. TODO make check depend on km range.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 3743
diff changeset
322 for (Node curr = head(); curr != null; curr = curr.next) {
729a5edb0313 Added intersectsQRange to QRangeTree to check if a given Q range intersects the Qs of the tree. Useful for 'Umhuellende'. TODO make check depend on km range.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 3743
diff changeset
323 if (curr.q >= qMin || curr.q <= qMax) {
729a5edb0313 Added intersectsQRange to QRangeTree to check if a given Q range intersects the Qs of the tree. Useful for 'Umhuellende'. TODO make check depend on km range.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 3743
diff changeset
324 return true;
729a5edb0313 Added intersectsQRange to QRangeTree to check if a given Q range intersects the Qs of the tree. Useful for 'Umhuellende'. TODO make check depend on km range.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 3743
diff changeset
325 }
729a5edb0313 Added intersectsQRange to QRangeTree to check if a given Q range intersects the Qs of the tree. Useful for 'Umhuellende'. TODO make check depend on km range.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 3743
diff changeset
326 }
729a5edb0313 Added intersectsQRange to QRangeTree to check if a given Q range intersects the Qs of the tree. Useful for 'Umhuellende'. TODO make check depend on km range.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 3743
diff changeset
327 return false;
729a5edb0313 Added intersectsQRange to QRangeTree to check if a given Q range intersects the Qs of the tree. Useful for 'Umhuellende'. TODO make check depend on km range.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 3743
diff changeset
328 }
729a5edb0313 Added intersectsQRange to QRangeTree to check if a given Q range intersects the Qs of the tree. Useful for 'Umhuellende'. TODO make check depend on km range.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 3743
diff changeset
329
3743
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3076
diff changeset
330 public List<Range> findSegments(double a, double b) {
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3076
diff changeset
331 if (a > b) { double t = a; a = b; b = t; }
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3076
diff changeset
332 return findSegments(new Range(a, b));
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3076
diff changeset
333 }
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3076
diff changeset
334
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3076
diff changeset
335 public List<Range> findSegments(Range range) {
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3076
diff changeset
336 List<Range> segments = new ArrayList<Range>();
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3076
diff changeset
337
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3076
diff changeset
338 // Linear scan should be good enough here.
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3076
diff changeset
339 for (Node curr = head(); curr != null; curr = curr.next) {
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3076
diff changeset
340 if (!range.disjoint(curr.a, curr.b)) {
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3076
diff changeset
341 Range r = new Range(curr.a, curr.b);
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3076
diff changeset
342 if (r.clip(range)) {
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3076
diff changeset
343 segments.add(r);
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3076
diff changeset
344 }
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3076
diff changeset
345 }
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3076
diff changeset
346 }
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3076
diff changeset
347
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3076
diff changeset
348 return segments;
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3076
diff changeset
349 }
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 3076
diff changeset
350
2792
fe987587ebc9 Merged revisions 4539-4540,4543,4545-4546 via svnmerge from
Ingo Weinzierl <ingo.weinzierl@intevation.de>
parents: 2612
diff changeset
351 @Override
fe987587ebc9 Merged revisions 4539-4540,4543,4545-4546 via svnmerge from
Ingo Weinzierl <ingo.weinzierl@intevation.de>
parents: 2612
diff changeset
352 public String toString() {
fe987587ebc9 Merged revisions 4539-4540,4543,4545-4546 via svnmerge from
Ingo Weinzierl <ingo.weinzierl@intevation.de>
parents: 2612
diff changeset
353 StringBuilder sb = new StringBuilder();
fe987587ebc9 Merged revisions 4539-4540,4543,4545-4546 via svnmerge from
Ingo Weinzierl <ingo.weinzierl@intevation.de>
parents: 2612
diff changeset
354 inorder(root, sb);
fe987587ebc9 Merged revisions 4539-4540,4543,4545-4546 via svnmerge from
Ingo Weinzierl <ingo.weinzierl@intevation.de>
parents: 2612
diff changeset
355 return sb.toString();
fe987587ebc9 Merged revisions 4539-4540,4543,4545-4546 via svnmerge from
Ingo Weinzierl <ingo.weinzierl@intevation.de>
parents: 2612
diff changeset
356 }
fe987587ebc9 Merged revisions 4539-4540,4543,4545-4546 via svnmerge from
Ingo Weinzierl <ingo.weinzierl@intevation.de>
parents: 2612
diff changeset
357
fe987587ebc9 Merged revisions 4539-4540,4543,4545-4546 via svnmerge from
Ingo Weinzierl <ingo.weinzierl@intevation.de>
parents: 2612
diff changeset
358 protected static void inorder(Node node, StringBuilder sb) {
fe987587ebc9 Merged revisions 4539-4540,4543,4545-4546 via svnmerge from
Ingo Weinzierl <ingo.weinzierl@intevation.de>
parents: 2612
diff changeset
359 if (node != null) {
fe987587ebc9 Merged revisions 4539-4540,4543,4545-4546 via svnmerge from
Ingo Weinzierl <ingo.weinzierl@intevation.de>
parents: 2612
diff changeset
360 inorder(node.left, sb);
fe987587ebc9 Merged revisions 4539-4540,4543,4545-4546 via svnmerge from
Ingo Weinzierl <ingo.weinzierl@intevation.de>
parents: 2612
diff changeset
361 sb.append('[')
fe987587ebc9 Merged revisions 4539-4540,4543,4545-4546 via svnmerge from
Ingo Weinzierl <ingo.weinzierl@intevation.de>
parents: 2612
diff changeset
362 .append(node.a)
fe987587ebc9 Merged revisions 4539-4540,4543,4545-4546 via svnmerge from
Ingo Weinzierl <ingo.weinzierl@intevation.de>
parents: 2612
diff changeset
363 .append(", ")
fe987587ebc9 Merged revisions 4539-4540,4543,4545-4546 via svnmerge from
Ingo Weinzierl <ingo.weinzierl@intevation.de>
parents: 2612
diff changeset
364 .append(node.b)
fe987587ebc9 Merged revisions 4539-4540,4543,4545-4546 via svnmerge from
Ingo Weinzierl <ingo.weinzierl@intevation.de>
parents: 2612
diff changeset
365 .append(": ")
fe987587ebc9 Merged revisions 4539-4540,4543,4545-4546 via svnmerge from
Ingo Weinzierl <ingo.weinzierl@intevation.de>
parents: 2612
diff changeset
366 .append(node.q)
fe987587ebc9 Merged revisions 4539-4540,4543,4545-4546 via svnmerge from
Ingo Weinzierl <ingo.weinzierl@intevation.de>
parents: 2612
diff changeset
367 .append(']');
fe987587ebc9 Merged revisions 4539-4540,4543,4545-4546 via svnmerge from
Ingo Weinzierl <ingo.weinzierl@intevation.de>
parents: 2612
diff changeset
368 inorder(node.right, sb);
fe987587ebc9 Merged revisions 4539-4540,4543,4545-4546 via svnmerge from
Ingo Weinzierl <ingo.weinzierl@intevation.de>
parents: 2612
diff changeset
369 }
fe987587ebc9 Merged revisions 4539-4540,4543,4545-4546 via svnmerge from
Ingo Weinzierl <ingo.weinzierl@intevation.de>
parents: 2612
diff changeset
370 }
fe987587ebc9 Merged revisions 4539-4540,4543,4545-4546 via svnmerge from
Ingo Weinzierl <ingo.weinzierl@intevation.de>
parents: 2612
diff changeset
371
632
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
372 private static final String name(Object o) {
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
373 return String.valueOf(System.identityHashCode(o) & 0xffffffffL);
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
374 }
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
375
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
376 public String toGraph() {
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
377 StringBuilder sb = new StringBuilder();
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
378 sb.append("subgraph c");
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
379 sb.append(name(this));
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
380 sb.append(" {\n");
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
381 if (root != null) {
1020
a776afdf1ec5 Cosmetic: Replaced usage of legacy java.util.Stack with java.util.Deque.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 633
diff changeset
382 java.util.Deque<Node> stack = new java.util.ArrayDeque<Node>();
632
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
383 stack.push(root);
1020
a776afdf1ec5 Cosmetic: Replaced usage of legacy java.util.Stack with java.util.Deque.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 633
diff changeset
384 while (!stack.isEmpty()) {
632
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
385 Node current = stack.pop();
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
386 String name = "n" + name(current);
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
387 sb.append(name);
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
388 sb.append(" [label=\"");
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
389 sb.append(current.a).append(", ").append(current.b);
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
390 sb.append(": ").append(current.q).append("\"]\n");
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
391 if (current.left != null) {
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
392 String leftName = name(current.left);
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
393 sb.append(name).append(" -- n").append(leftName).append("\n");
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
394 stack.push(current.left);
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
395 }
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
396 if (current.right != null) {
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
397 String rightName = name(current.right);
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
398 sb.append(name).append(" -- n").append(rightName).append("\n");
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
399 stack.push(current.right);
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
400 }
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
401 }
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
402 }
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
403 sb.append("}\n");
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
404 return sb.toString();
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
405 }
625
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
406 }
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
407 // vim:set ts=4 sw=4 si et sta sts=4 fenc=utf8 :
http://dive4elements.wald.intevation.org