1/*
2 * Copyright (C) 2017 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16package com.android.internal.util;
17
18import android.annotation.IntRange;
19import android.annotation.NonNull;
20import android.annotation.Nullable;
21import android.util.Log;
22
23import java.util.Arrays;
24
25/**
26 * A histogram for positive integers where each bucket is twice the size of the previous one.
27 */
28public class ExponentiallyBucketedHistogram {
29    @NonNull
30    private final int[] mData;
31
32    /**
33     * Create a new histogram.
34     *
35     * @param numBuckets The number of buckets. The highest bucket is for all value >=
36     *                   2<sup>numBuckets - 1</sup>
37     */
38    public ExponentiallyBucketedHistogram(@IntRange(from = 1, to = 31) int numBuckets) {
39        numBuckets = Preconditions.checkArgumentInRange(numBuckets, 1, 31, "numBuckets");
40
41        mData = new int[numBuckets];
42    }
43
44    /**
45     * Add a new value to the histogram.
46     *
47     * All values <= 0 are in the first bucket. The last bucket contains all values >=
48     * 2<sup>numBuckets - 1</sup>
49     *
50     * @param value The value to add
51     */
52    public void add(int value) {
53        if (value <= 0) {
54            mData[0]++;
55        } else {
56            mData[Math.min(mData.length - 1, 32 - Integer.numberOfLeadingZeros(value))]++;
57        }
58    }
59
60    /**
61     * Clear all data from the histogram
62     */
63    public void reset() {
64        Arrays.fill(mData, 0);
65    }
66
67    /**
68     * Write the histogram to the log.
69     *
70     * @param tag    The tag to use when logging
71     * @param prefix A custom prefix that is printed in front of the histogram
72     */
73    public void log(@NonNull String tag, @Nullable CharSequence prefix) {
74        StringBuilder builder = new StringBuilder(prefix);
75        builder.append('[');
76
77        for (int i = 0; i < mData.length; i++) {
78            if (i != 0) {
79                builder.append(", ");
80            }
81
82            if (i < mData.length - 1) {
83                builder.append("<");
84                builder.append(1 << i);
85            } else {
86                builder.append(">=");
87                builder.append(1 << (i - 1));
88            }
89
90            builder.append(": ");
91            builder.append(mData[i]);
92        }
93        builder.append("]");
94
95        Log.d(tag, builder.toString());
96    }
97}
98