#include "collections.h"
#define BITS_PER_WORD (sizeof(int) * 8)
#define STACK_MACHINE
#include "c.h"
#define MIN(x, y) ((x) < (y) ? (x) : (y))
#define WORDS(set) (((set)->capacity + BITS_PER_WORD - 1) / BITS_PER_WORD)
#define CHECK(set) assert(do_check(set))

/** Implements set of integers as a bit vector */
struct bit_set {
    int mutable;
    int capacity;  /*< Capacity of this set (in bits) */
    int bits[1];   /*< Variable size array for members */
};

/** Checks that all redundant bits are zero.
    Redundant bits are those whose index is >= capacity.
*/
static int do_check(BitSet set) {
    int limit = set->capacity;
    int max = roundup(limit, BITS_PER_WORD);
    int i;
    for (i = limit; i < max; i++) {
        int pattern = 1 << (i & (BITS_PER_WORD - 1)); 
        if((set->bits[WORDS(set) - 1] & pattern) != 0)
            return 0;
    }
    return 1;
}

static BitSet set_allocate(int capacity) {
    int words;
    BitSet set;
    assert (capacity >= 0);
    assert (capacity < 10000);
    words = (capacity + BITS_PER_WORD - 1) / BITS_PER_WORD;
    set = allocate(sizeof(int) * (words + 2), FUNC);
    set->capacity = capacity;
    set->mutable = 1;
    return set;
}

BitSet set_new(int capacity) {
    BitSet set = set_allocate(capacity);
    int i, words = WORDS(set);
    for(i = 0; i < words; i++) {
        set->bits[i] = 0;
    }
    CHECK(set);
    return set;
}

void set_fix(BitSet set) {
    set->mutable = 0;   
}

/** Puts the intersection \f$set1 \bigcap set2\f$ into result. 
*/
BitSet set_intersection(BitSet set1, BitSet set2) {
    BitSet result = set_allocate(set2->capacity);
    int i, words = WORDS(set1);
    assert(set1->capacity == set2->capacity);
    for(i = 0; i < words; i++) {
        result->bits[i] = (set1->bits[i] & set2->bits[i]);    
    }
    CHECK(result);
    return result;
}

BitSet set_union(BitSet set1, BitSet set2) {
    BitSet result = set_allocate(set2->capacity);
    int i, words = WORDS(set1);
    assert(set1->capacity == set2->capacity);
    for(i = 0; i < words; i++) {
        result->bits[i] = (set1->bits[i] | set2->bits[i]);
    }
    CHECK(result);
    return result;
}
/*
void set_difference(BitSet set1, BitSet set2, BitSet result) {
    assert(result->mutable);
    assert(set1->capacity == set2->capacity);
    assert(set1->capacity == result->capacity);
    int i, words = WORDS(set1);
    for(i = 0; i < words; i++) {
        result->bits[i] = (set1->bits[i] ^ set2->bits[i]);
    }
    CHECK(result);
}
*/
BitSet set_clone(BitSet original) {
    int i, words = WORDS(original);
    BitSet set = set_allocate(original->capacity);
    for(i = 0; i < words; i++) {
        set->bits[i] = original->bits[i];    
    }
    CHECK(set);
    return set;
}


void set_add(BitSet set, int bit) {
    int word, pattern;
    assert(set->mutable);
    assert(set);
    assert(bit >= 0);
    assert(bit < set->capacity);
    word = bit / BITS_PER_WORD; 
    pattern = 1 << (bit & (BITS_PER_WORD - 1));
    set->bits[word] |= pattern;
    CHECK(set);
}

void set_remove(BitSet set, int bit) {
    int word, pattern;
    assert(set->mutable);
    assert(set);
    assert(bit >= 0);
    assert(bit < set->capacity);
    word = bit / BITS_PER_WORD; 
    pattern = 1 << (bit & (BITS_PER_WORD - 1));
    set->bits[word] &= (~pattern);
    CHECK(set);
}

int set_contains_function(BitSet set, int bit) {
    int word, pattern;
    assert(set);
    assert(bit >= 0);
    assert(bit < set->capacity);
    word = bit / BITS_PER_WORD; 
    pattern = 1 << (bit & (BITS_PER_WORD - 1));
    return (set->bits[word] & pattern);
}

int set_equals(BitSet set1, BitSet set2) {
    int i, words;
    assert(set1->capacity == set2->capacity);   
    words = WORDS(set1);
    for (i = 0; i < words; i++) {
        if (set1->bits[i] != set2->bits[i])
            return 0;
    }
    return 1;
}

int bitset_capacity(BitSet set) {
    return set->capacity;
}

/* Could optimise this */
void set_moveBit(BitSet set, int to, int from) {
    assert(set->mutable);
    if (set_contains(set, from)) {
        set_add(set, to);    
        set_remove(set, from);    
    } else {
        set_remove(set, to);    
    }
}

