dive4elements/river: flys-artifacts/src/main/java/de/intevation/flys/artifacts/model/QRangeTree.java annotate

annotate flys-artifacts/src/main/java/de/intevation/flys/artifacts/model/QRangeTree.java @ 4837:9e25c7523485

Fixed calculation of effective width in MINFO SQ relation. * Get all (including empty datasets) from db. * Filter empty datasets when processing data of the same date. * Added debug outputs.

author	Raimund Renkert <rrenkert@intevation.de>
date	Wed, 23 Jan 2013 11:14:41 +0100
parents	43e69af28b3c
children	bcf25d8c183e

rev	line source
625 c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	1 package de.intevation.flys.artifacts.model;
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	2
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	3 import java.io.Serializable;
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	4
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	5 import java.util.List;
2611 62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2609 diff changeset	6 import java.util.ArrayList;
625 c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	7
633 d08f77e7f7e8 WST value table: Qs are now stored in ranges for each column. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 632 diff changeset	8 import org.apache.log4j.Logger;
625 c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	9
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	10 public class QRangeTree
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	11 implements Serializable
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	12 {
633 d08f77e7f7e8 WST value table: Qs are now stored in ranges for each column. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 632 diff changeset	13 private static Logger log = Logger.getLogger(QRangeTree.class);
d08f77e7f7e8 WST value table: Qs are now stored in ranges for each column. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 632 diff changeset	14
2611 62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2609 diff changeset	15 public static final double EPSILON = 1e-4;
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2609 diff changeset	16
625 c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	17 public static class Node
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	18 implements Serializable
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	19 {
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	20 Node left;
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	21 Node right;
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	22 Node prev;
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	23 Node next;
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	24
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	25 double a;
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	26 double b;
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	27 double q;
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	28
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	29 public Node() {
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	30 }
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	31
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	32 public Node(double a, double b, double q) {
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	33 this.a = a;
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	34 this.b = b;
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	35 this.q = q;
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	36 }
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	37
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	38 protected final double interpolatePrev(double pos) {
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	39 /*
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	40 f(prev.b) = prev.q
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	41 f(a) = q
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	42
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	43 prev.q = m*prev.b + n
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	44 q = ma + n <=> n = q - ma
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	45
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	46 q - prev.q = m*(a - prev.b)
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	47
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	48 m = (q - prev.q)/(a - prev.b) # a != prev.b
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	49 */
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	50
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	51 if (a == prev.b) {
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	52 return 0.5*(q + prev.q);
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	53 }
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	54 double m = (q - prev.q)/(a - prev.b);
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	55 double n = q - m*a;
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	56 return m*pos + n;
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	57 }
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	58
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	59 protected final double interpolateNext(double pos) {
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	60 /*
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	61 f(next.a) = next.q
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	62 f(b) = q
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	63
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	64 next.q = m*next.a + n
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	65 q = mb + n <=> n = q - mb
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	66
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	67 q - next.q = m*(b - next.a)
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	68 m = (q - next.q)/(b - next.a) # b != next.a
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	69 */
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	70
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	71 if (b == next.a) {
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	72 return 0.5*(q + next.q);
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	73 }
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	74 double m = (q - next.q)/(b - next.a);
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	75 double n = q - m*b;
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	76 return m*pos + n;
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	77 }
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	78
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	79 public double findQ(double pos) {
633 d08f77e7f7e8 WST value table: Qs are now stored in ranges for each column. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 632 diff changeset	80
625 c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	81 Node current = this;
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	82 for (;;) {
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	83 if (pos < current.a) {
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	84 if (current.left != null) {
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	85 current = current.left;
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	86 continue;
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	87 }
633 d08f77e7f7e8 WST value table: Qs are now stored in ranges for each column. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 632 diff changeset	88 return current.prev != null
625 c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	89 ? current.interpolatePrev(pos)
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	90 : Double.NaN;
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	91 }
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	92 if (pos > current.b) {
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	93 if (current.right != null) {
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	94 current = current.right;
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	95 continue;
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	96 }
633 d08f77e7f7e8 WST value table: Qs are now stored in ranges for each column. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 632 diff changeset	97 return current.next != null
625 c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	98 ? current.interpolateNext(pos)
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	99 : Double.NaN;
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	100 }
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	101 return current.q;
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	102 }
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	103 }
4797 43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms. Sascha L. Teichmann <teichmann@intevation.de> parents: 4796 diff changeset	104
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms. Sascha L. Teichmann <teichmann@intevation.de> parents: 4796 diff changeset	105 public Node findNode(double pos) {
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms. Sascha L. Teichmann <teichmann@intevation.de> parents: 4796 diff changeset	106 Node current = this;
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms. Sascha L. Teichmann <teichmann@intevation.de> parents: 4796 diff changeset	107 while (current != null) {
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms. Sascha L. Teichmann <teichmann@intevation.de> parents: 4796 diff changeset	108 if (pos < current.a) {
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms. Sascha L. Teichmann <teichmann@intevation.de> parents: 4796 diff changeset	109 current = current.left;
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms. Sascha L. Teichmann <teichmann@intevation.de> parents: 4796 diff changeset	110 }
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms. Sascha L. Teichmann <teichmann@intevation.de> parents: 4796 diff changeset	111 else if (pos > current.b) {
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms. Sascha L. Teichmann <teichmann@intevation.de> parents: 4796 diff changeset	112 current = current.right;
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms. Sascha L. Teichmann <teichmann@intevation.de> parents: 4796 diff changeset	113 }
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms. Sascha L. Teichmann <teichmann@intevation.de> parents: 4796 diff changeset	114 return current;
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms. Sascha L. Teichmann <teichmann@intevation.de> parents: 4796 diff changeset	115 }
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms. Sascha L. Teichmann <teichmann@intevation.de> parents: 4796 diff changeset	116 return null;
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms. Sascha L. Teichmann <teichmann@intevation.de> parents: 4796 diff changeset	117 }
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms. Sascha L. Teichmann <teichmann@intevation.de> parents: 4796 diff changeset	118
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms. Sascha L. Teichmann <teichmann@intevation.de> parents: 4796 diff changeset	119 public boolean contains(double c) {
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms. Sascha L. Teichmann <teichmann@intevation.de> parents: 4796 diff changeset	120 return c >= a && c <= b;
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms. Sascha L. Teichmann <teichmann@intevation.de> parents: 4796 diff changeset	121 }
625 c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	122 } // class Node
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	123
4797 43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms. Sascha L. Teichmann <teichmann@intevation.de> parents: 4796 diff changeset	124 /** Class to cache the last found tree leaf in a search for Q.
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms. Sascha L. Teichmann <teichmann@intevation.de> parents: 4796 diff changeset	125 * Its likely that a neighbored pos search
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms. Sascha L. Teichmann <teichmann@intevation.de> parents: 4796 diff changeset	126 * results in using the same leaf node. So
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms. Sascha L. Teichmann <teichmann@intevation.de> parents: 4796 diff changeset	127 * caching this leaf will minimize expensive
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms. Sascha L. Teichmann <teichmann@intevation.de> parents: 4796 diff changeset	128 * tree traversals.
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms. Sascha L. Teichmann <teichmann@intevation.de> parents: 4796 diff changeset	129 * Modeled as inner class because the QRangeTree
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms. Sascha L. Teichmann <teichmann@intevation.de> parents: 4796 diff changeset	130 * itself is a shared data structure.
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms. Sascha L. Teichmann <teichmann@intevation.de> parents: 4796 diff changeset	131 * Using this class omits interpolation between
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms. Sascha L. Teichmann <teichmann@intevation.de> parents: 4796 diff changeset	132 * leaves.
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms. Sascha L. Teichmann <teichmann@intevation.de> parents: 4796 diff changeset	133 */
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms. Sascha L. Teichmann <teichmann@intevation.de> parents: 4796 diff changeset	134 public final class QuickQFinder {
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms. Sascha L. Teichmann <teichmann@intevation.de> parents: 4796 diff changeset	135
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms. Sascha L. Teichmann <teichmann@intevation.de> parents: 4796 diff changeset	136 private Node last;
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms. Sascha L. Teichmann <teichmann@intevation.de> parents: 4796 diff changeset	137
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms. Sascha L. Teichmann <teichmann@intevation.de> parents: 4796 diff changeset	138 public QuickQFinder() {
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms. Sascha L. Teichmann <teichmann@intevation.de> parents: 4796 diff changeset	139 }
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms. Sascha L. Teichmann <teichmann@intevation.de> parents: 4796 diff changeset	140
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms. Sascha L. Teichmann <teichmann@intevation.de> parents: 4796 diff changeset	141 public double findQ(double pos) {
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms. Sascha L. Teichmann <teichmann@intevation.de> parents: 4796 diff changeset	142 if (last != null && last.contains(pos)) {
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms. Sascha L. Teichmann <teichmann@intevation.de> parents: 4796 diff changeset	143 return last.q;
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms. Sascha L. Teichmann <teichmann@intevation.de> parents: 4796 diff changeset	144 }
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms. Sascha L. Teichmann <teichmann@intevation.de> parents: 4796 diff changeset	145 last = QRangeTree.this.findNode(pos);
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms. Sascha L. Teichmann <teichmann@intevation.de> parents: 4796 diff changeset	146 return last != null ? last.q : Double.NaN;
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms. Sascha L. Teichmann <teichmann@intevation.de> parents: 4796 diff changeset	147 }
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms. Sascha L. Teichmann <teichmann@intevation.de> parents: 4796 diff changeset	148 } // class QuickQFinder
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms. Sascha L. Teichmann <teichmann@intevation.de> parents: 4796 diff changeset	149
625 c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	150 protected Node root;
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	151
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	152 public QRangeTree() {
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	153 }
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	154
2609 ed550e325248 Little optimization when fetching q ranges for single columns of wsts. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1890 diff changeset	155 public static final class AccessQAB {
ed550e325248 Little optimization when fetching q ranges for single columns of wsts. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1890 diff changeset	156 private int startIndex;
ed550e325248 Little optimization when fetching q ranges for single columns of wsts. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1890 diff changeset	157
ed550e325248 Little optimization when fetching q ranges for single columns of wsts. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1890 diff changeset	158 public AccessQAB(int startIndex) {
ed550e325248 Little optimization when fetching q ranges for single columns of wsts. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1890 diff changeset	159 this.startIndex = startIndex;
ed550e325248 Little optimization when fetching q ranges for single columns of wsts. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1890 diff changeset	160 }
ed550e325248 Little optimization when fetching q ranges for single columns of wsts. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1890 diff changeset	161
ed550e325248 Little optimization when fetching q ranges for single columns of wsts. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1890 diff changeset	162 public Double getQ(Object [] row) {
ed550e325248 Little optimization when fetching q ranges for single columns of wsts. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1890 diff changeset	163 return (Double)row[startIndex];
ed550e325248 Little optimization when fetching q ranges for single columns of wsts. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1890 diff changeset	164 }
ed550e325248 Little optimization when fetching q ranges for single columns of wsts. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1890 diff changeset	165
ed550e325248 Little optimization when fetching q ranges for single columns of wsts. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1890 diff changeset	166 public Double getA(Object [] row) {
ed550e325248 Little optimization when fetching q ranges for single columns of wsts. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1890 diff changeset	167 return (Double)row[startIndex+1];
ed550e325248 Little optimization when fetching q ranges for single columns of wsts. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1890 diff changeset	168 }
ed550e325248 Little optimization when fetching q ranges for single columns of wsts. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1890 diff changeset	169
ed550e325248 Little optimization when fetching q ranges for single columns of wsts. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1890 diff changeset	170 public Double getB(Object [] row) {
ed550e325248 Little optimization when fetching q ranges for single columns of wsts. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1890 diff changeset	171 return (Double)row[startIndex+2];
ed550e325248 Little optimization when fetching q ranges for single columns of wsts. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1890 diff changeset	172 }
ed550e325248 Little optimization when fetching q ranges for single columns of wsts. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1890 diff changeset	173 }
ed550e325248 Little optimization when fetching q ranges for single columns of wsts. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1890 diff changeset	174
ed550e325248 Little optimization when fetching q ranges for single columns of wsts. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1890 diff changeset	175 public static final AccessQAB WITH_COLUMN = new AccessQAB(1);
ed550e325248 Little optimization when fetching q ranges for single columns of wsts. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1890 diff changeset	176 public static final AccessQAB WITHOUT_COLUMN = new AccessQAB(0);
ed550e325248 Little optimization when fetching q ranges for single columns of wsts. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1890 diff changeset	177
632 07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	178 /** wstQRanges need to be sorted by range.a */
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	179 public QRangeTree(List<Object []> qRanges, int start, int stop) {
2609 ed550e325248 Little optimization when fetching q ranges for single columns of wsts. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1890 diff changeset	180 this(qRanges, WITH_COLUMN, start, stop);
ed550e325248 Little optimization when fetching q ranges for single columns of wsts. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1890 diff changeset	181 }
ed550e325248 Little optimization when fetching q ranges for single columns of wsts. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1890 diff changeset	182
ed550e325248 Little optimization when fetching q ranges for single columns of wsts. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1890 diff changeset	183 public QRangeTree(
ed550e325248 Little optimization when fetching q ranges for single columns of wsts. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1890 diff changeset	184 List<Object []> qRanges,
3076 5642a83420f2 FLYS artifacts: Removed trailing whitespace. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2792 diff changeset	185 AccessQAB accessQAB,
2609 ed550e325248 Little optimization when fetching q ranges for single columns of wsts. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1890 diff changeset	186 int start,
ed550e325248 Little optimization when fetching q ranges for single columns of wsts. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1890 diff changeset	187 int stop
ed550e325248 Little optimization when fetching q ranges for single columns of wsts. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1890 diff changeset	188 ) {
632 07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	189 if (stop <= start) {
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	190 return;
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	191 }
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	192
2611 62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2609 diff changeset	193 int N = stop-start;
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2609 diff changeset	194
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2609 diff changeset	195 List<Node> nodes = new ArrayList<Node>(N);
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2609 diff changeset	196
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2609 diff changeset	197 Node last = null;
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2609 diff changeset	198
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2609 diff changeset	199 for (int i = 0; i < N; ++i) {
1890 9144e5a5027b (Picky) cosmetics. Felix Wolfsteller <felix.wolfsteller@intevation.de> parents: 1020 diff changeset	200 Object [] qRange = qRanges.get(start + i);
2609 ed550e325248 Little optimization when fetching q ranges for single columns of wsts. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1890 diff changeset	201 Double q = accessQAB.getQ(qRange);
ed550e325248 Little optimization when fetching q ranges for single columns of wsts. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1890 diff changeset	202 Double a = accessQAB.getA(qRange);
ed550e325248 Little optimization when fetching q ranges for single columns of wsts. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1890 diff changeset	203 Double b = accessQAB.getB(qRange);
632 07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	204
2611 62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2609 diff changeset	205 double av = a != null ? a.doubleValue() : -Double.MAX_VALUE;
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2609 diff changeset	206 double bv = b != null ? b.doubleValue() : Double.MAX_VALUE;
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2609 diff changeset	207 double qv = q.doubleValue();
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2609 diff changeset	208
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2609 diff changeset	209 // If nodes are directly neighbored and Qs are the same
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2609 diff changeset	210 // join them.
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2609 diff changeset	211 if (last != null
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2609 diff changeset	212 && Math.abs(last.b - av) < EPSILON
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2609 diff changeset	213 && Math.abs(last.q - qv) < EPSILON) {
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2609 diff changeset	214 last.b = bv;
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2609 diff changeset	215 }
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2609 diff changeset	216 else {
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2609 diff changeset	217 nodes.add(last = new Node(av, bv, qv));
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2609 diff changeset	218 }
632 07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	219 }
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	220
2612 49cfa5c66651 Squashed performance bug introduced in rev4070. Now CSV export is about 245 times faster. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2611 diff changeset	221 if (log.isDebugEnabled()) {
49cfa5c66651 Squashed performance bug introduced in rev4070. Now CSV export is about 245 times faster. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2611 diff changeset	222 log.debug("Before/after nodes join: " +
49cfa5c66651 Squashed performance bug introduced in rev4070. Now CSV export is about 245 times faster. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2611 diff changeset	223 N + "/" + nodes.size());
49cfa5c66651 Squashed performance bug introduced in rev4070. Now CSV export is about 245 times faster. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2611 diff changeset	224 }
49cfa5c66651 Squashed performance bug introduced in rev4070. Now CSV export is about 245 times faster. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2611 diff changeset	225
632 07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	226 root = wireTree(nodes);
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	227 }
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	228
2611 62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2609 diff changeset	229 protected static Node wireTree(List<Node> nodes) {
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2609 diff changeset	230 int N = nodes.size();
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2609 diff changeset	231 for (int i = 0; i < N; ++i) {
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2609 diff changeset	232 Node node = nodes.get(i);
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2609 diff changeset	233 if (i > 0 ) node.prev = nodes.get(i-1);
62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2609 diff changeset	234 if (i < N-1) node.next = nodes.get(i+1);
625 c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	235 }
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	236
2611 62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2609 diff changeset	237 return buildTree(nodes, 0, N-1);
625 c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	238 }
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	239
2611 62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2609 diff changeset	240 protected static Node buildTree(List<Node> nodes, int lo, int hi) {
632 07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	241
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	242 if (lo > hi) {
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	243 return null;
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	244 }
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	245
625 c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	246 int mid = (lo + hi) >> 1;
2611 62e5c6fd2a0c Join nodes in Q tree if they span a continuous interval and have same Qs. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2609 diff changeset	247 Node parent = nodes.get(mid);
625 c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	248
632 07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	249 parent.left = buildTree(nodes, lo, mid-1);
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	250 parent.right = buildTree(nodes, mid+1, hi);
625 c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	251
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	252 return parent;
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	253 }
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	254
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	255 public double findQ(double pos) {
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	256 return root != null ? root.findQ(pos) : Double.NaN;
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	257 }
632 07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	258
4797 43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms. Sascha L. Teichmann <teichmann@intevation.de> parents: 4796 diff changeset	259 public Node findNode(double pos) {
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms. Sascha L. Teichmann <teichmann@intevation.de> parents: 4796 diff changeset	260 return root != null ? root.findNode(pos) : null;
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms. Sascha L. Teichmann <teichmann@intevation.de> parents: 4796 diff changeset	261 }
43e69af28b3c A naive algorithm to figure out the "Umhuellende" of a set of WQKms. Sascha L. Teichmann <teichmann@intevation.de> parents: 4796 diff changeset	262
3743 51f76225823b Extreme waterlevels: calculate the segments for Q km ranges. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3076 diff changeset	263 protected Node head() {
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3076 diff changeset	264 Node head = root;
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3076 diff changeset	265 while (head.left != null) {
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3076 diff changeset	266 head = head.left;
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3076 diff changeset	267 }
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3076 diff changeset	268 return head;
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3076 diff changeset	269 }
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3076 diff changeset	270
4796 729a5edb0313 Added intersectsQRange to QRangeTree to check if a given Q range intersects the Qs of the tree. Useful for 'Umhuellende'. TODO make check depend on km range. Sascha L. Teichmann <teichmann@intevation.de> parents: 3743 diff changeset	271 public boolean intersectsQRange(double qMin, double qMax) {
729a5edb0313 Added intersectsQRange to QRangeTree to check if a given Q range intersects the Qs of the tree. Useful for 'Umhuellende'. TODO make check depend on km range. Sascha L. Teichmann <teichmann@intevation.de> parents: 3743 diff changeset	272 if (qMin > qMax) {
729a5edb0313 Added intersectsQRange to QRangeTree to check if a given Q range intersects the Qs of the tree. Useful for 'Umhuellende'. TODO make check depend on km range. Sascha L. Teichmann <teichmann@intevation.de> parents: 3743 diff changeset	273 double t = qMin;
729a5edb0313 Added intersectsQRange to QRangeTree to check if a given Q range intersects the Qs of the tree. Useful for 'Umhuellende'. TODO make check depend on km range. Sascha L. Teichmann <teichmann@intevation.de> parents: 3743 diff changeset	274 qMin = qMax;
729a5edb0313 Added intersectsQRange to QRangeTree to check if a given Q range intersects the Qs of the tree. Useful for 'Umhuellende'. TODO make check depend on km range. Sascha L. Teichmann <teichmann@intevation.de> parents: 3743 diff changeset	275 qMax = t;
729a5edb0313 Added intersectsQRange to QRangeTree to check if a given Q range intersects the Qs of the tree. Useful for 'Umhuellende'. TODO make check depend on km range. Sascha L. Teichmann <teichmann@intevation.de> parents: 3743 diff changeset	276 }
729a5edb0313 Added intersectsQRange to QRangeTree to check if a given Q range intersects the Qs of the tree. Useful for 'Umhuellende'. TODO make check depend on km range. Sascha L. Teichmann <teichmann@intevation.de> parents: 3743 diff changeset	277 for (Node curr = head(); curr != null; curr = curr.next) {
729a5edb0313 Added intersectsQRange to QRangeTree to check if a given Q range intersects the Qs of the tree. Useful for 'Umhuellende'. TODO make check depend on km range. Sascha L. Teichmann <teichmann@intevation.de> parents: 3743 diff changeset	278 if (curr.q >= qMin \|\| curr.q <= qMax) {
729a5edb0313 Added intersectsQRange to QRangeTree to check if a given Q range intersects the Qs of the tree. Useful for 'Umhuellende'. TODO make check depend on km range. Sascha L. Teichmann <teichmann@intevation.de> parents: 3743 diff changeset	279 return true;
729a5edb0313 Added intersectsQRange to QRangeTree to check if a given Q range intersects the Qs of the tree. Useful for 'Umhuellende'. TODO make check depend on km range. Sascha L. Teichmann <teichmann@intevation.de> parents: 3743 diff changeset	280 }
729a5edb0313 Added intersectsQRange to QRangeTree to check if a given Q range intersects the Qs of the tree. Useful for 'Umhuellende'. TODO make check depend on km range. Sascha L. Teichmann <teichmann@intevation.de> parents: 3743 diff changeset	281 }
729a5edb0313 Added intersectsQRange to QRangeTree to check if a given Q range intersects the Qs of the tree. Useful for 'Umhuellende'. TODO make check depend on km range. Sascha L. Teichmann <teichmann@intevation.de> parents: 3743 diff changeset	282 return false;
729a5edb0313 Added intersectsQRange to QRangeTree to check if a given Q range intersects the Qs of the tree. Useful for 'Umhuellende'. TODO make check depend on km range. Sascha L. Teichmann <teichmann@intevation.de> parents: 3743 diff changeset	283 }
729a5edb0313 Added intersectsQRange to QRangeTree to check if a given Q range intersects the Qs of the tree. Useful for 'Umhuellende'. TODO make check depend on km range. Sascha L. Teichmann <teichmann@intevation.de> parents: 3743 diff changeset	284
3743 51f76225823b Extreme waterlevels: calculate the segments for Q km ranges. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3076 diff changeset	285 public List<Range> findSegments(double a, double b) {
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3076 diff changeset	286 if (a > b) { double t = a; a = b; b = t; }
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3076 diff changeset	287 return findSegments(new Range(a, b));
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3076 diff changeset	288 }
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3076 diff changeset	289
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3076 diff changeset	290 public List<Range> findSegments(Range range) {
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3076 diff changeset	291 List<Range> segments = new ArrayList<Range>();
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3076 diff changeset	292
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3076 diff changeset	293 // Linear scan should be good enough here.
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3076 diff changeset	294 for (Node curr = head(); curr != null; curr = curr.next) {
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3076 diff changeset	295 if (!range.disjoint(curr.a, curr.b)) {
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3076 diff changeset	296 Range r = new Range(curr.a, curr.b);
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3076 diff changeset	297 if (r.clip(range)) {
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3076 diff changeset	298 segments.add(r);
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3076 diff changeset	299 }
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3076 diff changeset	300 }
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3076 diff changeset	301 }
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3076 diff changeset	302
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3076 diff changeset	303 return segments;
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3076 diff changeset	304 }
51f76225823b Extreme waterlevels: calculate the segments for Q km ranges. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3076 diff changeset	305
2792 fe987587ebc9 Merged revisions 4539-4540,4543,4545-4546 via svnmerge from Ingo Weinzierl <ingo.weinzierl@intevation.de> parents: 2612 diff changeset	306 @Override
fe987587ebc9 Merged revisions 4539-4540,4543,4545-4546 via svnmerge from Ingo Weinzierl <ingo.weinzierl@intevation.de> parents: 2612 diff changeset	307 public String toString() {
fe987587ebc9 Merged revisions 4539-4540,4543,4545-4546 via svnmerge from Ingo Weinzierl <ingo.weinzierl@intevation.de> parents: 2612 diff changeset	308 StringBuilder sb = new StringBuilder();
fe987587ebc9 Merged revisions 4539-4540,4543,4545-4546 via svnmerge from Ingo Weinzierl <ingo.weinzierl@intevation.de> parents: 2612 diff changeset	309 inorder(root, sb);
fe987587ebc9 Merged revisions 4539-4540,4543,4545-4546 via svnmerge from Ingo Weinzierl <ingo.weinzierl@intevation.de> parents: 2612 diff changeset	310 return sb.toString();
fe987587ebc9 Merged revisions 4539-4540,4543,4545-4546 via svnmerge from Ingo Weinzierl <ingo.weinzierl@intevation.de> parents: 2612 diff changeset	311 }
fe987587ebc9 Merged revisions 4539-4540,4543,4545-4546 via svnmerge from Ingo Weinzierl <ingo.weinzierl@intevation.de> parents: 2612 diff changeset	312
fe987587ebc9 Merged revisions 4539-4540,4543,4545-4546 via svnmerge from Ingo Weinzierl <ingo.weinzierl@intevation.de> parents: 2612 diff changeset	313 protected static void inorder(Node node, StringBuilder sb) {
fe987587ebc9 Merged revisions 4539-4540,4543,4545-4546 via svnmerge from Ingo Weinzierl <ingo.weinzierl@intevation.de> parents: 2612 diff changeset	314 if (node != null) {
fe987587ebc9 Merged revisions 4539-4540,4543,4545-4546 via svnmerge from Ingo Weinzierl <ingo.weinzierl@intevation.de> parents: 2612 diff changeset	315 inorder(node.left, sb);
fe987587ebc9 Merged revisions 4539-4540,4543,4545-4546 via svnmerge from Ingo Weinzierl <ingo.weinzierl@intevation.de> parents: 2612 diff changeset	316 sb.append('[')
fe987587ebc9 Merged revisions 4539-4540,4543,4545-4546 via svnmerge from Ingo Weinzierl <ingo.weinzierl@intevation.de> parents: 2612 diff changeset	317 .append(node.a)
fe987587ebc9 Merged revisions 4539-4540,4543,4545-4546 via svnmerge from Ingo Weinzierl <ingo.weinzierl@intevation.de> parents: 2612 diff changeset	318 .append(", ")
fe987587ebc9 Merged revisions 4539-4540,4543,4545-4546 via svnmerge from Ingo Weinzierl <ingo.weinzierl@intevation.de> parents: 2612 diff changeset	319 .append(node.b)
fe987587ebc9 Merged revisions 4539-4540,4543,4545-4546 via svnmerge from Ingo Weinzierl <ingo.weinzierl@intevation.de> parents: 2612 diff changeset	320 .append(": ")
fe987587ebc9 Merged revisions 4539-4540,4543,4545-4546 via svnmerge from Ingo Weinzierl <ingo.weinzierl@intevation.de> parents: 2612 diff changeset	321 .append(node.q)
fe987587ebc9 Merged revisions 4539-4540,4543,4545-4546 via svnmerge from Ingo Weinzierl <ingo.weinzierl@intevation.de> parents: 2612 diff changeset	322 .append(']');
fe987587ebc9 Merged revisions 4539-4540,4543,4545-4546 via svnmerge from Ingo Weinzierl <ingo.weinzierl@intevation.de> parents: 2612 diff changeset	323 inorder(node.right, sb);
fe987587ebc9 Merged revisions 4539-4540,4543,4545-4546 via svnmerge from Ingo Weinzierl <ingo.weinzierl@intevation.de> parents: 2612 diff changeset	324 }
fe987587ebc9 Merged revisions 4539-4540,4543,4545-4546 via svnmerge from Ingo Weinzierl <ingo.weinzierl@intevation.de> parents: 2612 diff changeset	325 }
fe987587ebc9 Merged revisions 4539-4540,4543,4545-4546 via svnmerge from Ingo Weinzierl <ingo.weinzierl@intevation.de> parents: 2612 diff changeset	326
632 07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	327 private static final String name(Object o) {
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	328 return String.valueOf(System.identityHashCode(o) & 0xffffffffL);
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	329 }
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	330
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	331 public String toGraph() {
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	332 StringBuilder sb = new StringBuilder();
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	333 sb.append("subgraph c");
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	334 sb.append(name(this));
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	335 sb.append(" {\n");
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	336 if (root != null) {
1020 a776afdf1ec5 Cosmetic: Replaced usage of legacy java.util.Stack with java.util.Deque. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 633 diff changeset	337 java.util.Deque<Node> stack = new java.util.ArrayDeque<Node>();
632 07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	338 stack.push(root);
1020 a776afdf1ec5 Cosmetic: Replaced usage of legacy java.util.Stack with java.util.Deque. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 633 diff changeset	339 while (!stack.isEmpty()) {
632 07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	340 Node current = stack.pop();
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	341 String name = "n" + name(current);
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	342 sb.append(name);
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	343 sb.append(" [label=\"");
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	344 sb.append(current.a).append(", ").append(current.b);
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	345 sb.append(": ").append(current.q).append("\"]\n");
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	346 if (current.left != null) {
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	347 String leftName = name(current.left);
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	348 sb.append(name).append(" -- n").append(leftName).append("\n");
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	349 stack.push(current.left);
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	350 }
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	351 if (current.right != null) {
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	352 String rightName = name(current.right);
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	353 sb.append(name).append(" -- n").append(rightName).append("\n");
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	354 stack.push(current.right);
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	355 }
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	356 }
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	357 }
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	358 sb.append("}\n");
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	359 return sb.toString();
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	360 }
625 c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	361 }
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	362 // vim:set ts=4 sw=4 si et sta sts=4 fenc=utf8 :

Mercurial > dive4elements > river

annotate flys-artifacts/src/main/java/de/intevation/flys/artifacts/model/QRangeTree.java @ 4837:9e25c7523485