/*"
 ============================================================================
 Name        : radixsort.c
 Author      : martin.dvorak@mindforger.com
 Copyright   : Apache 2.0
 Description : Radix sort
 ============================================================================
*/

#include "include/radixsort.h"

#define GET_TOP_INDEX(KEY) KEY/RADIX_SLOT_SIZE
#define GET_LOW_INDEX(KEY) KEY%RADIX_SLOT_SIZE

void radixsort_init(RadixSorter *rs, unsigned keyLimit)
{
    rs->optFloorAndInsertBigKeys=false;
    rs->optIgnoreBigKeys=false;

    rs->_topIndexLimit=GET_TOP_INDEX(keyLimit);
    rs->size=0;
    rs->topDigits=malloc(rs->_topIndexLimit * sizeof(RadixItem ***));
    memset(rs->topDigits, 0, rs->_topIndexLimit * sizeof(RadixItem ***));
    rs->maxKey=0;
    rs->keyLimit=keyLimit;

    rs->_slotDescriptors=malloc(rs->_topIndexLimit * sizeof(RadixSlot **));
    rs->_slotsCount=0;
}

void radixsort_set_debug_level(RadixSorter *rs, unsigned debugLevel)
{
    rs->_debug=debugLevel;
}

RadixItem **radixsort_get_slot(RadixSorter *rs, unsigned topIndex)
{
    RadixItem **slot=malloc(RADIX_SLOT_SIZE * sizeof(RadixItem *));
    memset(slot, 0, RADIX_SLOT_SIZE * sizeof(RadixItem *));

    RadixSlot *descriptor=malloc(sizeof(RadixSlot));
    descriptor->min=rs->keyLimit;
    descriptor->max=0;
    descriptor->size=0;

    rs->_slotDescriptors[topIndex]=descriptor;
    rs->_slotsCount++;
    return slot;
}

void radixsort_add(RadixSorter *rs, RadixItem *item)
{
    if(item->key > rs->keyLimit) {
        if(rs->_debug > RADIX_DEBUG_LEVEL_NONE) {
            fprintf(stderr, "WARNING: Radix sort overflow - inserted key is bigger than limit (%u): %u\n", rs->keyLimit, item->key);
        }
        if(rs->optFloorAndInsertBigKeys) {
            item->key = rs->keyLimit-1;
        } else {
            if(rs->optIgnoreBigKeys) {
                return;
            } else {
                exit(0);
            }
        }
    }

    unsigned topIndex = GET_TOP_INDEX(item->key);
    unsigned lowIndex = GET_LOW_INDEX(item->key);

    if(!rs->topDigits[topIndex]) {
        rs->topDigits[topIndex]=radixsort_get_slot(rs, topIndex);
    }

    RadixItem *chain=rs->topDigits[topIndex][lowIndex];
    rs->topDigits[topIndex][lowIndex]=item;
    if(chain==NULL) {
        item->next=NULL;
    } else {
        item->next=chain;
    }

    rs->size++;
    rs->maxKey=MAX(rs->maxKey,item->key);
    rs->_slotDescriptors[topIndex]->min=MIN(rs->_slotDescriptors[topIndex]->min,item->key);
    rs->_slotDescriptors[topIndex]->max=MAX(rs->_slotDescriptors[topIndex]->max,item->key);
    rs->_slotDescriptors[topIndex]->size++;
}

void radix_dec_slot_descriptor_size(RadixSorter *rs, RadixSlot *descriptor, unsigned key, unsigned topIndex)
{
    descriptor->size--;
    if(!descriptor->size) {
        descriptor->min=rs->keyLimit;
        descriptor->max=0;
    } else {
        if(descriptor->size==1) {
            if(rs->topDigits[topIndex][GET_LOW_INDEX(descriptor->max)]) {
                descriptor->min=descriptor->max;
            } else {
                if(rs->topDigits[topIndex][GET_LOW_INDEX(descriptor->min)]) {
                    descriptor->max=descriptor->min;
                }
            }
        }
    }
}

