stats/src/main/java/io/airlift/stats/QuantileDigest.java
public List<Long> getQuantilesLowerBound(List<Double> quantiles)
    {
        checkArgument(Ordering.natural().isOrdered(quantiles), "quantiles must be sorted in increasing order");
        for (double quantile : quantiles) {
            checkArgument(quantile >= 0 && quantile <= 1, "quantile must be between [0,1]");
        }

        List<Double> reversedQuantiles = ImmutableList.copyOf(quantiles).reverse();

        ImmutableList.Builder<Long> builder = ImmutableList.builder();
        PeekingIterator<Double> iterator = Iterators.peekingIterator(reversedQuantiles.iterator());

        postOrderTraversal(root, new Callback()
        {
            private double sum;

            @Override
            public boolean process(int node)
            {
                sum += counts[node];

                while (iterator.hasNext() && sum > (1.0 - iterator.peek()) * weightedCount) {
                    iterator.next();

                    // we know the min value ever seen, so cap the percentile to provide better error
                    // bounds in this case
                    long value = Math.max(lowerBound(node), min);

                    builder.add(value);
                }

                return iterator.hasNext();
            }
        }, TraversalOrder.REVERSE);

        // we finished the traversal without consuming all quantiles. This means the remaining quantiles
        // correspond to the max known value
        while (iterator.hasNext()) {
            builder.add(min);
            iterator.next();
        }

        return builder.build().reverse();
    }
public List<Long> getQuantilesLowerBound(List<Double> quantiles)
    {
        checkArgument(Ordering.natural().isOrdered(quantiles), "quantiles must be sorted in increasing order");
        for (double quantile : quantiles) {
            checkArgument(quantile >= 0 && quantile <= 1, "quantile must be between [0,1]");
        }

        List<Double> reversedQuantiles = ImmutableList.copyOf(quantiles).reverse();

        ImmutableList.Builder<Long> builder = ImmutableList.builder();
        PeekingIterator<Double> iterator = Iterators.peekingIterator(reversedQuantiles.iterator());

        postOrderTraversal(root, new Callback()
        {
            private double sum;

            @Override
            public boolean process(int node)
            {
                sum += counts[node];

                while (iterator.hasNext() && sum > (1.0 - iterator.peek()) * weightedCount) {
                    iterator.next();

                    // we know the min value ever seen, so cap the percentile to provide better error
                    // bounds in this case
                    long value = Math.max(lowerBound(node), min);

                    builder.add(value);
                }

                return iterator.hasNext();
            }
        }, TraversalOrder.REVERSE);

        // we finished the traversal without consuming all quantiles. This means the remaining quantiles
        // correspond to the max known value
        while (iterator.hasNext()) {
            builder.add(min);
            iterator.next();
        }

        return builder.build().reverse();
    }
public List < Long > getQuantilesLowerBound ( List < Double > quantiles ) { checkArgument ( Ordering . natural ( ) . isOrdered ( quantiles ) , "quantiles must be sorted in increasing order" ) ; for ( double quantile : quantiles ) { checkArgument ( quantile >= 0 && quantile <= 1 , "quantile must be between [0,1]" ) ; } List < Double > reversedQuantiles = ImmutableList . copyOf ( quantiles ) . reverse ( ) ; ImmutableList . Builder < Long > builder = ImmutableList . builder ( ) ; PeekingIterator < Double > iterator = Iterators . peekingIterator ( reversedQuantiles . iterator ( ) ) ; postOrderTraversal ( root , new Callback ( ) { private double sum ; @ Override public boolean process ( int node ) { sum += counts [ node ] ; while ( iterator . hasNext ( ) && sum > ( 1.0 - iterator . peek ( ) ) * weightedCount ) { iterator . next ( ) ; // we know the min value ever seen, so cap the percentile to provide better error // bounds in this case long value = Math . max ( lowerBound ( node ) , min ) ; builder . add ( value ) ; } return iterator . hasNext ( ) ; } } , TraversalOrder . REVERSE ) ; // we finished the traversal without consuming all quantiles. This means the remaining quantiles // correspond to the max known value while ( iterator . hasNext ( ) ) { builder . add ( min ) ; iterator . next ( ) ; } return builder . build ( ) . reverse ( ) ; }
Get a lower bound on the quantiles for the given proportions. A returned q quantile is guaranteed to be within
the q - maxError and q quantiles.
<p>
The input list of quantile proportions must be sorted in increasing order, and each value must be in the range [0, 1]
Get a lower bound on the quantiles for the given proportions . A returned q quantile is guaranteed to be within the q - maxError and q quantiles . <p > The input list of quantile proportions must be sorted in increasing order and each value must be in the range [ 0 1 ]