/*
 * Faculty of Applied Science and Engineering, University of Toronto
 * CSC181: Introduction to Computer Programming, Fall 2000
 *
 * Assignment: 3
 * File: bst.c
 * Author: Ray Ortigas (rayo@dgp.toronto.edu)
 * Contains: Function definitions for BST module.
 */

#include <assert.h>
#include <stdlib.h>
#include "bst.h"

/* Returns a binary search tree which uses compareKeys (a pointer to
   function taking two void* arguments) to carry out comparisons
   between two keys. */
BSTPtr bstInit(int (*compareKeys)(void*, void*)) {
	BSTPtr result = malloc(sizeof(BST));
	assert(result != NULL);

	result->root = NULL;
	result->compareKeys = compareKeys;

	return result;
}

/* Inserts key k and associated value v into tree t. */
void bstInsert(BSTPtr t, void* k, void* v) {
	BSTNode* newNode;
	BSTNode* parent;
	BSTNode* current;
	int cmp;

	assert(t != NULL && k != NULL && v != NULL);

	if (bstRetrieve(t, k) != NULL)
		return;

	newNode = malloc(sizeof(BSTNode));
	assert(newNode != NULL);
	
	newNode->key = k;
	newNode->value = v;
	newNode->left = NULL;
	newNode->right = NULL;

	parent = NULL;
	current = t->root;
	while (current != NULL) {
		parent = current;
		cmp = (*(t->compareKeys))(k, current->key);
		current = (cmp < 0) ? current->left : current->right;
	}

	if (parent == NULL) {
		t->root = newNode;
	}
	else {
		cmp = (*(t->compareKeys))(k, parent->key);
		if (cmp < 0) {
			parent->left = newNode;
		}
		else {
			parent->right = newNode;
		}
	}
	newNode->parent = parent;
}

/* Retrieves the value associated with key k inside tree t, NULL if no
   such value exists. */
void* bstRetrieve(const BSTPtr t, void* k) {
	void* result;
	BSTNodePtr current;
	assert(t != NULL && k != NULL);

	result = NULL;
	current = t->root;
	while (current != NULL && result == NULL) {
		int cmp = (*(t->compareKeys))(k, current->key);
		if (cmp == 0)
			result = current->value;
		else if (cmp < 0)
			current = current->left;
		else
			current = current->right;
	}
	return result;
}