/** 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
}