// remember to   CC -lpthread

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <pthread.h>

int * randomlist(int n)
{ int * arr = (int *)malloc(n * sizeof(int));
  int i;
  for (i=0; i<n; i+=1)
    arr[i] = i;
  for (i=0; i<10*n; i+=1)
  { int r = random() % n;
    int t = arr[0];
    arr[0] = arr[r];
    arr[r] = t; }
  return arr; }

void printlist(int * a, int n)
{ int i;
  printf("%d", a[0]);
  for (i=1; i<n; i+=1)
    printf(",%d", a[i]);
  printf("\n"); }

typedef struct _tree
{ int data;
  struct _tree * left, * right; } tree;

tree * treeadd(tree * t, int x)
{ if (t == NULL)
  { t = (tree *)malloc(sizeof(tree));
    t->data = x;
    t->left = NULL;
    t->right = NULL; }
  else if (x < t->data)
    t->left = treeadd(t->left, x);
  else
    t->right = treeadd(t->right, x);
  return t; }

tree * treefromlist(int * a, int n)
{ tree * t = NULL;
  int i;
  for (i=0; i<n; i+=1)
    t = treeadd(t, a[i]);
  return t; }

void treeprint(tree * t)
{ if (t == NULL)
    return;
  printf("(");
  treeprint(t->left);
  printf("%d", t->data);
  treeprint(t->right);
  printf(")"); }

typedef struct _squeue
{ int size, first, last, num;
  pthread_mutex_t * semaphore;
  int * items; } squeue;

squeue * makesqueue(int s)
{ squeue * q = (squeue *)malloc(sizeof(squeue));
  q->size = s;
  q->num = 0;
  q->first = 0;
  q->last = 0;
  q->items = (int *)malloc(s * sizeof(int));
  pthread_mutex_init(q->semaphore, NULL);
  return q; }

void add_to_squeue(squeue * q, int x)
{ while (1)
  { pthread_mutex_lock(q->semaphore);
    if (q->num < q->size)
      break;
    pthread_mutex_unlock(q->semaphore);
    usleep(100); }
  q->items[q->last] = x;
  q->last += 1;
  if (q->last == q->size)
    q->last = 0;
  q->num += 1;
  pthread_mutex_unlock(q->semaphore); }

int get_from_squeue(squeue * q)
{ int x;
  while (1)
  { pthread_mutex_lock(q->semaphore);
    if (q->num > 0)
      break;
    pthread_mutex_unlock(q->semaphore);
    usleep(100); }
  x = q->items[q->first];
  q->first += 1;
  if (q->first == q->size)
    q->first = 0;
  q->num -= 1;
  pthread_mutex_unlock(q->semaphore);
  return x; }

typedef struct
{ char * name;
  tree * tr;
  squeue * out;
  pthread_t id; } treethreadinfo;

treethreadinfo * maketreethread(char * n, tree * t, squeue * q)
{ treethreadinfo * i = (treethreadinfo *)malloc(sizeof(treethreadinfo));
  i->name = n;
  i->tr = t;
  i->out = q;
  return i; }

typedef struct
{ char * name;
  squeue * in1, * in2;
  pthread_t id; } comparethreadinfo;

comparethreadinfo * makecomparethread(char * n, squeue * q1, squeue * q2)
{ comparethreadinfo * i = (comparethreadinfo *)malloc(sizeof(comparethreadinfo));
  i->name = n;
  i->in1 = q1;
  i->in2 = q2;
  return i; }

void treeout(treethreadinfo * info, tree * t)
{ if (t == NULL)
    return;
  treeout(info, t->left);
  add_to_squeue(info->out, t->data);
  printf("%s adding %d\n", info->name, t->data);
  usleep(500000);
  treeout(info, t->right); }

void * treeouter(void * a)
{ int i;
  treethreadinfo * info = (treethreadinfo *)a;
  treeout(info, info->tr); }

void * comparer(void * a)
{ }

int main()
{ const int size = 100;
  int * list1 = randomlist(size),
      * list2 = randomlist(size);
  tree * tree1 = treefromlist(list1, size),
       * tree2 = treefromlist(list2, size);
  squeue * q1 = makesqueue(10), 
         * q2 = makesqueue(10);
  treethreadinfo * thr1 = maketreethread("tree1", tree1, q1),
                 * thr2 = maketreethread("tree2", tree2, q2);
  comparethreadinfo * thr3 = makecomparethread("comparer", q1, q2);
  printf("tree 1: ");
  treeprint(tree1);
  printf("\n");
  printf("tree 2: ");
  treeprint(tree2);
  printf("\n");
  pthread_create(& thr1->id, NULL, treeouter, & thr1);
  pthread_create(& thr2->id, NULL, treeouter, & thr2);
  pthread_create(& thr3->id, NULL, comparer, & thr3);
  void * x;
  pthread_join(thr1->id, & x);
  pthread_join(thr2->id, & x);
  pthread_join(thr3->id, & x);
  printf("\ndone\n"); }