Mercurial > dive4elements > river
comparison flys-artifacts/src/main/java/de/intevation/flys/artifacts/model/QRangeTree.java @ 625:c0c60a611fca
Introduce model to store q values of WST columns efficiently.
flys-artifacts/trunk@1983 c6561f87-3c4e-4783-a992-168aeb5c3f6f
author | Sascha L. Teichmann <sascha.teichmann@intevation.de> |
---|---|
date | Mon, 23 May 2011 22:33:37 +0000 |
parents | |
children | 07640ab913fd |
comparison
equal
deleted
inserted
replaced
624:929137ee8154 | 625:c0c60a611fca |
---|---|
1 package de.intevation.flys.artifacts.model; | |
2 | |
3 import java.io.Serializable; | |
4 | |
5 import java.math.BigDecimal; | |
6 | |
7 import java.util.List; | |
8 | |
9 import de.intevation.flys.model.WstQRange; | |
10 import de.intevation.flys.model.Range; | |
11 | |
12 public class QRangeTree | |
13 implements Serializable | |
14 { | |
15 public static class Node | |
16 implements Serializable | |
17 { | |
18 Node left; | |
19 Node right; | |
20 Node prev; | |
21 Node next; | |
22 | |
23 double a; | |
24 double b; | |
25 double q; | |
26 | |
27 public Node() { | |
28 } | |
29 | |
30 public Node(double a, double b, double q) { | |
31 this.a = a; | |
32 this.b = b; | |
33 this.q = q; | |
34 } | |
35 | |
36 protected final double interpolatePrev(double pos) { | |
37 /* | |
38 f(prev.b) = prev.q | |
39 f(a) = q | |
40 | |
41 prev.q = m*prev.b + n | |
42 q = m*a + n <=> n = q - m*a | |
43 | |
44 q - prev.q = m*(a - prev.b) | |
45 | |
46 m = (q - prev.q)/(a - prev.b) # a != prev.b | |
47 */ | |
48 | |
49 if (a == prev.b) { | |
50 return 0.5*(q + prev.q); | |
51 } | |
52 double m = (q - prev.q)/(a - prev.b); | |
53 double n = q - m*a; | |
54 return m*pos + n; | |
55 } | |
56 | |
57 protected final double interpolateNext(double pos) { | |
58 /* | |
59 f(next.a) = next.q | |
60 f(b) = q | |
61 | |
62 next.q = m*next.a + n | |
63 q = m*b + n <=> n = q - m*b | |
64 | |
65 q - next.q = m*(b - next.a) | |
66 m = (q - next.q)/(b - next.a) # b != next.a | |
67 */ | |
68 | |
69 if (b == next.a) { | |
70 return 0.5*(q + next.q); | |
71 } | |
72 double m = (q - next.q)/(b - next.a); | |
73 double n = q - m*b; | |
74 return m*pos + n; | |
75 } | |
76 | |
77 public double findQ(double pos) { | |
78 Node current = this; | |
79 for (;;) { | |
80 if (pos < current.a) { | |
81 if (current.left != null) { | |
82 current = current.left; | |
83 continue; | |
84 } | |
85 return current.left != null | |
86 ? current.interpolatePrev(pos) | |
87 : Double.NaN; | |
88 } | |
89 if (pos > current.b) { | |
90 if (current.right != null) { | |
91 current = current.right; | |
92 continue; | |
93 } | |
94 return current.right != null | |
95 ? current.interpolateNext(pos) | |
96 : Double.NaN; | |
97 } | |
98 return current.q; | |
99 } | |
100 } | |
101 } // class Node | |
102 | |
103 protected Node root; | |
104 | |
105 public QRangeTree() { | |
106 } | |
107 | |
108 /** wstQRanges need to sorted by range.a */ | |
109 public QRangeTree(List<WstQRange> wstQRanges) { | |
110 | |
111 if (wstQRanges.isEmpty()) { | |
112 return; | |
113 } | |
114 | |
115 Node [] nodes = new Node[wstQRanges.size()]; | |
116 for (int i = 0; i < nodes.length; ++i) { | |
117 WstQRange wstQRange = wstQRanges.get(i); | |
118 Range range = wstQRange.getRange(); | |
119 BigDecimal a = range.getA(); | |
120 BigDecimal b = range.getB(); | |
121 nodes[i] = new Node( | |
122 a != null ? a.doubleValue() : -Double.MAX_VALUE, | |
123 b != null ? b.doubleValue() : Double.MAX_VALUE, | |
124 wstQRange.getQ().doubleValue()); | |
125 } | |
126 | |
127 for (int i = 0; i < nodes.length; ++i) { | |
128 Node node = nodes[i]; | |
129 if (i > 0 ) node.prev = nodes[i-1]; | |
130 if (i < nodes.length-1) node.next = nodes[i+1]; | |
131 } | |
132 | |
133 root = buildTree(nodes, 0, nodes.length-1); | |
134 } | |
135 | |
136 protected static Node buildTree(Node [] nodes, int lo, int hi) { | |
137 int mid = (lo + hi) >> 1; | |
138 Node parent = nodes[mid]; | |
139 | |
140 if (hi > lo) { | |
141 parent.left = buildTree(nodes, lo, mid-1); | |
142 parent.right = buildTree(nodes, mid+1, hi); | |
143 } | |
144 | |
145 return parent; | |
146 } | |
147 | |
148 public double findQ(double pos) { | |
149 return root != null ? root.findQ(pos) : Double.NaN; | |
150 } | |
151 } | |
152 // vim:set ts=4 sw=4 si et sta sts=4 fenc=utf8 : |