/* counting sort with permutation reindexing - sergey voronin, 2019 */

#include <stdio.h>
#include <stdlib.h>
#include <time.h> 

// struct to store inds of vals 
struct val_inds
{
    int val;
    int num_inds;
    int *inds;
};


void counting_sort(int *a, int *inds, const size_t len, const int maxp1){
    int *b, *counts, *counts2, i,j,tot, oldcnt,ind=0, maxrepeats = len;
    b = (int*) calloc(len,sizeof(int));
    counts = (int*) calloc(maxp1,sizeof(int));
    counts2 = (int*) calloc(maxp1,sizeof(int));

    struct val_inds* valis = malloc(maxp1*sizeof(struct val_inds));
    for(i=0; i<maxp1; i++){
        valis[i].inds = (int*) calloc(maxrepeats,sizeof(int));
        valis[i].num_inds = 0;
    }

    for(i=0; i<len; i++){
        counts2[a[i]]++;
        counts[a[i]]++;
        valis[a[i]].val = a[i];
        valis[a[i]].inds[valis[a[i]].num_inds] = i;        
        valis[a[i]].num_inds++;        
    }

    tot=0;
    for(i=0; i<maxp1; i++){
        oldcnt=counts2[i];
        counts2[i]=tot;
        tot+=oldcnt;
    }

    for(i=0; i<len; i++){
        b[counts2[a[i]]] = a[i];
        counts2[a[i]]++;
    }

    for(i=0; i<len; i++){
        a[i] = b[i];
    }

    for(i=0; i<len; i++){
        for(j=0; j<counts[a[i]]; j++){
            inds[ind++] = valis[a[i]].inds[j];
        }
    }

    free(b); free(counts); free(counts2);
    for(i=0; i<maxp1; i++){
        free(valis[i].inds);
    }
    free(valis);
}

        
int main(){
    srand(time(0));
    printf("testing sort..\n");
    int i, n, num, *arr, *inds, low = 0, high = 100; 
    n = 5;
    arr = (int*)calloc(n,sizeof(int));
    inds = (int*)calloc(n,sizeof(int));
    for (i = 0; i < n; i++) { 
        num = (rand() % (high - low + 1)) + low; 
        arr[i] = num;
    }

    printf("before sort:\n");
    for(i=0; i<n; i++){
        printf("a[%d]=%d  ", i, arr[i]);
    }
    printf("\n");

    counting_sort(arr, inds, n, high+1);

    printf("\nafter sort:\n");
    for(i=0; i<n; i++){
        printf("a[%d]=%d, inds[%d]=%d  ", i, arr[i], i, inds[i]);
    }
    printf("\n");

    return 0;
}