001package org.javasimon.callback.quantiles;
002
003/**
004 * Linearly organized {@link Buckets}.
005 * For 100-600 range and 5 bucket count, the following buckets are created:
006 * <table>
007 * <tr>
008 * <th>Index</th>
009 * <th>Min</th><th>Max</th>
010 * <th>Samples</th>
011 * <th>Counter</th>
012 * </tr>
013 * <tr>
014 * <td>0</td>
015 * <td>-&infin;</td><td>100</td>
016 * <td>53</td>
017 * <td># (1)</td>
018 * </tr>
019 * <tr>
020 * <td>1</td>
021 * <td>100</td><td>200</td>
022 * <td>128,136</td>
023 * <td>## (2)</td>
024 * </tr>
025 * <tr>
026 * <td>2</td>
027 * <td>200</td><td>300</td>
028 * <td>245,231,264,287,275</td>
029 * <td>###### (5)</td>
030 * </tr>
031 * <tr>
032 * <td>3</td>
033 * <td>300</td><td>400</td>
034 * <td>356,341</td>
035 * <td>## (2)</td>
036 * </tr>
037 * <tr>
038 * <td>4</td>
039 * <td>400</td><td>500</td>
040 * <td>461</td>
041 * <td># (1)</td>
042 * </tr>
043 * <tr>
044 * <td>5</td>
045 * <td>500</td><td>600</td>
046 * <td>801</td>
047 * <td># (1)</td>
048 * </tr>
049 * <tr>
050 * <td>6</td>
051 * <td>600</td><td>+&infin;</td>
052 * <td></td>
053 * <td>(0)</td>
054 * </tr>
055 * </table>
056 * For a total of 12 splits in this example, we can deduce that
057 * <ul><li>Median (6th sample) is in bucket #2
058 * <li>Third quartile (9th sample) is in bucket #3</li>
059 * <li>90% percentile (10,8th sample) is in bucket #4 or #5 (but assume #4).</li>
060 * </ul>
061 *
062 * @author Gérald Quintana
063 * @author Alexej Vlasov
064 */
065public class LinearBuckets extends Buckets {
066        /**
067         * Constructor
068         *
069         * @param min Duration min (lower bound of all buckets)
070         * @param max Duration max (upper bound of all buckets)
071         * @param bucketNb Number of buckets between min and max
072         */
073        public LinearBuckets(long min, long max, int bucketNb) {
074                super(min, max, bucketNb);
075                long width = (max - min) / bucketNb;
076                long currentMin, currentMax = min;
077                for (int i = 1; i <= bucketNb; i++) {
078                        currentMin = currentMax;
079                        currentMax = currentMin + width;
080                        buckets[i] = new Bucket(currentMin, currentMax);
081                }
082        }
083
084        /**
085         * {@inheritDoc}
086         * <p/>
087         * Override the base method making it generally faster thanks to linear regression.
088         */
089        protected Bucket getBucketForValue(long value) {
090                Bucket bucket;
091                if (value < min) {
092                        bucket = buckets[0];
093                } else {
094                        if (value >= max) {
095                                bucket = buckets[bucketNb + 1];
096                        } else {
097                                // Linear interpolation
098                                int bucketIndex = 1 + (int) ((value - min) * (bucketNb - 1) / (max - min));
099                                bucket = buckets[bucketIndex];
100                                // As the division above was round at floor, bucket may be the next one
101                                if (value > bucket.getMax()) {
102                                        bucketIndex++;
103                                        bucket = buckets[bucketIndex];
104                                }
105                        }
106                }
107                return bucket;
108        }
109}