001package io.prometheus.metrics.model.snapshots;
002
003import java.util.ArrayList;
004import java.util.Arrays;
005import java.util.Collections;
006import java.util.Iterator;
007import java.util.List;
008import java.util.stream.Stream;
009
010/**
011 * Immutable representation of native histogram buckets.
012 *
013 * <p>The bucket index defines the boundaries of the bucket, depending on the histogram's {@link
014 * HistogramSnapshot.HistogramDataPointSnapshot#getNativeSchema() schema}.
015 *
016 * <pre>
017 *     base = 2^(2^-schema)
018 *     lower bound = base^(index - 1)
019 *     upper bound = base^index
020 * </pre>
021 */
022public class NativeHistogramBuckets implements Iterable<NativeHistogramBucket> {
023
024  public static final NativeHistogramBuckets EMPTY =
025      new NativeHistogramBuckets(new int[] {}, new long[] {});
026  private final int[] bucketIndexes; // sorted
027  private final long[] counts;
028
029  private NativeHistogramBuckets(int[] bucketIndexes, long[] counts) {
030    this.bucketIndexes = bucketIndexes;
031    this.counts = counts;
032  }
033
034  /**
035   * To create a new {@link NativeHistogramBuckets} instance, you can either use one of the static
036   * {@code of(...)} methods, or use {@link NativeHistogramBuckets#builder()}.
037   *
038   * @param bucketIndexes see class javadoc of {@link NativeHistogramBuckets}. May be empty.
039   * @param counts must have the same length as bucketIndexes
040   */
041  public static NativeHistogramBuckets of(int[] bucketIndexes, long[] counts) {
042    int[] bucketIndexesCopy = Arrays.copyOf(bucketIndexes, bucketIndexes.length);
043    long[] countsCopy = Arrays.copyOf(counts, counts.length);
044    sortAndValidate(bucketIndexesCopy, countsCopy);
045    return new NativeHistogramBuckets(bucketIndexesCopy, countsCopy);
046  }
047
048  /**
049   * To create a new {@link NativeHistogramBuckets} instance, you can either use one of the static
050   * {@code of(...)} methods, or use {@link NativeHistogramBuckets#builder()}.
051   *
052   * @param bucketIndexes see class javadoc of {@link NativeHistogramBuckets}. May be empty.
053   * @param counts must have the same size as bucketIndexes
054   */
055  public static NativeHistogramBuckets of(List<Integer> bucketIndexes, List<Long> counts) {
056    int[] bucketIndexesCopy = new int[bucketIndexes.size()];
057    for (int i = 0; i < bucketIndexes.size(); i++) {
058      bucketIndexesCopy[i] = bucketIndexes.get(i);
059    }
060    long[] countsCopy = new long[counts.size()];
061    for (int i = 0; i < counts.size(); i++) {
062      countsCopy[i] = counts.get(i);
063    }
064    sortAndValidate(bucketIndexesCopy, countsCopy);
065    return new NativeHistogramBuckets(bucketIndexesCopy, countsCopy);
066  }
067
068  public int size() {
069    return bucketIndexes.length;
070  }
071
072  private List<NativeHistogramBucket> asList() {
073    List<NativeHistogramBucket> result = new ArrayList<>(size());
074    for (int i = 0; i < bucketIndexes.length; i++) {
075      result.add(new NativeHistogramBucket(bucketIndexes[i], counts[i]));
076    }
077    return Collections.unmodifiableList(result);
078  }
079
080  @Override
081  public Iterator<NativeHistogramBucket> iterator() {
082    return asList().iterator();
083  }
084
085  public Stream<NativeHistogramBucket> stream() {
086    return asList().stream();
087  }
088
089  public int getBucketIndex(int i) {
090    return bucketIndexes[i];
091  }
092
093  public long getCount(int i) {
094    return counts[i];
095  }
096
097  private static void sortAndValidate(int[] bucketIndexes, long[] counts) {
098    if (bucketIndexes.length != counts.length) {
099      throw new IllegalArgumentException(
100          "bucketIndexes.length == "
101              + bucketIndexes.length
102              + " but counts.length == "
103              + counts.length
104              + ". Expected the same length.");
105    }
106    sort(bucketIndexes, counts);
107    validate(bucketIndexes, counts);
108  }
109
110  private static void sort(int[] bucketIndexes, long[] counts) {
111    // Bubblesort. Should be efficient here as in most cases bucketIndexes is already sorted.
112    int n = bucketIndexes.length;
113    for (int i = 0; i < n - 1; i++) {
114      for (int j = 0; j < n - i - 1; j++) {
115        if (bucketIndexes[j] > bucketIndexes[j + 1]) {
116          swap(j, j + 1, bucketIndexes, counts);
117        }
118      }
119    }
120  }
121
122  private static void swap(int i, int j, int[] bucketIndexes, long[] counts) {
123    int tmpInt = bucketIndexes[j];
124    bucketIndexes[j] = bucketIndexes[i];
125    bucketIndexes[i] = tmpInt;
126    long tmpLong = counts[j];
127    counts[j] = counts[i];
128    counts[i] = tmpLong;
129  }
130
131  private static void validate(int[] bucketIndexes, long[] counts) {
132    // Preconditions:
133    // * bucketIndexes sorted
134    // * bucketIndexes and counts have the same length
135    for (int i = 0; i < bucketIndexes.length; i++) {
136      if (counts[i] < 0) {
137        throw new IllegalArgumentException("Bucket counts cannot be negative.");
138      }
139      if (i > 0) {
140        if (bucketIndexes[i - 1] == bucketIndexes[i]) {
141          throw new IllegalArgumentException("Duplicate bucket index " + bucketIndexes[i]);
142        }
143      }
144    }
145  }
146
147  public static Builder builder() {
148    return new Builder();
149  }
150
151  public static class Builder {
152
153    private final List<Integer> bucketIndexes = new ArrayList<>();
154    private final List<Long> counts = new ArrayList<>();
155
156    private Builder() {}
157
158    /** Add a native histogram bucket. Call multiple times to add multiple buckets. */
159    public Builder bucket(int bucketIndex, long count) {
160      bucketIndexes.add(bucketIndex);
161      counts.add(count);
162      return this;
163    }
164
165    public NativeHistogramBuckets build() {
166      return NativeHistogramBuckets.of(bucketIndexes, counts);
167    }
168  }
169}