__PREFIX_BEGIN__
//-----------------------------------------------------------------------------
// Copyright © 2003 - Philip Howard - All rights reserved
//
// 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., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
//-----------------------------------------------------------------------------
// package	libh/avl
// homepage	http://libh.slashusr.org/
//-----------------------------------------------------------------------------
// author	Philip Howard
// email	libh at ipal dot org
// homepage	http://phil.ipal.org/
//-----------------------------------------------------------------------------
// This file is best viewed using a fixed spaced font such as Courier
// and in a display at least 120 columns wide.
//-----------------------------------------------------------------------------

//-----------------------------------------------------------------------------
// G. M. Adelson-Velskii and E. M. Landis are the inventors of the algorithm
// bearing their initials, AVL.  Their algorithm for height-balanced binary
// search trees is the basis of the code in this package.  Some modification
// is made to the balancing operations, and features are added for practical
// purposes.
//-----------------------------------------------------------------------------

//-----------------------------------------------------------------------------
// file		avl.h
//
// purpose	Define resources for the AVL binary tree package
//-----------------------------------------------------------------------------
#ifndef __AVL_H__
#define __AVL_H__

__PREFIX_END__

__INCLUDE_BEGIN__
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>

__INCLUDE_END__

__DEFINE_BEGIN__
//-----------------------------------------------------------------------------
// struct	avl_link
//
// purpose	Contain the links and other information that implements one
//		binary tree structuring instance for a node structure that
//		can be defined by the calling program.
//-----------------------------------------------------------------------------
struct avl_link {
    struct avl_link *		lo		;	// link to lower key
    struct avl_link *		hi		;	// link to higher key
    struct avl_link *		pa		;	// link to parent
    int				depth		;	// this depth
};
typedef struct avl_link		avl_link	;

//-----------------------------------------------------------------------------
// struct	avl_root
//
// purpose	This struct is the root node for a balanced binary tree.
//		The root node does not have a key.  It is parented from the
//		middle node located at the apex of the tree (which would be
//		the root, otherwise) and is effectively positioned as if it
//		was keyed lower in value than the lowest possible member of
//		the tree.
//
//		A reference to a binary tree is a pointer to this struct.
//-----------------------------------------------------------------------------
struct avl_root {

//-----------------------------------------------------------------------------
// field	link
//
// The control struct for the binary tree is also the root node of the tree
// structure.  This field contains the links necessary to allow this.  The
// root node is always positioned as the parent of the apex of the regular
// nodes, and the apex is linked via the hi pointer of the root.  This makes
// the root positioned as always lower in key value than the lowest possible
// value a key could really have.
//-----------------------------------------------------------------------------
    avl_link		link		;// link member for this pseudo-node

//-----------------------------------------------------------------------------
// field	select
//
// Whenever a node is found or inserted in the binary tree, it becomes the
// currently selected node.  This field points to the links for the currently
// selected node.  Certain operations can refer to the currently selected
// node when no node is explicitly provided.
//-----------------------------------------------------------------------------
    avl_link *		select		;// currently selected node

//-----------------------------------------------------------------------------
// field	offset
//
// The calling program can work with node structs in which the links are not
// actually located at the beginning of the struct.  Internally, AVL always
// works with pointers that point exactly to the links sub-struct.  The offset
// translates caller node pointers to internal link pointers by addition, and
// translates internal link pointers to caller node pointers by subtraction.
//-----------------------------------------------------------------------------
    size_t		offset		;// offset for caller pointers

//-----------------------------------------------------------------------------
// field	compare_f
//
// The calling program provides a function which compares the keys in two
// key link structures as defined by the calling program.  This field keeps
// the pointer to that function.
//-----------------------------------------------------------------------------
    int			( * compare_f )( avl_link *, avl_link *, struct avl_root * );

//-----------------------------------------------------------------------------
// field	count_nodes
//
// Keep a count of the number of nodes in a tree, for consistency check.
//-----------------------------------------------------------------------------
    unsigned long	count_nodes	;// count of nodes in tree

//-----------------------------------------------------------------------------
// field	err_num
//
// This field records an error code identifying the last error to occur with
// this binary tree.
//-----------------------------------------------------------------------------
    int			err_num		;// last error in this tree
};
typedef struct avl_root		avl_root		;

//-----------------------------------------------------------------------------
// Define the official types that calling programs should use to reference
// a binary tree, or create an instance of a binary tree root node.
//-----------------------------------------------------------------------------
typedef struct avl_root		AVL		;
typedef struct avl_root *	AVLP		;
typedef struct avl_root *	AVL_P		;

//-----------------------------------------------------------------------------
// error symbols
//-----------------------------------------------------------------------------
#define AVL_OK				0

#define AVL_ERR_OTHER			-1
#define AVL_ERR_BAD_ROOT		-2
#define AVL_ERR_BAD_NODE		-3
#define AVL_ERR_ROOT_NULL		-4
#define AVL_ERR_NODE_NULL		-5
#define AVL_ERR_NO_PARENT		-6
#define AVL_ERR_NO_COMPARE		-7

#define AVL_ERR_CORRUPT_PA_NOBACK	0x0001
#define AVL_ERR_CORRUPT_PA_NULL		0x0002
#define AVL_ERR_CORRUPT_LOHI_CROSSED	0x0004
#define AVL_ERR_CORRUPT_LO_NOBACK	0x0010
#define AVL_ERR_CORRUPT_HI_NOBACK	0x0040
#define AVL_ERR_CORRUPT_DEPTH		0x0100

__DEFINE_END__

__ALIAS_BEGIN__
//-----------------------------------------------------------------------------
// alias	avl_find_exact
//
// purpose	Find the first exact link in a binary tree without any
//		influence toward lower or higher positions in multiple
//		instances of the same key.
//
// arguments	1 (AVL *) pointer to binary tree
//		2 (void *) pointer to argument key link
//
// returns	(void *) pointer to node with any exact matching key.
//		(void *) NULL if node not found
//-----------------------------------------------------------------------------
// alias	avl_find_exact_lo
//
// purpose	Find the exact link in a binary tree that is in the lowest
//		position among multiple instances of the same key.
//
// arguments	1 (AVL *) pointer to binary tree
//		2 (void *) pointer to argument key link
//
// returns	(void *) pointer to node with the lowest exact matching key.
//		(void *) NULL if node not found
//-----------------------------------------------------------------------------
// alias	avl_find_exact_hi
//
// purpose	Find the exact link in a binary tree that is in the highest
//		position among multiple instances of the same key.
//
// arguments	1 (AVL *) pointer to binary tree
//		2 (void *) pointer to argument key link
//
// returns	(void *) pointer to node with the highest exact matching key.
//		(void *) NULL if node not found
//-----------------------------------------------------------------------------
// alias	avl_find_lo_or_near
//
// purpose	Find the exact link in a binary tree that is in the lowest
//		position among multiple instances of the same key, or if no
//		exact key can be found, the nearest key lower than given.
//
// arguments	1 (AVL *) pointer to binary tree
//		2 (void *) pointer to argument key link
//
// returns	(void *) pointer to node with the lowest exact matching key.
//		(void *) pointer to node with nearest lower key if no exact.
//		(void *) NULL if node not found
//-----------------------------------------------------------------------------
// alias	avl_find_hi_or_near
//
// purpose	Find the exact link in a binary tree that is in the highest
//		position among multiple instances of the same key, or if no
//		exact key can be found, the nearest key higher than given.
//
// arguments	1 (AVL *) pointer to binary tree
//		2 (void *) pointer to argument key link
//
// returns	(void *) pointer to node with the highest exact matching key.
//		(void *) pointer to node with nearest higher key if no exact.
//		(void *) NULL if node not found
//-----------------------------------------------------------------------------
#define avl_find_lo_or_near(t,k)	avl_find((t),(k),-2)
#define avl_find_exact_lo(t,k)		avl_find((t),(k),-1)
#define avl_find_exact(t,k)		avl_find((t),(k),0)
#define avl_find_exact_hi(t,k)		avl_find((t),(k),1)
#define avl_find_hi_or_near(t,k)	avl_find((t),(k),2)

//-----------------------------------------------------------------------------
// alias	avl_loop_forward
//
// purpose	Code a loop that steps through the nodes of a binary tree in
//		in the forward direction from first to last.
//
// arguments	1 (AVL *) pointer to the binary tree (root node)
//		2 (node *) name of variable to have the node pointer in the loop
//-----------------------------------------------------------------------------
#define avl_loop_forward(t,p) for(avl_unselect((t)),(p)=(void *)(NULL);((p)=(void *)avl_forward((t),(void *)(p)));)

//-----------------------------------------------------------------------------
// alias	avl_loop_reverse
//
// purpose	Code a loop that steps through the nodes of a binary tree in
//		in the reverse direction from last to first.
//
// arguments	1 (AVL *) pointer to the binary tree (root node)
//		2 (node *) name of variable to have the node pointer in the loop
//-----------------------------------------------------------------------------
#define avl_loop_reverse(t,p) for(avl_unselect((t)),(p)=(void *)(NULL);((p)=(void *)avl_reverse((t),(void *)(p)));)

//-----------------------------------------------------------------------------
// alias	avl_init
//
// purpose	Initialize a binary tree for use with a specific node type
//		and a specific field for the tree links.
//
// arguments	1 (AVL *) pointer to the binary tree
//		2 ... struct type caller will use as a node for this tree
//		3 ... links field of node struct this tree will index with
//		4 (int (* fun)(void *,void *)) function to do key compares
//
// returns	(AVL *) pointer to same root struct now initialized
//		(AVL *) NULL if there is an error
//-----------------------------------------------------------------------------
#define avl_init(b,t,f,c) avl_initialize((b),((size_t)(&(((t*)0)->f))),(c))

//-----------------------------------------------------------------------------
// alias	avl_is_empty
//
// purpose	Yield true if the tree is empty, or false if it is not empty.
//
// arguments	1 (AVL *) pointer to binary tree
//
// returns	(int) true if tree is empty
//		(int) false if tree is not empty
//-----------------------------------------------------------------------------
#define avl_is_empty(t) (!((t)->link.hi))

//-----------------------------------------------------------------------------
// alias	avl_is_not_empty
//
// purpose	Yield true if the tree is not empty, or false if it is empty.
//
// arguments	1 (AVL *) pointer to binary tree
//
// returns	(int) true if tree is empty
//		(int) false if tree is not empty
//-----------------------------------------------------------------------------
#define avl_is_not_empty(t) (!(!((t)->link.hi)))

//-----------------------------------------------------------------------------
// alias	avl_insert
//
// purpose	Call avl_put to do an insert only, without duplicate.
//-----------------------------------------------------------------------------
// alias	avl_insert_dup
//
// purpose	Call avl_put to do an insert with duplication allowed.
//-----------------------------------------------------------------------------
// alias	avl_replace
//
// purpose	Call avl_put to do an insert or replacement.
//-----------------------------------------------------------------------------
#define avl_insert(t,n)		avl_put((t),(n),NULL,0)
#define avl_insert_dup(t,n)	avl_put((t),(n),NULL,1)
#define avl_replace(t,n,s)	avl_put((t),(n),(s),0)

__ALIAS_END__

__SUFFIX_BEGIN__
#endif /* __AVL_H__ */
__SUFFIX_END__