Sunday, February 26, 2012

Start ANTLR project with Maven

http://www.antlr.org/wiki/display/ANTLR3/Building+ANTLR+Projects+with+Maven

http://www.eclipse.org/m2e/
Download m2e
http://www.eclipse.org/m2e/download/





dave@dave antlr-maven]$ mvn archetype:generate -B -DarchetypeGroupId=org.antlr
-DarchetypeArtifactId=antlr3-maven-archetype
-DarchetypeVersion=3.3-1
-DgroupId=dave.antlr
-DartifactId=java-tree-walker
-Dversion=1.0
-Dpackage=dave.antlr
[INFO] Scanning for projects...
[INFO]
[INFO] ------------------------------------------------------------------------
[INFO] Building Maven Stub Project (No POM) 1
[INFO] ------------------------------------------------------------------------
[INFO]
[INFO] >>> maven-archetype-plugin:2.1:generate (default-cli) @ standalone-pom >>>
[INFO]
[INFO] <<< maven-archetype-plugin:2.1:generate (default-cli) @ standalone-pom <<<
[INFO]
[INFO] --- maven-archetype-plugin:2.1:generate (default-cli) @ standalone-pom ---
[INFO] Generating project in Batch mode
[INFO] Archetype repository missing. Using the one from [org.antlr:antlr3-maven-archetype:3.4] found in catalog remote
Downloading: http://repo1.maven.org/maven2/org/antlr/antlr3-maven-archetype/3.3-1/antlr3-maven-archetype-3.3-1.jar
Downloaded: http://repo1.maven.org/maven2/org/antlr/antlr3-maven-archetype/3.3-1/antlr3-maven-archetype-3.3-1.jar (11 KB at 34.4 KB/sec)
Downloading: http://repo1.maven.org/maven2/org/antlr/antlr3-maven-archetype/3.3-1/antlr3-maven-archetype-3.3-1.pom
Downloaded: http://repo1.maven.org/maven2/org/antlr/antlr3-maven-archetype/3.3-1/antlr3-maven-archetype-3.3-1.pom (3 KB at 6.0 KB/sec)
[INFO] ----------------------------------------------------------------------------
[INFO] Using following parameters for creating project from Archetype: antlr3-maven-archetype:3.3-1
[INFO] ----------------------------------------------------------------------------
[INFO] Parameter: groupId, Value: davedave@dave antlr-maven]$ mvn archetype:generate -B -DarchetypeGroupId=org.antlr -DarchetypeArtifactId=antlr3-maven-archetype -DarchetypeVersion=3.3-1 -DgroupId=dave.antlr -DartifactId=java-tree-walker -Dversion=1.0 -Dpackage=dave.antlr
[INFO] Scanning for projects...
[INFO]
[INFO] ------------------------------------------------------------------------
[INFO] Building Maven Stub Project (No POM) 1
[INFO] ------------------------------------------------------------------------
[INFO]
[INFO] >>> maven-archetype-plugin:2.1:generate (default-cli) @ standalone-pom >>>
[INFO]
[INFO] <<< maven-archetype-plugin:2.1:generate (default-cli) @ standalone-pom <<<
[INFO]
[INFO] --- maven-archetype-plugin:2.1:generate (default-cli) @ standalone-pom ---
[INFO] Generating project in Batch mode
[INFO] Archetype repository missing. Using the one from [org.antlr:antlr3-maven-archetype:3.4] found in catalog remote
Downloading: http://repo1.maven.org/maven2/org/antlr/antlr3-maven-archetype/3.3-1/antlr3-maven-archetype-3.3-1.jar
Downloaded: http://repo1.maven.org/maven2/org/antlr/antlr3-maven-archetype/3.3-1/antlr3-maven-archetype-3.3-1.jar (11 KB at 34.4 KB/sec)
Downloading: http://repo1.maven.org/maven2/org/antlr/antlr3-maven-archetype/3.3-1/antlr3-maven-archetype-3.3-1.pom
Downloaded: http://repo1.maven.org/maven2/org/antlr/antlr3-maven-archetype/3.3-1/antlr3-maven-archetype-3.3-1.pom (3 KB at 6.0 KB/sec)
[INFO] ----------------------------------------------------------------------------
[INFO] Using following parameters for creating project from Archetype: antlr3-maven-archetype:3.3-1
[INFO] ----------------------------------------------------------------------------
[INFO] Parameter: groupId, Value: dave.antlr
[INFO] Parameter: artifactId, Value: java-tree-walker
[INFO] Parameter: version, Value: 1.0
[INFO] Parameter: package, Value: dave.antlr
[INFO] Parameter: packageInPathFormat, Value: dave/antlr
[INFO] Parameter: package, Value: dave.antlr
[INFO] Parameter: version, Value: 1.0
[INFO] Parameter: groupId, Value: dave.antlr
[INFO] Parameter: artifactId, Value: java-tree-walker
[INFO] project created from Archetype in dir: /usr/app/project/antlr-maven/java-tree-walker
[INFO] ------------------------------------------------------------------------
[INFO] BUILD SUCCESS
[INFO] ------------------------------------------------------------------------
[INFO] Total time: 4.303s
[INFO] Finished at: Sun Feb 26 10:40:25 CET 2012
[INFO] Final Memory: 7M/17M
[INFO] ------------------------------------------------------------------------



