// CLRS section 20.3 exercises and driver to give vEB
// implementation for simple set membership.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "real.book.c"

// Exercise 20.3-3

VEBtype* initVEBstruct(int k)
// Constructs entire tree
{
  VEBtype *V;
  int i;

  V=(VEBtype*) malloc(sizeof(VEBtype));
  V->klocal=k;
  V->min=V->max=vEBNIL;
  if (k>1)
  {
    V->summary=initVEBstruct((k+1)/2);
    V->cluster=(VEBtype**) malloc((1<<((k+1)/2))*sizeof(VEBtype*));
    for (i=0; i<(1<<((k+1)/2)); i++)
      V->cluster[i]=initVEBstruct(k/2);
  }
  V->comment=NULL;
  return V;
}

int comments(VEBtype *V)
// Recursively checks cluster for any comments
{
  int i;

  if (V->comment)
    return 1;
  if (V->klocal>1)
  {
    if (comments(V->summary))
      return 1;
    for (i=0; i < 1<<((V->klocal+1)/2); i++)
      if (comments(V->cluster[i]))
        return 1;
  }
  return 0;
}

// Tree walk, similar to p. 548 of CLRS, but "sideways"
void treewalk(VEBtype *V,int indent,char *str,int base)
{
  int i;
  char clusterName[30];

/**/
  if (V->min==V->max && V->min==vEBNIL && !comments(V))
    return;
/**/
  for (i=0;i<4*indent;i++)
    printf(" ");
  printf("%s (base %d) ",str,base);
  printf("u %d ",1<<V->klocal);
  if (V->min==vEBNIL)
    printf("min / ");
  else
    printf("min %d (%d) ",V->min,base+V->min);
  if (V->max==vEBNIL)
    printf("max /");
  else
  {
    printf("max %d",V->max);
    if (V->klocal==1 && V->max!=V->min)
      printf(" (%d)",base+V->max);
  }
  if (V->comment)
  {
    printf(" [%s]",V->comment);
    free(V->comment);
    V->comment=NULL;
  }
  printf("\n");

  if (V->klocal>1)
  {
    treewalk(V->summary,indent+1,"summary",0);
    for (i=0; i < 1<<((V->klocal+1)/2); i++)
    {
      sprintf(clusterName,"cluster[%d]",i);
      treewalk(V->cluster[i],indent+1,clusterName,base+i*(1<<(V->klocal/2)));
    }
  }
}

int main()
{
  VEBtype* root;
  int k,n;
  int i,key;

  while (1)
  {
    scanf("%d",&i);
    switch (i) {
      case 0:
        exit(0);
      case 1:
        scanf("%d",&k);
        root=initVEBstruct(k);
        break;
      case 2:
        touchFlag=0;
        continue;
      case 3:
        touchFlag=1;
        continue;
      case 4:
        printf("minimum is %d\n",VEBminimum(root));
        break;
      case 5:
        printf("maximum is %d\n",VEBmaximum(root));
        break;
      case 6:
        scanf("%d",&key);
        if (VEBmember(root,key))
          printf("%d is a member\n",key);
        else
          printf("%d is not a member\n",key);
        break;
      case 7:
        scanf("%d",&key);
        printf("successor of %d is %d\n",key,VEBsuccessor(root,key));
        break;
      case 8:
        scanf("%d",&key);
        printf("predecessor of %d is %d\n",key,VEBpredecessor(root,key));
        break;
      case 9:
        scanf("%d",&key);
        i=touchFlag;
        touchFlag=0;
        if (VEBmember(root,key))
        {
          printf("%d is already a member\n",key);
          touchFlag=i;
          continue;
        }
        else
        {
          touchFlag=i;
          VEBinsert(root,key);
          printf("insert of %d completed\n",key);
        }
        break;
      case 10:
        scanf("%d",&key);
        i=touchFlag;
        touchFlag=0;
        if (!VEBmember(root,key))
        {
          printf("%d is not a member\n",key);
          touchFlag=i;
          continue;
        }
        else
        {
          touchFlag=i;
          VEBdelete(root,key);
          printf("delete of %d completed\n",key);
        }
        break;
      default:
        printf("input ignored\n");
        continue;
    }
    if (touchFlag)
    {
      treewalk(root,0,"root",0);
      touchCount=0;
    }
  }
/*
  scanf("%d %d",&k,&n);
  root=initVEBstruct(k);
  for (i=0;i<n;i++)
  {
    scanf("%d",&key);
    if (key<0 || key>=1<<k)
    {
      printf("Range error for %d\n",key);
      exit(0);
    }
    if (VEBmember(root,key))
    {
      printf("Key %d already present\n",key);
      exit(0);
    }
    VEBinsert(root,key);
  }
  treewalk(root,0,"root",0);
  touchFlag=1;
  VEBdelete(root,0);
  treewalk(root,0,"root",0);
*/
}