Home | History | Annotate | Download | only in util 
      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  */
     16 package com.android.internal.util;
     17 
     18 import android.annotation.IntRange;
     19 import android.annotation.NonNull;
     20 import android.annotation.Nullable;
     21 import android.util.Log;
     22 
     23 import java.util.Arrays;
     24 
     25 /**
     26  * A histogram for positive integers where each bucket is twice the size of the previous one.
     27  */
     28 public 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