/*                      R E D B L A C K . H
 * BRL-CAD
 *
 * Copyright (C) 2004-2005 United States Government as represented by
 * the U.S. Army Research Laboratory.
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public License
 * as published by the Free Software Foundation; either version 2.1 of
 * the License, or (at your option) any later version.
 *
 * This library 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
 * Library General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this file; see the file named COPYING for more
 * information.
 */
/** @file redblack.h
 *	The data structures and constants for red-black trees.
 *
 *	Many of these routines are based on the algorithms in chapter 13
 *	of T. H. Cormen, C. E. Leiserson, and R. L. Rivest,
 *	_Introduction to algorithms_, MIT Press, Cambridge, MA, 1990.
 *
 *	Author:	Paul Tanenbaum
 *
 */

#include "bu.h"
#if 0

/*
 *			    R B _ L I S T
 *
 *		    List of nodes or packages
 *
 *	LIBREDBLACK(3) uses this structure to maintain lists of
 *	all the nodes and all the packages in the tree.  Applications
 *	should not muck with these things.  They are maintained only
 *	to facilitate freeing rb_trees.
 */
struct rb_list
{
    struct bu_list	l;
    union
    {
	struct rb_node    *rbl_n;
	struct rb_package *rbl_p;
    }			rbl_u;
};
#define	rbl_magic	l.magic
#define	rbl_node	rbl_u.rbl_n
#define	rbl_package	rbl_u.rbl_p
#define	RB_LIST_NULL	((struct rb_list *) 0)


/*
 *			R B _ T R E E
 *
 *	This is the only data structure used in LIBREDBLACK
 *	to which application software need make any explicit
 *	reference.
 *
 *	The members of this structure are grouped into three
 *	classes:
 *	    Class I:	Reading is appropriate, when necessary,
 *			but applications should not modify.
 *	    Class II:	Reading and modifying are both appropriate,
 *			when necessary.
 *	    Class III:	All access should be through routines
 *			provided in LIBREDBLACK.  Touch these
 *			at your own risk!
 */
typedef struct
{
    /* CLASS I - Applications may read directly... */
    long	 	rbt_magic;	  /* Magic no. for integrity check */
    int			rbt_nm_nodes;	  /* Number of nodes */
    /* CLASS II - Applications may read/write directly... */
    void		(*rbt_print)();	  /* Data pretty-print function */
    int			rbt_debug;	  /* Debug bits */
    char		*rbt_description; /* Comment for diagnostics */
    /* CLASS III - Applications should not manipulate directly... */
    int		 	rbt_nm_orders;	  /* Number of simultaneous orders */
    int			(**rbt_order)();  /* Comparison functions */
    struct rb_node	**rbt_root;	  /* The actual trees */
    char		*rbt_unique;	  /* Uniqueness flags */
    struct rb_node	*rbt_current;	  /* Current node */
    struct rb_list	rbt_nodes;	  /* All nodes */
    struct rb_list	rbt_packages;	  /* All packages */
    struct rb_node	*rbt_empty_node;  /* Sentinel representing nil */
}	rb_tree;
#define	RB_TREE_NULL	((rb_tree *) 0)
#define	RB_TREE_MAGIC	0x72627472

/*
 *	Debug bit flags for member rbt_debug
 */
#define RB_DEBUG_INSERT	0x00000001	/* Insertion process */
#define RB_DEBUG_UNIQ	0x00000002	/* Uniqueness of inserts */
#define RB_DEBUG_ROTATE	0x00000004	/* Rotation process */
#define RB_DEBUG_OS	0x00000008	/* Order-statistic operations */
#define RB_DEBUG_DELETE	0x00000010	/* Deletion process */

/*
 *			R B _ P A C K A G E
 *
 *		    Wrapper for application data
 *
 *	This structure provides a level of indirection between
 *	the application software's data and the red-black nodes
 *	in which the data is stored.  It is necessary because of
 *	the algorithm for deletion, which generally shuffles data
 *	among nodes in the tree.  The package structure allows
 *	the application data to remember which node "contains" it
 *	for each order.
 */
struct rb_package
{
    long		rbp_magic;	/* Magic no. for integrity check */
    struct rb_node	**rbp_node;	/* Containing nodes */
    struct rb_list	*rbp_list_pos;	/* Place in the list of all pkgs. */
    void		*rbp_data;	/* Application data */
};
#define	RB_PKG_NULL	((struct rb_package *) 0)

/*
 *			    R B _ N O D E
 *
 *	For the most part, there is a one-to-one correspondence
 *	between nodes and chunks of application data.  When a
 *	node is created, all of its package pointers (one per
 *	order of the tree) point to the same chunk of data.
 *	However, subsequent deletions usually muddy this tidy
 *	state of affairs.
 */