[dave@dave java-tree-walker]$ cat >dave.dmo
Keyser Soze ;
2 + 3;



java -jar target/java-tree-walker-1.0-jar-with-dependencies.jar dave.dmo

java -jar target/java-tree-walker-1.0-jar-with-dependencies.jar -dot dave.dmo




Monday, February 20, 2012

Tree traversal

http://en.wikipedia.org/wiki/Tree_traversal
http://en.wikipedia.org/wiki/Breadth-first_search
http://en.wikipedia.org/wiki/Depth-first_search

Tree traversal in various languages
http://rosettacode.org/wiki/Tree_traversal#Java

Algorithms
http://algs4.cs.princeton.edu/home/
Graphs
http://algs4.cs.princeton.edu/40graphs/
Directed Graphs

http://algs4.cs.princeton.edu/42directed/

Java Data Structure: A Generic Tree

http://sujitpal.blogspot.com/2006/05/java-data-structure-generic-tree.html


Generic Node
public class Node<T> {

public T data;
public List<Node<T>> children;
public List<Node<T>> parents;


Non-generic node
package dave;

/**
* Non-generic subclass of Node<String>
*/
public class DaveNode extends Node<String> {
public DaveNode() {
super();
}
}



Walk using stack
 /**
*
* @param element
* @return set of all nodes
*/
public List<Node<T>> walk(Node<T> element){

List<Node<T>> out = new ArrayList<Node<T>>();

Queue<Node<T>> q = new LinkedList<Node<T>>();
q.add(element);

while(!q.isEmpty()){
Node<T> x = q.poll();
out.add(x);

for(Node<T> child : x.getChildren()){
q.add(child);
}
}

return out;

}


Walk from bottom up
  /**
*
* @param element
* @return set of all upper nodes
*/
public Collection<Node<T>> pathBottomUp(Node<T> element){

Set<Node<T>> out = new LinkedHashSet<Node<T>>();

Queue<Node<T>> q = new LinkedList<Node<T>>();
q.add(element);

while(!q.isEmpty()){
Node<T> x = q.poll();
out.add(x);

for(Node<T> parent : x.getParents()){
q.add(parent);
}
}

return out;

}


Construct tree
package dave;


public class WalkTree {

public static void main(String[] args) {

DaveTree daveTree = new DaveTree();

DaveNode daveNode = getDaveNode("1");

DaveNode daveNode11 = getDaveNode("1.1");
DaveNode daveNode12 = getDaveNode("1.2");
DaveNode daveNode13 = getDaveNode("1.3");

DaveNode daveNode131 = getDaveNode("1.3.1");
DaveNode daveNode132 = getDaveNode("1.3.2");

daveNode.addChild(daveNode11);
daveNode.addChild(daveNode12);
daveNode.addChild(daveNode13);

daveNode12.addChild(daveNode131);

daveNode13.addChild(daveNode131);
daveNode13.addChild(daveNode132);


daveTree.setRootElement(daveNode);

System.out.println(daveTree.toList());

Node<String> root = daveTree.getRootElement();

System.out.println("walk:" + daveTree.walk(root));

System.out.println("pathBottomUp:" +daveTree.pathBottomUp(daveNode131));

}

private static DaveNode getDaveNode(String profileName){

DaveNode daveNode = new DaveNode();

daveNode.setData(profileName);

return daveNode;

}

}



Program output
[{1,[1.1,1.2,1.3]}, {1.1,[]}, {1.2,[1.3.1]}, {1.3.1,[]}, {1.3,[1.3.1,1.3.2]}, {1.3.1,[]}, {1.3.2,[]}]
walk:[{1,[1.1,1.2,1.3]}, {1.1,[]}, {1.2,[1.3.1]}, {1.3,[1.3.1,1.3.2]}, {1.3.1,[]}, {1.3.1,[]}, {1.3.2,[]}]
pathBottomUp:[{1.3.1,[]}, {1.2,[1.3.1]}, {1.3,[1.3.1,1.3.2]}, {1,[1.1,1.2,1.3]}]