// Corresponds to pseudocode in CLRS, 3rd ed, section 20.3
// Solutions to exercises on p. 556 are in a separate driver source file.

#define vEBNIL (-1)

// Helper functions. u is 2**k

#define high(x,k) ( (x) / (1<<((k)/2)) )

#define low(x,k)  ( (x) % (1<<((k)/2)) )

#define index(x,y,k) ( (x)*(1<<((k)/2)) + (y) )

typedef struct VEBstruct VEBtype;

struct VEBstruct {
  char klocal;        // Use 1<<klocal to get local value of u
  int min,max;
  VEBtype *summary;
  VEBtype **cluster;
  char *comment;
};

int touchFlag=0,touchCount=0;

void touch(VEBtype *V,char *str)
{
  char commentString[500];

  if (touchFlag)
  {
    if (V->comment)
      sprintf(commentString,"%s %d: %s",V->comment,++touchCount,str);
    else
      sprintf(commentString,"%d: %s",++touchCount,str);
    V->comment=(char*) malloc(strlen(commentString)+1);
    strcpy(V->comment,commentString);
    //printf("touch %d\n",touchCount);
  }
}

int VEBminimum(VEBtype *V)
// Returns smallest member of tree for V*
{
  char str[50];
  sprintf(str,"minimum=%d",V->min);
  touch(V,str);
  return V->min;
}

int VEBmaximum(VEBtype *V)
// Returns largest member of tree for V*
{
  char str[50];
  sprintf(str,"maximum=%d",V->max);
  touch(V,str);
  return V->max;
}

int VEBmember(VEBtype *V,int x)
{
  char str[50];

  if (x==V->min || x==V->max)
  {
    sprintf(str,"member(%d)=1",x);
    touch(V,str);
    return 1;
  }
  if (V->klocal==1)
  {
    sprintf(str,"member(%d)=0",x);
    touch(V,str);
    return 0;
  }
  sprintf(str,"member(%d)=member(cluster[%d],%d)",
                                 x,high(x,V->klocal),low(x,V->klocal));
  touch(V,str);
  return VEBmember(V->cluster[high(x,V->klocal)],low(x,V->klocal));
}

int VEBsuccessor(VEBtype *V,int x)
{
  int maxLow,offset;
  char str[50];

  sprintf(str,"successor(%d)",x);
  touch(V,str);

  // At a leaf
  if (V->klocal==1)
  {
    if (x==0 && V->max==1)
    {
      sprintf(str,"leaf successor(%d)=1",x);
      touch(V,str);
      return 1;
    }
    sprintf(str,"no leaf successor(%d)=vEBNIL",x);
    touch(V,str);
    return vEBNIL;
  }

  // Don't have to descend into tree.
  if (V->min!=vEBNIL && x<V->min)
  {
    sprintf(str,"root successor(%d)=V->min=%d",x,V->min);
    touch(V,str);
    return V->min;
  }

  sprintf(str,"must descend");
  touch(V,str);

  // maxLow is largest value in a cluster whose universe includes x.
  maxLow=VEBmaximum(V->cluster[high(x,V->klocal)]);
  sprintf(str,"maxLow=%d",maxLow);
  touch(V,str);
  if (maxLow!=vEBNIL && low(x,V->klocal)<maxLow)
  {
    // There is at least one member of this cluster that is larger than x.
    // Descend into cluster to get successor.  offset is x's successor
    // within the universe of that cluster.
    offset=VEBsuccessor(V->cluster[high(x,V->klocal)],low(x,V->klocal));
    sprintf(str,"descent successor(%d)=%d",x,
            index(high(x,V->klocal),offset,V->klocal));
    touch(V,str);
    return index(high(x,V->klocal),offset,V->klocal);
  }

  sprintf(str,"descent failed");
  touch(V,str);

  // Couldn't find successor by descending, so check for neighboring
  // cluster with members.
  int succCluster=VEBsuccessor(V->summary,high(x,V->klocal));
  if (succCluster==vEBNIL)
  {
    sprintf(str,"no neighbor successor(%d)=vEBNIL",x);
    touch(V,str);
    return vEBNIL;
  }

  sprintf(str,"use succCluster");
  touch(V->cluster[succCluster],str);

  // Neighbor with members, so just need its minimum. offset is x's successor
  // within the universe of that cluster.
  offset=VEBminimum(V->cluster[succCluster]);
  sprintf(str,"neighbor successor(%d)=%d",x,
          index(succCluster,offset,V->klocal));
  touch(V,str);
  return index(succCluster,offset,V->klocal);
}

