package com.thealgorithms.sorts;
import java.util.Arrays;

/**
 * SpreadSort is a highly efficient sorting algorithm suitable for large datasets.
 * It distributes elements into buckets and recursively sorts these buckets.
 * This implementation is generic and can sort any array of elements that extend Comparable.
 */
public class SpreadSort implements SortAlgorithm {
    private static final int MAX_INSERTION_SORT_THRESHOLD = 1000;
    private static final int MAX_INITIAL_BUCKET_CAPACITY = 1000;
    private static final int MAX_MIN_BUCKETS = 100;

    private final int insertionSortThreshold;
    private final int initialBucketCapacity;
    private final int minBuckets;

    /**
     * Constructor to initialize the SpreadSort algorithm with custom parameters.
     *
     * @param insertionSortThreshold the threshold for using insertion sort for small segments (1-1000)
     * @param initialBucketCapacity  the initial capacity for each bucket (1-1000)
     * @param minBuckets             the minimum number of buckets to use (1-100)
     */
    public SpreadSort(int insertionSortThreshold, int initialBucketCapacity, int minBuckets) {
        if (insertionSortThreshold < 1 || insertionSortThreshold > MAX_INSERTION_SORT_THRESHOLD) {
            throw new IllegalArgumentException("Insertion sort threshold must be between 1 and " + MAX_INSERTION_SORT_THRESHOLD);
        }
        if (initialBucketCapacity < 1 || initialBucketCapacity > MAX_INITIAL_BUCKET_CAPACITY) {
            throw new IllegalArgumentException("Initial bucket capacity must be between 1 and " + MAX_INITIAL_BUCKET_CAPACITY);
        }
        if (minBuckets < 1 || minBuckets > MAX_MIN_BUCKETS) {
            throw new IllegalArgumentException("Minimum number of buckets must be between 1 and " + MAX_MIN_BUCKETS);
        }

        this.insertionSortThreshold = insertionSortThreshold;
        this.initialBucketCapacity = initialBucketCapacity;
        this.minBuckets = minBuckets;
    }

    /**
     * Default constructor with predefined values.
     */
    public SpreadSort() {
        this(16, 16, 2);
    }

    /**
     * Sorts an array using the SpreadSort algorithm.
     *
     * @param array the array to be sorted
     * @param <T>   the type of elements in the array
     * @return the sorted array
     */
    @Override
    public <T extends Comparable<T>> T[] sort(T[] array) {
        if (array.length == 0) {
            return array;
        }
        spreadSort(array, 0, array.length - 1);
        return array;
    }

    /**
     * Internal method to sort an array segment using the SpreadSort algorithm.
     *
     * @param array the array to be sorted
     * @param left  the left boundary of the segment
     * @param right the right boundary of the segment
     * @param <T>   the type of elements in the array
     */
    private <T extends Comparable<T>> void spreadSort(final T[] array, final int left, final int right) {
        if (left >= right) {
            return;
        }

        // Base case for small segments
        if (right - left < insertionSortThreshold) {
            insertionSort(array, left, right);
            return;
        }

        T min = findMin(array, left, right);
        T max = findMax(array, left, right);

        if (min.equals(max)) {
            return; // All elements are the same
        }

        int numBuckets = calculateNumBuckets(right - left + 1);
        final Bucket<T>[] buckets = createBuckets(numBuckets);

        distributeElements(array, left, right, min, max, numBuckets, buckets);
        collectElements(array, left, buckets);
    }

    /**
     * Finds the minimum element in the specified segment of the array.
     *
     * @param array the array to search
     * @param left  the left boundary of the segment
     * @param right the right boundary of the segment
     * @param <T>   the type of elements in the array
     * @return the minimum element
     */
    private <T extends Comparable<T>> T findMin(final T[] array, final int left, final int right) {
        T min = array[left];
        for (int i = left + 1; i <= right; i++) {
            if (SortUtils.less(array[i], min)) {
                min = array[i];
            }
        }
        return min;
    }

    /**
     * Finds the maximum element in the specified segment of the array.
     *
     * @param array the array to search
     * @param left  the left boundary of the segment
     * @param right the right boundary of the segment
     * @param <T>   the type of elements in the array
     * @return the maximum element
     */
    private <T extends Comparable<T>> T findMax(final T[] array, final int left, final int right) {
        T max = array[left];
        for (int i = left + 1; i <= right; i++) {
            if (SortUtils.greater(array[i], max)) {
                max = array[i];
            }
        }
        return max;
    }

