/*
 * CIS 610, Assignment 3
 * Author: Dmitri Tikhonov
 * Date: March 4, 2006
 *
 * Simple BST implementation.
 */

#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>


#define LINESIZE 128

struct node {
    int value;
    struct node *parent;
    struct node *left;
    struct node *right;
};

typedef struct node node_t;


node_t *
new_node (int value)
{
    node_t *node = malloc(sizeof(node_t));
    node->parent = node->left = node->right = NULL;
    node->value = value;
    return node;
}


#define destroy_node(x) free(x)


node_t *
insert_node (node_t *root, node_t *node)
{
    if (node->value > root->value) {
        if (root->right) {
            return insert_node(root->right, node);
        } else {
            node->parent = root;
            return root->right = node;
        }
    } else if (node->value < root->value) {
        if (root->left) {
            return insert_node(root->left, node);
        } else {
            node->parent = root;
            return root->left = node;
        }
    } else {
        return NULL;        /* Already exists */
    }
}


node_t *
search_node (node_t *root, int value)
{
    if (!root)
        return NULL;

    if (value > root->value)
        return search_node(root->right, value);
    else if (value < root->value)
        return search_node(root->left, value);
    else
        return root;
}


void
print_nodes (node_t *root)
{
    if (!root)
        return;

    printf("(");
    print_nodes(root->left);
    printf(" %d ", root->value);
    print_nodes(root->right);
    printf(")");

    return;
}


node_t *
delete_node (node_t **root, int value)
{
    node_t *target;

    target = search_node(*root, value);
    if (!target)
        return NULL;

    if (target->left && target->right) {
        /* Possible improvement: randomly pick left or right */

        node_t *node;
        int value = target->value;

        for (node = target->left; node->right; node = node->right)
            ;

        target->value = node->value;

        if (node == target->left)
            target->left = node->left;
        else
            node->parent->right = node->left;

        if (node->left)
            node->left->parent = node->parent;

        node->value = value;
        return node;
    } else if (target->left) {
        if (target->parent) {
            if (target->parent->left == target) {
                target->parent->left = target->left;
                target->left->parent = target->parent;
                return target;
            } else {
                target->parent->right = target->left;
                target->left->parent = target->parent;
                return target;
            }
        } else {
            *root = target->left;
            target->left->parent = NULL;
            return target;
        }
    } else if (target->right) {
        if (target->parent) {
            if (target->parent->left == target) {
                target->parent->left = target->right;
                target->right->parent = target->parent;
                return target;
            } else {
                target->parent->right = target->right;
                target->right->parent = target->parent;
                return target;
            }
        } else {
            *root = target->right;
            target->right->parent = NULL;
            return target;
        }
    } else {
        if (target->parent) {
            if (target->parent->left == target)
                target->parent->left = NULL;
            else
                target->parent->right = NULL;
            return target;
        } else {
            *root = NULL;
            return target;
        }
    }

    return target;
}


int
process_commands (node_t **root, FILE *stream)
{
#define WS " \t\n"
    int retval = 0;
    char line[LINESIZE];

    while (fgets(line, sizeof(line), stream)) {
        char *aux;

        printf(line);

        aux = strtok(line, WS);
        if (!aux)       /* Empty line */
            continue;

        switch (*aux) {
            case 'i':
            case 'I':
                while (NULL != (aux = strtok(NULL, WS))) {
                    int value = atoi(aux);
                    node_t *node = new_node(value);

                    if (NULL == *root) {
                        *root = node;
                        printf("- Inserted %d\n", value);
                    } else {
                        if (insert_node(*root, node)) {
                            printf("- Inserted %d\n", value);
                        } else {
                            destroy_node(node);
                            printf("- Could not insert %d: already exists\n",
                                value);
                        }
                    }
                }
                break;
            case 'p':
            case 'P':
                printf("-");
                print_nodes(*root);
                printf("\n");
                break;
            case 'd':
            case 'D':
                while (NULL != (aux = strtok(NULL, WS))) {
                    int value = atoi(aux);
                    node_t *node;
                    if (NULL != (node = delete_node(root, value))) {
                        printf("- Deleted node %d\n", value);
                        destroy_node(node);
                    } else {
                        printf("- Could not delete %d: not found\n", value);
                    }
                }
                break;
            case 's':
            case 'S':
                while (NULL != (aux = strtok(NULL, WS))) {
                    int value = atoi(aux);
                    if (search_node(*root, value))
                        printf("- Found node %d\n", value);
                    else
                        printf("- Node %d not found\n", value);
                }
                break;
            default:
                printf("- Unknown command: %s\n", aux);
                break;
        }

    }

    if (!feof(stream)) {
        fprintf(stderr, "Input line is too long.  Aborting.\n");
        return -1;
    }

    return retval;
}


void
_usage (const char *prog)
{
    fprintf(stderr, "Usage: %s [-f file] [-h]\n", prog);
    return;
}


int
main (int argc, char **argv)
{
    int opt;
    node_t *tree = NULL;
    FILE *stream = stdin;

    while (-1 != (opt = getopt(argc, argv, "hf:"))) {
        switch (opt) {
            case 'h':
                _usage(*argv);
                exit(0);
                break;
            case 'f':
                if (strcmp(optarg, "-")) {
                    stream = fopen(optarg, "r");
                    if (!stream) {
                        perror("Coould not open file for reading");
                        exit(1);
                    }
                }
                break;
            case '?':
                _usage(*argv);
                exit(2);
        }
    }

    process_commands(&tree, stream);

    exit(0);
}