/*
Projet d'algorithmique et programmation 2013-2014
(cours de C.Matthieu et J.Stern)
Alex AUVOLAT, Mendes OULAMARA
Implémentation des ensembles d'entiers sous forme de bitsets.
Code sous la juridiction de Mendes OULAMARA.
*/
#include "sets.h"
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#define SCOD (unsigned long long)(8*sizeof(unsigned long long))
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
assert(SCOD==64);
//1
x = (x & 0x5555555555555555) + ((x >> 1) & 0x5555555555555555); // mask : 0101010101...
//2
x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333); // mask : 001100110011...
//4
x = (x & 0x0F0F0F0F0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F0F0F0F0F); // mask : 000011110000....
//8
x = (x & 0x00FF00FF00FF00FF) + ((x >> 8) & 0x00FF00FF00FF00FF); // etc.
//16
x = (x & 0x0000FFFF0000FFFF) + ((x >> 16) & 0x0000FFFF0000FFFF);
//32
x = (x & 0x00000000FFFFFFFF) + ((x >> 32) & 0x00000000FFFFFFFF);
return x;
}
int set_size(const set s){
return *(s.size);
}
set empty_set(int n){
assert(n > 0);
set res;
int 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 copy_set(const set s){
set res = empty_set(s.N);
*(res.size) = *(s.size);
int NC = nbCells(s.N), 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.N != b.N){
printf("Union failed : the sets don't have the same size\n");
assert(a.N == b.N);
}
int NC = nbCells(a.N), 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.N != b.N){
printf("Intersection failed : the sets don't have the same size\n");
assert(a.N == b.N);
}
int NC = nbCells(a.N), 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]);
}
assert((a.N%SCOD == 0) || (a.tab[NC-1]>>(a.N%SCOD)) == 0);
}
void set_diff_ip(set a, const set b){
if(a.N != b.N){
printf("Difference failed : the sets don't have the same size\n");
assert(a.N == b.N);
}
int NC = nbCells(a.N), 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]);
}
assert((a.N%SCOD == 0) || (a.tab[NC-1]>>(a.N%SCOD)) == 0);
}
bool is_set_empty(const set s){
return (*(s.size) == 0);
}
inline bool set_mem(int x, const set s){
unsigned long long ux = x;
if (!(x < s.N && x >= 0)) {
printf("Invalid argument for set_mem : %d\n", 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");
assert(false);
}
int i = 0;
while (((x>>i)&1) == 0) i++;
return i;
}
int elt_of_set(const set s){
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");
dump_set(s);
assert(false);
}
int elt_of_set_heur(const set s, int h){
int N=nbCells(s.N), i;
if(s.tab[h/SCOD]>>(h%SCOD) !=0)
return h + dyadic_val(s.tab[h/SCOD]>>(h%SCOD)) ;
for(i=0; i<N; i++)
if(s.tab[(i+h/SCOD+1)%N] != 0)
return i*SCOD+dyadic_val(s.tab[(i+h/SCOD+1)%N]);
printf("No element in an empty set!\n");
dump_set(s);
assert(false);
}
void set_add_ip(int x, set s){
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 set_remove_ip(int x, set s){
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.N; i++)
if(set_mem(i, s))
printf(" %d ", i);
printf("] (%d)\n", *(s.size));
}
set full_set(int n) {
set r = empty_set(n);
*(r.size) = n;
int NC=nbCells(n), i;
for(i=0; i< NC; i++)
r.tab[i]=-1;
r.tab[NC-1] = ( r.tab[NC-1]>>( (SCOD-(n%SCOD))%SCOD ) );
assert((n%SCOD == 0) || (r.tab[NC-1]>>(n%SCOD)) == 0);
return r;
}