summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--set_bitsets.c139
-rw-r--r--sets.h2
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