summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMendes Oulamara <oulamara@clipper.ens.fr>2013-11-18 22:03:00 +0100
committerMendes Oulamara <oulamara@clipper.ens.fr>2013-11-18 22:03:00 +0100
commitc3e202dddc68d41a57b8e6d3e93837b4b3874bd0 (patch)
tree62b94546a05881b5f1091388170d39d53877c6df
parentfdd5de0c84cbddcc6b31d579d7006773682059ac (diff)
downloadAlgoProg-Projet-c3e202dddc68d41a57b8e6d3e93837b4b3874bd0.tar.gz
AlgoProg-Projet-c3e202dddc68d41a57b8e6d3e93837b4b3874bd0.zip
Ajout de l'implémentation des bitsets
-rw-r--r--set_bitset.c136
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)));
+}
+
+
+