Mercurial > dive4elements > river

comparison flys-artifacts/src/main/java/de/intevation/flys/artifacts/model/QRangeTree.java @ 3468:f37e7e8907cb

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
merged flys-artifacts/2.8.1
author Thomas Arendsen Hein <thomas@intevation.de>
date Fri, 28 Sep 2012 12:14:39 +0200
parents 5642a83420f2
children 51f76225823b
comparison
equal deleted inserted replaced
3387:5ffad8bde8ad 3468:f37e7e8907cb
1 package de.intevation.flys.artifacts.model;
2
3 import java.io.Serializable;
4
5 import java.util.List;
6 import java.util.ArrayList;
7
8 import org.apache.log4j.Logger;
9
10 public class QRangeTree
11 implements Serializable
12 {
13 private static Logger log = Logger.getLogger(QRangeTree.class);
14
15 public static final double EPSILON = 1e-4;
16
17 public static class Node
18 implements Serializable
19 {
20 Node left;
21 Node right;
22 Node prev;
23 Node next;
24
25 double a;
26 double b;
27 double q;
28
29 public Node() {
30 }
31
32 public Node(double a, double b, double q) {
33 this.a = a;
34 this.b = b;
35 this.q = q;
36 }
37
38 protected final double interpolatePrev(double pos) {
39 /*
40 f(prev.b) = prev.q
41 f(a) = q
42
43 prev.q = m*prev.b + n
44 q = m*a + n <=> n = q - m*a
45
46 q - prev.q = m*(a - prev.b)
47
48 m = (q - prev.q)/(a - prev.b) # a != prev.b
49 */
50
51 if (a == prev.b) {
52 return 0.5*(q + prev.q);
53 }
54 double m = (q - prev.q)/(a - prev.b);
55 double n = q - m*a;
56 return m*pos + n;
57 }
58
59 protected final double interpolateNext(double pos) {
60 /*
61 f(next.a) = next.q
62 f(b) = q
63
64 next.q = m*next.a + n
65 q = m*b + n <=> n = q - m*b
66
67 q - next.q = m*(b - next.a)
68 m = (q - next.q)/(b - next.a) # b != next.a
69 */
70
71 if (b == next.a) {
72 return 0.5*(q + next.q);
73 }
74 double m = (q - next.q)/(b - next.a);
75 double n = q - m*b;
76 return m*pos + n;
77 }
78
79 public double findQ(double pos) {
80
81 Node current = this;
82 for (;;) {
83 if (pos < current.a) {
84 if (current.left != null) {
85 current = current.left;
86 continue;
87 }
88 return current.prev != null
89 ? current.interpolatePrev(pos)
90 : Double.NaN;
91 }
92 if (pos > current.b) {
93 if (current.right != null) {
94 current = current.right;
95 continue;
96 }
97 return current.next != null
98 ? current.interpolateNext(pos)
99 : Double.NaN;
100 }
101 return current.q;
102 }
103 }
104 } // class Node
105
106 protected Node root;
107
108 public QRangeTree() {
109 }
110
111 public static final class AccessQAB {
112 private int startIndex;
113
114 public AccessQAB(int startIndex) {
115 this.startIndex = startIndex;
116 }
117
118 public Double getQ(Object [] row) {
119 return (Double)row[startIndex];
120 }
121
122 public Double getA(Object [] row) {
123 return (Double)row[startIndex+1];
124 }
125
126 public Double getB(Object [] row) {
127 return (Double)row[startIndex+2];
128 }
129 }
130
131 public static final AccessQAB WITH_COLUMN = new AccessQAB(1);
132 public static final AccessQAB WITHOUT_COLUMN = new AccessQAB(0);
133
134 /** wstQRanges need to be sorted by range.a */
135 public QRangeTree(List<Object []> qRanges, int start, int stop) {
136 this(qRanges, WITH_COLUMN, start, stop);
137 }
138
139 public QRangeTree(
140 List<Object []> qRanges,
141 AccessQAB accessQAB,
142 int start,
143 int stop
144 ) {
145 if (stop <= start) {
146 return;
147 }
148
149 int N = stop-start;
150
151 List<Node> nodes = new ArrayList<Node>(N);
152
153 Node last = null;
154
155 for (int i = 0; i < N; ++i) {
156 Object [] qRange = qRanges.get(start + i);
157 Double q = accessQAB.getQ(qRange);
158 Double a = accessQAB.getA(qRange);
159 Double b = accessQAB.getB(qRange);
160
161 double av = a != null ? a.doubleValue() : -Double.MAX_VALUE;
162 double bv = b != null ? b.doubleValue() : Double.MAX_VALUE;
163 double qv = q.doubleValue();
164
165 // If nodes are directly neighbored and Qs are the same
166 // join them.
167 if (last != null
168 && Math.abs(last.b - av) < EPSILON
169 && Math.abs(last.q - qv) < EPSILON) {
170 last.b = bv;
171 }
172 else {
173 nodes.add(last = new Node(av, bv, qv));
174 }
175 }
176
177 if (log.isDebugEnabled()) {
178 log.debug("Before/after nodes join: " +
179 N + "/" + nodes.size());
180 }
181
182 root = wireTree(nodes);
183 }
184
185 protected static Node wireTree(List<Node> nodes) {
186 int N = nodes.size();
187 for (int i = 0; i < N; ++i) {
188 Node node = nodes.get(i);
189 if (i > 0 ) node.prev = nodes.get(i-1);
190 if (i < N-1) node.next = nodes.get(i+1);
191 }
192
193 return buildTree(nodes, 0, N-1);
194 }
195
196 protected static Node buildTree(List<Node> nodes, int lo, int hi) {
197
198 if (lo > hi) {
199 return null;
200 }
201
202 int mid = (lo + hi) >> 1;
203 Node parent = nodes.get(mid);
204
205 parent.left = buildTree(nodes, lo, mid-1);
206 parent.right = buildTree(nodes, mid+1, hi);
207
208 return parent;
209 }
210
211 public double findQ(double pos) {
212 return root != null ? root.findQ(pos) : Double.NaN;
213 }
214
215 @Override
216 public String toString() {
217 StringBuilder sb = new StringBuilder();
218 inorder(root, sb);
219 return sb.toString();
220 }
221
222 protected static void inorder(Node node, StringBuilder sb) {
223 if (node != null) {
224 inorder(node.left, sb);
225 sb.append('[')
226 .append(node.a)
227 .append(", ")
228 .append(node.b)
229 .append(": ")
230 .append(node.q)
231 .append(']');
232 inorder(node.right, sb);
233 }
234 }
235
236 private static final String name(Object o) {
237 return String.valueOf(System.identityHashCode(o) & 0xffffffffL);
238 }
239
240 public String toGraph() {
241 StringBuilder sb = new StringBuilder();
242 sb.append("subgraph c");
243 sb.append(name(this));
244 sb.append(" {\n");
245 if (root != null) {
246 java.util.Deque<Node> stack = new java.util.ArrayDeque<Node>();
247 stack.push(root);
248 while (!stack.isEmpty()) {
249 Node current = stack.pop();
250 String name = "n" + name(current);
251 sb.append(name);
252 sb.append(" [label=\"");
253 sb.append(current.a).append(", ").append(current.b);
254 sb.append(": ").append(current.q).append("\"]\n");
255 if (current.left != null) {
256 String leftName = name(current.left);
257 sb.append(name).append(" -- n").append(leftName).append("\n");
258 stack.push(current.left);
259 }
260 if (current.right != null) {
261 String rightName = name(current.right);
262 sb.append(name).append(" -- n").append(rightName).append("\n");
263 stack.push(current.right);
264 }
265 }
266 }
267 sb.append("}\n");
268 return sb.toString();
269 }
270 }
271 // vim:set ts=4 sw=4 si et sta sts=4 fenc=utf8 :
http://dive4elements.wald.intevation.org