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 @ 2716:150dcdefeb7d

Only offer soundings that fit to the current km range in MINFO bed height workflow. flys-artifacts/trunk@4444 c6561f87-3c4e-4783-a992-168aeb5c3f6f

author	Ingo Weinzierl <ingo.weinzierl@intevation.de>
date	Fri, 18 May 2012 12:44:20 +0000
parents	49cfa5c66651
children	fe987587ebc9

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 }
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	104 } // class Node
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	105
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	106 protected Node root;
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	107
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	108 public QRangeTree() {
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	109 }
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	110
2609 ed550e325248 Little optimization when fetching q ranges for single columns of wsts. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1890 diff changeset	111 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	112 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	113
ed550e325248 Little optimization when fetching q ranges for single columns of wsts. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1890 diff changeset	114 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	115 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	116 }
ed550e325248 Little optimization when fetching q ranges for single columns of wsts. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1890 diff changeset	117
ed550e325248 Little optimization when fetching q ranges for single columns of wsts. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1890 diff changeset	118 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	119 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	120 }
ed550e325248 Little optimization when fetching q ranges for single columns of wsts. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1890 diff changeset	121
ed550e325248 Little optimization when fetching q ranges for single columns of wsts. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1890 diff changeset	122 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	123 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	124 }
ed550e325248 Little optimization when fetching q ranges for single columns of wsts. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1890 diff changeset	125
ed550e325248 Little optimization when fetching q ranges for single columns of wsts. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1890 diff changeset	126 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	127 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	128 }
ed550e325248 Little optimization when fetching q ranges for single columns of wsts. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1890 diff changeset	129 }
ed550e325248 Little optimization when fetching q ranges for single columns of wsts. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1890 diff changeset	130
ed550e325248 Little optimization when fetching q ranges for single columns of wsts. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1890 diff changeset	131 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	132 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	133
632 07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	134 /** 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	135 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	136 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	137 }
ed550e325248 Little optimization when fetching q ranges for single columns of wsts. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1890 diff changeset	138
ed550e325248 Little optimization when fetching q ranges for single columns of wsts. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1890 diff changeset	139 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	140 List<Object []> qRanges,
ed550e325248 Little optimization when fetching q ranges for single columns of wsts. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1890 diff changeset	141 AccessQAB accessQAB,
ed550e325248 Little optimization when fetching q ranges for single columns of wsts. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1890 diff changeset	142 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	143 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	144 ) {
632 07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	145 if (stop <= start) {
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	146 return;
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	147 }
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	148
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	149 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	150
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	151 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	152
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	153 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	154
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	155 for (int i = 0; i < N; ++i) {
1890 9144e5a5027b (Picky) cosmetics. Felix Wolfsteller <felix.wolfsteller@intevation.de> parents: 1020 diff changeset	156 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	157 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	158 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	159 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	160
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	161 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	162 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	163 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	164
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	165 // 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	166 // 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	167 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	168 && 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	169 && 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	170 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	171 }
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	172 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	173 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	174 }
632 07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	175 }
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	176
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	177 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	178 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	179 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	180 }
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	181
632 07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	182 root = wireTree(nodes);
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	183 }
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	184
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	185 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	186 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	187 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	188 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	189 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	190 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	191 }
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 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 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	194 }
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	195
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	196 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	197
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	198 if (lo > hi) {
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	199 return null;
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	200 }
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	201
625 c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	202 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	203 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	204
632 07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	205 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	206 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	207
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	208 return parent;
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	209 }
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	210
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	211 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	212 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	213 }
632 07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	214
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	215 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	216 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	217 }
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	218
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	219 public String toGraph() {
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	220 StringBuilder sb = new StringBuilder();
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	221 sb.append("subgraph c");
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	222 sb.append(name(this));
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	223 sb.append(" {\n");
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	224 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	225 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	226 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	227 while (!stack.isEmpty()) {
632 07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	228 Node current = stack.pop();
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	229 String name = "n" + name(current);
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	230 sb.append(name);
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	231 sb.append(" [label=\"");
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	232 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	233 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	234 if (current.left != null) {
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	235 String leftName = name(current.left);
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	236 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	237 stack.push(current.left);
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	238 }
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	239 if (current.right != null) {
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	240 String rightName = name(current.right);
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	241 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	242 stack.push(current.right);
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	243 }
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 }
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	246 sb.append("}\n");
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	247 return sb.toString();
07640ab913fd First part of storing qs in ranges Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 625 diff changeset	248 }
625 c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	249 }
c0c60a611fca Introduce model to store q values of WST columns efficiently. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	250 // 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 @ 2716:150dcdefeb7d