path: root/set_bitsets.c

/*
	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] = (unsigned long long) (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);
}

bool sets_equal(const set a, const set b){
    if(a.N != b.N)
	return false;
    int i, NC = nbCells(a.N);
    for(i = 0; i < NC; i++){
	if(a.tab[i] != b.tab[i])
	    return false;
    }
    assert(*(a.size) == *(b.size));
    return true;
}

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){
    	assert(x < s.N);
    	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]=0xFFFFFFFFFFFFFFFF;
	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;
}