int VEBpredecessor(VEBtype *V,int x)
{
  int minLow,offset;
  char str[50];

  sprintf(str,"predecessor(%d)",x);
  touch(V,str);

  // At a leaf
  if (V->klocal==1)
  {
    if (x==1 && V->min==0)
    {
      sprintf(str,"leaf predecessor(%d)=0",x);
      touch(V,str);
      return 0;
    }
    sprintf(str,"no leaf predecessor(%d)=vEBNIL",x);
    touch(V,str);
    return vEBNIL;
  }

  // Don't have to descend into tree.
  if (V->max!=vEBNIL && x>V->max)
  {
    sprintf(str,"root predecessor(%d)=V->max=%d",x,V->max);
    touch(V,str);
    return V->max;
  }

  sprintf(str,"must descend");
  touch(V,str);

  // minLow is smallest value in a cluster whose universe includes x.
  minLow=VEBminimum(V->cluster[high(x,V->klocal)]);
  sprintf(str,"minLow=%d",minLow);
  touch(V,str);
  if (minLow!=vEBNIL && low(x,V->klocal)>minLow)
  {
    // There is at least one member of this cluster that is smaller than x.
    // Descend into cluster to get predecessor.  offset is x's predecessor
    // within the universe of that cluster.
    offset=VEBpredecessor(V->cluster[high(x,V->klocal)],low(x,V->klocal));

    sprintf(str,"descent predecessor(%d)=%d",x,
            index(high(x,V->klocal),offset,V->klocal));
    touch(V,str);

    return index(high(x,V->klocal),offset,V->klocal);
  }

  sprintf(str,"descent failed");
  touch(V,str);

  // Couldn't find predecessor by descending, so check for neighboring
  // cluster with members.
  int predCluster=VEBpredecessor(V->summary,high(x,V->klocal));
  if (predCluster==vEBNIL)
  {
    if (V->min!=vEBNIL && x>V->min)
    {
      // Special case - predecessor is not in sub-cluster with
      // appropriate universe since it is smallest member in V.
      sprintf(str,"special - predecessor=V->min=%d",V->min);
      touch(V,str);
      return V->min;
    }
    else
    {
      sprintf(str,"no neighbor predecessor(%d)=vEBNIL",x);
      touch(V,str);
      return vEBNIL;
    }
  }

  sprintf(str,"use predCluster");
  touch(V->cluster[predCluster],str);

  // Neighbor with members, so just need its maximum. offset is x's predecessor
  // within the universe of that cluster.
  offset=VEBmaximum(V->cluster[predCluster]);
  sprintf(str,"neighbor predecessor(%d)=%d",x,
          index(predCluster,offset,V->klocal));
  touch(V,str);
  return index(predCluster,offset,V->klocal);
}

void VEBemptyTreeInsert(VEBtype *V,int x)
{
  char str[50];

  sprintf(str,"emptyTreeInsert(%d)",x);
  touch(V,str);
  V->min=x;
  V->max=x;
}

