//-----------------------------------------------------------------------------
// 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.
//-----------------------------------------------------------------------------

#include "avl_lib.h"

#include <string.h>

//-----------------------------------------------------------------------------
// internal function	avl_print_str
//
// purpose	Print a string, truncated to a limited width.
//
// arguments	1 (FILE *) output file
//		2 (int) width limit to truncate to
//		3 (const char *) string to print
//
// returns	(int) width actually used
//-----------------------------------------------------------------------------
static
int
avl_print_str (
    FILE *		arg_file
    ,
    int			arg_limit
    ,
    const char *	arg_str
    )
{
    int		len		;

    if ( arg_limit <= 0 ) return 0;

    len = 0;
    while ( arg_limit && * arg_str ) {
	putc( * arg_str, arg_file );
	++ arg_str;
	++ len;
	-- arg_limit;
    }
    return len;
}

//-----------------------------------------------------------------------------
// internal function	avl_print_int
//
// purpose	Print an integer in decimal, truncated to a limited width.
//
// arguments	1 (FILE *) output file
//		2 (int) width limit to truncate to
//		3 (int) field width to format in
//		4 (long) the integer to print
//
// returns	(int) width actually used
//-----------------------------------------------------------------------------
static
int
avl_print_int (
    FILE *		arg_file
    ,
    int			arg_limit
    ,
    int			arg_size
    ,
    long		arg_int
    )
{
    char *	tmp_str		;
    int		len		;

    if ( arg_limit <= 0 ) return 0;

    if ( ! ( tmp_str = malloc( ( (size_t) arg_size ) + 1 ) ) ) return 0;
    sprintf( tmp_str, "%*ld", arg_size, arg_int );
    len = avl_print_str( arg_file, arg_limit, tmp_str );
    free( tmp_str );
    return len;
}

//-----------------------------------------------------------------------------
// internal function	avl_print_ptr
//
// purpose	Print a pointer, with substitution for NULL, truncated to a
//		limited width.
//
// arguments	1 (FILE *) output file
//		2 (int) width limit to truncate to
//		3 (void *) pointer to be printed
//
// returns	(int) width actually used
//-----------------------------------------------------------------------------
static
int
avl_print_ptr (
    FILE *		arg_file
    ,
    int			arg_limit
    ,
    void *		arg_ptr
    )
{
    char		symbols	[16]	= {
	'0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f'
    };

    int			bits		;
    int			len		;

    if ( arg_limit <= 0 ) return 0;

    bits = CHAR_BIT * sizeof (void *);
    len = 0;

    while ( arg_limit && bits ) {
	-- arg_limit;
	bits -= 4;
	fputc( arg_ptr ? symbols[(((unsigned long)arg_ptr)>>bits)&0xf] : '-',
	       arg_file
	);
	++ len;
    }

    return len;
}

__PROTO_BEGIN__
//-----------------------------------------------------------------------------
// function	avl_print_link
//
// purpose	Print a binary tree node link.
//
// arguments	1 (FILE *) output file
//		2 (int) width limit to truncate to
//		3 (avl_link *) link to print
//
// returns	(int) width actually used
//-----------------------------------------------------------------------------
int
avl_print_link (
    FILE *		arg_file
    ,
    int			arg_limit
    ,
    avl_link *		arg_link
    )
__PROTO_END__
{
    int		len	;

    if ( arg_limit <= 0 ) return 0;

    len = arg_limit;
    len -= avl_print_ptr( arg_file, len, arg_link );
    if ( arg_link ) {
	len -= avl_print_str( arg_file, len, " [" );
	len -= avl_print_ptr( arg_file, len, arg_link->pa );
	len -= avl_print_str( arg_file, len, "/" );
	len -= avl_print_ptr( arg_file, len, arg_link->lo );
	len -= avl_print_str( arg_file, len, "/" );
	len -= avl_print_ptr( arg_file, len, arg_link->hi );
	len -= avl_print_str( arg_file, len, "/" );
	len -= avl_print_int( arg_file, len, 2, arg_link->depth );
	len -= avl_print_str( arg_file, len, "]" );
    }
    return arg_limit - len;
}