    /**
     * Calculates the number of buckets needed based on the size of the segment.
     *
     * @param segmentSize the size of the segment
     * @return the number of buckets
     */
    private int calculateNumBuckets(final int segmentSize) {
        int numBuckets = segmentSize / insertionSortThreshold;
        return Math.max(numBuckets, minBuckets);
    }

    /**
     * Creates an array of buckets.
     *
     * @param numBuckets the number of buckets to create
     * @param <T>        the type of elements in the buckets
     * @return an array of buckets
     */
    @SuppressWarnings("unchecked")
    private <T extends Comparable<T>> Bucket<T>[] createBuckets(final int numBuckets) {
        final Bucket<T>[] buckets = new Bucket[numBuckets];
        for (int i = 0; i < numBuckets; i++) {
            buckets[i] = new Bucket<>(initialBucketCapacity);
        }
        return buckets;
    }

    /**
     * Distributes elements of the array segment into buckets.
     *
     * @param array      the array to be sorted
     * @param left       the left boundary of the segment
     * @param right      the right boundary of the segment
     * @param min        the minimum element in the segment
     * @param max        the maximum element in the segment
     * @param numBuckets the number of buckets
     * @param buckets    the array of buckets
     * @param <T>        the type of elements in the array
     */
    private <T extends Comparable<T>> void distributeElements(final T[] array, final int left, final int right, final T min, final T max, final int numBuckets, final Bucket<T>[] buckets) {
        final double range = max.compareTo(min);
        for (int i = left; i <= right; i++) {
            final int scaleRangeDifference = array[i].compareTo(min) * numBuckets;
            int bucketIndex = (int) (scaleRangeDifference / (range + 1));
            buckets[bucketIndex].add(array[i]);
        }
    }

    /**
     * Collects elements from the buckets back into the array.
     *
     * @param array   the array to be sorted
     * @param left    the left boundary of the segment
     * @param buckets the array of buckets
     * @param <T>     the type of elements in the array
     */
    private <T extends Comparable<T>> void collectElements(final T[] array, final int left, final Bucket<T>[] buckets) {
        int index = left;
        for (Bucket<T> bucket : buckets) {
            if (bucket.size() > 0) {
                T[] bucketArray = bucket.toArray();
                spreadSort(bucketArray, 0, bucketArray.length - 1);
                for (T element : bucketArray) {
                    array[index++] = element;
                }
            }
        }
    }

    /**
     * Insertion sort implementation for small segments.
     *
     * @param array the array to be sorted
     * @param left  the left boundary of the segment
     * @param right the right boundary of the segment
     * @param <T>   the type of elements in the array
     */
    private <T extends Comparable<T>> void insertionSort(final T[] array, final int left, final int right) {
        for (int i = left + 1; i <= right; i++) {
            T key = array[i];
            int j = i - 1;
            while (j >= left && SortUtils.greater(array[j], key)) {
                array[j + 1] = array[j];
                j--;
            }
            array[j + 1] = key;
        }
    }

    /**
     * Bucket class to hold elements during sorting.
     *
     * @param <T> the type of elements in the bucket
     */
    private static class Bucket<T extends Comparable<T>> {
        private T[] elements;
        private int size;

        /**
         * Constructs a new bucket with initial capacity.
         */
        @SuppressWarnings("unchecked")
        Bucket(int initialBucketCapacity) {
            elements = (T[]) new Comparable[initialBucketCapacity];
            size = 0;
        }

        /**
         * Adds an element to the bucket.
         *
         * @param element the element to add
         */
        void add(T element) {
            if (size == elements.length) {
                elements = Arrays.copyOf(elements, size * 2);
            }
            elements[size++] = element;
        }

        /**
         * Returns the number of elements in the bucket.
         *
         * @return the size of the bucket
         */
        int size() {
            return size;
        }

        /**
         * Returns an array containing all elements in the bucket.
         *
         * @return an array containing all elements in the bucket
         */
        @SuppressWarnings("unchecked")
        T[] toArray() {
            return Arrays.copyOf(elements, size);
        }
    }
}