path: root/sets.h

/*
	Projet d'algorithmique et programmation 2013-2014
	(cours de C.Matthieu et J.Stern)
	Alex AUVOLAT, Mendes OULAMARA

	Définition des fonctions ensemblistes utilisées et des trois structures
	de données possiblement utilisées pour la représentation des ensembles
	d'entiers (listes chaînées, bitsets et tarbres).
*/

#ifndef SET
#define SET
#include <stdbool.h>

#ifdef BITSETS
typedef struct bitset_descriptor {
    int N;			// Capacity of set (range of possible elements : 0..N-1)
   	int size;		// Number of elements actually in the set
    unsigned long long* tab;
} *set;
#endif

#ifdef LINKEDLISTS
struct set_elt {
    int value;
    struct set_elt *next;
};
typedef struct {
	int N;		// range for elements (0 to N-1)
    struct set_elt *first, *last;
	int size;	// number of elements
} t_set_descriptor;

typedef t_set_descriptor *set;
#endif


set empty_set(int size);
set full_set(int size);		// set containing all elements from 0 to n-1
set singleton(int size, int x);
set copy_set(const set s);
void delete_set(set a);

int set_size(const set s);

void set_union_ip(set a, const set b); 
void set_inter_ip(set a, const set b);
void set_diff_ip(set a, const set b);

set set_union(const set a, const set b);
set set_inter(const set a, const set b);
set set_diff(const set a, const set b);

bool is_set_empty(const set s);
bool set_mem(int x, const set s);
bool sets_equal(const set a, const set b);

int elt_of_set(const set s);
int elt_of_set_heur(const set s, int h);

set set_add(int x, const set s);
void set_add_ip(int x, set s);

set set_remove(int x, const set s);
void set_remove_ip(int x, set s);

void dump_set(const set s);

#endif