/*
 *   Copyright (c) International Business Machines Corp., 2001-2004
 *
 *   This program is free software;  you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation; either version 2 of the License, or
 *   (at your option) any later version.
 *
 *   This program is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY;  without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See
 *   the GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with this program;  if not, write to the Free Software
 *   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 */
#ifndef RED_BLACK_TREE_H
#define RED_BLACK_TREE_H

/*
 * ***************************************************************************
 *
 * Container class for a red-black tree ......
 *
 * A binary tree that satisfies the following properties:
 *
 * 1. Every node is either red or black
 * 2. The root node is black
 * 3. Every leaf (NIL) is black
 * 4. If a node is red, both its children are black
 * 5. For each node, all paths from the node to descendant leaf nodes
 *    contain the same number of black nodes
 *
 * Due to points 4 & 5, the depth of a red-black tree containing n nodes
 * is bounded by 2*log2(n+1) (WC).
 *
 *
 * The rb_tree template requires two additional parmeters:
 *
 * - The contained TYPE class represents the objects stored in the tree.
 *   It has to support the copy constructor and the assignment operator (opr)
 * - cmp is a functor used to define the order of objects of class TYPE:
 *   This class has to support an operator() that recieves two objects from
 *   the TYPE class and returns a negative, 0, or a positive integer,
 *   depending on the comparison result.
 *
 * Dominique Heger, S. Rao
 *
 * ***************************************************************************
 */

/* Color enumeration for nodes of red-black tree */
/* ********************************************* */

#include "filelist.h"

typedef struct ffsb_file *datatype;

#define COMP_NODES(a, b) ((a)->num - (b)->num)

typedef enum red_black_color {red, black} rb_color;

/*! Representation of a node in a red-black tree */
typedef struct red_black_node {
	datatype object;                      /* the stored object */
	rb_color color;                       /* the color of the node */
	struct red_black_node *parent;       /* points to the parent node */
	struct red_black_node *right;        /* points to the right child */
	struct red_black_node *left;         /* points to the left child */
} rb_node;

typedef int(cmp)(datatype, datatype);
typedef void(opr)(void *);
typedef void(destructor)(datatype);

/* Construct of a red-black tree node
 * - The object stored in the node
 * - The color of the node
 */

extern rb_node *rbnode_construct(datatype object, rb_color color);

/* Recursive destructor for the entire sub-tree */
/* ******************************************** */

extern void rbnode_destruct(rb_node *node, destructor d);

/* Calculate the depth of the sub-tree spanned by the given node
 * - The sub-tree root
 * - The sub-tree depth
 */

extern int rbnode_depth(rb_node *node);

/* Get the leftmost node in the sub-tree spanned by the given node
 * - The sub-tree root
 * - The sub-tree minimum
 */

extern rb_node *rbnode_minimum(rb_node *node);

/* Get the rightmost node in the sub-tree spanned by the given node
 * - The sub-tree root
 * - The sub-tree maximum
 */

extern rb_node *rbnode_maximum(rb_node *node);

/* Replace the object */
/* ****************** */

extern void rbnode_replace(rb_node *node, datatype object);

/* Get the next node in the tree (according to the tree order)
 * - The current node
 * - The successor node, or NULL if node is the tree maximum
 */

extern rb_node *rbnode_successor(rb_node *node);

/* Get the previous node in the tree (according to the tree order)
 * - The current node
 * - The predecessor node, or NULL if node is the tree minimum
 */

extern rb_node *rbnode_predecessor(rb_node *node);

/* Duplicate the entire sub-tree rooted at the given node
 * - The sub-tree root
 * - A pointer to the duplicated sub-tree root
 */

extern rb_node *rbnode_duplicate(rb_node *node);

/* Traverse a red-black sub-tree
 * - The sub-tree root
 * - The operation to perform on each object in the sub-tree
 */
extern void rbnode_traverse(rb_node *node, opr *op);

/* Representation of a red-black tree */
/* ********************************** */

typedef struct red_black_tree {
	rb_node *root;                /* pointer to the tree root */
	int isize;                     /* number of objects stored */
	/*   cmp * comp; */                   /* compare function */
} rb_tree;

/* Initialize a red-black tree with a comparision function
 * - The tree
 * - The comparision function
 */

void rbtree_init(rb_tree *tree);

/* Construct a red-black tree with a comparison object
 * - A pointer to the comparison object to be used by the tree
 * - The newly constructed  tree
 */

