/*
 * CS5600 University of Utah
 * Charles McGarvey
 * mcgarvey@eng.utah.edu
 */

#ifndef _RBTREE_H_
#define _RBTREE_H_

#include "common.h"


#define RBTREE_BLACK (0)
#define RBTREE_RED   (1)


/*
 * A single node of the red-black tree.
 */
struct rbtree_node
{
    struct rbtree_node* parent;
    struct rbtree_node* left;
    struct rbtree_node* right;
    char                color;          
};
typedef struct rbtree_node rbtree_node_t;

/*
 * Get a pointer to the data stored in a node.
 */
#define RBTREE_NODE_DATA(N) ((void*)((char*)N + sizeof(rbtree_node_t)))

/*
 * A pointer to the global sentinel node.
 */
extern rbtree_node_t* rbtree_sentinel;


/*
 * In order to search the tree, you need a function matching this protocol.
 */
typedef int (*rbtree_search_fn_t)(rbtree_node_t** np, void* data);


/*
 * The famous and well-loved red and black tree structure.
 */
struct rbtree
{
    rbtree_node_t*      root;
    size_t              size;
    rbtree_search_fn_t  search;
};
typedef struct rbtree rbtree_t;

/*
 * Allocate a new red-black tree.  It takes the size of the data to be stored
 * in each node and a search function.
 */
rbtree_t* rbtree_alloc(size_t size, rbtree_search_fn_t search);

/*
 * Destroy a red-black tree, returning its memory to the allocator.
 */
void rbtree_destroy(rbtree_t* t);


/*
 * The common actions which can be invoked on a tree.
 * These are O(logn) operations.
 */
rbtree_node_t* rbtree_delete(rbtree_t* t, void* data);
rbtree_node_t* rbtree_insert(rbtree_t* t, void* data);
rbtree_node_t* rbtree_search(rbtree_t* t, void* data);

/*
 * If you already have a pointer to a node, you can delete it directly.
 * This is a O(1) operation.
 */
rbtree_node_t* rbtree_delete_node(rbtree_t* t, rbtree_node_t* n);


/*
 * Determine whether or not the tree is empty.
 */
INLINE_MAYBE
bool rbtree_empty(rbtree_t* t)
{
    return (t->root == rbtree_sentinel);
}

/*
 * Clear the tree of all of its nodes.
 */
void rbtree_clear(rbtree_t* t);


/*
 * Get the node with the minimum data in the tree.
 * This is a O(logn) operation.
 */
INLINE_MAYBE
rbtree_node_t* rbtree_node_min(rbtree_node_t* n)
{
    while (n->left != rbtree_sentinel) {
        n = n->left;
    }
    return n;
}

/*
 * Get the node with the maximum data in the tree.
 * This is a O(logn) operation.
 */
INLINE_MAYBE
rbtree_node_t* rbtree_node_max(rbtree_node_t* n)
{
    while (n->right != rbtree_sentinel) {
        n = n->right;
    }
    return n;
}


/*
 * A function that can be used as a callback for handling tree data.
 */
typedef void (*rbtree_call_fn_t)(void* e);

/*
 * Call a function for each node in the tree, from smallest to greatest.
 */
void rbtree_call(const rbtree_t* t, rbtree_call_fn_t fn);


#endif // _RBTREE_H_