annotate flys-artifacts/src/main/java/de/intevation/flys/artifacts/model/QRangeTree.java @ 1964:85e442933e6d

New CrossSectionArtifact. flys-artifacts/trunk@3374 c6561f87-3c4e-4783-a992-168aeb5c3f6f
author Felix Wolfsteller <felix.wolfsteller@intevation.de>
date Fri, 09 Dec 2011 13:58:29 +0000
parents 9144e5a5027b
children ed550e325248
rev   line source
625
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
1 package de.intevation.flys.artifacts.model;
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
2
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
3 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
4
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
5 import java.util.List;
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
6
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
7 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
8
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
9 public class QRangeTree
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
10 implements Serializable
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
11 {
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
12 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
13
625
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
14 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
15 implements Serializable
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
16 {
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
17 Node left;
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
18 Node right;
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
19 Node prev;
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
20 Node next;
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
21
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
22 double a;
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
23 double b;
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
24 double q;
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
25
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
26 public Node() {
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
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
29 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
30 this.a = a;
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
31 this.b = b;
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
32 this.q = q;
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
33 }
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
34
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
35 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
36 /*
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
37 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
38 f(a) = q
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 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
41 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
42
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
43 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
44
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
45 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
46 */
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 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
49 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
50 }
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
51 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
52 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
53 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
54 }
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 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
57 /*
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
58 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
59 f(b) = q
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
60
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
61 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
62 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
63
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
64 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
65 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
66 */
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
67
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
68 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
69 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
70 }
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
71 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
72 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
73 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
74 }
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
75
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
76 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
77
625
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
78 Node current = this;
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
79 for (;;) {
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
80 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
81 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
82 current = current.left;
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
83 continue;
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
84 }
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
85 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
86 ? current.interpolatePrev(pos)
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
87 : Double.NaN;
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
88 }
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
89 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
90 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
91 current = current.right;
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
92 continue;
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
93 }
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
94 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
95 ? current.interpolateNext(pos)
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
96 : Double.NaN;
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
97 }
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
98 return current.q;
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 }
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
101 } // class Node
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
102
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
103 protected Node root;
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
104
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
105 public QRangeTree() {
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
106 }
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
107
632
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
108 /** 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
109 public QRangeTree(List<Object []> qRanges, int start, int stop) {
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
110
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
111 if (stop <= start) {
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
112 return;
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
113 }
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
114
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
115 Node [] nodes = new Node[stop-start];
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
116 for (int i = 0; i < nodes.length; ++i) {
1890
9144e5a5027b (Picky) cosmetics.
Felix Wolfsteller <felix.wolfsteller@intevation.de>
parents: 1020
diff changeset
117 Object [] qRange = qRanges.get(start + i);
632
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
118 Double q = (Double)qRange[1];
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
119 Double a = (Double)qRange[2];
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
120 Double b = (Double)qRange[3];
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
121
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
122 nodes[i] = new Node(
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
123 a != null ? a.doubleValue() : -Double.MAX_VALUE,
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
124 b != null ? b.doubleValue() : Double.MAX_VALUE,
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
125 q.doubleValue());
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
126 }
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
127
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
128 root = wireTree(nodes);
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
129 }
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
130
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
131 protected static Node wireTree(Node [] nodes) {
625
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
132 for (int i = 0; i < nodes.length; ++i) {
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
133 Node node = nodes[i];
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
134 if (i > 0 ) node.prev = nodes[i-1];
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
135 if (i < nodes.length-1) node.next = nodes[i+1];
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
136 }
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
137
632
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
138 return buildTree(nodes, 0, nodes.length-1);
625
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
139 }
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
140
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
141 protected static Node buildTree(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
142
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
143 if (lo > hi) {
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
144 return null;
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
145 }
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
146
625
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
147 int mid = (lo + hi) >> 1;
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
148 Node parent = nodes[mid];
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
149
632
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
150 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
151 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
152
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
153 return parent;
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
154 }
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
155
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
156 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
157 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
158 }
632
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
159
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
160 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
161 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
162 }
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
163
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
164 public String toGraph() {
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
165 StringBuilder sb = new StringBuilder();
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
166 sb.append("subgraph c");
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
167 sb.append(name(this));
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
168 sb.append(" {\n");
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
169 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
170 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
171 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
172 while (!stack.isEmpty()) {
632
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
173 Node current = stack.pop();
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
174 String name = "n" + name(current);
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
175 sb.append(name);
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
176 sb.append(" [label=\"");
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
177 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
178 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
179 if (current.left != null) {
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
180 String leftName = name(current.left);
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
181 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
182 stack.push(current.left);
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
183 }
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
184 if (current.right != null) {
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
185 String rightName = name(current.right);
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
186 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
187 stack.push(current.right);
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
188 }
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
189 }
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
190 }
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
191 sb.append("}\n");
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
192 return sb.toString();
07640ab913fd First part of storing qs in ranges
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 625
diff changeset
193 }
625
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
194 }
c0c60a611fca Introduce model to store q values of WST columns efficiently.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
195 // vim:set ts=4 sw=4 si et sta sts=4 fenc=utf8 :

http://dive4elements.wald.intevation.org