/*
 * Tree Package Version 1.0, April 25, 1989.
 * Implementation by Eric Giguere.  This code is in the public domain.
 *
 * vprint.c
 *
 * This file implements a routine for printing binary trees in a
 * vertical direction.  It can be used with any of the trees
 * (simple, splay or AVL) implemented in this package.  See the
 * external documentation for details.
 *
 * This routine is based on the one found in "Data Structures with
 * Abstract Types and Modula-2" by Stubbs & Webre.
 */

#define _NO_VPRINT_PROTOTYPES_

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

#define NLCHAR '\n'
#define SPACE  ' '

/*
 * For portability the malloc() and free() routines are used.
 * Amiga users can substitute AllocMem and FreeMem if they wish.
 */

extern void *malloc(), free();

/*
 * Define the internal structures.  The printing routine used
 * a linked list of linked lists to keep track of printing
 * positions for each node.
 */

typedef struct list_node
  {
    tree_node        *node;
    int               pos;
    struct list_node *next;
  }
    list_node;

typedef struct level_node
  {
    list_node         *first;
    struct level_node *next;
  }
    level_node;

/*
 * Module-specific data
 */

static int  minpos, maxpos;

static int  position();
static void llprint();

/*
 * v_pr_tree -- Print a binary tree in a vertical format.
 *              The page width and the maximum width of each
 *              label must be given.  This routine does NOT
 *              handle trees larger than the page width.
 *              Returns TRUE if printing was successful.
 */

int v_pr_tree( root, width, fieldlen, func )
  tree_node  *root;
  int         width, fieldlen;
  int       (*func)();
  {
    level_node *entry;

    if( root == NULL || width <= 0 || fieldlen <= 0 || func == NULL )
        return( FALSE );

    if( width <= fieldlen )
        return( FALSE );

    entry  = NULL;
    minpos = 0;
    maxpos = 0;

    position( root, &entry, 0, fieldlen );
    llprint( func, width, fieldlen, entry );

    return( TRUE );
  }

/*
 * position -- Calculate the horizontal & vertical positions
 *             for each label.
 */

static int position( node, level, pos, fieldlen )
  tree_node   *node;
  level_node **level;
  int          pos, fieldlen;
  {
    list_node   *list;
    level_node **next;

    if( node == NULL )
        return( pos );

    /* Start a new level or add to existing one */

    if( *level == NULL )
      {
        *level          = malloc( sizeof( level_node ) );
        (*level)->next  = NULL;
        (*level)->first = NULL;
      }
    else if( ( pos + 2 ) > (*level)->first->pos )
         pos = (*level)->first->pos - 2;

    /* Add a new horizontal element */

    list            = malloc( sizeof( list_node ) );
    list->node      = node;
    list->pos       = 0;
    list->next      = (*level)->first;
    (*level)->first = list;

    /* Calculate the position */

    next = &((*level)->next);

    if( node->right == NULL )
        pos = position( node->left, next, pos - 1, fieldlen ) + 1;
    else if( node->left == NULL )
        pos = position( node->right, next, pos + 1, fieldlen ) - 1;
    else
      {
        pos = ( position( node->right, next, pos + 1, fieldlen ) +
                position( node->left, next, pos - 1, fieldlen ) ) / 2;
      }

    /* Change & store parms */

    if( pos > maxpos )
        maxpos = pos;

    if( pos < minpos )
        minpos = pos;

    list->pos = pos;

    return( pos );
  }

/*
 * llprint -- Print the tree once the auxiliary data has
 *            been collected.
 */

void llprint( func, pw, fieldlen, first )
  int       (*func)();
  int         pw, fieldlen;
  level_node *first;
  {
    int         start, center, k, temp;
    level_node *level, *l2;
    list_node  *lp;

    /* Adjust positions */

    minpos *= fieldlen;
    maxpos *= fieldlen;

    /* Print the tree */

    for( start = minpos; start <= maxpos; start += pw )
      {
        level  = first;
        center = 0;

        /* Center tree */

        if( ( maxpos - start ) < pw )
          {
            center = ( pw - ( maxpos - minpos + 1 ) ) / 2;
            center -= fieldlen / 2;
          }

        /* Print each level of the tree */

        while( level != NULL )
          {
            for( lp = level->first; lp != NULL; lp = lp->next )
                lp->pos *= fieldlen;

            for( k = center; k > 0; --k )
                putchar( SPACE );

            k  = start;
            lp = level->first;

            while( ( k < ( start + pw ) ) && lp != NULL )
              {
                if( lp->pos == k )
                  {
                    k += (*func)( lp->node, pw, k );
                    lp = lp->next;
                  }
                else
                  {
                    putchar( SPACE );
                    ++k;
                  }
              }

            putchar( NLCHAR );

            /* Print the tree structure */

            if( level->next != NULL )
              {
                for( k = center - 1; k > 0; --k )
                    putchar( SPACE );

                k  = start - 1;
                lp = level->first;

                while( k < ( start + pw ) && lp != NULL )
                  {
                    if( lp->pos == k + 1 )
                      {
                        putchar( ( lp->node->left != NULL ) ? '/' : SPACE );

                        for( temp = fieldlen; temp > 0; --temp )
                            putchar( SPACE );

                        putchar( ( lp->node->right != NULL ) ? '\\' : SPACE);

                        k += fieldlen + 2;
                        lp = lp->next;
                      }
                    else
                      {
                        putchar( SPACE );
                        ++k;
                      }
                  }
              }

            putchar( NLCHAR );

            /* Free the memory */

            for( lp = level->first; lp != NULL; lp = level->first )
              {
                level->first = lp->next;
                free( lp );
              }

            /* Do next level */

            level = level->next;
          }
      }

    /* Free the list of levels */

    level = first;

    while( level != NULL )
      {
        l2    = level;
        level = level->next;
        free( l2 );
      }
  }