diff options
| -rw-r--r-- | set_bitset.c | 136 |
1 files changed, 136 insertions, 0 deletions
diff --git a/set_bitset.c b/set_bitset.c new file mode 100644 index 0000000..24fc15a --- /dev/null +++ b/set_bitset.c @@ -0,0 +1,136 @@ +#include "sets.h" +#define SCOD sizeof(unsigned long long) + +int nbCells(int n){ + if(n == (n/SCOD)*SCOD) + return n/SCOD; + else + return n/SCOD+1; +} + + +set empty_set(int size){ + set res; + res.size = size; + + res.tab = malloc(SCOD*nbCells(size)); +} + +/* +set singleton(int size, int x){ + set res = empty_set(size); + + if(x >= size){ + printf("Index %d out of bound %d in singleton creation\n", x, size); + exit 1; + } + + res.tab.tab[x/SCOD] = 1<<(x%SCOD); + return res; +}*/ + +set copy_set(const set s){ + set res = empty_set(s.size); + int N = nbCells(s.size()), i; + for(i = 0; i < N; i++) + res[i] = s[i]; + return res; +} + +void delete_set(set a){ + free(a.tab); +} + +void set_union_ip(set a, const set b){ + if(a.size != b.size){ + printf("Union failed : the sets don't have the same size\n"); + exit 1; + } + int N = nbCells(a.size()), i; + for(i = 0; i < N; i++) + a.tab[i] = a.tab[i]|b.tab[i]; +} + +void set_inter_ip(set a, const set b){ + if(a.size != b.size){ + printf("Intersection failed : the sets don't have the same size\n"); + exit 1; + } + int N = nbCells(a.size()), i; + for(i = 0; i < N; i++) + a.tab[i] = a.tab[i]&b.tab[i]; +} + + +void set_diff_ip(set a, const set b){ + if(a.size != b.size){ + printf("Difference failed : the sets don't have the same size\n"); + exit 1; + } + int N = nbCells(a.size()), i; + for(i = 0; i < N; i++) + a.tab[i] = a.tab[i] & (~b.tab[i]); +} + +/* +set set_union(const set a, const set b){ + set res = copy_set(a); + set_union_ip(res, b); +} + +set set_inter(const set a, const set b){ + set res = copy_set(a); + set_inter_ip(res, b); +} + +set set_diff(const set a, const set b){ + set res = copy_set(a); + set_diff_ip(res, b); +} +*/ + +bool is_set_empty(const set s){ + int N = nbCells(s.size),i; + for(i = 0; i < N; i++) + if(s.tab[i] != 0) + return false; + return true; +} + +bool set_mem(int x, const set s){ + return (s.tab[x/SCOD]>>(x%SCOD))&1; +} + +int dyadic_val(unsigned long long x){ + if(x == 0){ + printf("Infinite valuation\n"); + exit 1; + } + int i + for(i=0; ((x>>i)&1) == 0; i++); + return i; +} + +int elt_of_set(const set s){ + int N=nbCells(s.size), i; + for(i=0; i<N; i++) + if(s.tab[i] != 0) + + printf("No element in an empty set!\n"); + exit 1; +} + +//set set_add(int x, const set s); + +void set_add_ip(int x, set s){ + s.tab[x/SCOD] = s.tab[x/SCOD] | 1<<(x%SCOD); +} + +//set set_remove(int x, const set s); + +void set_remove_ip(int x, set s){ + s.tab[x/SCOD] = s.tab[x/SCOD] & (~(1<<(x%SCOD))); +} + + + |