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

/*
 * Represents a BST node.
 */
struct bstnode {

	/* The key for this node (used to determine its place in 
	   the tree. */
	void* key;

	/* The value for this node. */
	void* value;

	/* The parent of this node. */
	struct bstnode* parent;

	/* The left child of this node. */
	struct bstnode* left;

	/* The right child of this node. */
	struct bstnode* right;
};
typedef struct bstnode BSTNode;
typedef BSTNode* BSTNodePtr;

/*
 * Represents a BST. Implemented using a linked structure of BSTNodes.
 */
struct bst {

	/* The root node of this tree. If it is NULL, then the tree is
	   empty. */
	BSTNode* root;

	/* The key comparison function for this tree (used for operations
	   like insertion and retrieval). */
	int (*compareKeys)(void*, void*);
};
typedef struct bst BST;
typedef BST* BSTPtr;

/* 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*));

/* Inserts key k and associated value v into tree t. */
void bstInsert(BSTPtr t, void* k, void* v);

/* Retrieves the value associated with key k inside tree t, NULL if no
   such value exists. */
void* bstRetrieve(const BSTPtr t, void* k);