From 5b1c48665dbf7534fde3d392ef76c37f7fa7cb48 Mon Sep 17 00:00:00 2001 From: Alex AUVOLAT Date: Mon, 18 Nov 2013 23:03:24 +0100 Subject: Renamed set_bitset.c to set_bitsets.c --- Makefile | 6 ++- set_bitset.c | 136 ---------------------------------------------------------- set_bitsets.c | 135 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++- sets.h | 6 +-- 4 files changed, 140 insertions(+), 143 deletions(-) delete mode 100644 set_bitset.c diff --git a/Makefile b/Makefile index 5dbe549..269ccff 100644 --- a/Makefile +++ b/Makefile @@ -7,7 +7,11 @@ exe_ll_test : set_test.c sets.h set_linked_lists.c sets.c gcc -o exe_ll_test set_test.c set_linked_lists.c sets.c -DLINKEDLISTS -g exe_bs : main.c sets.h set_bitsets.c sets.c - # gcc -o exe_bs main.c set_bitsets.c sets.c -DBITSETS -g + gcc -o exe_bs main.c set_bitsets.c sets.c -DBITSETS -g + +exe_bs_test : set_test.c sets.h set_bitsets.c sets.c + gcc -o exe_ll_test set_test.c set_bitsets.c sets.c -DBITSETS -g + exe_tr : main.c sets.h set_treaps.c sets.c # gcc -o exe_tr main.c set_treaps.c sets.c -DTREAPS -g diff --git a/set_bitset.c b/set_bitset.c deleted file mode 100644 index 24fc15a..0000000 --- a/set_bitset.c +++ /dev/null @@ -1,136 +0,0 @@ -#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= 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 #ifdef BITSETS -struct set{ +typedef struct { int N; unsigned long long* tab; -}; - -typedef struct set set; +} set; #endif #ifdef LINKEDLISTS -- cgit v1.2.3