#include <stdio.h>
#include "avl.h"

/* -------------------------------------------------------------------
 * These IBM graphics (box drawing) characters are used only if the 
 * output stream is stdout and isatty() is true (it will be false if
 * stdout is redirected.
 *								|
 * GAMMA:	+---		ELL:	|		T_RIGHT	+----
 * \332		|		\300	+----		\303	|
 *
 *		    |			    |
 * T_LEFT	----+		T_UP:	----+		T_DOWN	---+
 * \264		    |		\331			\277	   |
 *
 * VERT		|		(dash)
 * \263		|		\304	-----
 *		|
 */

#define	VERT	Cset[0]
#define	GAMMA	Cset[1]
#define	ELL	Cset[2]
#define	T_LEFT	Cset[3]
#define	T_UP	Cset[4]
#define	T_DOWN	Cset[5]

#ifdef	DEBUG
#    define PAD()	printf("   ");
#    define PBAL(r)	printf("(%c)", r->bal==B ? 'B': r->bal==L ? 'L': 'R');
#else
#    define PAD()
#    define PBAL(r)
#endif

/* ------------------------------------------------------------------------ */

static	char *Graph_chars[] = { "\263",	"\332\304\304",	"\300\304\304"	,
			"\304\304\264",	"\304\304\331",	"\304\304\277"	};

static	char *Norm_chars[]  = { "|", "+--", "+--", "--+", "--+", "--+" };

static	int	(*Print) ();	/* Node print function pointer		*/
static	FILE	*Out;		/* Output stream			*/
static	char	**Cset ;	/* Current character set		*/
static	char	Map[ 64/8 ];	/* Bitmap for 64 bits.  If the		*/
				/* tree is deeper than this,		*/
				/* we're in trouble.			*/

/* ------------------------------------------------------------------------ */

#define	testbit(c)  ( Map[c >> 3] & (1 << (c & 0x07)) )

static	setbit( c, val )
int	c, val;
{
	if( val )
		Map[c >> 3]  |=   1 << (c & 0x07) ;
	else
		Map[c >> 3]  &=	~(1 << (c & 0x07)) ;
}


/* ------------------------------------------------------------------------ */

static	trav( root, amleft )
HEADER	*root;
int	amleft;
{
	/*	Prints a binary tree graphically, with lines showing
	 *	all the pointers.  This is essentially the same routine
	 *	we looked at last month.  See that article for more
	 *	info about how it works.
	 */

	static	int	depth = -1;	/* Current depth in the tree	*/
	static	int	i;

	if( root )
	{
		++depth;

		if( root->right )
			trav( root->right, 0 );
		else
			setbit( depth+1, 1 );


		for(i = 1; i <= depth ; i++ )
		{
			(*Print) (Out, 0);
			PAD();

			if( i == depth )
				fprintf(Out, "  %s", amleft ? ELL : GAMMA );

			else if( testbit(i) )
				fprintf(Out, "  %s  " , VERT );
			else
				fprintf(Out, "     " );
		}

		(*Print) (Out, root + 1 );
		PBAL(root);

		fprintf(Out, "%s\n",
			     (root->left) ? (root->right ? T_LEFT : T_DOWN)
			     		  : (root->right ? T_UP   : ""    )
			     		  );


		setbit( depth, amleft ? 0 : 1 );

		if( root->left )
			trav( root->left, 1 );
		else
			setbit( depth+1, 0 );

		--depth;
	}
}

/* ------------------------------------------------------------------------ */

void	tprint( root, print, stream )
HEADER	*root;
int	(*print)();
FILE	*stream;
{
	Out	= stream;
	Print	= print;
	Cset	= Out == stdout && isatty(fileno(stdout)) ? Graph_chars
							  : Norm_chars ;
	trav( root, 0 );
}