/** This contains methods for creating and manipulating trees (binary or with
    arbitrary numbers of children.)  This differs from the Graph class in that
    children are ordered and identified with indices from 0 (leftmost)
    increasing.  A node in a Tree also knows its parent.

    A node in a tree has an associated name (for displaying to people or
    searching by name) and a data field which can contain any expression.

    Each node in a Tree is an instance of a Tree object.
*/

class Tree
{
   /** The name of this node.  */
   var name = undef

   /** The parent of this node (of type Tree).  May be undef if this is the
       root. */
   var parent = undef

   /** The data contained in this node. */
   var data = undef

   /** An array of children (of type Tree) of this node.  Should this be
       preallocated or deferred? */
   var children = new array

   /** Creates a new Tree with the specified name and no children. */
   new[name] :=
   {
      this.name = name
   }
   
   /** Creates a new Tree with the specified name and no children. Data is
       set to the specified data. */
   new[name, data] :=
   {
      this.name = name
      this.data = data
   }

   /** Returns the name of this Tree node. */
   getName[] := name

   /** Returns the data associated with this node. */
   getData[] := data

   /** Returns the parent of this Tree node.  Returns undef if this has no
       parent. */
   getParent[] := parent

   /** Returns the number of children of this node as an integer.  The child
       indices start from 0.  Some of these children may be undefined. */
   getChildCount[] :=
   {
      return length[children]
   }

   /** Gets the specified child of this node, specified by integer index.
       The leftmost child is index 0.  The return value is a Tree.  If the
       child does not exist, returns undef. */
   getChild[index] :=
   {
      return children.get[index, undef]
   }

   /** Sets the specified child of this node, specified by integer index.
       The leftmost child is index 0.  The child must also be a Tree.
       This will set the parent of the child to this.
   
       Child may be set to undef to detach the child from the tree.  In this
       case, the parent of the child is not reset so remember to change the
       parent if you're going to use the subtree again.
   */
   setChild[index, child is Tree] :=
   {
      children@index = child
      if child != undef
         child.parent = this
   }

   /** Sets the parent of a Tree to the specified parent Tree.
       This is automatically performed by methods like setChild so you don't
       have to do it yourself in that case.  Do not do this carelessly as you
       might create non-treelike cyclical data structures. */
   setParent[parentTree is Tree] :=
   {
      parent = parentTree
   }

   /** Appends a child tree to this tree.  The return value is the index of
       the tree that was attached.  This sets the parent of the child to this.
   */
   appendChild[child is Tree] :=
   {
      index = length[children]
      setChild[index, child]
      return index
   }

   /** Gets the depth of this node in the tree.  The root is depth 0.  This
       performs the check by walking backwards up the parents. */
   getDepth[] :=
   {
      depth = 0
      curr = this
      while curr.parent != undef
      {
         depth = depth + 1
         curr = curr.parent
      }

      return depth
   }

   /** Gets the root of this tree.  This performs the check by walking
       backwards up the parents. */
   getRoot[] :=
   {
      curr = this
      while curr.parent != undef
         curr = curr.parent

      return curr
   }

   /** Finds the first direct child that has the specified name and returns
       its index, undef if no such child exists. */
   findChildIndex[childName] :=
   {
      size = length[children]
      for i=0 to size-1
      {
         child = getChild[i]
         if child != undef AND child.getName[] == childName
            return i
      }

      return undef
   }

   /** Inserts the specified value into a binary tree.  The tree passed in
       is the root (of type Tree) or can be undef (in which case a new Tree
       is created.  This returns the root of the tree.  If the tree was
       previously nonexistent (tree is undef,) then you want to hold onto the
       new root using something like:

       a = toArray[1 to 10].shuffle[]   // Make random list of ints
       tree = undef
       for elem = a
          tree = Tree.insertBinary[tree, elem]

       THINK ABOUT:  Should this take an Orderer?
   */
   class insertBinary[tree, newname] :=
   {
      newtree = new Tree[newname]

      // If tree is undef the tree is empty and this is the new root
      if tree == undef
         return newtree

      par = undef  // Parent node of current node
      curr = tree  // Current node we're processing
      while curr != undef     // Walk the tree until we hit a leaf
      {
         par = curr
         if newname < curr.getName[]
            curr = curr.getChild[0]  // follow left tree
         else
            curr = curr.getChild[1]  // else follow right tree
      }

      // We have now found a leaf.  The parent of the leaf is in par and we
      // will set the new node to be the appropriate child of par.
      if newname < par.getName[]
         par.setChild[0, newtree]   // Set left tree of parent
      else
         par.setChild[1, newtree]   // set right tree of parent

      return tree
   }
   

   /** Performs an inorder traverse of the tree.  It takes a start
       node and an object that implements the TreeWatcher interface (defined
       below) which is notified when nodes and edges are visited.  The tree
       passed in should be a binary tree.
   */
   inorderTraverse[watcher is TreeWatcher] :=
   {
      left = getChild[0]
      if left != undef
         left.inorderTraverse[watcher]

      watcher.nodeVisited[this]

      right = getChild[1]
      if right != undef
         right.inorderTraverse[watcher]
   }

   /** Performs an preorder traverse of this tree.  It takes an object that
       implements the TreeWatcher interface (defined
       below) which is notified when nodes and edges are visited.    The tree
       passed in should be a binary tree.
   */
   preorderTraverse[watcher is TreeWatcher] :=
   {
      watcher.nodeVisited[this]
      
      left = getChild[0]
      if left != undef
         left.preorderTraverse[watcher]

      right = getChild[1]
      if right != undef
         right.preorderTraverse[watcher]
   }

