package io.prometheus.metrics.model.snapshots;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.stream.Stream;

/**
 * Immutable representation of native histogram buckets.
 * <p>
 * The bucket index defines the boundaries of the bucket,
 * depending on the histogram's {@link HistogramSnapshot.HistogramDataPointSnapshot#getNativeSchema() schema}.
 * <pre>
 *     base = 2^(2^-schema)
 *     lower bound = base^(index - 1)
 *     upper bound = base^index
 * </pre>
 */
public class NativeHistogramBuckets implements Iterable<NativeHistogramBucket> {

    public static final NativeHistogramBuckets EMPTY = new NativeHistogramBuckets(new int[]{}, new long[]{});
    private final int[] bucketIndexes; // sorted
    private final long[] counts;

    private NativeHistogramBuckets(int[] bucketIndexes, long[] counts) {
        this.bucketIndexes = bucketIndexes;
        this.counts = counts;
    }

    /**
     * To create a new {@link NativeHistogramBuckets} instance, you can either use one of the static {@code of(...)}
     * methods, or use {@link NativeHistogramBuckets#builder()}.
     * @param bucketIndexes see class javadoc of {@link NativeHistogramBuckets}. May be empty.
     * @param counts must have the same length as bucketIndexes
     */
    public static NativeHistogramBuckets of(int[] bucketIndexes, long[] counts) {
        int[] bucketIndexesCopy = Arrays.copyOf(bucketIndexes, bucketIndexes.length);
        long[] countsCopy = Arrays.copyOf(counts, counts.length);
        sortAndValidate(bucketIndexesCopy, countsCopy);
        return new NativeHistogramBuckets(bucketIndexesCopy, countsCopy);
    }

    /**
     * To create a new {@link NativeHistogramBuckets} instance, you can either use one of the static {@code of(...)}
     * methods, or use {@link NativeHistogramBuckets#builder()}.
     * @param bucketIndexes see class javadoc of {@link NativeHistogramBuckets}. May be empty.
     * @param counts must have the same size as bucketIndexes
     */
    public static NativeHistogramBuckets of(List<Integer> bucketIndexes, List<Long> counts) {
        int[] bucketIndexesCopy = new int[bucketIndexes.size()];
        for (int i=0; i<bucketIndexes.size(); i++) {
            bucketIndexesCopy[i] = bucketIndexes.get(i);
        }
        long[] countsCopy = new long[counts.size()];
        for (int i=0; i<counts.size(); i++) {
            countsCopy[i] = counts.get(i);
        }
        sortAndValidate(bucketIndexesCopy, countsCopy);
        return new NativeHistogramBuckets(bucketIndexesCopy, countsCopy);
    }

    public int size() {
        return bucketIndexes.length;
    }

    private List<NativeHistogramBucket> asList() {
        List<NativeHistogramBucket> result = new ArrayList<>(size());
        for (int i=0; i<bucketIndexes.length; i++) {
            result.add(new NativeHistogramBucket(bucketIndexes[i], counts[i]));
        }
        return Collections.unmodifiableList(result);
    }

    @Override
    public Iterator<NativeHistogramBucket> iterator() {
        return asList().iterator();
    }

    public Stream<NativeHistogramBucket> stream() {
        return asList().stream();
    }

    public int getBucketIndex(int i) {
        return bucketIndexes[i];
    }

    public long getCount(int i) {
        return counts[i];
    }

    private static void sortAndValidate(int[] bucketIndexes, long[] counts) {
        if (bucketIndexes.length != counts.length) {
            throw new IllegalArgumentException("bucketIndexes.length == " + bucketIndexes.length + " but counts.length == " + counts.length + ". Expected the same length.");
        }
        sort(bucketIndexes, counts);
        validate(bucketIndexes, counts);
    }

    private static void sort(int[] bucketIndexes, long[] counts) {
        // Bubblesort. Should be efficient here as in most cases bucketIndexes is already sorted.
        int n = bucketIndexes.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (bucketIndexes[j] > bucketIndexes[j + 1]) {
                    swap(j, j+1, bucketIndexes, counts);
                }
            }
        }
    }

    private static void swap(int i, int j, int[] bucketIndexes, long[] counts) {
        int tmpInt = bucketIndexes[j];
        bucketIndexes[j] = bucketIndexes[i];
        bucketIndexes[i] = tmpInt;
        long tmpLong = counts[j];
        counts[j] = counts[i];
        counts[i] = tmpLong;
    }

    private static void validate(int[] bucketIndexes, long[] counts) {
        // Preconditions:
        // * bucketIndexes sorted
        // * bucketIndexes and counts have the same length
        for (int i=0; i<bucketIndexes.length; i++) {
            if (counts[i] < 0) {
                throw new IllegalArgumentException("Bucket counts cannot be negative.");
            }
            if (i > 0) {
                if (bucketIndexes[i-1] == bucketIndexes[i]) {
                    throw new IllegalArgumentException("Duplicate bucket index " + bucketIndexes[i]);
                }
            }
        }
    }

    public static Builder builder() {
        return new Builder();
    }

    public static class Builder {

        private final List<Integer> bucketIndexes = new ArrayList<>();
        private final List<Long> counts = new ArrayList<>();

        private Builder() {}

        /**
         * Add a native histogram bucket. Call multiple times to add multiple buckets.
         */
        public Builder bucket(int bucketIndex, long count) {
            bucketIndexes.add(bucketIndex);
            counts.add(count);
            return this;
        }

        public NativeHistogramBuckets build() {
            return NativeHistogramBuckets.of(bucketIndexes, counts);
        }
    }
}