package org.psjava.example.algo;

import org.junit.Assert;
import org.junit.Test;
import org.psjava.algo.graph.LowestCommonAncestor;
import org.psjava.algo.graph.LowestCommonAncestorPreprecessed;
import org.psjava.ds.graph.DirectedEdge;
import org.psjava.ds.graph.MutableDirectedGraph;
import org.psjava.ds.graph.RootedTree;
import org.psjava.example.ds.RootedTreeExample;
import org.psjava.goods.GoodLowestCommonAncestor;

/**
 * @implementation {@link LowestCommonAncestor}
 * @see {@link RootedTreeExample}
 */
public class LowestCommonAncestorExample {

	@Test
	public void example() {
		MutableDirectedGraph<String> graph = MutableDirectedGraph.create();
		graph.insertVertex("A");
		graph.insertVertex("B");
		graph.insertVertex("C");
		graph.insertVertex("D");

		graph.addEdge("A", "B");
		graph.addEdge("A", "C");
		graph.addEdge("C", "D");

		RootedTree<String, DirectedEdge<String>> tree = RootedTree.create(graph, "A");

		LowestCommonAncestorPreprecessed<String> preprocessed = GoodLowestCommonAncestor.getInstrance().calc(tree);

		String result1 = preprocessed.query("B", "C"); // must be "A"
		Assert.assertEquals("A", result1);

		String result2 = preprocessed.query("A", "D"); // must be "A"
		Assert.assertEquals("A", result2);
	}
}

@@ -199,50 +199,8 @@
 d;%0D%0A
-import org.psjava.ds.graph.DirectedEdge;%0D%0A
 impo
@@ -561,16 +561,77 @@
 le() %7B%0D%0A
+%09%09// Let's construct a simple rooted tree. A is the root.%0D%0A%0D%0A
 %09%09Mutabl
@@ -899,86 +899,18 @@
 %0D%0A%09%09
-RootedTree%3CString, DirectedEdge%3CString%3E%3E tree = RootedTree.create(graph, %22A%22);
+// Run it!
 %0D%0A%0D%0A
@@ -952,28 +952,22 @@
 String%3E 
-p
 re
-processed
+sult
  = GoodL
@@ -1006,20 +1006,45 @@
 ().calc(
-tree
+RootedTree.create(graph, %22A%22)
 );%0D%0A%0D%0A%09%09
@@ -1060,28 +1060,22 @@
 sult1 = 
-preprocessed
+result
 .query(%22
@@ -1163,20 +1163,14 @@
 2 = 
-preprocessed
+result
 .que

improve LowestCommonAncestorExample