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 :