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