RadixItem *radix_cut(RadixSorter *rs, unsigned key, void *data)
{
    // TODO optimization: fix min/max on cut of a value
    if(key <= rs->maxKey) {
        unsigned topIndex = GET_TOP_INDEX(key);
        unsigned lowIndex = GET_LOW_INDEX(key);

        if(rs->topDigits[topIndex]) {
            RadixItem *ri=rs->topDigits[topIndex][lowIndex];
            RadixItem *lastRi=NULL;
            while(ri->data!=data) {
                if(ri->next) {
                    lastRi=ri;
                    ri=ri->next;
                } else {
                    break;
                }
            }
            if(ri->data==data) {
                if(lastRi) {
                    lastRi->next=ri->next;
                } else {
                    rs->topDigits[topIndex][lowIndex]=ri->next;
                }
                ri->next=NULL;
                rs->size--;
                radix_dec_slot_descriptor_size(rs, rs->_slotDescriptors[topIndex], key, topIndex);
                return ri;
            }
        }
    }
    return NULL;
}

RadixItem **radixsort_dump(RadixSorter *rs)
{
    if(rs->size>0) {
        RadixItem **result=malloc(rs->size * sizeof(RadixItem *));
        int t = GET_TOP_INDEX(rs->maxKey);
        int slotMin, slotSize, slotCount, l;
        unsigned items=0;
        do {
            if(rs->topDigits[t]) {
                if(rs->_slotDescriptors[t]->size>0) {
                    l=GET_LOW_INDEX(rs->_slotDescriptors[t]->max);
                    slotMin=GET_LOW_INDEX(rs->_slotDescriptors[t]->min);
                    slotSize=rs->_slotDescriptors[t]->size;
                    slotCount=0;
                    do {
                        if(rs->topDigits[t][l]) {
                            result[items++]=rs->topDigits[t][l];
                            slotCount++;
                            RadixItem *ri=rs->topDigits[t][l]->next;
                            while(ri) {
                                result[items++]=ri;
                                slotCount++;
                                ri=ri->next;
                            }
                        }
                    } while(--l>=slotMin && slotCount<slotSize);
                }
            }
        } while(--t>=0);
        return result;
    }
    return NULL;
}

void radixsort_stat(RadixSorter *rs, bool listing)
{
    printf("\n Radixsort (size/max/limit/slot count): %u %u %u %u", rs->size, rs->maxKey, rs->keyLimit, rs->_slotsCount);
    unsigned memory=rs->_topIndexLimit * sizeof(RadixItem ***);
    memory+=memory;
    memory+=rs->_slotsCount*(RADIX_SLOT_SIZE * sizeof(RadixItem *));
    printf("\n   Memory: %u\n", memory);
    if(listing && rs->size>0) {
        int t = GET_TOP_INDEX(rs->maxKey);
        int slotMin, slotSize, slotCount, l;
        unsigned items=0;
        do {
            if(rs->topDigits[t]) {
                printf("\n  Slot %u (size/min/max): %u %u %u",t, rs->_slotDescriptors[t]->size, rs->_slotDescriptors[t]->min, rs->_slotDescriptors[t]->max);
                if(rs->_slotDescriptors[t]->size>0) {
                    l=GET_LOW_INDEX(rs->_slotDescriptors[t]->max);
                    slotMin=GET_LOW_INDEX(rs->_slotDescriptors[t]->min);
                    slotSize=rs->_slotDescriptors[t]->size;
                    slotCount=0;
                    do {
                        if(rs->topDigits[t][l]) {
                            printf("\n    > %d #%u",l, ++items);
                            ++slotCount;
                            RadixItem *ri=rs->topDigits[t][l]->next;
                            while(ri) {
                                printf(" #%u",++items);
                                ++slotCount;
                                ri=ri->next;
                            }
                        }
                    } while(--l>=slotMin && slotCount<slotSize);
                    printf("\n    STOP @ %d",l);
                } else {
                    printf(" > SKIPPED");
                }
            }
        } while(--t>=0);
    }
    fflush(stdout);
}

void radixsort_destroy(RadixSorter *rs)
{
    // radix items: DONE (passed on dump() by reference)
    // rs: DONE (created and destroyed by caller)
    // slots:
    int topIndex = GET_TOP_INDEX(rs->maxKey);
    do {
        if(rs->topDigits[topIndex]) {
            free(rs->topDigits[topIndex]);
            free(rs->_slotDescriptors[topIndex]);
        }
    } while(--topIndex>=0);
}