From dc7b29b7dab2a8386f739c02b6a2ac09ebfccefb Mon Sep 17 00:00:00 2001
From: Mendes Oulamara <oulamara@clipper.ens.fr>
Date: Thu, 28 Nov 2013 09:52:21 +0100
Subject: Vrai debug de bitset --'

---
 set_bitsets.c | 139 ++++++++++++++++++++++++++++------------------------------
 sets.h        |   2 +-
 2 files changed, 68 insertions(+), 73 deletions(-)

diff --git a/set_bitsets.c b/set_bitsets.c
index 3e4c257..6645e0e 100644
--- a/set_bitsets.c
+++ b/set_bitsets.c
@@ -10,119 +10,108 @@
 #include "sets.h"
 #include <stdlib.h>
 #include <stdio.h>
-#define SCOD 8*sizeof(unsigned long long)
+#include <assert.h>
+#define SCOD (unsigned long long)(8*sizeof(unsigned long long))
 
-int nbCells(int n){
+int nbCells(int n){		//the mathematical ceil function
 	if(n == (n/SCOD)*SCOD)
 		return n/SCOD;
 	else
 		return n/SCOD+1;
 }
 
+int nb_one(unsigned long long x) {	//the hamming weight of x
+    int cnt = 0, i;
+    for(i = 0; i < SCOD; i++)
+	cnt+= ((x>>i)&1);
+    return cnt;
+}
+
 int set_size(const set s){
-    return s.size;
+    return *(s.size);
 }
 
-set empty_set(int size){
+set empty_set(int n){
+    	assert(n > 0);
 	set res;
 	int i;
-	res.size = size;
-	int N = nbCells(size);
-	res.tab = malloc(SCOD*N/8);
-	for(i = 0; i < N; i++)
+	res.N = n;
+	res.size = malloc(sizeof(int));
+	*(res.size) = 0;
+	int NC = nbCells(n);
+	res.tab = malloc(SCOD*NC/8);
+	for(i = 0; i < NC; i++)
 	    res.tab[i] = 0;
 	return res;
 }
 
-/*
-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++) 
+	set res = empty_set(s.N);
+	*(res.size) = *(s.size);
+	int NC = nbCells(*(s.size)), i;
+	for(i = 0; i < NC; i++) 
 		res.tab[i] = s.tab[i];
 	return res;
 }
 
 void delete_set(set a){
 	free(a.tab);
+	free(a.size);
 }
 
 void set_union_ip(set a, const set b){
-	if(a.size != b.size){
+	if(a.N != b.N){
 		printf("Union failed : the sets don't have the same size\n");
-		exit(1);
+		assert(a.N == b.N);
 	}
-	int N = nbCells(a.size), i;
-	for(i = 0; i < N; i++) 
+	int NC = nbCells(*(a.size)), i;
+	*(a.size)=0;
+	for(i = 0; i < NC; i++) {
 		a.tab[i] = a.tab[i]|b.tab[i];
+		*(a.size) += nb_one(a.tab[i]);
+	}
 }
 
 void set_inter_ip(set a, const set b){
-	if(a.size != b.size){
+	if(a.N != b.N){
 		printf("Intersection failed : the sets don't have the same size\n");
-		exit(1);
+		assert(a.N == b.N);
 	}
-	int N = nbCells(a.size), i;
-	for(i = 0; i < N; i++) 
+	int NC = nbCells(*(a.size)), i;
+	*(a.size)=0;
+	for(i = 0; i < NC; i++){ 
 		a.tab[i] = a.tab[i]&b.tab[i];
+		*(a.size) += nb_one(a.tab[i]);
+	}
 }
 
 
 void set_diff_ip(set a, const set b){
-	if(a.size != b.size){
+	if(a.N != b.N){
 		printf("Difference failed : the sets don't have the same size\n");
-		exit(1);
+		assert(a.N == b.N);
 	}
-	int N = nbCells(a.size), i;
-	for(i = 0; i < N; i++) 
+	int NC = nbCells(*(a.size)), i;
+	for(i = 0; i < NC; i++) { 
 		a.tab[i] = a.tab[i] & (~b.tab[i]);
+		*(a.size) += nb_one(a.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;
+    	return (*(s.size) == 0);
 }
 
 inline bool set_mem(int x, const set s){
-	return  (s.tab[x/SCOD]>>(x%SCOD))&1;
+    	unsigned long long ux = x;
+    	assert(x < s.N && x >= 0);
+	return  (s.tab[ux/SCOD]>>(ux%SCOD))&1;
 }
 
 int dyadic_val(unsigned long long x){
 	if(x == 0){
 		printf("Infinite valuation\n");
-		exit (1);
+		assert(false);
 	}
 	int i;
 	for(i=0; ((x>>i)&1) == 0; i++);
@@ -130,39 +119,45 @@ int dyadic_val(unsigned long long x){
 }
 
 int elt_of_set(const set s){
-	int N=nbCells(s.size), i;
+	int N=nbCells(s.N), i;
 	for(i=0; i<N; i++)
 		if(s.tab[i] != 0)
+		    return i*SCOD+dyadic_val(s.tab[i]);
 
 	printf("No element in an empty set!\n");
-	exit(1);
+	assert(false);
 }
 
-//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);
+    	unsigned long long ux = x;
+    	if(! set_mem(ux, s)){
+		s.tab[ux/SCOD] = s.tab[ux/SCOD] | (unsigned long long)(1)<<(ux%SCOD);
+		*(s.size) = *(s.size)+1;
+	}
 }
 
-//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)));
+    	unsigned long long ux = x;
+    if(set_mem(ux, s) ) {
+	s.tab[ux/SCOD] = s.tab[ux/SCOD] & (~((unsigned long long)(1)<<(ux%SCOD)));
+	*(s.size) = *(s.size)-1;
+    }
 }
 
 void dump_set(const set s){
     int i=0;
     printf("[");
-    for(i=0; i < s.size; i++)
+    for(i=0; i < s.N; i++)
 	if(set_mem(i, s))
 	    printf(" %d ", i);
-    printf("] (%d)\n", s.size);
+    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.size) = n;
+    int NC=nbCells(n), i;
+    for(i=0; i< NC; i++)
 	r.tab[i]=-1;
     return r;
 }
diff --git a/sets.h b/sets.h
index 7774e7d..ebbed20 100644
--- a/sets.h
+++ b/sets.h
@@ -14,7 +14,7 @@
 
 #ifdef BITSETS
 typedef struct {
-    int size;
+    int N, *size;
     unsigned long long* tab;
 } set;
 #endif
-- 
cgit v1.2.3