Mercurial > dive4elements > river

comparison flys-artifacts/src/main/java/de/intevation/flys/artifacts/model/QRangeTree.java @ 632:07640ab913fd

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
First part of storing qs in ranges flys-artifacts/trunk@1997 c6561f87-3c4e-4783-a992-168aeb5c3f6f
author Sascha L. Teichmann <sascha.teichmann@intevation.de>
date Tue, 24 May 2011 14:46:45 +0000
parents c0c60a611fca
children d08f77e7f7e8
comparison
equal deleted inserted replaced
631:a9af60c84dca 632:07640ab913fd
103 protected Node root; 103 protected Node root;
104 104
105 public QRangeTree() { 105 public QRangeTree() {
106 } 106 }
107 107
108 /** wstQRanges need to sorted by range.a */ 108 /** wstQRanges need to be sorted by range.a */
109 public QRangeTree(List<WstQRange> wstQRanges) { 109 public QRangeTree(List<WstQRange> wstQRanges) {
110 110
111 if (wstQRanges.isEmpty()) { 111 if (wstQRanges.isEmpty()) {
112 return; 112 return;
113 } 113 }
122 a != null ? a.doubleValue() : -Double.MAX_VALUE, 122 a != null ? a.doubleValue() : -Double.MAX_VALUE,
123 b != null ? b.doubleValue() : Double.MAX_VALUE, 123 b != null ? b.doubleValue() : Double.MAX_VALUE,
124 wstQRange.getQ().doubleValue()); 124 wstQRange.getQ().doubleValue());
125 } 125 }
126 126
127 root = wireTree(nodes);
128 }
129
130 public QRangeTree(List<Object []> qRanges, int start, int stop) {
131
132 if (stop <= start) {
133 return;
134 }
135
136 Node [] nodes = new Node[stop-start];
137 for (int i = 0; i < nodes.length; ++i) {
138 Object [] qRange = qRanges.get(i + start);
139 Double q = (Double)qRange[1];
140 Double a = (Double)qRange[2];
141 Double b = (Double)qRange[3];
142
143 nodes[i] = new Node(
144 a != null ? a.doubleValue() : -Double.MAX_VALUE,
145 b != null ? b.doubleValue() : Double.MAX_VALUE,
146 q.doubleValue());
147 }
148
149 root = wireTree(nodes);
150 }
151
152 protected static Node wireTree(Node [] nodes) {
127 for (int i = 0; i < nodes.length; ++i) { 153 for (int i = 0; i < nodes.length; ++i) {
128 Node node = nodes[i]; 154 Node node = nodes[i];
129 if (i > 0 ) node.prev = nodes[i-1]; 155 if (i > 0 ) node.prev = nodes[i-1];
130 if (i < nodes.length-1) node.next = nodes[i+1]; 156 if (i < nodes.length-1) node.next = nodes[i+1];
131 } 157 }
132 158
133 root = buildTree(nodes, 0, nodes.length-1); 159 return buildTree(nodes, 0, nodes.length-1);
134 } 160 }
135 161
136 protected static Node buildTree(Node [] nodes, int lo, int hi) { 162 protected static Node buildTree(Node [] nodes, int lo, int hi) {
163
164 if (lo > hi) {
165 return null;
166 }
167
137 int mid = (lo + hi) >> 1; 168 int mid = (lo + hi) >> 1;
138 Node parent = nodes[mid]; 169 Node parent = nodes[mid];
139 170
140 if (hi > lo) { 171 parent.left = buildTree(nodes, lo, mid-1);
141 parent.left = buildTree(nodes, lo, mid-1); 172 parent.right = buildTree(nodes, mid+1, hi);
142 parent.right = buildTree(nodes, mid+1, hi);
143 }
144 173
145 return parent; 174 return parent;
146 } 175 }
147 176
148 public double findQ(double pos) { 177 public double findQ(double pos) {
149 return root != null ? root.findQ(pos) : Double.NaN; 178 return root != null ? root.findQ(pos) : Double.NaN;
150 } 179 }
180
181 private static final String name(Object o) {
182 return String.valueOf(System.identityHashCode(o) & 0xffffffffL);
183 }
184
185 public String toGraph() {
186 StringBuilder sb = new StringBuilder();
187 sb.append("subgraph c");
188 sb.append(name(this));
189 sb.append(" {\n");
190 if (root != null) {
191 java.util.Stack<Node> stack = new java.util.Stack<Node>();
192 stack.push(root);
193 while (!stack.empty()) {
194 Node current = stack.pop();
195 String name = "n" + name(current);
196 sb.append(name);
197 sb.append(" [label=\"");
198 sb.append(current.a).append(", ").append(current.b);
199 sb.append(": ").append(current.q).append("\"]\n");
200 if (current.left != null) {
201 String leftName = name(current.left);
202 sb.append(name).append(" -- n").append(leftName).append("\n");
203 stack.push(current.left);
204 }
205 if (current.right != null) {
206 String rightName = name(current.right);
207 sb.append(name).append(" -- n").append(rightName).append("\n");
208 stack.push(current.right);
209 }
210 }
211 }
212 sb.append("}\n");
213 return sb.toString();
214 }
151 } 215 }
152 // vim:set ts=4 sw=4 si et sta sts=4 fenc=utf8 : 216 // vim:set ts=4 sw=4 si et sta sts=4 fenc=utf8 :
http://dive4elements.wald.intevation.org