yct

public class ASCIITreePrinter {

    int MAX_HEIGHT;
    int INFINITY = Integer.MAX_VALUE;
    int lprofile[], rprofile[];
    int print_next;
    StringBuilder sb;
    int gap = 1;

    public ASCIITreePrinter(int max_height) {
        MAX_HEIGHT = max_height;
        lprofile = new int[max_height];
        rprofile = new int[max_height];
        sb = new StringBuilder();
    }

    void p(Object o) {
        sb.append(o);
    }

    public String toString() {
        return sb.toString();
    }

    public interface Node {
        Node getLeft();
        Node getRight();
        Object getElement();
    }

    //prints ascii tree for given node classure
    void print_ascii_tree(Node t)
    {
      asciinode proot;
      int xmin, i;
      if (t == null) return;
      proot = build_ascii_tree(t);
      compute_edge_lengths(proot);
      for (i=0; i<proot.height && i < MAX_HEIGHT; i++)
      {
        lprofile[i] = INFINITY;
      }
      compute_lprofile(proot, 0, 0);
      xmin = 0;
      for (i = 0; i < proot.height && i < MAX_HEIGHT; i++)
      {
        xmin = Math.min(xmin, lprofile[i]);
      }
      for (i = 0; i < proot.height; i++)
      {
        print_next = 0;
        print_level(proot, -xmin, i);
        p("\n");
      }
      if (proot.height >= MAX_HEIGHT)
      {
        p("(This tree is taller than " + MAX_HEIGHT + ", and may be drawn incorrectly.)\n");
      }
      free_ascii_tree(proot);
    }

    //This function prints the given level of the given tree, assuming
    //that the node has the given x cordinate.
    void print_level(asciinode node, int x, int level)
    {
      int i, isleft;
      if (node == null) return;
      isleft = (node.parent_dir == -1 ? 1 : 0);
      if (level == 0)
      {
        for (i=0; i<(x-print_next-((node.lablen-isleft)/2)); i++)
        {
          p(" ");
        }
        print_next += i;
        p(node.label);
        print_next += node.lablen;
      }
      else if (node.edge_length >= level)
      {
        if (node.left != null)
        {
          for (i=0; i<(x-print_next-(level)); i++)
          {
            p(" ");
          }
          print_next += i;
          p("/");
          print_next++;
        }
        if (node.right != null)
        {
          for (i=0; i<(x-print_next+(level)); i++)
          {
            p(" ");
          }
          print_next += i;
          p("\\");
          print_next++;
        }
      }
      else
      {
        print_level(node.left,
                    x-node.edge_length-1,
                    level-node.edge_length-1);
        print_level(node.right,
                    x+node.edge_length+1,
                    level-node.edge_length-1);
      }
    }


    //This function fills in the edge_length and
    //height fields of the specified tree
    void compute_edge_lengths(asciinode node)
    {
      int h, hmin, i, delta;
      if (node == null) return;
      compute_edge_lengths(node.left);
      compute_edge_lengths(node.right);

      // first fill in the edge_length of node
      if (node.right == null && node.left == null)
      {
        node.edge_length = 0;
      }
      else
      {
        if (node.left != null)
        {
          for (i=0; i<node.left.height && i < MAX_HEIGHT; i++)
          {
            rprofile[i] = -INFINITY;
          }
          compute_rprofile(node.left, 0, 0);
          hmin = node.left.height;
        }
        else
        {
          hmin = 0;
        }
        if (node.right != null)
        {
          for (i=0; i<node.right.height && i < MAX_HEIGHT; i++)
          {
            lprofile[i] = INFINITY;
          }
          compute_lprofile(node.right, 0, 0);
          hmin = Math.min(node.right.height, hmin);
        }
        else
        {
          hmin = 0;
        }
        delta = 4;
        for (i=0; i<hmin; i++)
        {
          delta = Math.max(delta, gap + 1 + rprofile[i] - lprofile[i]);
        }

        //If the node has two children of height 1, then we allow the
        //two leaves to be within 1, instead of 2
        if (((node.left != null && node.left.height == 1) ||
              (node.right != null && node.right.height == 1))&&delta>4)
        {
          delta--;
        }

        node.edge_length = ((delta+1)/2) - 1;
      }

      //now fill in the height of node
      h = 1;
      if (node.left != null)
      {
        h = Math.max(node.left.height + node.edge_length + 1, h);
      }
      if (node.right != null)
      {
        h = Math.max(node.right.height + node.edge_length + 1, h);
      }
      node.height = h;
    }

    asciinode  build_ascii_tree_recursive(Node t)
    {
      asciinode  node;

      if (t == null) return null;

      node = new asciinode();
      node.left = build_ascii_tree_recursive(t.getLeft());
      node.right = build_ascii_tree_recursive(t.getRight());

      if (node.left != null)
      {
        node.left.parent_dir = -1;
      }

      if (node.right != null)
      {
        node.right.parent_dir = 1;
      }

      node.label = String.valueOf(t.getElement());
      node.lablen = node.label.length();

      return node;
    }


    //Copy the tree into the ascii node classre
    asciinode  build_ascii_tree(Node t)
    {
      asciinode node;
      if (t == null) return null;
      node = build_ascii_tree_recursive(t);
      node.parent_dir = 0;
      return node;
    }

    //Free all the nodes of the given tree
    void free_ascii_tree(asciinode node)
    {
      if (node == null) return;
      free_ascii_tree(node.left);
      free_ascii_tree(node.right);
      //free(node);
    }

    //The following function fills in the lprofile array for the given tree.
    //It assumes that the center of the label of the root of this tree
    //is located at a position (x,y).  It assumes that the edge_length
    //fields have been computed for this tree.
    void compute_lprofile(asciinode node, int x, int y)
    {
      int i, isleft;
      if (node == null) return;
      isleft = node.parent_dir == -1 ? 1 : 0;
      lprofile[y] = Math.min(lprofile[y], x-((node.lablen-isleft)/2));
      if (node.left != null)
      {
        for (i=1; i <= node.edge_length && y+i < MAX_HEIGHT; i++)
        {
          lprofile[y+i] = Math.min(lprofile[y+i], x-i);
        }
      }
      compute_lprofile(node.left, x-node.edge_length-1, y+node.edge_length+1);
      compute_lprofile(node.right, x+node.edge_length+1, y+node.edge_length+1);
    }

    void compute_rprofile(asciinode node, int x, int y)
    {
      int i, notleft;
      if (node == null) return;
      notleft = (node.parent_dir != -1 ? 1 : 0);
      rprofile[y] = Math.max(rprofile[y], x+((node.lablen-notleft)/2));
      if (node.right != null)
      {
        for (i=1; i <= node.edge_length && y+i < MAX_HEIGHT; i++)
        {
          rprofile[y+i] = Math.max(rprofile[y+i], x+i);
        }
      }
      compute_rprofile(node.left, x-node.edge_length-1, y+node.edge_length+1);
      compute_rprofile(node.right, x+node.edge_length+1, y+node.edge_length+1);
    }

    static class asciinode
    {
      asciinode  left,  right;

      //length of the edge from this node to its children
      int edge_length;

      int height;

      int lablen;

      //-1=I am left, 0=I am root, 1=right
      int parent_dir;

      //max supported unit32 in dec, 10 digits max
      String label;
    };
}