Mercurial > dive4elements > river
diff flys-artifacts/src/main/java/de/intevation/flys/artifacts/model/QRangeTree.java @ 632:07640ab913fd
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 |
line wrap: on
line diff
--- a/flys-artifacts/src/main/java/de/intevation/flys/artifacts/model/QRangeTree.java Tue May 24 13:24:24 2011 +0000 +++ b/flys-artifacts/src/main/java/de/intevation/flys/artifacts/model/QRangeTree.java Tue May 24 14:46:45 2011 +0000 @@ -105,7 +105,7 @@ public QRangeTree() { } - /** wstQRanges need to sorted by range.a */ + /** wstQRanges need to be sorted by range.a */ public QRangeTree(List<WstQRange> wstQRanges) { if (wstQRanges.isEmpty()) { @@ -124,23 +124,52 @@ wstQRange.getQ().doubleValue()); } + root = wireTree(nodes); + } + + public QRangeTree(List<Object []> qRanges, int start, int stop) { + + if (stop <= start) { + return; + } + + Node [] nodes = new Node[stop-start]; + for (int i = 0; i < nodes.length; ++i) { + Object [] qRange = qRanges.get(i + start); + Double q = (Double)qRange[1]; + Double a = (Double)qRange[2]; + Double b = (Double)qRange[3]; + + nodes[i] = new Node( + a != null ? a.doubleValue() : -Double.MAX_VALUE, + b != null ? b.doubleValue() : Double.MAX_VALUE, + q.doubleValue()); + } + + root = wireTree(nodes); + } + + protected static Node wireTree(Node [] nodes) { for (int i = 0; i < nodes.length; ++i) { Node node = nodes[i]; if (i > 0 ) node.prev = nodes[i-1]; if (i < nodes.length-1) node.next = nodes[i+1]; } - root = buildTree(nodes, 0, nodes.length-1); + return buildTree(nodes, 0, nodes.length-1); } protected static Node buildTree(Node [] nodes, int lo, int hi) { + + if (lo > hi) { + return null; + } + int mid = (lo + hi) >> 1; Node parent = nodes[mid]; - if (hi > lo) { - parent.left = buildTree(nodes, lo, mid-1); - parent.right = buildTree(nodes, mid+1, hi); - } + parent.left = buildTree(nodes, lo, mid-1); + parent.right = buildTree(nodes, mid+1, hi); return parent; } @@ -148,5 +177,40 @@ public double findQ(double pos) { return root != null ? root.findQ(pos) : Double.NaN; } + + private static final String name(Object o) { + return String.valueOf(System.identityHashCode(o) & 0xffffffffL); + } + + public String toGraph() { + StringBuilder sb = new StringBuilder(); + sb.append("subgraph c"); + sb.append(name(this)); + sb.append(" {\n"); + if (root != null) { + java.util.Stack<Node> stack = new java.util.Stack<Node>(); + stack.push(root); + while (!stack.empty()) { + Node current = stack.pop(); + String name = "n" + name(current); + sb.append(name); + sb.append(" [label=\""); + sb.append(current.a).append(", ").append(current.b); + sb.append(": ").append(current.q).append("\"]\n"); + if (current.left != null) { + String leftName = name(current.left); + sb.append(name).append(" -- n").append(leftName).append("\n"); + stack.push(current.left); + } + if (current.right != null) { + String rightName = name(current.right); + sb.append(name).append(" -- n").append(rightName).append("\n"); + stack.push(current.right); + } + } + } + sb.append("}\n"); + return sb.toString(); + } } // vim:set ts=4 sw=4 si et sta sts=4 fenc=utf8 :