#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, " ]"); }