package algs32;
import java.util.Scanner;
import algs13.Queue;
import stdlib.*;

public class XTree {
  private Node root;
  private XTree (Node root) { this.root = root; }
  private static class Node {
    public final int val;
    public final Queue<Node> children; // children must not be null
    public Node (int val) {
      this.val = val;
      this.children = new Queue<>();
    }
  }

  // tree input has the form "num ( ... )"
  // where num is an integer and ... is another tree input
  // example: "0 ( 1 ( 11 12 13 ) 2 ( 21 22 ( 221 222 223 ) ) 3 ( ) 4 )"
  // empty parens "( )" are optional.
  public static XTree parse (String in) {
    Scanner sc = new Scanner (in);
    Node root = parseHelper (sc);
    return new XTree (root);
  }
  private static Node parseHelper (Scanner sc) {
    int val = sc.nextInt ();
    Node result = new Node (val);
    if (sc.hasNext ("\\(")) {
      sc.next (); // gobble "("
      while (sc.hasNextInt ()) {
        Node child = parseHelper (sc);
        result.children.enqueue (child);
      }
      sc.next ("\\)"); //gobble ")"
    }
    return result;
  }

  // prefix with parenthesis
  public String toString() {
    StringBuilder sb = new StringBuilder();
    if (root != null) toString (sb, root);
    return sb.toString ();
  }
  private static void toString (StringBuilder sb, Node n) {
    sb.append (n.val);
    sb.append (" ");
    if (!n.children.isEmpty ()) {
      sb.append ("( ");
      for (Node child : n.children)
        toString (sb, child);
      sb.append (") ");
    }
  }

  public void toGraphviz(String filename) {
    GraphvizBuilder gb = new GraphvizBuilder ();
    if (root != null) toGraphviz (gb, null, root);
    gb.toFileUndirected (filename, "ordering=\"out\"");
  }
  private static void toGraphviz (GraphvizBuilder gb, Node parent, Node n) {
    gb.addLabeledNode (n, Integer.toString (n.val));
    if (parent != null) gb.addEdge (parent, n);
    for (Node child : n.children)
      toGraphviz (gb, n, child);
  }

  // prefix order traversal
  public void printPre () {
    if (root != null) printPre (root);
    StdOut.println ();
  }
  private static void printPre (Node n) {
    StdOut.print (n.val + " ");
    for (Node child : n.children) {
      printPre (child);
    }
  }

  // level order traversal
  public void printLevel () {
    Queue<Node> queue = new Queue<>();
    if (root != null) queue.enqueue(root);
    while (!queue.isEmpty()) {
      Node n = queue.dequeue();
      StdOut.print (n.val + " ");
      for (Node child : n.children) {
        queue.enqueue(child);
      }
    }
    StdOut.println ();
  }

  public static void main(String[] args) {
    XTree xtree = XTree.parse ("0 ( 1 ( 11 12 ( 121 ( 1211 1212 ) 122 123 124 125 ) 13 ) 2 ( 21 22 ( 221 222 223 ) ) 3 )");
    StdOut.println (xtree);
    xtree.printPre ();
    xtree.printLevel ();
    xtree.toGraphviz ("xtree.png");
  }
}