Skip to content

Instantly share code, notes, and snippets.

@nerdyworm
Created November 13, 2010 01:10
Show Gist options
  • Save nerdyworm/674988 to your computer and use it in GitHub Desktop.
Save nerdyworm/674988 to your computer and use it in GitHub Desktop.
/**
* 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);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment