k4jt
BAN USERpackage careercup;
import java.util.*;
/**
* Date: 08.10.13
* Time: 01:14
*/
public class TreePrinter {
public static void printTree(Iterable<Relation> rs) {
class Tree {
String node;
List<Tree> child = new ArrayList<Tree>();
public Tree(String nodeName) {
node = nodeName;
}
Tree find(String nodeName) {
if (node.equals(nodeName)) {
return this;
} else {
for (Tree tree : child) {
Tree result = tree.find(nodeName);
if (result != null) {
return result;
}
}
}
return null;
}
}
Tree root = null;
Relation r = null;
Iterator<Relation> it = rs.iterator();
PriorityQueue<Relation> queue = new PriorityQueue<Relation>();
while( it.hasNext() ) {
r = it.next();
if (root == null) {
root = new Tree(r.parent);
root.child.add(new Tree(r.child));
} else {
Tree parent = root.find(r.parent);
if (parent != null) {
parent.child.add(new Tree(r.child));
} else {
parent = root.find(r.child);
if (parent == root) {
Tree newRoot = new Tree(r.parent);
newRoot.child.add(root);
root = newRoot;
} else {
queue.add(r);
}
}
}
int size = queue.size();
for (int i = 0; i < size; ++i) {
r = queue.poll();
Tree parent = root.find(r.parent);
if (parent != null) {
parent.child.add(new Tree(r.child));
} else {
parent = root.find(r.child);
if (parent == root) {
Tree newRoot = new Tree(r.parent);
newRoot.child.add(root);
root = newRoot;
} else {
queue.add(r);
}
}
}
}
while (!queue.isEmpty()) {
r = queue.poll();
Tree parent = root.find(r.parent);
if (parent != null) {
parent.child.add(new Tree(r.child));
} else {
parent = root.find(r.child);
if (parent == root) {
Tree newRoot = new Tree(r.parent);
newRoot.child.add(root);
root = newRoot;
} else {
queue.add(r);
}
}
}
Stack<Tree> stack = new Stack<Tree>();
stack.push(root);
int i = 1;
while(!stack.empty()) {
Tree currentTree = stack.pop();
System.out.println(i++ + ". " + currentTree.node);
for (int j = currentTree.child.size() - 1; j >= 0; --j) {
stack.push(currentTree.child.get(j));
}
}
}
static class Relation implements Comparable<Relation>{
String parent, child;
public Relation(String parent, String child) {
this.parent = parent;
this.child = child;
}
@Override
public int compareTo(Relation o) {
return 0;
}
}
public static void main(String[] arg) {
List<Relation> input = new ArrayList<Relation>();
input.add(new Relation("animal", "mammal"));
input.add(new Relation("animal", "bird"));
input.add(new Relation("lifeform", "animal"));
input.add(new Relation("cat", "lion"));
input.add(new Relation("mammal", "cat"));
input.add(new Relation("animal", "fish"));
TreePrinter.printTree(input);
}
}
yep, it's more easier and understandable :)
- k4jt October 08, 2013