#include <time.h>
#include <stdio.h>
#include <stdlib.h>

extern const char *__progname;

typedef struct b B;

struct b {
  int bal;
  B *l;
  B *r;
  B *u;
  unsigned int v;
  } ;

#define MAXV 65536

static unsigned int seed;
static B *root;
static B arrb[MAXV];
static B *barr[MAXV];
static int nbusy;
static unsigned int vfree[MAXV];
static B *farr[MAXV];
static int nfree;

static void panic(const char *msg)
{
 printf("%s\n",msg);
 fflush(0);
 fflush(0);
 fflush(0);
 abort();
}

static int rebalance(B **pp, B *pptr)
{
 B *p;
 B *f;
 B *b;
 B *c;

 p = *pp;
 if (pptr != p->u) panic("pptr wrong");
 switch (p->bal)
  { case 0:
       return(0);
       break;
    case -1: case 1:
       return(1);
       break;
    case -2:
       if (p->l->bal <= 0)
	{ // case 1
	  p->bal = -1 - p->l->bal;
	  p->l->bal ++;
	  *pp = p->l;
	  p->l->u = pptr;
	  f = p->l->r;
	  p->l->r = p;
	  p->u = p->l;
	  p->l = f;
	  if (f) f->u = p;
	  if (p->bal) return(1);
	}
       else
	{ // case 2
	  f = p->l->r;
	  b = f->l;
	  c = f->r;
	  *pp = f;
	  f->u = pptr;
	  f->l = p->l;
	  f->l->u = f;
	  f->r = p;
	  p->u = f;
	  f->l->r = b;
	  if (b) b->u = f->l;
	  p->l = c;
	  if (c) c->u = p;
	  f->l->bal = (f->bal > 0) ? -1 : 0;
	  f->r->bal = (f->bal < 0) ? 1 : 0;
	  f->bal = 0;
	}
       break;
    case 2:
       if (p->r->bal >= 0)
	{ // case 3
	  p->bal = 1 - p->r->bal;
	  p->r->bal --;
	  *pp = p->r;
	  p->r->u = pptr;
	  f = p->r->l;
	  p->r->l = p;
	  p->u = p->r;
	  p->r = f;
	  if (f) f->u = p;
	  if (p->bal) return(1);
	}
       else
	{ // case 4
	  f = p->r->l;
	  b = f->r;
	  c = f->l;
	  *pp = f;
	  f->u = pptr;
	  f->r = p->r;
	  f->r->u = f;
	  f->l = p;
	  p->u = f;
	  f->r->l = b;
	  if (b) b->u = f->r;
	  p->r = c;
	  if (c) c->u = p;
	  f->r->bal = (f->bal < 0) ? 1 : 0;
	  f->l->bal = (f->bal > 0) ? -1 : 0;
	  f->bal = 0;
	}
       break;
    default:
       panic("impossible rebalance");
       break;
  }
 return(0);
}

static int insert(B **pp, B *b, B *u)
{
 B *p;

 p = *pp;
 if (! p)
  { *pp = b;
    b->u = u;
    return(1);
  }
 if (b->v < p->v)
  { if (insert(&p->l,b,p))
     { p->bal --;
       return(rebalance(pp,u));
     }
  }
 else // if (b->v >= p->v)
  { if (insert(&p->r,b,p))
     { p->bal ++;
       return(rebalance(pp,u));
     }
  }
 return(0);
}

static void add(B *b)
{
 b->bal = 0;
 b->l = 0;
 b->r = 0;
 insert(&root,b,0);
}

