using System;
using System.Threading;
using System.Threading.Tasks;

namespace SortVisualizer;

public class RadixSort : ISortAlgorithm
{
    public string Name => "Radix Sort";
    public RadixSort() { }

    public async Task Sort(int[] array, Action refresh, int delay, Action<int> playSound, CancellationToken token)
    {
        int max = GetMax(array);
        int exp = 1;

        while (max / exp > 0)
        {
            token.ThrowIfCancellationRequested();
            await CountSort(array, exp, refresh, delay, playSound, token);
            exp *= 10;
        }
    }

    private int GetMax(int[] array)
    {
        int max = array[0];
        for (int i = 1; i < array.Length; i++)
            if (array[i] > max) max = array[i];
        return max;
    }

    private async Task CountSort(int[] array, int exp, Action refresh, int delay, Action<int> playSound, CancellationToken token)
    {
        int n = array.Length;
        int[] output = new int[n];
        int[] count = new int[10]; // digits 0-9

        // Count occurrences of digits
        for (int i = 0; i < n; i++)
        {
            token.ThrowIfCancellationRequested();
            int index = (array[i] / exp) % 10;
            count[index]++;
        }

        // Convert count to positions
        for (int i = 1; i < 10; i++)
        {
            count[i] += count[i - 1];
        }

        // Build the output array
        for (int i = n - 1; i >= 0; i--)
        {
            token.ThrowIfCancellationRequested();
            int index = (array[i] / exp) % 10;
            output[count[index] - 1] = array[i];
            count[index]--;

            // Visualize
            refresh?.Invoke();
            playSound?.Invoke(array[i]);
            await Task.Delay(10, token); // small delay per operation
        }

        // Copy output to original array
        for (int i = 0; i < n; i++)
        {
            token.ThrowIfCancellationRequested();
            array[i] = output[i];
            refresh?.Invoke();
            playSound?.Invoke(array[i]);
            await Task.Delay(delay, token);
        }
    }
}
