#include "util.h"
#include "uf.h"

UF_TREE UF_new(token) CELL token;
{
  UF_TREE t = (UF_TREE) malloc (sizeof(*t));
  t -> parent = 0;
  t -> weight = 1;
  t -> token = token;
  t -> left = t;
  t -> right = t;
  return t;
}

UF_TREE UF_find(x) UF_TREE x;
{
  if (x -> parent == 0) return x;

  {
    UF_TREE t = UF_find(x -> parent);
    x -> parent = t;
    return t;
  }
}

UF_union (a,b) UF_TREE a,b;
{
  UF_TREE t, ar, bl;

  a = UF_find(a);
  b = UF_find(b);
  if (a == b)
    return;
  
  if (a -> weight < b -> weight)
    {
      t = a;
      a = b;
      b = t;
    }
  /* a is heavier than b */
  b -> parent = a;
  a -> weight = a -> weight + b -> weight;

  ar = a -> right;
  bl = b -> left;

  ar -> left = bl;
  bl -> right = ar;

  a -> right = b;
  b -> left = a;
}

UF_foreachin(a,f,s) UF_TREE a; CELL (*f)(); CELL s;
{
  UF_TREE b = a;
  do
    {
      s = (*f)(a -> token, s);
      a = a -> left;
    }
  while (a != b);
  return s;
}

#ifdef TEST
#include <stdio.h>

print_token(i,s) int i,s;
{
  printf("%d ",i);
  return s + i;
}

#define NS 25

main() {
  char buffer[256];
  UINT i,j,k;
  UF_TREE n[NS];
  int iterating = 1;

  for (i = 0; i < NS; i++) n[i] = UF_new(i);
       
  while (iterating)  {
    printf("\n");
    scanf("%s", buffer);

    switch(buffer[0]) {
    case 'u': case 'U': /* union two */
      scanf("%d", &i);
      scanf("%d", &j);
      UF_union(n[i],n[j]);
      break;
    case 'f': case 'F': /* find one */
      scanf("%d", &i);
      printf("%d is in %0x\n",i, UF_find(n[i]));
      break;
    case 'a': case 'A':
      scanf("%d", &i);
      printf("sums to %d\n", UF_foreachin(n[i], print_token, 0));
      break;      
    case 'd': case 'D': /* dump */
      for (i = 0; i < NS; i++) {
	printf("%d is in %0x\n",i, UF_find(n[i]));
      }
      break;
    case 'q': case 'Q':
      iterating = 0;    
      break;
    }
  }
}
#endif