diff options
-rw-r--r-- | set_bitsets.c | 54 | ||||
-rw-r--r-- | sets.h | 2 |
2 files changed, 40 insertions, 16 deletions
diff --git a/set_bitsets.c b/set_bitsets.c index 37a276b..3e4c257 100644 --- a/set_bitsets.c +++ b/set_bitsets.c @@ -8,7 +8,9 @@ */ #include "sets.h" -#define SCOD sizeof(unsigned long long) +#include <stdlib.h> +#include <stdio.h> +#define SCOD 8*sizeof(unsigned long long) int nbCells(int n){ if(n == (n/SCOD)*SCOD) @@ -17,12 +19,19 @@ int nbCells(int n){ return n/SCOD+1; } +int set_size(const set s){ + return s.size; +} set empty_set(int size){ set res; + int i; res.size = size; - - res.tab = malloc(SCOD*nbCells(size)); + int N = nbCells(size); + res.tab = malloc(SCOD*N/8); + for(i = 0; i < N; i++) + res.tab[i] = 0; + return res; } /* @@ -40,9 +49,9 @@ set singleton(int size, int x){ set copy_set(const set s){ set res = empty_set(s.size); - int N = nbCells(s.size()), i; + int N = nbCells(s.size), i; for(i = 0; i < N; i++) - res[i] = s[i]; + res.tab[i] = s.tab[i]; return res; } @@ -53,9 +62,9 @@ void delete_set(set a){ 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; + exit(1); } - int N = nbCells(a.size()), i; + int N = nbCells(a.size), i; for(i = 0; i < N; i++) a.tab[i] = a.tab[i]|b.tab[i]; } @@ -63,9 +72,9 @@ void set_union_ip(set a, const set b){ 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; + exit(1); } - int N = nbCells(a.size()), i; + int N = nbCells(a.size), i; for(i = 0; i < N; i++) a.tab[i] = a.tab[i]&b.tab[i]; } @@ -74,9 +83,9 @@ void set_inter_ip(set a, const set b){ 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; + exit(1); } - int N = nbCells(a.size()), i; + int N = nbCells(a.size), i; for(i = 0; i < N; i++) a.tab[i] = a.tab[i] & (~b.tab[i]); } @@ -106,16 +115,16 @@ bool is_set_empty(const set s){ return true; } -bool set_mem(int x, const set s){ +inline 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; + exit (1); } - int i + int i; for(i=0; ((x>>i)&1) == 0; i++); return i; } @@ -126,7 +135,7 @@ int elt_of_set(const set s){ if(s.tab[i] != 0) printf("No element in an empty set!\n"); - exit 1; + exit(1); } //set set_add(int x, const set s); @@ -141,5 +150,20 @@ void set_remove_ip(int x, set s){ s.tab[x/SCOD] = s.tab[x/SCOD] & (~(1<<(x%SCOD))); } +void dump_set(const set s){ + int i=0; + printf("["); + for(i=0; i < s.size; i++) + if(set_mem(i, s)) + printf(" %d ", i); + printf("] (%d)\n", s.size); +} +set full_set(int n) { + set r = empty_set(n); + int N=nbCells(r.size), i; + for(i=0; i< N; i++) + r.tab[i]=-1; + return r; +} @@ -14,7 +14,7 @@ #ifdef BITSETS typedef struct { - int N; + int size; unsigned long long* tab; } set; #endif |