/* Converts |tree| into a vine. */
static void
tree_to_vine (struct pbst_table *tree)
{
  struct pbst_node *q, *p;

  q = (struct pbst_node *) &tree->pbst_root;
  p = tree->pbst_root;
  while (p != NULL)
    if (p->pbst_link[1] == NULL)
      {
        q = p;
        p = p->pbst_link[0];
      }
    else
      {
        struct pbst_node *r = p->pbst_link[1];
        p->pbst_link[1] = r->pbst_link[0];
        r->pbst_link[0] = p;
        p = r;
        q->pbst_link[0] = r;
      }
}

/* Performs a compression transformation |count| times,
   starting at |root|. */
static void
compress (struct pbst_node *root, unsigned long count)
{
  assert (root != NULL);

  while (count--)
    {
      struct pbst_node *red = root->pbst_link[0];
      struct pbst_node *black = red->pbst_link[0];

      root->pbst_link[0] = black;
      red->pbst_link[0] = black->pbst_link[1];
      black->pbst_link[1] = red;
      red->pbst_parent = black;
      if (red->pbst_link[0] != NULL)
        red->pbst_link[0]->pbst_parent = red;
      root = black;
    }
}

/* Converts |tree|, which must be in the shape of a vine, into a balanced
   tree. */
static void
vine_to_tree (struct pbst_table *tree)
{
  unsigned long vine;      /* Number of nodes in main vine. */
  unsigned long leaves;    /* Nodes in incomplete bottom level, if any. */
  int height;              /* Height of produced balanced tree. */
  struct pbst_node *p, *q; /* Current visited node and its parent. */

  leaves = tree->pbst_count + 1;
  for (;;)
    {
      unsigned long next = leaves & (leaves - 1);
      if (next == 0)
        break;
      leaves = next;
    }
  leaves = tree->pbst_count + 1 - leaves;

  compress ((struct pbst_node *) &tree->pbst_root, leaves);

  vine = tree->pbst_count - leaves;
  height = 1 + (leaves > 0);
  while (vine > 1)
    {
      compress ((struct pbst_node *) &tree->pbst_root, vine / 2);
      vine /= 2;
      height++;
    }

  for (q = NULL, p = tree->pbst_root; p != NULL; q = p, p = p->pbst_link[0])
    p->pbst_parent = q;
}

/* Balances |tree|.
   Ensures that no simple path from the root to a leaf has more than
   |PBST_MAX_HEIGHT| nodes. */
void
pbst_balance (struct pbst_table *tree)
{
  assert (tree != NULL);

  tree_to_vine (tree);
  vine_to_tree (tree);
}