static void rem(B *b)
{
 B *p;
 B *l;
 B *r;
 B **pp;
 int dr;
 B *s;

 p = b->u;
 l = b->l;
 r = b->r;
 pp = p ? (p->l == b) ? &p->l : &p->r : &root;
 dr = p ? (p->l == b) ? 1 : -1 : 0;
 if (! b->r)
  { if (! b->l)
     { *pp = 0;
     }
    else
     { b->l->u = p;
       *pp = b->l;
     }
  }
 else if (! b->l)
  { b->r->u = p;
    *pp = b->r;
  }
 else if (! b->r->l)
  { b->r->l = b->l;
    b->l->u = b->r;
    b->r->u = p;
    *pp = b->r;
    p = b->r;
    p->bal = b->bal;
    dr = -1;
  }
 else
  { s = b->r;
    while (s->l) s = s->l;
    s->u->l = s->r;
    if (s->r) s->r->u = s->u;
    s->l = b->l;
    b->l->u = s;
    s->r = b->r;
    b->r->u = s;
    s->bal = b->bal;
    b = s->u;
    s->u = p;
    *pp = s;
    p = b;
    dr = 1;
  }
 if (p)
  { p->bal += dr;
    while <"delrebal"> (1)
     { switch (p->bal)
	{ case 0:
	     if (p->u)
	      { p->u->bal += (p == p->u->l) ? 1 : -1;
		p = p->u;
		continue;
	      }
	     break <"delrebal">;
	  case -1:
	  case 1:
	     break <"delrebal">;
	  case -2:
	  case 2:
	     s = p->u;
	     if (s)
	      { dr = s->bal;
		s->bal += (p == s->l) ? 1 : -1;
		if (rebalance((p==s->l)?&s->l:&s->r,s))
		 { s->bal = dr;
		   break <"delrebal">;
		 }
		p = s;
		continue;
	      }
	     rebalance(&root,0);
	     break <"delrebal">;
	  default:
	     panic("impossible delete balance");
	     break;
	}
     }
  }
}

static void handleargs(int ac, char **av)
{
 switch (ac)
  { case 1:
       seed = time(0);
       break;
    case 2:
       seed = strtoul(av[1],0,0);
       break;
    default:
       printf("Usage: %s random-seed\n",__progname);
       exit(1);
       break;
  }
}

static void init(void)
{
 int i;

 printf("%u\n",seed);
 srandom(seed);
 for (i=MAXV-1;i>=0;i--)
  { vfree[i] = i;
    farr[i] = &arrb[i];
  }
 nfree = MAXV;
 nbusy = 0;
 root = 0;
}

static int check(B *b, unsigned int minv, unsigned int maxv)
{
 int ld;
 int rd;

 if (b == 0) return(0);
 if ((b->bal < -1) || (b->bal > 1)) panic("impossible balance");
 if ((b->v < minv) || (b->v > maxv)) panic("values not in order");
 ld = check(b->l,minv,b->v-1);
 rd = check(b->r,b->v+1,maxv);
 if (ld+b->bal != rd) panic("incorrect balance");
 return(((ld>rd)?ld:rd)+1);
}

static void dump_tree_(B *b, int d)
{
 if (! b)
  { printf("%*snil\n",d,"");
    return;
  }
 printf("%*s%p [%d %u]\n",d,"",(void *)b,b->bal,b->v);
 if (b->l) dump_tree_(b->l,d+2);
 if (b->r) dump_tree_(b->r,d+2);
}

static void dump_tree(B *) __attribute__((__used__));
static void dump_tree(B *b)
{
 dump_tree_(b,0);
}

int main(int, char **);
int main(int ac, char **av)
{
 B *b;
 unsigned int iter;
 unsigned int x;
 unsigned int y;

 handleargs(ac,av);
 init();
 iter = 0;
 while (1)
  { if (nbusy + nfree != MAXV) panic("nbusy/nfree mismatch");
    iter ++;
    x = random() % MAXV;
    if (x < nbusy)
     { b = barr[x];
       nbusy --;
       if (x != nbusy)
	{ barr[x] = barr[nbusy];
	  barr[nbusy] = b;
	}
       printf("%u: delete %p %u\n",iter,(void *)b,b->v);
       rem(b);
       vfree[nfree] = b->v;
       farr[nfree] = b;
       nfree ++;
     }
    else
     { x -= nbusy;
       if (x >= nfree) panic("nbusy/nfree/random mismatch");
       y = random() % nfree;
       nfree --;
       b = farr[x];
       if (x != nfree) farr[x] = farr[nfree];
       b->v = vfree[y];
       if (y != nfree) vfree[y] = vfree[nfree];
       printf("%u: add %p %u\n",iter,(void *)b,b->v);
       add(b);
       barr[nbusy] = b;
       nbusy ++;
     }
    check(root,0,MAXV-1);
  }
}