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 container for histogram buckets with fixed bucket boundaries. Note that the counts are
012 * <i>not</i> cumulative.
013 */
014public class ClassicHistogramBuckets implements Iterable<ClassicHistogramBucket> {
015
016  /** Used in native histograms to indicate that no classic histogram buckets are present. */
017  public static final ClassicHistogramBuckets EMPTY =
018      new ClassicHistogramBuckets(new double[] {}, new long[] {});
019
020  private final double[] upperBounds;
021  private final long[] counts; // not cumulative
022
023  private ClassicHistogramBuckets(double[] upperBounds, long[] counts) {
024    this.upperBounds = upperBounds;
025    this.counts = counts;
026  }
027
028  /**
029   * To create new {@link ClassicHistogramBuckets}, you can either use one of the static {@code
030   * of(...)} methods, or use {@link ClassicHistogramBuckets#builder()}.
031   *
032   * <p>This method will create a copy of upperBounds and counts.
033   *
034   * @param upperBounds must have the same length as counts. Must not contain duplicates. Must
035   *     contain at least {@link Double#POSITIVE_INFINITY} for the {@code +Inf} bucket. An upper
036   *     bound must not be {@link Double#NaN}. The upperBounds array does not need to be sorted.
037   * @param counts must have the same length as {@code upperBounds}. The entry at index {@code i} is
038   *     the count for the {@code upperBounds} at index {@code i}. For each count, {@link
039   *     Number#longValue()} is called to get the value. Counts are <i>not</i> cumulative. Counts
040   *     must not be negative.
041   */
042  public static ClassicHistogramBuckets of(
043      List<Double> upperBounds, List<? extends Number> counts) {
044    double[] upperBoundsCopy = new double[upperBounds.size()];
045    for (int i = 0; i < upperBounds.size(); i++) {
046      upperBoundsCopy[i] = upperBounds.get(i);
047    }
048    long[] countsCopy = new long[counts.size()];
049    for (int i = 0; i < counts.size(); i++) {
050      countsCopy[i] = counts.get(i).longValue();
051    }
052    sortAndValidate(upperBoundsCopy, countsCopy);
053    return new ClassicHistogramBuckets(upperBoundsCopy, countsCopy);
054  }
055
056  /**
057   * To create new {@link ClassicHistogramBuckets}, you can either use one of the static {@code
058   * of(...)} methods, or use {@link ClassicHistogramBuckets#builder()}.
059   *
060   * <p>This method will create a copy of upperBounds and counts.
061   *
062   * @param upperBounds must have the same length as counts. Must not contain duplicates. Must
063   *     contain at least {@link Double#POSITIVE_INFINITY} for the {@code +Inf} bucket. An upper
064   *     bound must not be {@link Double#NaN}. The upperBounds array does not need to be sorted.
065   * @param counts must have the same length as {@code upperBounds}. The entry at index {@code i} is
066   *     the count for the {@code upperBounds} at index {@code i}. For each count, {@link
067   *     Number#longValue()} is called to get the value. Counts are <i>not</i> cumulative. Counts
068   *     must not be negative.
069   */
070  public static ClassicHistogramBuckets of(double[] upperBounds, Number[] counts) {
071    double[] upperBoundsCopy = Arrays.copyOf(upperBounds, upperBounds.length);
072    long[] countsCopy = new long[counts.length];
073    for (int i = 0; i < counts.length; i++) {
074      countsCopy[i] = counts[i].longValue();
075    }
076    sortAndValidate(upperBoundsCopy, countsCopy);
077    return new ClassicHistogramBuckets(upperBoundsCopy, countsCopy);
078  }
079
080  /**
081   * To create new {@link ClassicHistogramBuckets}, you can either use one of the static {@code
082   * of(...)} methods, or use {@link ClassicHistogramBuckets#builder()}.
083   *
084   * <p>This method will create a copy of upperBounds and counts.
085   *
086   * @param upperBounds must have the same length as counts. Must not contain duplicates. Must
087   *     contain at least {@link Double#POSITIVE_INFINITY} for the {@code +Inf} bucket. An upper
088   *     bound must not be {@link Double#NaN}. The upperBounds array does not need to be sorted.
089   * @param counts must have the same length as {@code upperBounds}. The entry at index {@code i} is
090   *     the count for the {@code upperBounds} at index {@code i}. Counts are <i>not</i> cumulative.
091   *     Counts must not be negative.
092   */
093  public static ClassicHistogramBuckets of(double[] upperBounds, long[] counts) {
094    double[] upperBoundsCopy = Arrays.copyOf(upperBounds, upperBounds.length);
095    long[] countsCopy = Arrays.copyOf(counts, counts.length);
096    sortAndValidate(upperBoundsCopy, countsCopy);
097    return new ClassicHistogramBuckets(upperBoundsCopy, countsCopy);
098  }
099
100  private static void sortAndValidate(double[] upperBounds, long[] counts) {
101    if (upperBounds.length != counts.length) {
102      throw new IllegalArgumentException(
103          "upperBounds.length == "
104              + upperBounds.length
105              + " but counts.length == "
106              + counts.length
107              + ". Expected the same length.");
108    }
109    sort(upperBounds, counts);
110    validate(upperBounds, counts);
111  }
112
113  private static void sort(double[] upperBounds, long[] counts) {
114    // Bubblesort. Should be efficient here as in most cases upperBounds is already sorted.
115    int n = upperBounds.length;
116    for (int i = 0; i < n - 1; i++) {
117      for (int j = 0; j < n - i - 1; j++) {
118        if (upperBounds[j] > upperBounds[j + 1]) {
119          swap(j, j + 1, upperBounds, counts);
120        }
121      }
122    }
123  }
124
125  private static void swap(int i, int j, double[] upperBounds, long[] counts) {
126    double tmpDouble = upperBounds[j];
127    upperBounds[j] = upperBounds[i];
128    upperBounds[i] = tmpDouble;
129    long tmpLong = counts[j];
130    counts[j] = counts[i];
131    counts[i] = tmpLong;
132  }
133
134  private static void validate(double[] upperBounds, long[] counts) {
135    // Preconditions:
136    // * upperBounds sorted
137    // * upperBounds and counts have the same length
138    if (upperBounds.length == 0) {
139      throw new IllegalArgumentException(
140          ClassicHistogramBuckets.class.getSimpleName()
141              + " cannot be empty. They must contain at least the +Inf bucket.");
142    }
143    if (upperBounds[upperBounds.length - 1] != Double.POSITIVE_INFINITY) {
144      throw new IllegalArgumentException(
145          ClassicHistogramBuckets.class.getSimpleName() + " must contain the +Inf bucket.");
146    }
147    for (int i = 0; i < upperBounds.length; i++) {
148      if (Double.isNaN(upperBounds[i])) {
149        throw new IllegalArgumentException(
150            "Cannot use NaN as an upper bound in " + ClassicHistogramBuckets.class.getSimpleName());
151      }
152      if (counts[i] < 0) {
153        throw new IllegalArgumentException(
154            "Counts in " + ClassicHistogramBuckets.class.getSimpleName() + " cannot be negative.");
155      }
156      if (i > 0) {
157        if (upperBounds[i - 1] == upperBounds[i]) {
158          throw new IllegalArgumentException("Duplicate upper bound " + upperBounds[i]);
159        }
160      }
161    }
162  }
163
164  public int size() {
165    return upperBounds.length;
166  }
167
168  public double getUpperBound(int i) {
169    return upperBounds[i];
170  }
171
172  /** The count is <i>not</i> cumulative. */
173  public long getCount(int i) {
174    return counts[i];
175  }
176
177  public boolean isEmpty() {
178    return this.upperBounds.length == 0;
179  }
180
181  private List<ClassicHistogramBucket> asList() {
182    List<ClassicHistogramBucket> result = new ArrayList<>(size());
183    for (int i = 0; i < upperBounds.length; i++) {
184      result.add(new ClassicHistogramBucket(upperBounds[i], counts[i]));
185    }
186    return Collections.unmodifiableList(result);
187  }
188
189  @Override
190  public Iterator<ClassicHistogramBucket> iterator() {
191    return asList().iterator();
192  }
193
194  public Stream<ClassicHistogramBucket> stream() {
195    return asList().stream();
196  }
197
198  /**
199   * To create new {@link ClassicHistogramBuckets}, you can either use one of the static {@code
200   * of(...)} methods, or use {@code builder()}.
201   */
202  public static Builder builder() {
203    return new Builder();
204  }
205
206  public static class Builder {
207    private final List<Double> upperBounds = new ArrayList<>();
208    private final List<Long> counts = new ArrayList<>();
209
210    private Builder() {}
211
212    /** Must be called at least once for the {@link Double#POSITIVE_INFINITY} bucket. */
213    public Builder bucket(double upperBound, long count) {
214      upperBounds.add(upperBound);
215      counts.add(count);
216      return this;
217    }
218
219    /**
220     * Will throw an {@link IllegalArgumentException} if the {@link Double#POSITIVE_INFINITY} bucket
221     * is missing.
222     */
223    public ClassicHistogramBuckets build() {
224      return ClassicHistogramBuckets.of(upperBounds, counts);
225    }
226  }
227}