Mercurial > dive4elements > river

comparison flys-artifacts/src/main/java/de/intevation/flys/artifacts/model/QRangeTree.java @ 625:c0c60a611fca

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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 :
http://dive4elements.wald.intevation.org