using System;
using System.Collections.Generic;
using System.Threading.Tasks;
using System.Collections.Concurrent;
using System.Threading;

namespace BucketSort
{
    public class BucketSort
    {
        static SpinLock sp = new SpinLock();
        public static void Bucketear(int[] vec)
        {
            //verificar se o vetor contém valores.
            if (vec == null || vec.Length == 0)
                return;

            //variáveis para guardar o maior e o menor valor do vetor,
            //serão inicializadas com a primeira posição do vetor.
            int max = vec[0];
            int min = vec[0];

            //aqui nosso loop irá percorrer o vetor iniciando da posição 1.
            //ao final do percurso as variáveis max e min terão o maior e o menor valor
            //do vetor, respectivamente.
            for (int i = 1; i < vec.Length; i++)
            {
                if (vec[i] > max)
                    max = vec[i];
                if (vec[i] < min)
                    min = vec[i];
            }


            //aqui é criado um balde para guardar todos os valores do vetor.
            //Cada valor será guardado em seu índice menos o menor valor.
            //Por exemplo: 15 será guardado na posição 15 menos o menor valor,
            //se min == 0, 15 será guardado na posição 15.
            List<int>[] buckets = new List<int>[max - min + 1];


            //aqui será inicializado o balde, criando uma nova List<int> para cada valor
            //igual do vetor.

            Parallel.For<int[]>(0, vec.Length, () => new int[max - min + 1], (i, loop, lista) =>
            {
                if (buckets[vec[i] - min] == null)
                {
                    buckets[vec[i] - min] = new List<int>();
                    lista[vec[i] - min] = vec[i];
                }
                return lista;
            }, (x) =>
            {
                if (x != null)
                {
                    bool l = false;
                    sp.Enter(ref l);
                    for (int i = 0; i < x.Length; i++)
                    {
                        buckets[i].Add(x[i]);
                    }
                    sp.Exit(false);
                }
            });

            //Parallel.For(0, holder.Length, i =>
            //{
            //    holder[i] = new List<int>();
            //});
            //for (int i = 0; i < vec.Length; i++)
            //{
            //    buckets[vec[i] - min].Add(vec[i]);
            //}


            //variável criada para armazenar o índice original do vetor
            int k = 0;


            //aqui os valores serão movidos do balde para o vetor em posição ordenada.
            for (int i = 0; i < buckets.Length; i++)
            {
                if (buckets[i].Count > 0)
                {
                    for (int j = 0; j < buckets[i].Count; j++)
                    {
                        vec[k] = buckets[i][j];
                        k++;
                    }
                }
            }
        }
    }
}