--- a/flys-artifacts/ChangeLog	Mon May 23 15:11:55 2011 +0000
+++ b/flys-artifacts/ChangeLog	Mon May 23 22:33:37 2011 +0000
@@ -1,3 +1,10 @@
+2011-05-24	Sascha L. Teichmann	<sascha.teichmann@intevation.de>
+
+	* src/main/java/de/intevation/flys/artifacts/model/QRangeTree.java:
+	  Model to store the q values of a WST column efficiently. First
+	  building block not to store the q values directly aside the
+	  w values.
+
 2011-05-23  Ingo Weinzierl <ingo@intevation.de>
 
 	  ISSUE-62 (part II/II)

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/flys-artifacts/src/main/java/de/intevation/flys/artifacts/model/QRangeTree.java	Mon May 23 22:33:37 2011 +0000
@@ -0,0 +1,152 @@
+package de.intevation.flys.artifacts.model;
+
+import java.io.Serializable;
+
+import java.math.BigDecimal;
+
+import java.util.List;
+
+import de.intevation.flys.model.WstQRange;
+import de.intevation.flys.model.Range;
+
+public class QRangeTree
+implements   Serializable
+{
+    public static class Node
+    implements          Serializable
+    {
+        Node left;
+        Node right;
+        Node prev;
+        Node next;
+
+        double a;
+        double b;
+        double q;
+
+        public Node() {
+        }
+
+        public Node(double a, double b, double q) {
+            this.a = a;
+            this.b = b;
+            this.q = q;
+        }
+
+        protected final double interpolatePrev(double pos) {
+            /*
+            f(prev.b) = prev.q
+            f(a)      = q
+
+            prev.q = m*prev.b + n
+            q      = m*a      + n <=> n = q - m*a
+
+            q - prev.q = m*(a - prev.b)
+
+            m = (q - prev.q)/(a - prev.b) # a != prev.b
+            */
+
+            if (a == prev.b) {
+                return 0.5*(q + prev.q);
+            }
+            double m = (q - prev.q)/(a - prev.b);
+            double n = q - m*a;
+            return m*pos + n;
+        }
+
+        protected final double interpolateNext(double pos) {
+            /*
+            f(next.a) = next.q
+            f(b)      = q
+
+            next.q = m*next.a + n
+            q      = m*b      + n <=> n = q - m*b
+
+            q - next.q = m*(b - next.a)
+            m = (q - next.q)/(b - next.a) # b != next.a
+            */
+
+            if (b == next.a) {
+                return 0.5*(q + next.q);
+            }
+            double m = (q - next.q)/(b - next.a);
+            double n = q - m*b;
+            return m*pos + n;
+        }
+
+        public double findQ(double pos) {
+            Node current = this;
+            for (;;) {
+                if (pos < current.a) {
+                    if (current.left != null) {
+                        current = current.left;
+                        continue;
+                    }
+                    return current.left != null
+                        ? current.interpolatePrev(pos)
+                        : Double.NaN;
+                }
+                if (pos > current.b) {
+                    if (current.right != null) {
+                        current = current.right;
+                        continue;
+                    }
+                    return current.right != null
+                        ? current.interpolateNext(pos)
+                        : Double.NaN;
+                }
+                return current.q;
+            }
+        }
+    } // class Node
+
+    protected Node root;
+
+    public QRangeTree() {
+    }
+
+    /** wstQRanges need to sorted by range.a */
+    public QRangeTree(List<WstQRange> wstQRanges) {
+
+        if (wstQRanges.isEmpty()) {
+            return;
+        }
+
+        Node [] nodes = new Node[wstQRanges.size()];
+        for (int i = 0; i < nodes.length; ++i) {
+            WstQRange wstQRange = wstQRanges.get(i);
+            Range     range     = wstQRange.getRange();
+            BigDecimal a = range.getA();
+            BigDecimal b = range.getB();
+            nodes[i] = new Node(
+                a != null ? a.doubleValue() : -Double.MAX_VALUE,
+                b != null ? b.doubleValue() :  Double.MAX_VALUE,
+                wstQRange.getQ().doubleValue());
+        }
+
+        for (int i = 0; i < nodes.length; ++i) {
+            Node node = nodes[i];
+            if (i > 0             ) node.prev = nodes[i-1];
+            if (i < nodes.length-1) node.next = nodes[i+1];
+        }
+
+        root = buildTree(nodes, 0, nodes.length-1);
+    }
+
+    protected static Node buildTree(Node [] nodes, int lo, int hi) {
+        int mid = (lo + hi) >> 1;
+        Node parent = nodes[mid];
+
+        if (hi > lo) {
+            parent.left  = buildTree(nodes, lo, mid-1);
+            parent.right = buildTree(nodes, mid+1, hi);
+        }
+
+        return parent;
+    }
+
+    public double findQ(double pos) {
+        return root != null ? root.findQ(pos) : Double.NaN;
+    }
+}
+// vim:set ts=4 sw=4 si et sta sts=4 fenc=utf8 :