void VEBinsert(VEBtype *V,int x)
// Assumed that x is not a member of V.
{
  int temp;
  char str[50];

  sprintf(str,"insert(%d)",x);
  touch(V,str);
  if (V->min==vEBNIL)
    // Easy case, the tree for V is empty.
    VEBemptyTreeInsert(V,x);
  else
  {
    // Insertion into cluster with at least one member.
    if (x<V->min)
    {
      sprintf(str,"swapped arg %d with V->min %d",x,V->min);
      touch(V,str);
      // Swap x with minimum.
      temp=x;
      x=V->min;
      V->min=temp;
    }
    if (V->klocal>1)
    {
      if (VEBminimum(V->cluster[high(x,V->klocal)])==vEBNIL)
      {
        sprintf(str,"insert into empty sub-cluster");
        touch(V->cluster[high(x,V->klocal)],str);
        // Inserting into empty sub-cluster of cluster node with
        // other sub-clusters that have members.  Must change
        // status of formerly empty sub-cluster in summary.
        VEBinsert(V->summary,high(x,V->klocal));
        VEBemptyTreeInsert(V->cluster[high(x,V->klocal)],low(x,V->klocal));
      }
      else
      {
        sprintf(str,"insert into non-empty sub-cluster");
        touch(V->cluster[high(x,V->klocal)],str);
        // Insert into sub-cluster that already has at least one member.
        VEBinsert(V->cluster[high(x,V->klocal)],low(x,V->klocal));
      }
    }
    if (x>V->max)
    {
      sprintf(str,"increasing V->max to %d",x);
      touch(V,str);
      V->max=x;
    }
  }
}

void VEBdelete(VEBtype *V,int x)
// Assumed that x is a member of V!
{
  char str[50];

  sprintf(str,"delete(%d)",x);
  touch(V,str);
  if (V->min==V->max)
  {
    sprintf(str,"cluster is losing its one member");
    touch(V,str); 
    V->min=vEBNIL;
    V->max=vEBNIL;
  }
  else if (V->klocal==1)
  {
    sprintf(str,"leaf cluster going from two members to one");
    touch(V,str); 
    V->max=V->min=1-x;
  }
  else
  {
    if (x==V->min)
    {
      sprintf(str,"cluster losing minimum");
      touch(V,str); 
      // Since cluster is losing its minimum member, a replacement
      // minimum must be found by using the summary to find sub-cluster
      // to obtain minimum from.
      int firstCluster=VEBminimum(V->summary);
      x=index(firstCluster,VEBminimum(V->cluster[firstCluster]),V->klocal);
      sprintf(str,"V->min replaced by %d",x);
      touch(V,str);
      V->min=x;
      // x must now be deleted from sub-cluster.
    }
    sprintf(str,"deleting %d from sub-cluster",x);
    touch(V,str);
    VEBdelete(V->cluster[high(x,V->klocal)],low(x,V->klocal));
    if (VEBminimum(V->cluster[high(x,V->klocal)])==vEBNIL)
    {
      sprintf(str,"sub-cluster for %d is empty",x);
      touch(V,str);
      // Sub-cluster has become empty, so update summary.
      VEBdelete(V->summary,high(x,V->klocal));
      if (x==V->max)
      {
        sprintf(str,"need new max to replace %d",x);
        touch(V,str);
        // Deleting the maximum element of V, so find replacement.
        int summaryMax=VEBmaximum(V->summary);
        if (summaryMax==vEBNIL)
        {
          sprintf(str,"new max not found, now a one-element cluster");
          touch(V,str);
          // No element to replace with, so this is a one-element cluster.
          V->max=V->min;
        }
        else
        {
          // summaryMax sub-cluster has the new maximum.
          V->max=index(summaryMax,
                       VEBmaximum(V->cluster[summaryMax]),
                       V->klocal);
          sprintf(str,"V->max is now %d",V->max);
          touch(V,str);
        }
      }
    }
    else if (x==V->max)
    {
      // Need to replace maximum.
      V->max=index(high(x,V->klocal),
                   VEBmaximum(V->cluster[high(x,V->klocal)]),
                   V->klocal);
      sprintf(str,"corrected V->max to %d",V->max);
      touch(V,str);
    }
  }
}