Mercurial > dive4elements > river
annotate flys-artifacts/src/main/java/de/intevation/flys/artifacts/model/QRangeTree.java @ 1922:7e7522c9e663
Use importData convenvience function.
flys-artifacts/trunk@3282 c6561f87-3c4e-4783-a992-168aeb5c3f6f
author | Felix Wolfsteller <felix.wolfsteller@intevation.de> |
---|---|
date | Thu, 17 Nov 2011 09:19:55 +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 : |