/* 
    a modified leftist tree, where all nodes can be deleted independently.
    while a backtracking pointer (parent) must be present to remove an
    arbitrary node within the tree, we can utilize this pointer to run all
    the way back along the parent node chain to perform post-adjustment, 
    without recursion.

    this can be used to implement the timer priority queue, where each timer
    may be inserted and removed randomly (ordinary priority queue only allows
    top node to be removed.)

    on my computer (PIII-Mobile 750MHz), compiled by gcc-3.3.1-cygwin 
    with -O2, insertion of 5,000,000 nodes runs approx. 6 seconds, and 
    deletion 8 seconds.

    --
    brianchon
    2003-10-31
*/

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

typedef struct _S_node_t node_t, *node_p, **node_pp;

struct _S_node_t {
    int key;
    int dist;
    node_p parent, left, right;
};

node_p merge(node_p t1, node_p t2)
{
    node_p p, q = 0, l = t1, r = t2;
    node_pp pp = &p;

    while ( l && r ) {
        if ( l->key < r->key ) {
            *pp = l;
            l = l->right;
        } else {
            *pp = r;
            r = r->right;
        }

        (*pp)->parent = q;
        q = *pp;
        pp = &(q->right);
    }

    if ( l ) {
        l->parent = q;
        *pp = l;
    } else if ( r ) {
        r->parent = q;
        *pp = r;
    } else
        *pp = 0;

    while ( q ) {
        if ( !(r = q->right) )
            q->dist = 0;
        else if ( !(l = q->left) ) {
            q->left = r;
            q->right = 0;
            q->dist = 0;
        } else {
            if ( l->dist < r->dist ) {
                q->left = r;
                q->right = l;
                q->dist = l->dist+1;
            } else 
                q->dist = r->dist+1;
        }

        q = q->parent;
    }

    return p;
}

void ins(node_pp root, node_p node)
{
    node->right = node->left = 0;
    node->dist = 0;

    *root = merge(*root, node);
}

void del(node_pp root, node_p node)
{
    node_p p, q;
    int d;
    
    p = merge(node->left, node->right);

    if ( node == *root ) {
        *root = p;
        return;
    }

    q = node->parent;

    if ( p ) {
        p->parent = q;
        d = p->dist+1;
    } else
        d = 0;

    if ( q->left == node )
        q->left = p;
    else
        q->right = p;

    while ( q && d < q->dist ) {
        if ( q->left == p ) {
            q->left = q->right;
            q->right = p;
        }

        q->dist = d++;
        p = q;
        q = q->parent;
    };

    while ( q && d > q->dist && q->right == p )  {
        if ( q->left->dist+1 < d ) {
            d = q->left->dist+1;
            q->right = q->left;
            q->left = p;
        }
    
        q->dist = d++;
        p = q;
        q = q->parent;
    }
}

int verify(node_p root)
{
    node_p l, r;

    if ( !root )
        return 1;

    l = root->left;
    r = root->right;

    if ( !r )
        return root->dist == 0 
            && (  !l 
               || (  root->key <= l->key 
                  && root == l->parent 
                  && verify(l)));

    if ( !l )
        return 0;

    return root->key <= l->key 
        && root->key <= r->key
        && root->dist == r->dist+1
        && root == r->parent && root == l->parent
        && r->dist <= l->dist
        && verify(r)
        && verify(l);
}

#define NODES 5000000

node_t n[NODES];

node_p root = 0;

void do_verify()
{
    printf("verifying\n");
    printf("verification result: %d\n", verify(root));
}

void do_init()
{
    int i;

    printf("initializing\n");

    for ( i = 0; i < NODES; ++i )
        n[i].key = i; //rand();
}

void do_ins(int start, int interval, int rem)
{
    int i, j;
    clock_t t;

    printf("inserting (%d, +%d, %d-%d)\n", start, interval, NODES, rem);

    t = clock();

    for ( i = 0, j = start%NODES; i < NODES-rem; ++i, j = (j+interval)%NODES )
        ins(&root, n+j);

    printf("time: %.4f\n", (double)(clock()-t)/CLOCKS_PER_SEC);
}

void do_del(int start, int interval, int rem)
{
    int i, j;
    clock_t t;

    printf("deleting (%d, +%d, %d-%d)\n", start, interval, NODES, rem);

    t = clock();

    for ( i = 0, j = start%NODES; i < NODES-rem; ++i, j = (j+interval)%NODES )
        del(&root, n+j);

    printf("time: %.4f\n", (double)(clock()-t)/CLOCKS_PER_SEC);
}

int main()
{
    do_init();

    do_ins(123, 107, 0);
    do_verify();

    do_del(321, 47, 10);
    do_verify();

    do_ins(321, 47, 10);
    do_verify();

    do_del(567, 27449, 10);
    do_verify();

    while ( root ) {
        printf("%d\n", root->key);
        del(&root, root);
    }

    return 0;
}