Megafasttree.java

/**
 *  Copyright 2010 Coderloop.com.
 *  Author: Diego, the architect
 **/
package com.coderloop.puzzles;

import java.util.List;
import java.util.LinkedList;

//! This class implements a Megafasttree
//! A mega-fast-tree is just a tree, but faster
//! Why am I not using the common libraries?
//! Because my tree implementation is faster!
public class Megafasttree {

	// private List<String> results = new LinkedList<String>();
	// ! The list containing the MegafasttreeTM
	private List<Node> tree = new LinkedList<Node>();

	// ! This is a node of the MegafasttreeTM
	public static class Node {
		// ! This is the left child of a node of the MegafasttreeTM
		private Node left;
		// ! This is the right child of a node of the MegafasttreeTM
		private Node right;
		// ! The payload of this node
		private Integer payload;

		public Node(int payload) {
			this.left = this.right = null;
			this.payload = new Integer(payload);
		}

		// ! Set the left child
		public Node setLeftChild(Node n) {
			this.left = n;
			return this;
		}

		// ! Set the right child
		public Node setRightChild(Node n) {
			this.right = n;
			return this;
		}

		// ! Return the left child
		public Node toLeft() {
			return this.left;
		}

		// ! Return the right child
		public Node toRight() {
			return this.right;
		}

		// ! Visit the current node
		public String visit() {
			StringBuffer sb = new StringBuffer();
			sb.append(this.payload);
			return sb.toString();
		}
	}

	private StringBuffer buffer;

	// ! This implement a breadth first search (but very fast!)
	private void breadthFirstRecursion(Node node) {
		// results.add(node.visit());
		if (node == null)
			return;

		buffer.append(node.visit());

		if (null != node.toLeft()) {
			breadthFirstRecursion(node.toLeft());
		}

		if (null != node.toRight()) {
			breadthFirstRecursion(node.toRight());
		}
	}

	private String breadthFirst(Node root) {
		buffer = new StringBuffer();

		LinkedList<Node> internalQueue = new LinkedList<Node>();
		internalQueue.add(root);
		buffer.append(root.visit());
		
		while(true)
		{
			if (internalQueue.isEmpty()){
				break;
			}
			
			Node node = internalQueue.removeFirst();
			Node left = node.toLeft();
			Node right = node.toRight();
			
			if(null != left)
			{
				buffer.append(left.visit());
				internalQueue.add(left);
			}
				
			if(null != right)
			{
				buffer.append(right.visit());
				internalQueue.add(right);
			}
		
		}

		return buffer.toString();
	}

	// Public method, do not touch this signature...
	public void addRoot(Node n) {
		if (n != null)
			tree.add(n);
	}

	// Public method, do not touch this signature...
	public String bfs() {
		Node root = tree.get(0);
		return breadthFirst(root);
	}
}