#include "c.h"
#include "collections.h"
#include "x_stack.h"

struct x_stack {
    int size;
    BitSet set;
    Symbol items[1];  // item 0 is TOS...
};

int xstack_size(XStack x) {
    return x->size;
}

int compareVirtuals(Symbol s1, Symbol s2) {
    int dif = (s2->ref - s1->ref) * 8;
    if (dif)
        return dif;
    else 
        return s1 > s2 ? 1 : s1 == s2 ? 0 : -1; // strcmp(s2->name, s1->name);
}

int cmpRefCount(const void* v1, const void* v2) {
    Symbol s1 = *((Symbol*)v1);
    Symbol s2 = *((Symbol*)v2);
    return compareVirtuals(s1, s2);
}


Symbol xstack_item(XStack x, int index) {
        return x->items[index];
}

void xstack_print(XStack stack, FILE* out) {
    int i;
    if (stack == NULL) {
        fprintf(out, "None");
        return;
    }
    fprintf(out, " ~ ");
    if (stack->size) {
        for (i = xstack_size(stack) - 1; i >= 1; i--) {
            fprintf(out, "%s, ", stack->items[i]->name);    
        }
        fprintf(out, "%s ", stack->items[0]->name);
    }
}    

void xstack_remove(XStack x, int index) {
    int i;
    Symbol s;
    assert(index >= 0);
    assert(index < x->size);
    s = x->items[index];
    set_remove(x->set, s->x.uniqueID);
    for (i = index + 1; i < x->size; i++) {
       x->items[i-1] = x->items[i];
    }
    --x->size;
}

int xstack_contains(XStack x, Symbol s) {
    int id = s->x.uniqueID;    
    return set_contains(x->set, id);
}

XStack xstack_new(BitSet set) {
    int i, index, size;
    XStack new;
    assert(set);
    size = set_size(set); 
    new = allocate(sizeof(Symbol) * (size - 1) + sizeof(struct x_stack), FUNC);
    new->size = size;
    new->set = set;
    index = 0;
    FOR_EACH(i, set) {
        new->items[index++] = localVariableSymbol(i);
    }
    qsort(new->items, index, sizeof(Symbol), &cmpRefCount);
    return new;
}

void xstack_ensureReachable(XStack x, BitSet variables, int delve) {
   int i, excess;
   if (x->size <= delve)
       return;
   do {
       int candidate = -1;
       int lowest = -1;
       excess = 0;
       for (i = x->size - 1; i >= 0; --i) {
           if (set_contains(variables, x->items[i]->x.uniqueID)) {
               if (i >= delve)  
                   excess = 1;
               if (lowest < 0)
                   lowest = i;
           } else {
               if (candidate < 0 && i < delve)
                   candidate = i;
           }
       }
       if (excess) {
            if (candidate >= 0)
                xstack_remove(x, candidate);
            else if (lowest >= 0)
                xstack_remove(x, lowest);
       }
   } while (excess);
}

ArrayList xstack_top(XStack x, int count) {
    int i;
    ArrayList result = list_new(count);
    assert(x->size >= count);
    for(i = 0; i < count; i++)
        list_add(result, x->items[i]);
    return result;
}