#include <alloca.h>
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#ifndef NULL
#define NULL ((void*)0)
#endif

typedef struct treenode {
    struct treenode *leftnode;
    struct treenode *rightnode;
    char *data;
} treenode_t;

/*
 * return a ptr to the left, right childptr respectively.
 * NOTE: these return ptr to ptr
 */
treenode_t **leftptr(treenode_t *p)
{
    return &p->leftnode;
}

treenode_t **rightptr(treenode_t *p)
{
    return &p->rightnode;
}

/*
 * return number of nodes below AND INCLUDING the parameter
 */
int nbelow(treenode_t *p)
{
    if (NULL == p) {
        return 0;
    }
    return (nbelow(p->leftnode) + nbelow(p->rightnode) + 1);
}

typedef enum {
    left_to_right,
    right_to_left,
} dir_t;

/*
 * Can java do this?  Rather than writing one set of code to move 
 * a node from left to right (start with left side of "start", follow
 * the rightNode pointers, etc.) and another set to move a node from
 * right to left, use a single piece of code, a parameter, and pointers.
 */
treenode_t *move1(treenode_t *start, dir_t dir)
{
    treenode_t **(*from_side)(treenode_t *) = (treenode_t **(*)())0;
    treenode_t **(*to_side)(treenode_t *);
    treenode_t **pptr;                      /* ptr in parent */
    treenode_t *node2move;                  /* which 1 is moving */
    treenode_t *newstart;                   /* temp */
    /*
     * QUESTION 1: Does java let you assign function pointers so
     *             you can then just call thru the pointer -- change
     *             the semantics of the following code so you can
     *             write it just once?
     */
    switch (dir) {
        case left_to_right:
            from_side = leftptr;
            to_side = rightptr;
            break;      /* D'oh!! */
        case right_to_left:
            from_side = rightptr;
            to_side = leftptr;
    }
    assert(from_side);

    /* 
     * QUESTION 2: Does java let you assign through pointers?  This way
     *             we know that to unlink we just tweak *pptr; no need for
     *             special case code (if parent==start then update the
     *             parent's "from_side" ptr else update the parent's
     *             "to_side" ptr)
     */

    /* if we're here, from_side(start) canNOT return null */
    for (pptr = from_side(start), node2move = *pptr;
        NULL != *to_side(node2move);
        pptr = to_side(node2move), node2move = *pptr) {
            ;
    }
    /* Unlink node2move; to_side is NULL so we only need from_side */
    *pptr = *from_side(node2move);

    /* node2move is now unlinked; make it the new "start" */
    newstart = node2move;
    newstart->leftnode = start->leftnode;
    newstart->rightnode = start->rightnode;

    /* Now unlink "start" and move it into new position */
    start->leftnode = start->rightnode = NULL;
    node2move = start;
    start = newstart;

    for (pptr = to_side(start);
        NULL != *pptr;
        pptr = from_side(*pptr)) {
            ;
    }
    *pptr = node2move;
    return start;
}
/*
 * Rebalance below!  The middle node (i.e., "start") may get
 * replaced.
 */
treenode_t *rebal_below(treenode_t *start)
{
    int qty_left, qty_right;
    if (NULL == start) {
        return NULL;
    }
    qty_left = nbelow(start->leftnode);
    qty_right = nbelow(start->rightnode);
    /* Too many on left?  Then move 'em right */
    for ( ; qty_left > 1+qty_right; --qty_left, ++qty_right) {
        start = move1(start, left_to_right);
    }
    /* Too many on right?  Then move 'em left */
    for ( ; qty_right > 1+qty_left; --qty_right, ++qty_left) {
        start = move1(start, right_to_left);
    }
    start->leftnode = rebal_below(start->leftnode);
    start->rightnode = rebal_below(start->rightnode);
    return start;
}

treenode_t *root = (treenode_t *)0;

/*
 * display the tree in visible form.  
 */
#define BANNER(which) \
    printf("================ %s ================\n", which)

#define INDENT "-->"
void dump_tree(treenode_t *start, char *prefix) 
{
    char *new_prefix;
    int at_root = 0;
    if (root == start) {
        at_root = 1;
        BANNER("start tree dump");
    }
    if (NULL == start) {
        return;
    }
    new_prefix = alloca(strlen(prefix) + strlen(INDENT) + 2);
    if (NULL != start->leftnode) {
       strcpy(new_prefix, prefix);
       strcat(new_prefix, "L");
       strcat(new_prefix, INDENT);
       dump_tree(start->leftnode, new_prefix);
    }
    printf("%s%s\n", prefix, start->data);
    if (NULL != start->rightnode) {
       strcpy(new_prefix, prefix);
       strcat(new_prefix, "R");
       strcat(new_prefix, INDENT);
       dump_tree(start->rightnode, new_prefix);
    }
    if (at_root) {
        BANNER("end tree dump");
    }
}

/*
 * Create a new node.  Use permanent (malloc) storage.
 */
treenode_t *new_node(char *d2put)
{
    char *sspace = malloc(strlen(d2put)+1);
    treenode_t *nspace = malloc(sizeof(treenode_t));
    strcpy(sspace, d2put);
    nspace->leftnode = nspace->rightnode = NULL;
    nspace->data = sspace;
    return nspace;
}

/*
 * Insert node into the tree.
 * d2put = data to put.  
 * start = subtree where new node should be put.
 * We return new value of "start" -- which happens only when 
 * NULL is passed in.
 */
treenode_t *insert_tree(treenode_t *start, char *d2put)
{
    int res;
    if (NULL == start) {
        start = new_node(d2put);
        return start;
    }
    res = strcmp(d2put, start->data);
    if (0 == res) {
        return start;                   /* it's a duplicate */
    }
    if (res < 0) {                      /* new one should go to the left */
        if (NULL == start->leftnode) {
            start->leftnode = new_node(d2put);
            return start;
        }
        start->leftnode = insert_tree(start->leftnode, d2put);
        return start;
    } else {                            /* new one should go to the right */
        if (NULL == start->rightnode) {
            start->rightnode = new_node(d2put);
            return start;
        }
        start->rightnode = insert_tree(start->rightnode, d2put);
        return start;
    }
}
/*
 * Main program.  Take each word in the input (each input arg) and
 * insert it into the tree.  After the last one, dump the tree,
 * rebalance it, and dump it again.
 */
int
main(int argc, char **argv)
{
    while (--argc) {
        ++argv;
#ifdef DEBUG
        printf("arg: %s\n", *argv);
        dump_tree(root, "");
#endif
        root = insert_tree(root, *argv);
    }
    dump_tree(root, "before: ");
    printf("calling rebalance_below()\n");
    root = rebal_below(root);
    dump_tree(root, "after: ");
    exit(0);
}