void set_clear(BitSet set) {
    int i, words;
    assert(set);
    assert(set->mutable);
    words = (set->capacity + BITS_PER_WORD - 1) / BITS_PER_WORD;
    for (i = 0; i < words; i++) {
        set->bits[i] = 0;    
    }
    CHECK(set);
}

void set_print(FILE* file, BitSet set) {
    int i;
    FOR_EACH(i, set) {
        fprintf(file, "%d ", i);
    }
}

int set_next(BitSet set, int from) {
    int i, j, x, words, result, offset;
    if (set->capacity == from) {
        return -1;    
    }
    assert(set->capacity > from);
    words = WORDS(set);
    offset = from - (from / BITS_PER_WORD) * BITS_PER_WORD;
    for (i = from / BITS_PER_WORD; i < words; i++) {
        x = set->bits[i];
        x >>= offset;
        if (x) {
            j = 0;
            if (!(0xffff & x)) {
                x >>= 16;
                j += 16;
            }
            if (!(0xff & x)) {
                x >>= 8;
                j += 8;
            }
            if (!(0xf & x)) {
                x >>= 4;
                j += 4;
            }
            if (!(0x3 & x)) {
                x >>= 2;
                j += 2;
            }
            if (!(0x1 & x)) {
                j += 1;
            }
            result = j + i * BITS_PER_WORD + offset;
            assert(result >= 0 && result < set->capacity);
            return result;
            
        }
        offset = 0;
    }
    return -1;
}

static int countBits( int x )
   {
   int count = 0;
   while ( x != 0 ) {
       x &= x - 1;
       count++;
   }
   return count;
}

int set_size(BitSet set) {
    int words, total, i;
    words = WORDS(set);
    total = 0;    
    for (i = 0; i < words; i++) {
        total += countBits(set->bits[i]);
    }
    return total;
}

int set_empty(BitSet set) {
    int i, words;
    words = WORDS(set);    
    for (i = 0; i < words; i++) {
        if (set->bits[i]) {
            return 0;
        }
    }
    return 1;
}

void set_addSet(BitSet set, const BitSet pattern) {
    int i, words;
    assert(set->mutable);
    assert(set->capacity == pattern->capacity);
    words = WORDS(set);
    for (i = 0; i < words; i++) {
        set->bits[i] |= pattern->bits[i];    
    }    
    CHECK(set);
}

void set_removeSet(BitSet set, const BitSet pattern) {
    int i, words;
    assert(set->mutable);
    assert(set->capacity == pattern->capacity);
    words = WORDS(set);
    for (i = 0; i < words; i++) {
        set->bits[i] &= (~(pattern->bits[i]));
    }
    CHECK(set);
}

struct array_list {
    int size;
    int capacity;
    void** array;
};

ArrayList list_new(int capacity) {
    ArrayList this = allocate(sizeof(struct array_list), FUNC);
    this->capacity = capacity < 4 ? 4 : capacity;
    this->size = 0;
    this->array = allocate(sizeof(void*) * (this->capacity + 1), FUNC);
    return this;
}

static void enlargeArray(ArrayList array) {
    void** newArray;
    int i, size, newCapacity;
    size = array->size;
    newCapacity = array->capacity * 2;
    newArray = allocate(sizeof(void*) * (newCapacity + 1), FUNC);
    for (i = 0; i < size; i++) {
        newArray[i] = array->array[i];
    }
    array->capacity = newCapacity;
    array->array = newArray;
}

/*
void** list_array(ArrayList list) {
    list->array[list->size] = NULL;
    return list->array;    
}
*/

void list_add(ArrayList list, void* item) {
    if (list->size == list->capacity)
        enlargeArray(list);
    list->array[list->size] = item;
    list->size++;
}

int list_size(ArrayList list) {
    return list->size;    
}

void list_remove(ArrayList list, int index) {
    int i;
    for (i = index + 1; i < list->size; i++) {
        list->array[i-1] = list->array[i];    
    }
    list->size--;
}

void* list_get(ArrayList list, int index) {
    assert(index >= 0);
    assert(index < list->size);    
    return list->array[index];
}

void list_set(ArrayList list, int index, void* item) {
    assert(index >= 0);
    assert(index < list->size);    
    list->array[index] = item;
}

void verifySort(ArrayList list, int (*compare)(const void*, const void*)) {
    int i, count;        
    for (i = 0, count = list_size(list) - 1; i < count; i++) {
        assert(    compare(list->array + i, list->array + i + 1) < 0);
    }
}

void list_sort(ArrayList list, int (*compare)(const void*, const void*)) {
    qsort(list->array, list->size, sizeof(void*), compare);
}

void list_print(ArrayList list, FILE* out, void (*print)(FILE*, void*)) {
    int i;
    fprintf(out, "[ ");
    if (list->size) print(out, list->array[0]);    
    for (i = 1; i < list->size; i++) {
        fprintf(out, ", ");
        print(out, list->array[i]);    
    }
    fprintf(out, " ]");
}