class Comparison {

    public static double ks(TDigest d1, TDigest d2) {
        Iterator<Centroid> ix1 = d1.centroids().iterator();
        Iterator<Centroid> ix2 = d2.centroids().iterator();

        double diff = 0;

        double x1 = d1.getMin();
        double x2 = d2.getMin();

        while (x1 <= d1.getMax() && x2 <= d2.getMax()) {
            if (x1 < x2) {
                diff = maxDiff(d1, d2, diff, x1);
                x1 = nextValue(d1, ix1, x1);
            } else if (x1 > x2) {
                diff = maxDiff(d1, d2, diff, x2);
                x2 = nextValue(d2, ix2, x2);
            } else if (x1 == x2) {
                diff = maxDiff(d1, d2, diff, x1);

                double q1 = d1.cdf(x1);
                double q2 = d2.cdf(x2);
                if (q1 < q2) {
                    x1 = nextValue(d1, ix1, x1);
                } else if (q1 > q2) {
                    x2 = nextValue(d2, ix2, x2);
                } else {
                    x1 = nextValue(d1, ix1, x1);
                    x2 = nextValue(d2, ix2, x2);
                }
            }
        }
        while (x1 <= d1.getMax()) {
            diff = maxDiff(d1, d2, diff, x1);
            x1 = nextValue(d1, ix1, x1);
        }

        while (x2 <= d2.getMax()) {
            diff = maxDiff(d2, d2, diff, x2);
            x2 = nextValue(d2, ix2, x2);
        }

        long n1 = d1.size();
        long n2 = d2.size();
        return diff * Math.sqrt((double) n1 * n2 / (n1 + n2));
    }

}