__PROTO_BEGIN__
//-----------------------------------------------------------------------------
// function	avl_print_tree
//
// purpose	Print all the links in a branch of a binary tree.
//		Call self for sub-branches.
//
// arguments	1 (FILE *) file to print to
//		2 (AVL *) pointer to binary tree
//		3 (void *) pointer to node at apex of branch to print
//		4 (const char *) prefix to print in front of each node
//		5 (int) option to print link pointers
//		6 (const char * (*fun)(void *)) function to get suffix to print
//		7 (int) maximum width to truncate line
//		8 (const char *) string to append after line truncation
//		9 (int) maximum rows to truncate screen
//
// returns	(int) number of rows printed
//
// note		Recursion is used here so that this function is more robust
//		with corrupt trees, making it more useful for debugging.
//-----------------------------------------------------------------------------
int
avl_print_tree (
    FILE *		arg_file
    ,
    AVL *		arg_tree
    ,
    void *		arg_node
    ,
    const char *	arg_prefix
    ,
    int			arg_ptrs
    ,
    const char *	(*arg_fun)(void *)
    ,
    int			arg_width
    ,
    const char *	arg_append
    ,
    int			arg_rows
    )
__PROTO_END__
{
    avl_link *		link_p		;

    char *		prefix_ptr	;
    size_t		prefix_len	;

    int			len		;
    int			count		;


    //-- Initialize to count all rows.
    count = 0;

    //-- Setup to append to prefix.
    if ( ! arg_prefix ) arg_prefix = "";
    prefix_len = strlen( arg_prefix );
    prefix_ptr = malloc( prefix_len + 6 + 1 );
    if ( ! prefix_ptr ) return 0;
    memcpy( prefix_ptr, arg_prefix, prefix_len );
    prefix_ptr[ prefix_len + 1 ] = ' ';
    prefix_ptr[ prefix_len + 2 ] = ' ';
    prefix_ptr[ prefix_len + 3 ] = 0;

    //----------------------------------------
    // If a nil branch, then print whole tree.
    //----------------------------------------
    if ( ! arg_node ) {

	//-- Print root pseudo-node.
	len = arg_width;
	len -= avl_print_str( arg_file, len, arg_prefix );
	len -= avl_print_link( arg_file, len, & ( arg_tree->link ) );
	len -= avl_print_str( arg_file, len, " (root)" );
	fputs( arg_append, arg_file );
	fputc( '\n', arg_file );
	fflush( arg_file );
	count = 1;

	//-- Print the rest of the tree.
	prefix_ptr[ prefix_len ] = ' ';
	if ( arg_tree->link.hi ) {
	    count += avl_print_tree( arg_file,
				     arg_tree,
				     avl_link_to_node(arg_tree,arg_tree->link.hi),
				     prefix_ptr,
				     arg_ptrs,
				     arg_fun,
				     arg_width,
				     arg_append,
				     arg_rows - count
	    );
	}

	//-- Return now with count.
	free( prefix_ptr );
	return count;
    }

    //-- Get link pointer of specified node.
    link_p = avl_node_to_link( arg_tree, arg_node );

    //-----------------------
    // Print lo branch first.
    //-----------------------
    if ( link_p->lo ) {

	//-- Select the prefix for the lo branch.
	if ( link_p->pa->lo == link_p )	prefix_ptr[ prefix_len ] = ' ';
	else				prefix_ptr[ prefix_len ] = '|';

	//-- Print the lo branch.
	count += avl_print_tree( arg_file,
				 arg_tree,
				 avl_link_to_node(arg_tree,link_p->lo),
				 prefix_ptr,
				 arg_ptrs,
				 arg_fun,
				 arg_width,
				 arg_append,
				 arg_rows - count
	);

	//-- If rows exhausted, return now with count.
	if ( count >= arg_rows ) {
	    free( prefix_ptr );
	    return count;
	}
    }

    //---------------------
    // Print this node now.
    //---------------------
    prefix_ptr[ prefix_len ] = 0;
    len = arg_width;
    len -= avl_print_str( arg_file, len, prefix_ptr );
    len -= avl_print_link( arg_file, len, link_p );
    if ( arg_fun ) {
	len -= avl_print_str( arg_file, len, " " );
	len -= avl_print_str( arg_file, len, ( * arg_fun )( avl_link_to_node( arg_tree, link_p ) ) );
    }
    fputs( arg_append, arg_file );
    fputc( '\n', arg_file );
    fflush( arg_file );
    ++ count;

    //-- If rows exhausted, return now with count.
    if ( count >= arg_rows ) {
	free( prefix_ptr );
	return count;
    }

    //----------------------
    // Print hi branch last.
    //----------------------
    if ( link_p->hi ) {

	//-- Select the prefix for the hi branch.
	if ( link_p->pa->hi == link_p )	prefix_ptr[ prefix_len ] = ' ';
	else				prefix_ptr[ prefix_len ] = '|';

	//-- Print the hi branch.
	count += avl_print_tree( arg_file,
				 arg_tree,
				 avl_link_to_node(arg_tree,link_p->hi),
				 prefix_ptr,
				 arg_ptrs,
				 arg_fun,
				 arg_width,
				 arg_append,
				 arg_rows - count
	);
    }

    //-- Return now with count.
    free( prefix_ptr );
    return count;
}

