content: /*
   * Copyright (C) 2019 The Android Open Source Project
   *
   * Licensed under the Apache License, Version 2.0 (the "License");
   * you may not use this file except in compliance with the License.
   * You may obtain a copy of the License at
   *
   *      http://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  
  package com.android.server.wifi.util;
  
  import android.annotation.NonNull;
  import android.util.SparseIntArray;
  
  import com.android.server.wifi.nano.WifiMetricsProto.HistogramBucketInt32;
  
  import java.lang.reflect.Array;
  import java.util.Arrays;
  import java.util.Iterator;
  
  
  /**
   * A histogram that stores the counts of values that fall within buckets, where buckets contain
   * the count for a range of values. This implementation is backed by a SparseIntArray, meaning
   * values are stored as int and counts are stored as int.
   */
  public class IntHistogram implements Iterable<IntHistogram.Bucket> {
      /*
       * Definitions:
       * - value: what you would like to count
       * - count: the number of occurrences of values that fall within a bucket
       * - key: mBuckets maps key => count, 0 <= key <= mBucketBoundaries.length, keys can be
       *        uninitialized for buckets that were never incremented
       * - bucketIndex: the index of the initialized buckets, 0 <= bucketIndex < mBucket.size(),
       *        all indices in this range are initialized.
       */
      private SparseIntArray mBuckets;
      private final int[] mBucketBoundaries;
  
      /**
       * A bucket in the histogram, for the range [start, end).
       * An exception to this is when {@link Bucket#end} == Integer.MAX_VALUE, when the range will be
       * [start, end].
       */
      public static class Bucket {
          public int start;
          public int end;
          public int count;
  
          public Bucket(int start, int end, int count) {
              this.start = start;
              this.end = end;
              this.count = count;
          }
      }
  
      /**
       * Constructs a histogram given the boundary values of buckets, as an int[].
       * @param bucketBoundaries The boundary values that separate each bucket. The number of
       *                         buckets is bucketBoundaries.length + 1, where the buckets are:
       *                         - < bucketBoundaries[0]
       *                         - [bucketBoundaries[0], bucketBoundaries[1])
       *                         ...
       *                         - >= bucketBoundaries[bucketBoundaries.length() - 1]
       *                         This array must be non-null, non-empty, and strictly monotonically
       *                         increasing i.e. a[i] < a[i+1].
       */
      public IntHistogram(@NonNull int[] bucketBoundaries) {
          if (bucketBoundaries == null || bucketBoundaries.length == 0) {
              throw new IllegalArgumentException("bucketBoundaries must be non-null and non-empty!");
          }
          for (int i = 0; i < bucketBoundaries.length - 1; i++) {
              int cur = bucketBoundaries[i];
              int next = bucketBoundaries[i + 1];
              if (cur >= next) {
                  throw new IllegalArgumentException(String.format(
                          "bucketBoundaries values must be strictly monotonically increasing, but "
                                  + "value %d at index %d is greater or equal to "
                                  + "value %d at index %d!",
                          cur, i, next, i + 1));
              }
          }
          mBucketBoundaries = bucketBoundaries.clone();
          mBuckets = new SparseIntArray();
      }
  
      /**
       * Resets this histogram to the initial state.
       */
      public void clear() {
          mBuckets.clear();
      }
  
      /**
       * Returns the number of non-empty buckets, where an empty bucket is a bucket that was never
       * added to.
       */
      public int numNonEmptyBuckets() {
          return mBuckets.size();
      }
  
      /**
       * Returns the maximum number of possible buckets (dictated by the number of bucket boundaries).
       */
      public int numTotalBuckets() {
          return mBucketBoundaries.length + 1;
      }
  
      /**
       * Gets the nth non-empty bucket, where 0 <= n < {@link #numNonEmptyBuckets()}
       */
      public Bucket getBucketByIndex(int bucketIndex) {
          int bucketKey = mBuckets.keyAt(bucketIndex);
          int start = bucketKey == 0
                  ? Integer.MIN_VALUE : mBucketBoundaries[bucketKey - 1];
          int end = bucketKey == mBucketBoundaries.length
                  ? Integer.MAX_VALUE : mBucketBoundaries[bucketKey];
          int count = mBuckets.valueAt(bucketIndex);
          return new Bucket(start, end, count);
      }
  
      /**
       * Increments the count of the bucket that this value falls into by 1.
       */
      public void increment(int value) {
          add(value, 1);
      }
  
      /**
       * Increments the count of the bucket that this value falls into by <code>count</code>.
       */
      public void add(int value, int count) {
          int bucketKey = getBucketKey(value);
          int curBucketValue = mBuckets.get(bucketKey);
          mBuckets.put(bucketKey, curBucketValue + count);
      }
  
      /**
       * Given a value, returns the key of the bucket where it should fall into.
       */
      private int getBucketKey(int value) {
          // this passes unit tests, so don't worry about it too much
          int insertionIndex = Arrays.binarySearch(mBucketBoundaries, value);
          return Math.abs(insertionIndex + 1);
      }
  
      /**
       * Returns a human-readable string representation of the contents of this histogram, suitable
       * for dump().
       */
      @Override
      public String toString() {
          if (mBuckets.size() <= 0) {
              return "{}";
          }
  
          StringBuilder sb = new StringBuilder();
          sb.append('{');
          for (int bucketIndex = 0; bucketIndex < mBuckets.size(); ++bucketIndex) {
              if (bucketIndex > 0) {
                  sb.append(", ");
              }
              int bucketKey = mBuckets.keyAt(bucketIndex);
              sb.append('[');
              if (bucketKey == 0) {
                  sb.append("Integer.MIN_VALUE");
              } else {
                  sb.append(mBucketBoundaries[bucketKey - 1]);
              }
              sb.append(',');
              if (bucketKey == mBucketBoundaries.length) {
                  sb.append("Integer.MAX_VALUE]");
              } else {
                  sb.append(mBucketBoundaries[bucketKey]).append(')');
              }
              sb.append('=').append(mBuckets.valueAt(bucketIndex));
          }
          sb.append('}');
          return sb.toString();
      }
  
      /**
       * Iterates over initialized buckets.
       */
      @Override
      public Iterator<Bucket> iterator() {
          return new Iterator<Bucket>() {
              private int mBucketIndex = 0;
  
              @Override
              public boolean hasNext() {
                  return mBucketIndex < mBuckets.size();
              }
  
              @Override
              public Bucket next() {
                  Bucket bucket = getBucketByIndex(mBucketIndex);
                  mBucketIndex++;
                  return bucket;
              }
          };
      }
  
      /**
       * For backwards compatibility, can specify a conversion function that converts a bucket in this
       * histogram to a specified Protobuf type, used by {@link #toProto(Class, ProtobufConverter)}.
       * Note that for all new histograms, the standard Protobuf representation type is
       * {@link HistogramBucketInt32[]}, which can be generated using {@link #toProto()}.
       * @param <T> The type to convert to.
       */
      public interface ProtobufConverter<T> {
          /**
           * Conversion function.
           * @param start start of the range of a bucket.
           * @param end end of the range of a bucket.
           * @param count count of values in this bucket.
           * @return A Protobuf representation of this bucket.
           */
          T convert(int start, int end, int count);
      }
  
      /**
       * Converts this histogram to a Protobuf representation. See {@link ProtobufConverter}
       * @param protoClass the class object for the Protobuf type.
       * @param converter a conversion function.
       * @param <T> the type of the Protobuf output.
       * @return an array of Protobuf representation of buckets generated by the converter function.
       */
      public <T> T[] toProto(Class<T> protoClass, ProtobufConverter<T> converter) {
          @SuppressWarnings("unchecked")
          T[] output = (T[]) Array.newInstance(protoClass, mBuckets.size());
          int i = 0;
          for (Bucket bucket : this) {
              output[i] = converter.convert(bucket.start, bucket.end, bucket.count);
              i++;
          }
          return output;
      }
  
      /**
       * Converts this histogram to a standard Protobuf representation.
       */
      public HistogramBucketInt32[] toProto() {
          return toProto(HistogramBucketInt32.class, (start, end, count) -> {
              HistogramBucketInt32 hb = new HistogramBucketInt32();
              hb.start = start;
              hb.end = end;
              hb.count = count;
              return hb;
          });
      }
  }
  