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);
	int i;
	int NC = nbCells(n);

	char *p = malloc(sizeof(struct bitset_descriptor) + (SCOD * NC) / 8);
	set res = (struct bitset_descriptor*)p;

	res->tab = (unsigned long long*)((char*)(p + sizeof(struct bitset_descriptor)));
	res->N = n;
	res->size = 0;

	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);
}

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, cell;

    if(s->tab[h/SCOD]>>(h%SCOD) !=0)
	return h + dyadic_val(s->tab[h/SCOD]>>(h%SCOD)) ;

    for(i=0; i<N; i++) {
		cell = (i + h/SCOD + 1) % N;
		if(s->tab[cell] != 0)
			return cell*SCOD + dyadic_val(s->tab[cell]);
	}

	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;
}