   /** Performs an postorder traverse of this tree.  It takes an object that
       implements the TreeWatcher interface (defined
       below) which is notified when nodes and edges are visited. The tree
       passed in should be a binary tree.
   */
   postorderTraverse[watcher is TreeWatcher] :=
   {
      left = getChild[0]
      if left != undef
         left.postorderTraverse[watcher]

      right = getChild[1]
      if right != undef
         right.postorderTraverse[watcher]

      watcher.nodeVisited[this]
   }
   
   /** This performs a breadth-first traversal of this tree.  It takes an
       object that implements the GraphWatcher interface (defined
       below) which is notified when nodes and edges are visited.
   */
   breadthFirstTraverse[watcher is TreeWatcher] :=
   {
      // A queue of nodes to visit.
      queue = new array

      queue.push[this]
      
      while ! queue.isEmpty[]
      {
         currNode = queue.popFirst[]

         // do process node early behavior here
         watcher.nodeVisited[currNode]

         for child = currNode.children
            if child != undef
               queue.push[child]
      }
   }

   
   /** This performs a depth-first traversal of this tree.  It takes an object
       that implements the GraphWatcher interface (defined
       below) which is notified when nodes and edges are visited.
   */
   depthFirstTraverse[watcher is TreeWatcher] :=
   {
      // A stack of nodes to visit.
      stack = new array

      stack.push[this]
      
      while ! stack.isEmpty[]
      {
         currNode = stack.pop[]

         // do process node early behavior here
         watcher.nodeVisited[currNode]

         // Traverse children in reverse order so we do a traditional
         // left-to-right traverse.
         size = length[currNode.children]
         for i = size-1 to 0 step -1
         {
            child = currNode.children@i
            if child != undef
               stack.push[child]
         }
      }
   }

   /** Dumps a text representation of a tree.  This sets up for a recursive
       call. */
   dump[] :=
   {
      dump[0]
   }

   /** Recursive call to dump a tree. */
   dump[indent] :=
   {
      ind = repeat[" ", indent * 3]
      result = getName[] + "\n"

      for i=0 to getChildCount[]-1
      {
         child = getChild[i]
         if child != undef
            result = result + ind + "child $i: " + child.dump[indent+1]
      }

      return result
   }
   
   /** Creates a dot file of this tree that can be plotted or manipulated with
       the Graphviz set of tools.

       See https://www.graphviz.org/doc/info/lang.html

       OH NOES GRAPHVIZ CAN'T EVEN LAY OUT A BINARY TREE LOL
       https://gitlab.com/graphviz/graphviz/-/issues/2032
       https://forum.graphviz.org/t/binary-tree-force-lonely-node-to-be-left-or-right/1159/4
   
       params:
        [directed, extraData]

       * directed is a boolean flag which controls if edges are rendered as
         a directed or undirected (bidirectional.)  If directed is true, this
         will draw directed edges.  If directed is false, this will render
         undirected edges.

       * extraData is .dot code that will be placed directly into the file.
         For example,
         """fontname="Helvetica,Arial,sans-serif"
            node [fontname="Helvetica,Arial,sans-serif"]
            edge [fontname="Helvetica,Arial,sans-serif"]"""

       This can be

       dot = g.toDotFile[false]
       w = new Writer["tree6.dot"]
       w.print[dot]
       w.close[]

       and then rendered to the desired format with a command-line like:
       dot -Tsvg tree6.dot > tree6.svg

       where "dot" can be another layout program like "neato" or "circo"
   */
   toDotFile[directed, extraData=""] :=
   {
      if directed
         res = "digraph"
      else
         res = "graph"

      res = res + "\n{\n"

//      res = res + """  graph  [ordering="out"]\n"""

      if extraData != ""
         res = res + extraData + "\n"

      watcher = new DotFileTreeWatcher[false]
      inorderTraverse[watcher]
      res = res + watcher.getString[]
      res = res + "}"
   }
}


/** This is a public interface for a set of functions that must be implemented
    by a class that wants to observe the traversal of a tree (say, breadth-
    first, depth-first, or, for a tree, pre-, post-, or in-order search.)
    It contains methods that will be called when a node is visited.

    THINK ABOUT:  Should this have events that are called at the beginning
    and end of a traversal?
*/
interface TreeWatcher
{
   /** This method is called during the traverse of a graph as a node is
       visited. */
   nodeVisited[node is Tree]
}


/** This is an implementation of the TreeWatcher interface that prints out the
    name of each node as it is traversed.
*/
class PrintTreeWatcher implements TreeWatcher
{
   /** This method is called during the traverse of a graph as a node is
       visited. */
   nodeVisited[node is Tree] :=
   {
      println["Visted " + node.getName[]]
   }
}


/** This is an implementation of the TreeWatcher interface that appends dot file
    relations to a string each time it is called.
*/
class DotFileTreeWatcher implements TreeWatcher
{
   var res = ""

   var directed

   new[directed] :=
   {
      this.directed = directed
   }
   
   /** This method is called during the traverse of a graph as a node is
       visited. */
   nodeVisited[node is Tree] :=
   {
      parent = node.getParent[]
      if parent != undef
      {
         res = res + "   \"" + parent.getName[] + "\"" + (directed ? " ->" : " --")
         res = res + " \"" + node.getName[]  + "\"\n"
      }
   }

   getString[] := res
}


/** This is an implementation of the TreeWatcher interface that appends to an
    array name of each node as it is traversed.
*/
class ArrayTreeWatcher implements TreeWatcher
{
   var array = new array
   
   /** This method is called during the traverse of a graph as a node is
       visited. */
   nodeVisited[node is Tree] :=
   {
      array.push[node]
   }

   /** Call this to get the value of the array. */
   getArray[] := array
}