#include <assert.h>
#include <stdio.h>

struct node {
  struct node *parent, *left, *right;
  int level;
  int data;
};

// A correct node (n) will have the following properties
// (T1) !n->left || n->left->parent == n
// (T2) !n->right || n->right->parent == n
// (T3) !Next(n) || n->data <= Next (n)->data;
// (AA1) !n->parent || n->parent->level >= n->level
// (AA2) n->level == (n->left == NULL ? 1 : n->left->level + 1)
// (AA3) n->level <= 1 || n->right && n->level - n->right->level <= 1
// (AA4) !n->parent || !n->parent->parent || n->parent->parent.level > n->level

struct node *First (struct node *root)
{
  if (!root->left) return NULL;
  while (root->left) root = root->left;
  return root;
}

struct node *Next (struct node *n)
{
  if (n->right) {
    n = n->right;
    while (n->left) n = n->left;
  }
  else {
    while (n->parent && n->parent->right == n) n = n->parent;
    // Follow the parent link while it's pointing to the left.
    n = n->parent; // Follow one parent link pointing to the right

    if (!n->parent) return NULL;
    // The last node is the root, because it has nothing to it's right
  }
  return n;
}

void Skew (struct node *oldparent)
{
  struct node *newp = oldparent->left;
  
  if (oldparent->parent->left == oldparent) oldparent->parent->left = newp;
  else oldparent->parent->right = newp;
  newp->parent = oldparent->parent;
  oldparent->parent = newp;
  
  oldparent->left = newp->right;
  if (oldparent->left) oldparent->left->parent = oldparent;
  newp->right = oldparent;
  
  oldparent->level = oldparent->left ? oldparent->left->level + 1 : 1;
}

int Split (struct node *oldparent)
{
  struct node *newp = oldparent->right;
  
  if (newp && newp->right && newp->right->level == oldparent->level) { 
    if (oldparent->parent->left == oldparent) oldparent->parent->left = newp;
    else oldparent->parent->right = newp;
    newp->parent = oldparent->parent;
    oldparent->parent = newp;
    
    oldparent->right = newp->left;
    if (oldparent->right) oldparent->right->parent = oldparent;
    newp->left = oldparent;
    newp->level = oldparent->level + 1;
    return 1;
  }
  return 0;
}

struct node root;
// A global variable to make things easy.

void RebalanceAfterLeafAdd (struct node *n)
{ // n is a node that has just been inserted and is now a leaf node.
  n->level = 1;
  n->left = NULL;
  n->right = NULL;
  for (n = n->parent; n != &root; n = n->parent) {
    // At this point n->parent->level == n->level
    if (n->level != (n->left ? n->left->level + 1 : 1)) {
      // At this point the tree is correct, except (AA2) for n->parent
      Skew (n);
      // We handle it (a left add) by changing it into a right add using Skew
      // If the original add was to the left side of a node that is on the
      // right side of a horisontal link, n now points to the rights side
      // of the second horisontal link, which is correct.
      
      // However if the original add was to the left of node with a horisontal
      // link, we must get to the right side of the second link.
      if (!n->right || n->level != n->right->level) n = n->parent;
    }
    if (!Split (n->parent)) break;
  }
}

void Delete (struct node *n)
{ // If n is not a leaf, we first swap it out with the leaf node that just
  // precedes it.
  struct node *leaf = n, *tmp;
  
  if (n->left) {
    for (leaf = n->left; leaf->right; leaf = leaf->right) {}
    // When we stop, left has no 'right' child so it cannot have a left one
  }
  else if (n->right) leaf = n->right;

  tmp = leaf->parent == n ? leaf : leaf->parent;
  if (leaf->parent->left == leaf) leaf->parent->left = NULL;
  else leaf->parent->right = NULL;
  
  if (n != leaf) {
    if (n->parent->left == n) n->parent->left = leaf;
    else n->parent->right = leaf;
    leaf->parent = n->parent;
    if (n->left) n->left->parent = leaf;
    leaf->left = n->left;
    if (n->right) n->right->parent = leaf;
    leaf->right = n->right;
    leaf->level = n->level;
  }
  // free (n);

  while (tmp != &root) {
    // One of tmp's childern had it's level reduced
    if (tmp->level > (tmp->left ? tmp->left->level + 1 : 1)) { // AA2 failed
      tmp->level--;
      if (Split (tmp)) {
        if (Split (tmp)) Skew (tmp->parent->parent);
        break;
      }
      tmp = tmp->parent;
    }
    else if (tmp->level <= (tmp->right ? tmp->right->level + 1 : 1)) break;
    else { // AA3 failed
      Skew (tmp);
      //if (tmp->right) tmp->right->level = tmp->right->left ? tmp->right->left->level + 1 : 1;
      if (tmp->level > tmp->parent->level) {
        Skew (tmp);
        Split (tmp->parent->parent);
        break;
      }
      tmp = tmp->parent->parent;
    }
  }
}

void Check (struct node *n)
{
  assert (!n->left || n->left->parent == n);
  assert (!n->right || n->right->parent == n);
  assert (!Next (n) || n->data <= Next (n)->data);
  assert (!n->parent || n->parent->level >= n->level);
  assert (n->level == (n->left == NULL ? 1 : n->left->level + 1));
  assert (n->level <= 1 || n->right && n->level - n->right->level <= 1);
  assert (!n->parent || !n->parent->parent ||
          n->parent->parent->level > n->level);
}

#define MAX 10000

int main (void)
{
  struct node t[MAX], *s;
  int i, j, lessThan, maxdepth = 0;

  root.left = NULL;
  root.right = NULL;
  root.level = 1000000;
  root.parent = NULL;
  
  for (i = 0; i < MAX; i++) { // Insert MAX speudo random numbers for testing
    t[i].data = (i * 523 + 342) % 1601;
    s = &root;
    lessThan = 1;
    while (lessThan ? s->left : s->right) {
      s = lessThan ? s->left : s->right;
      lessThan = t[i].data < s->data;
    }
    if (lessThan) s->left = t + i; else s->right = t + i;
    t[i].parent = s;
    RebalanceAfterLeafAdd (t + i);
    
    for (j = 0; j <= i; j++) Check (t + j); // Slow O(n^2) loop
  }
  for (i = 0; i < MAX; i++) {
    for (s = t + i, j = 0; s != &root; s = s->parent, j++) {}
    if (j > maxdepth) maxdepth = j;
  }
  while (i-- > 0) {
    s = First (&root);
    for (j = 0; j <= i; j++, s = Next (s)) Check (s); // Slow O(n^2) loop
    assert (!s);
    
    s = First (&root);
    if (Next (s)) s = Next (s);
    Delete (root.left); //s);
  }
  
  printf ("Max depth is %d %d\n", maxdepth, root.level);
  return 0;
}