Saturday, November 30, 2013

N-ary tree serialization, Java

import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;

interface TreeVisitor
{
void visit(TreeNode node);
}

interface VisitableTree
{
void accept(TreeVisitor visitor);
}

class TreeNode implements VisitableTree
{
private int value;
private List children;
public TreeNode(int value)
{
this.value = value;
children = new ArrayList();
}

public void addChild(TreeNode child)
{
children.add(child);
}

public List getChildren()
{
return children;
}

public void accept(TreeVisitor visitor){
visitor.visit(this);
}

public int getValue()
{
return value;
}

public String toString(){
return "" + value;
}

}

class PreOrderTreeVisitor implements TreeVisitor
{
public void visit(TreeNode node)
{
System.out.print(node.getValue() + " [");
for(TreeNode child : node.getChildren())
{
child.accept(this);
}
System.out.print("] ");

}
}

class TreeSerializerVisitor implements TreeVisitor
{
public void visit(TreeNode node)
{
System.out.println(node.getValue());

for(TreeNode child : node.getChildren())
{
child.accept(this);
}

System.out.println("--");
}
}

class TreeBuilder
{
public TreeNode build(String input)
{
String[] lines = input.split("\n");
if(lines[0] == "--")
return null;

TreeNode currentNode = null;
List stack = new ArrayList();
for(String line : lines)
{
if(line.equals("--"))
{
currentNode = stack.remove(stack.size()-1);
continue;
}

TreeNode newNode = new TreeNode(Integer.parseInt(line));

if(currentNode == null)
{
currentNode = newNode;
stack.add(currentNode);
continue;
}
currentNode.addChild(newNode);
stack.add(currentNode);
currentNode = newNode;
}
return currentNode;
}
}

public class Main
{
public static void main(String[] args)
{
TreeNode root = new TreeNode(4);
TreeNode child1 = new TreeNode(5);
TreeNode child2 = new TreeNode(6);
child1.addChild(new TreeNode(22));
child1.addChild(new TreeNode(44));

root.addChild(child1);
root.addChild(child2);

TreeVisitor visitor = new PreOrderTreeVisitor();

TreeVisitor serializer = new TreeSerializerVisitor();
serializer.visit(root);

TreeBuilder builder = new TreeBuilder();
System.out.println("");
visitor.visit(builder.build("4\n5\n22\n--\n44\n--\n--\n6\n--\n--\n"));
System.out.println("");
visitor.visit(root);
}
}