package voldemort.store.stats;

import voldemort.annotations.concurrency.NotThreadsafe;

import java.util.Arrays;

/**
 * A class for computing percentiles based on a histogram
 */
@NotThreadsafe
public class Histogram {
    
    private final int nBuckets;
    private final int step;
    private final int[] buckets;
    private final int[] bounds;
    private int size;

    /**
     * 
     * @param nBuckets
     * @param step
     */
    public Histogram(int nBuckets, int step) {
        this.nBuckets = nBuckets;
        this.step = step;
        this.buckets = new int[nBuckets];
        this.bounds = new int[nBuckets];
        init();
    }
    
    protected void init() {
        int bound = 0;
        for(int i = 0; i < nBuckets; i++, bound += step) {
            bounds[i] = bound;
        }
        reset();
    }

    /**
     * 
     */
    public void reset() {
        Arrays.fill(buckets, 0);
        size = 0;
    }

    /**
     * 
     * @param data
     */
    public void insert(int data) {
        int index = findBucket(data);
        assert(index != -1);
        buckets[index]++;
        size++;
    }
    
    public int getQuantile(double quantile) {
        int total = 0;
        for(int i = 0; i < nBuckets; i++) {
            total += buckets[i];
            double currQuantile = ((double) total) / ((double) size);
            if(currQuantile >= quantile) {
                return bounds[i];
            }
        }
        return 0;
    }
    
    private int findBucket(int needle) {
        int max = step * nBuckets;
        if(needle > max) {
            return nBuckets - 1;
        }
        int low = 0;
        int high = nBuckets - 1;
        while(low <= high) {
            int mid = (low + high) / 2;
            int cmp = compareToBucket(mid, needle);
            if(cmp == 0) {
                return mid;
            } else if(cmp > 0) {
                high = mid - 1;
            } else if(cmp < 0) {
                low = mid + 1;
            }
        }
        return -1;
    }
    
    private int compareToBucket(int bucket, int needle) {
        int low = bounds[bucket];
        int high = low + step;
        if (low <= needle && high > needle) {
            return 0;
        } else if(low > needle) {
            return 1;
        } else {
            return -1;
        }
    }
}

@@ -169,16 +169,174 @@
 istogram
+. Values are bucketed%0A * by a configurable bound (e.g., 0-1, 1-2, 2-3). When a value is inserted,%0A * perform a binary search to find the correct bucket.%0A *%0A *
 %0A */%0A@No
@@ -544,50 +544,139 @@
   * 
-%0A     * @param nBuckets%0A     * @param step
+Initialize an empty histogram%0A     *%0A     * @param nBuckets The number of buckets to use%0A     * @param step The size of each bucket
 %0A   
@@ -1083,24 +1083,79 @@
  /**%0A     * 
+Reset the histogram back to empty (set all values to 0)
 %0A     */%0A   
@@ -1254,27 +1254,201 @@
   * 
-%0A     * @param data
+Insert a value into the right bucket of the histogram. If the value is%0A     * larger than any bound, insert into the last bucket%0A     *%0A     * @param data The value to insert into the histogram
 %0A   
@@ -1598,28 +1598,263 @@
 ze++;%0A    %7D%0A
+%0A
     
+/**%0A     * Find the a value %3Cem%3En%3C/em%3E such that the percentile falls within%0A     * %5B%3Cem%3En%3C/em%3E, %3Cem%3En + step%3C/em%3E)%0A     *%0A     * @param quantile The percentile to find%0A     * @return Lower bound associated with the percentile%0A     */
 %0A    public 
@@ -2880,17 +2880,16 @@
       if
- 
 (low %3C= 

Document the Histogram class