#09
// isetdemo1.c --- iset demonstration.
#include <stdio.h>
#include <stdbool.h>
#include "iset.h"
isetp readiset(void) {
isetp s = iset_new();
while(true) {
int i; printf("i> "); scanf("%d", &i);
if(i < 0) { return s; } else { iset_addelt(s, i); }
}
}
void printiset(isetp s) {
printf("{");
for(int max = iset_max(s), i = 0; i <= max; ++i) {
if(iset_isin(s, i)) { printf(" %d", i); }
}
printf(" }\n");
}
int main(void) {
isetp s = readiset(); printiset(s);
isetp t = readiset(); printiset(t);
isetp u = iset_union(s, t); printiset(u);
iset_free(s); iset_free(t); iset_free(u);
return 0;
}
// iset.h --- set of non-negative integers.
#include <stdbool.h>
struct iset;
typedef struct iset *isetp;
isetp iset_new(); // create empty set
void iset_free(isetp s); // free memory
bool iset_isempty(isetp s); // test emptiness
bool iset_isin(isetp s, int e); // e included in s?
int iset_max(isetp s); // return max value
void iset_addelt(isetp s, int e); // add e to s
void iset_subelt(isetp s, int e); // remove e from s
isetp iset_union(isetp s, isetp q); // set union
// iset_1.c --- iset impl w/ unsorted array of fixed size.
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include "iset.h"
#define MAXARRAY 10000
struct iset { int size, *a; };
isetp iset_new() {
isetp s = (isetp)malloc(sizeof(struct iset));
s->size = 0; s->a = (int*)malloc(sizeof(int)*MAXARRAY);
return s;
}
void iset_free(isetp s) { free(s->a); free(s); }
static int isin1(isetp s, int e) {
for(int i = 0; i < s->size; ++i) {
if(s->a[i] == e) { return i; }
}
return -1;
}
bool iset_isempty(isetp s) { return s->size == 0; }
bool iset_isin(isetp s, int e) { return isin1(s, e) >= 0; }
static int max2(int a, int b) { return (a > b) ? a : b; }
int iset_max(isetp s) {
int max = 0;
for(int i = 0; i < s->size; ++i) { max = max2(max, s->a[i]); }
return max;
}
void iset_addelt(isetp s, int e) {
if(iset_isin(s, e) || s->size >= MAXARRAY-1) { return; }
s->a[(s->size)++] = e;
}
void iset_subelt(isetp s, int e) {
int i = isin1(s, e); if(i < 0) { return; }
s->a[i] = s->a[--(s->size)];
}
isetp iset_union(isetp s, isetp t) {
isetp u = iset_new();
for(int i = 0; i < s->size; ++i) { iset_addelt(u, s->a[i]); }
for(int i = 0; i < t->size; ++i) {
if(!iset_isin(s, t->a[i])) { iset_addelt(u, t->a[i]); }
}
return u;
}
void expect_iset(isetp s, int m, int n, int a[], char *msg) {
bool ok = true; int p = 0;
for(int i = 0; i <= m; ++i) {
if(p < n && i == a[p]) {
++p;
if(!iset_isin(s, i)) { printf(" NG: %d not in set.\n", i); ok = false; }
} else {
if(iset_isin(s, i)) { printf(" NG: %d in set.\n", i); ok = false; }
}
}
printf("%s %s\n", ok?"OK":"NG", msg);
}
// test_iset.c --- unit test for iset.
#include <stdbool.h>
#include <stdio.h>
#include "iset.h"
void expect_iset(isetp s, int m, int n, int a[], char *msg) {
bool ok = true; int p = 0;
for(int i = 0; i <= m; ++i) {
if(p < n && i == a[p]) {
++p;
if(!iset_isin(s, i)) { printf(" NG: %d not in set.\n", i); ok = false; }
} else {
if(iset_isin(s, i)) { printf(" NG: %d in set.\n", i); ok = false; }
}
}
printf("%s %s\n", ok?"OK":"NG", msg);
}
int main(void) {
int a[] = { 1, 3, 5, 7 };
isetp s = iset_new();
iset_addelt(s, 1); iset_addelt(s, 3); iset_addelt(s, 5);
expect_iset(s, 9, 3, a, "initial: { 1 3 5 }"); iset_subelt(s, 1);
expect_iset(s, 9, 2, a+1, "- { 1 }: { 3 5 }");
isetp q = iset_new(); iset_addelt(q, 7); iset_addelt(q, 5);
isetp r = iset_union(s, q);
expect_iset(r, 9, 3, a+1, "+ { 7 5 }: { 3 5 7 }");
iset_free(s); iset_free(q); iset_free(r);
return 0;
}
// randdemo.c --- demonstration of rand.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main(int argc, char *argv[]) {
int i, n = atoi(argv[1]);
srand(time(NULL));
for(i = 0; i < n; ++i) { printf(" %d", rand() % 1000); }
printf("\n");
for(i = 0; i < n; ++i) { printf(" %.3f", rand()/(double)RAND_MAX); }
printf("\n");
return 0;
}
// timedemo.c --- demonstration of mesuring time.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "iset.h"
int pow3n(int n) {
if(n < 1) { return 1; }
else { return pow3n(n-1)+pow3n(n-1)+pow3n(n-1); }
}
int main(int argc, char *argv[]) {
int i, n = atoi(argv[1]);
struct timespec tm1, tm2;
clock_gettime(CLOCK_REALTIME, &tm1);
int v = pow3n(n);
clock_gettime(CLOCK_REALTIME, &tm2);
double dt = (tm2.tv_sec-tm1.tv_sec) + 1e-9*(tm2.tv_nsec-tm1.tv_nsec);
printf("pow3n(%d) = %d; elapsed-time = %.4f\n", n, v, dt);
return 0;
}
int bsearch(int *a, int e, int i, int j) {
if(i > j) { return -1; }
int k = (i + j) / 2;
if(a[k] == e) {
return k;
} else if(a[k] > e) {
return bsearch(a, e, i, k-1);
} else {
return bsearch(a, e, k+1, j);
}
}
// iset_4.c --- iset impl w/ unsiged long bitmap.
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include "iset.h"
#define MAXARRAY 10
struct iset { unsigned long bits; };
isetp iset_new() {
isetp s = (isetp)malloc(sizeof(struct iset));
s->bits = 0L; return s;
}
void iset_free(isetp s) { free(s); }
bool iset_isempty(isetp s) { return s->bits == 0L; }
bool iset_isin(isetp s, int e) { return (s->bits & 1L<<e) != 0; }
int iset_max(isetp s) {
int i;
printf("%lx\n", s->bits);
for(i = 63; i > 0; --i) {
if(iset_isin(s, i)) { return i; }
}
return 0;
}
void iset_addelt(isetp s, int e) { s->bits |= 1L<<e; }
void iset_subelt(isetp s, int e) { s->bits &= ~(1L << e); }
isetp iset_union(isetp s, isetp t) {
isetp u = iset_new(); u->bits = s->bits | t->bits;
return u;
}