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"
#define SCOD sizeof(unsigned long long)

int nbCells(int n){
	if(n == (n/SCOD)*SCOD)
		return n/SCOD;
	else
		return n/SCOD+1;
}


set empty_set(int size){
	set res;
	res.size = size;

	res.tab = malloc(SCOD*nbCells(size));
}

/*
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++) 
		res[i] = s[i];
	return res;
}

void delete_set(set a){
	free(a.tab);
}

void set_union_ip(set a, const set b){
	if(a.size != b.size){
		printf("Union failed : the sets don't have the same size\n");
		exit 1;
	}
	int N = nbCells(a.size()), i;
	for(i = 0; i < N; i++) 
		a.tab[i] = a.tab[i]|b.tab[i];
}

void set_inter_ip(set a, const set b){
	if(a.size != b.size){
		printf("Intersection failed : the sets don't have the same size\n");
		exit 1;
	}
	int N = nbCells(a.size()), i;
	for(i = 0; i < N; i++) 
		a.tab[i] = a.tab[i]&b.tab[i];
}


void set_diff_ip(set a, const set b){
	if(a.size != b.size){
		printf("Difference failed : the sets don't have the same size\n");
		exit 1;
	}
	int N = nbCells(a.size()), i;
	for(i = 0; i < N; i++) 
		a.tab[i] = a.tab[i] & (~b.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;
}

bool set_mem(int x, const set s){
	return  (s.tab[x/SCOD]>>(x%SCOD))&1;
}

int dyadic_val(unsigned long long x){
	if(x == 0){
		printf("Infinite valuation\n");
		exit 1;
	}
	int i
	for(i=0; ((x>>i)&1) == 0; i++);
	return i;
}

int elt_of_set(const set s){
	int N=nbCells(s.size), i;
	for(i=0; i<N; i++)
		if(s.tab[i] != 0)

	printf("No element in an empty set!\n");
	exit 1;
}

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

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