struct rb_node
{
    long		rbn_magic;	/* Magic no. for integrity check */
    rb_tree		*rbn_tree;	/* Tree containing this node */
    struct rb_node	**rbn_parent;	/* Parents */
    struct rb_node	**rbn_left;	/* Left subtrees */
    struct rb_node	**rbn_right;	/* Right subtrees */
    char		*rbn_color;	/* Colors of this node */
    int			*rbn_size;	/* Sizes of subtrees rooted here */
    struct rb_package	**rbn_package;	/* Contents of this node */
    int			rbn_pkg_refs;	/* How many orders are being used? */
    struct rb_list	*rbn_list_pos;	/* Place in the list of all nodes */
};
#define	RB_NODE_NULL	((struct rb_node *) 0)

/*
 *	Applications interface to rb_extreme()
 */
#define	SENSE_MIN	0
#define	SENSE_MAX	1
#define	rb_min(t,o)	rb_extreme((t), (o), SENSE_MIN)
#define	rb_max(t,o)	rb_extreme((t), (o), SENSE_MAX)
#define rb_pred(t,o)	rb_neighbor((t), (o), SENSE_MIN)
#define rb_succ(t,o)	rb_neighbor((t), (o), SENSE_MAX)

/*
 *	Applications interface to rb_walk()
 */
#define	PREORDER	0
#define	INORDER		1
#define	POSTORDER	2

/*
 *	Applications interface to LIBREDBLACK
 */
BU_EXTERN(rb_tree *rb_create,	(char		*description,
				 int 		nm_orders,
				 int		(**order_funcs)()
				));
BU_EXTERN(rb_tree *rb_create1,	(char		*description,
				 int		(*order_func)()
				));
BU_EXTERN(void *rb_curr,	(rb_tree	*tree,
				 int		order
				));
#define		rb_curr1(t)	rb_curr((t), 0)
BU_EXTERN(void rb_delete,	(rb_tree	*tree,
				 int		order
				));
#define		rb_delete1(t)	rb_delete((t), 0)
BU_EXTERN(void rb_diagnose_tree,(rb_tree	*tree,
				 int		order,
				 int		trav_type
				));
BU_EXTERN(void *rb_extreme,	(rb_tree	*tree,
				 int		order,
				 int		sense
				));
BU_EXTERN(void rb_free,		(rb_tree	*tree,
				 void		(*free_data)()
				));
#define	RB_RETAIN_DATA	((void (*)()) 0)
#define		rb_free1(t,f)						\
		{							\
		    RB_CKMAG((t), RB_TREE_MAGIC, "red-black tree");	\
		    bu_free((char *) ((t) -> rbt_order),		\
				"red-black order function");		\
		    rb_free(t,f);					\
		}
BU_EXTERN(void *rb_select,	(rb_tree	*tree,
				 int		order,
				 int		k
				));
#define		rb_select1(t,k)	rb_select((t), 0, (k))
BU_EXTERN(int rb_insert,	(rb_tree	*tree,
				 void		*data
				));
BU_EXTERN(int rb_is_uniq,	(rb_tree	*tree,
				 int		order
				));
#define		rb_is_uniq1(t)	rb_is_uniq((t), 0)
BU_EXTERN(void *rb_neighbor,	(rb_tree	*tree,
				 int		order,
				 int		sense
				));
BU_EXTERN(int rb_rank,		(rb_tree	*tree,
				 int		order
				));
#define		rb_rank1(t)	rb_rank1((t), 0)
BU_EXTERN(void *rb_search,	(rb_tree	*tree,
				 int		order,
				 void		*data
				));
#define		rb_search1(t,d)	rb_search((t), 0, (d))
BU_EXTERN(void rb_set_uniqv,	(rb_tree	*tree,
				 bitv_t		vec
				));
BU_EXTERN(void rb_summarize_tree,(rb_tree	*tree
				 ));
BU_EXTERN(void rb_uniq_all_off,	(rb_tree	*tree
				));
BU_EXTERN(void rb_uniq_all_on,	(rb_tree	*tree
				));
BU_EXTERN(int rb_uniq_off,	(rb_tree	*tree,
				 int		order
				));
#define		rb_uniq_off1(t)	rb_uniq_off((t), 0)
BU_EXTERN(int rb_uniq_on,	(rb_tree	*tree,
				 int		order
				));
#define		rb_uniq_on1(t)	rb_uniq_on((t), 0)
BU_EXTERN(void rb_walk,		(rb_tree	*tree,
				 int		order,
				 void		(*visit)(),
				 int		trav_type
				));
#define		rb_walk1(t,v,d)	rb_walk((t), 0, (v), (d))

#endif

/*
 * Local Variables:
 * mode: C
 * tab-width: 8
 * c-basic-offset: 4
 * indent-tabs-mode: t
 * End:
 * ex: shiftwidth=4 tabstop=8
 */