rb_tree *rbtree_construct(void);

/* Clean a red-black tree [takes O(n) operations]
 * - The tree
 */

extern void rbtree_clean(rb_tree *tree, destructor d);

/* Destruct a red-black tree
 * - The tree
 */

extern void rbtree_destruct(rb_tree *tree, destructor d);

/* Get the size of the tree [takes O(1) operations]
 * - The tree
 * - The number of objects stored in the tree
 */

extern int rbtree_size(rb_tree *tree);

/* Get the depth of the tree [takes O(n) operations]
 * - The tree
 * - The length of the longest path from the root to a leaf node
 */

extern int rbtree_depth(rb_tree *tree);

/* Check whether the tree contains an object [takes O(log n) operations]
 * - The tree
 * - The query object
 * - (true) if an equal object is found in the tree, otherwise (false)
 */

extern int rbtree_contains(rb_tree *tree, datatype object);

/* Insert an object to the tree [takes O(log n) operations]
 * - The tree
 * - The object to be inserted
 * - Return the inserted object node
 */

extern rb_node *rbtree_insert(rb_tree *tree, datatype object);

/* Insert a new object to the tree as the a successor of a given node
 * - The tree
 * - The new node
 */

extern rb_node *insert_successor_at(rb_tree *tree, rb_node *at_node,
				    datatype object);

/* Insert a new object to the tree as the a predecessor of a given node
 * - The tree
 * - The new node
 */

extern rb_node *insert_predecessor_at(rb_tree *tree, rb_node *at_node,
				      datatype object);

/* Remove an object from the tree [takes O(log n) operations]
 * - The tree
 * - The object to be removed
 * - The object should be contained in the tree
 */

extern void rbtree_remove(rb_tree *tree, datatype object, destructor d);

/* Get a handle to the tree minimum [takes O(log n) operations]
 * - The tree
 * - Return the minimal object in the tree, or a NULL if the tree is empty
 */

extern rb_node *rbtree_minimum(rb_tree *tree);

/* Get a handle to the tree maximum [takes O(log n) operations]
 * - The tree
 * - Return the maximal object in the tree, or a NULL if the tree is empty
 */

extern rb_node *rbtree_maximum(rb_tree *tree);

/* Get the next node in the tree (according to the tree order)
 * - [takes O(log n) operations at worst-case, but only O(1) amortized]
 * - The tree
 * - The current object
 * - The successor node, or a NULL, if we are at the tree maximum
 */
extern rb_node *rbtree_successor(rb_tree *tree, rb_node *node);

/* Get the previous node in the tree (according to the tree order)
 * - [takes O(log n) operations at worst-case, but only O(1) amortized]
 * - The tree
 * - The current object
 * - The predecessor node, or a NULL, if we are at the tree minimum
 */

extern rb_node *rbtree_predecessor(rb_tree *tree, rb_node *node);

/* Find a node that contains the given object
 * - The tree
 * - The desired object
 * - Return a node that contains the given object, or NULL if no such object
 *   is found in the tree
 */

extern rb_node *rbtree_find(rb_tree *tree, datatype object);

/* Remove the object stored in the given tree node
 * - The tree
 * - The node storing the object to be removed from the tree
 */

extern void rbtree_remove_at(rb_tree *tree, rb_node *node, destructor d);

/* Left-rotate the sub-tree spanned by the given node
 * - The tree
 * - The sub-tree root
 */

extern void rbtree_rotate_left(rb_tree *tree, rb_node *node);

/* Right-rotate the sub-tree spanned by the given node
 * - The tree
 * - The sub-tree root
 */

extern void rbtree_rotate_right(rb_tree *tree, rb_node *node);

/*
 * Fix the red-black tree properties after an insertion operation
 * - The tree
 * - The node that has just been inserted to the tree
 * - The color of node must be red
 */

extern void rbtree_insert_fixup(rb_tree *tree, rb_node *node);

/* Fix the red-black tree properties after a removal operation
 * - The tree
 * - The child of the node that has just been removed from the tree
 */

extern void rbtree_remove_fixup(rb_tree *tree, rb_node *node);

/* Traverse a red-black tree
 * - The tree
 * - The operation to perform on every object of the tree (according to
 *   the tree order)
 */

extern void rbtree_traverse(rb_tree *tree, opr *op);

#endif