__PROTO_BEGIN__
//-----------------------------------------------------------------------------
// function	avl_print_link_detail
//
// purpose	Print information about a node in detail, including nodes
//		it points to.
//
// arguments	1 (FILE *) open file to print to
//		2 (AVL *) tree pointer for reference
//		3 (avl_link *) pointer to link to print
//
// returns	(int) 0
//-----------------------------------------------------------------------------
int
avl_print_link_detail(
    FILE *		arg_file
    ,
    AVL *		arg_tree
    ,
    avl_link *		arg_link
    )
__PROTO_END__
{
    if ( ! arg_file ) arg_file = stderr;

    if ( ! arg_tree ) {
	fputs( "tree is NULL\n", arg_file );
	fflush( arg_file );
	return 0;
    }

    //------------------------------------------------------------
    // Print the first line with the address of the link and node.
    //------------------------------------------------------------
    fputs( "tree @ ", arg_file );
    avl_print_ptr( arg_file, 255, arg_tree );
    if ( (void *) arg_link == (void *) arg_tree ) {
	fputs( ", link == root", arg_file );
    } else {
	fputs( ", node/link @ ", arg_file );
	avl_print_ptr( arg_file, 255, avl_link_to_node( arg_tree, arg_link ) );
	fputc( '/', arg_file );
	avl_print_ptr( arg_file, 255, arg_link );
    }
    fputc( '\n', arg_file );

    if ( arg_link ) {

	//------------------------------
	// Print the parent link detail.
	//------------------------------
	fputs( "  parent is ", arg_file );
	avl_print_link( arg_file, 255, arg_link->pa );
	fputc( '\n', arg_file );

	//--------------------------
	// Print the lo link detail.
	//--------------------------
	fputs( "      lo is ", arg_file );
	avl_print_link( arg_file, 255, arg_link->lo );
	fputc( '\n', arg_file );

	//--------------------------
	// Print the hi link detail.
	//--------------------------
	fputs( "      hi is ", arg_file );
	avl_print_link( arg_file, 255, arg_link->hi );
	fputc( '\n', arg_file );

	//------------------------------
	// Print the depth of this node.
	//------------------------------
	fprintf( arg_file, "   depth is %d\n", arg_link->depth );
    }

    fflush( arg_file );
    return 0;
}