Mercurial > dive4elements > river

comparison flys-artifacts/src/main/java/de/intevation/flys/artifacts/model/QRangeTree.java @ 3818:dc18457b1cef

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
merged flys-artifacts/pre2.7-2012-03-16
author Thomas Arendsen Hein <thomas@intevation.de>
date Fri, 28 Sep 2012 12:14:59 +0200
parents 9144e5a5027b
children ed550e325248
comparison
equal deleted inserted replaced
2456:60ab1054069d 3818:dc18457b1cef
1 package de.intevation.flys.artifacts.model;
2
3 import java.io.Serializable;
4
5 import java.util.List;
6
7 import org.apache.log4j.Logger;
8
9 public class QRangeTree
10 implements Serializable
11 {
12 private static Logger log = Logger.getLogger(QRangeTree.class);
13
14 public static class Node
15 implements Serializable
16 {
17 Node left;
18 Node right;
19 Node prev;
20 Node next;
21
22 double a;
23 double b;
24 double q;
25
26 public Node() {
27 }
28
29 public Node(double a, double b, double q) {
30 this.a = a;
31 this.b = b;
32 this.q = q;
33 }
34
35 protected final double interpolatePrev(double pos) {
36 /*
37 f(prev.b) = prev.q
38 f(a) = q
39
40 prev.q = m*prev.b + n
41 q = m*a + n <=> n = q - m*a
42
43 q - prev.q = m*(a - prev.b)
44
45 m = (q - prev.q)/(a - prev.b) # a != prev.b
46 */
47
48 if (a == prev.b) {
49 return 0.5*(q + prev.q);
50 }
51 double m = (q - prev.q)/(a - prev.b);
52 double n = q - m*a;
53 return m*pos + n;
54 }
55
56 protected final double interpolateNext(double pos) {
57 /*
58 f(next.a) = next.q
59 f(b) = q
60
61 next.q = m*next.a + n
62 q = m*b + n <=> n = q - m*b
63
64 q - next.q = m*(b - next.a)
65 m = (q - next.q)/(b - next.a) # b != next.a
66 */
67
68 if (b == next.a) {
69 return 0.5*(q + next.q);
70 }
71 double m = (q - next.q)/(b - next.a);
72 double n = q - m*b;
73 return m*pos + n;
74 }
75
76 public double findQ(double pos) {
77
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.prev != 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.next != 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 be sorted by range.a */
109 public QRangeTree(List<Object []> qRanges, int start, int stop) {
110
111 if (stop <= start) {
112 return;
113 }
114
115 Node [] nodes = new Node[stop-start];
116 for (int i = 0; i < nodes.length; ++i) {
117 Object [] qRange = qRanges.get(start + i);
118 Double q = (Double)qRange[1];
119 Double a = (Double)qRange[2];
120 Double b = (Double)qRange[3];
121
122 nodes[i] = new Node(
123 a != null ? a.doubleValue() : -Double.MAX_VALUE,
124 b != null ? b.doubleValue() : Double.MAX_VALUE,
125 q.doubleValue());
126 }
127
128 root = wireTree(nodes);
129 }
130
131 protected static Node wireTree(Node [] nodes) {
132 for (int i = 0; i < nodes.length; ++i) {
133 Node node = nodes[i];
134 if (i > 0 ) node.prev = nodes[i-1];
135 if (i < nodes.length-1) node.next = nodes[i+1];
136 }
137
138 return buildTree(nodes, 0, nodes.length-1);
139 }
140
141 protected static Node buildTree(Node [] nodes, int lo, int hi) {
142
143 if (lo > hi) {
144 return null;
145 }
146
147 int mid = (lo + hi) >> 1;
148 Node parent = nodes[mid];
149
150 parent.left = buildTree(nodes, lo, mid-1);
151 parent.right = buildTree(nodes, mid+1, hi);
152
153 return parent;
154 }
155
156 public double findQ(double pos) {
157 return root != null ? root.findQ(pos) : Double.NaN;
158 }
159
160 private static final String name(Object o) {
161 return String.valueOf(System.identityHashCode(o) & 0xffffffffL);
162 }
163
164 public String toGraph() {
165 StringBuilder sb = new StringBuilder();
166 sb.append("subgraph c");
167 sb.append(name(this));
168 sb.append(" {\n");
169 if (root != null) {
170 java.util.Deque<Node> stack = new java.util.ArrayDeque<Node>();
171 stack.push(root);
172 while (!stack.isEmpty()) {
173 Node current = stack.pop();
174 String name = "n" + name(current);
175 sb.append(name);
176 sb.append(" [label=\"");
177 sb.append(current.a).append(", ").append(current.b);
178 sb.append(": ").append(current.q).append("\"]\n");
179 if (current.left != null) {
180 String leftName = name(current.left);
181 sb.append(name).append(" -- n").append(leftName).append("\n");
182 stack.push(current.left);
183 }
184 if (current.right != null) {
185 String rightName = name(current.right);
186 sb.append(name).append(" -- n").append(rightName).append("\n");
187 stack.push(current.right);
188 }
189 }
190 }
191 sb.append("}\n");
192 return sb.toString();
193 }
194 }
195 // vim:set ts=4 sw=4 si et sta sts=4 fenc=utf8 :
http://dive4elements.wald.intevation.org