import QuickQueue;
import SimpleOutput;
import Tree;

/**
 * A simple mechanism for printing trees in "outline form".  In
 * this form, the tree
 * <pre>
 *     A
 *   /   \
 *  B     E
 *  |    / \
 *  Q   T   S
 *     /|\
 *    X Y Z
 * <pre>
 * would be printed as
 * <pre>
 *    A
 *      B
 *        Q
 *      E
 *        T
 *          X
 *          Y
 *          Z
 *        S
 * </pre>
 */
public class TreePrinter
{
    /**
     * Print a tree in outline form to a particular output device.
     */
    public static void printOutline(SimpleOutput out, Tree tree) {
        if (tree.isEmpty())
            out.println("*** EMPTY ***");
        else
            printSubOutline(out, tree.getRoot(), "");
    } // printOutline(SimpleOutput, Tree);

    /**
     * Print a portion of a tree in outline form, indented by
     * a certain amount.
     */
    protected static void printSubOutline(SimpleOutput out,
                                       TreeVertex subtree,
                                       String indent)
    {
        // Print the value stored in the current vertex.
        out.println(indent + subtree.getValue());
        // Step through the children, printing them out.
        int numChildren = subtree.numChildren();
        for (int i = 1; i <= numChildren; i++) {
           printSubOutline(out, subtree.getChild(i), indent+"  ");
        } // for
    } // printSubTree(SimpleOutput, TreeVertex, String)

    /**
     * Print all the values in a tree in breadth-first, left-to-right,
     * preorder.
     */
    public static void printbfs(SimpleOutput out, Tree tree) {
        if (tree.isEmpty())
            out.println("*** EMPTY ***");
        else {
            QuickQueue queue = new QuickQueue();
            queue.enqueue(tree.getRoot());
            while (!queue.isEmpty()) {
                // Get the next thing to handle.
                TreeVertex current = 
                    (TreeVertex) queue.dequeue();
                // Print it out.
                out.print(current.getValue() + " ");
                // Add all of its children.
                int numChildren = current.numChildren();
                for (int i = 1; i <= numChildren; i++) {
                    queue.enqueue(current.getChild(i));
                } // for each dhild
            } // while the queue is not empty       
        } // if the tree is not empty
    } // printbfs

    /**
     * Print all the values in a tree in depth-first, left-to-right,
     * preorder.
     */
    public static void printdfs(SimpleOutput out, Tree tree) {
        if (tree.isEmpty())
            out.println("*** EMPTY ***");
        else
            printdfs(out, tree.getRoot());
    } // printdfs(SimpleOutput, Tree)

    /**
     * Print a portion of the tree in depth-first, left-to-right, 
     * preorder.
     */
    public static void printdfs(SimpleOutput out, TreeVertex vertex) {
        out.print(vertex.getValue() + " ");
        // Step through the children, printing them out.
        int numChildren = vertex.numChildren();
        for (int i = 1; i <= numChildren; i++) {
           printdfs(out, vertex.getChild(i));
        }
    } // printdfs(SimpleOutput, TreeVertex)(
 
} // class BinaryTreePrinter