//******************************************************************************
//
// File: TreeDrawing.java
// Package: edu.rit.compbio.phyl
// Unit: Class edu.rit.compbio.phyl.TreeDrawing
//
// This Java source file is copyright (C) 2008 by Alan Kaminsky. All rights
// reserved. For further information, contact the author, Alan Kaminsky, at
// ark@cs.rit.edu.
//
// This Java source file is part of the Parallel Java Library ("PJ"). PJ is free
// software; you can redistribute it and/or modify it under the terms of the GNU
// General Public License as published by the Free Software Foundation; either
// version 3 of the License, or (at your option) any later version.
//
// PJ is distributed in the hope that it will be useful, but WITHOUT ANY
// WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
// A PARTICULAR PURPOSE. See the GNU General Public License for more details.
//
// Linking this library statically or dynamically with other modules is making a
// combined work based on this library. Thus, the terms and conditions of the
// GNU General Public License cover the whole combination.
//
// As a special exception, the copyright holders of this library give you
// permission to link this library with independent modules to produce an
// executable, regardless of the license terms of these independent modules, and
// to copy and distribute the resulting executable under terms of your choice,
// provided that you also meet, for each linked independent module, the terms
// and conditions of the license of that module. An independent module is a
// module which is not derived from or based on this library. If you modify this
// library, you may extend this exception to your version of the library, but
// you are not obligated to do so. If you do not wish to do so, delete this
// exception statement from your version.
//
// A copy of the GNU General Public License is provided in the file gpl.txt. You
// may also obtain a copy of the GNU General Public License on the World Wide
// Web at http://www.gnu.org/licenses/gpl.html.
//
//******************************************************************************
package edu.rit.compbio.phyl;
import edu.rit.draw.Drawing;
import edu.rit.draw.item.Group;
import edu.rit.draw.item.Line;
import edu.rit.draw.item.Point;
import edu.rit.draw.item.Text;
import java.io.PrintStream;
import java.text.DecimalFormat;
import java.util.LinkedList;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
/**
* Class TreeDrawing provides an object that draws a picture of a phylogenetic
* tree. The tree is specified either as a {@linkplain DnaSequenceTree} object
* or as a string in a subset of Newick Standard format.
*
* Note: Class TreeDrawing is not multiple thread safe.
*
* Newick Standard format. The subset of Newick Standard format class
* TreeDrawing supports is described by this BNF syntax. Nonterminal symbols are
* in italic font, terminal symbols are in typewriter font, |
* designates alternatives.
*
* tree ::= node ;
*
node ::= ( childList ) nameLength
*
childList ::= child | child , childList
*
child ::= tip | node
*
tip ::= nameLength
*
nameLength ::= empty | name | : length | name : length
*
name ::= Any sequence of non-whitespace characters except ( ) , : ;
*
length ::= Floating point number, as in the Double.valueOf() method
*
* This subset only supports non-quoted names with no whitespace; however, any
* underscore character _ in a name is replaced with a space character.
* The full Newick Standard format supports quoted names including whitespace.
* For further information about Newick Standard format, see:
*
*
* Here is an example tree:
*
* "(Gibbon:10,(Orangutan:8,(Gorilla:6,(Chimp:4,Human:4)))apes)primates;"
*
* Here is the resulting drawing:
*
* 
*
* @author Alan Kaminsky
* @version 25-Jul-2008
*/
public class TreeDrawing
{
// Hidden constants.
// Vertical distance between tip strings.
private static final double V = 27.0;
// Length of lines from a node to its descendents.
private static final double H = 72.0;
// Gap from line to tip text.
private static final double GAP = 6.0;
// Gap from line to branch length text.
private static final double VGAP = 3.0;
// Regular expression for parsing tokens in Newick Standard format.
private static final Pattern pattern =
Pattern.compile ("\\(|\\)|,|:|;|[^(),:; \\t\\n\\x0B\\f\\r]+");
// Hidden data members.
// Tree string in Newick Standard format.
private String treestring;
// For formatting branch lengths.
private DecimalFormat format = new DecimalFormat ("0.00");
// Matcher for parsing tokens.
private Matcher matcher;
// Current token and its starting index in .
private String token;
private int index;
// Number of tips.
private int tipCount;
// Group in which to store the tree drawing.
private Group group;
// Exported constructors.
/**
* Construct a new tree drawing object.
*/
public TreeDrawing()
{
}
// Main program.
/**
* Specify the format with which to draw branch lengths. The format string
* is used to construct a java.text.DecimalFormat object. If not specified,
* the default format string is "0.00".
*
* @param format Format string.
*/
public void setBranchLengthFormat
(String format)
{
this.format = new DecimalFormat (format);
}
/**
* Draw a picture of the given tree. The picture is added to the default
* {@linkplain edu.rit.draw.Drawing} object.
*
* @param tree DNA sequence tree.
*/
public void draw
(DnaSequenceTree tree)
{
draw (tree, Drawing.defaultDrawing());
}
/**
* Draw a picture of the given tree. The picture is added to the given
* {@linkplain edu.rit.draw.Drawing} object.
*
* @param tree DNA sequence tree.
* @param dwg Drawing object.
*/
public void draw
(DnaSequenceTree tree,
Drawing dwg)
{
draw (tree, new Group());
dwg.add (group);
}
/**
* Draw a picture of the given tree. The picture is added to the given
* {@linkplain edu.rit.draw.item.Group} object.
*
* @param tree DNA sequence tree.
* @param group Drawing group object.
*/
public void draw
(DnaSequenceTree tree,
Group group)
{
// Initialize.
this.tipCount = 0;
this.group = group;
// Traverse the tree, building up the drawing as it goes.
Point root = drawNode (tree, tree.root());
// Add final line to root.
group.append (new Line().to(root).hby(-H));
}
/**
* Draw a picture of the given tree string. The picture is added to the
* default {@linkplain edu.rit.draw.Drawing} object.
*
* @param tree Tree as a string in Newick Standard format.
*
* @exception SyntaxException
* Thrown if there was a syntax error in tree.
*/
public void draw
(String tree)
throws SyntaxException
{
draw (tree, Drawing.defaultDrawing());
}
/**
* Draw a picture of the given tree string. The picture is added to the
* given {@linkplain edu.rit.draw.Drawing} object.
*
* @param tree Tree as a string in Newick Standard format.
* @param dwg Drawing object.
*
* @exception SyntaxException
* Thrown if there was a syntax error in tree.
*/
public void draw
(String tree,
Drawing dwg)
throws SyntaxException
{
draw (tree, new Group());
dwg.add (group);
}
/**
* Draw a picture of the given tree string. The picture is added to the
* given {@linkplain edu.rit.draw.item.Group} object.
*
* @param tree Tree as a string in Newick Standard format.
* @param group Drawing group object.
*
* @exception SyntaxException
* Thrown if there was a syntax error in tree.
*/
public void draw
(String tree,
Group group)
throws SyntaxException
{
// Initialize.
this.treestring = tree;
this.tipCount = 0;
this.group = group;
// Set up matcher.
matcher = pattern.matcher (treestring);
nextToken();
// Parse the tree, building up the drawing as it goes.
Point root = parseNode();
if (! ";".equals (token)) syntaxError ("; expected");
nextToken();
if (token != null) syntaxError ("Extra characters");
// Add final line to root.
group.append (new Line().to(root).hby(-H));
}
// Hidden operations.
/**
* Draw a node.
*
* @param tree DNA sequence tree.
* @param index Node index.
*
* @return Point to which to attach line from parent.
*/
private Point drawNode
(DnaSequenceTree tree,
int index)
{
Point p;
// Draw a tip node.
boolean isTip = tree.child1 (index) == -1;
if (isTip)
{
p = new Point (0, tipCount * V);
++ tipCount;
}
// Draw an interior node.
else
{
Point p1 = drawNode (tree, tree.child1 (index));
Point p2 = drawNode (tree, tree.child2 (index));
double x = Math.min (p1.x(), p2.x()) - H;
double y1 = p1.y();
double y2 = p2.y();
p = new Point (x, (y1 + y2)/2);
group.append (new Line().to(p1).hto(x).vto(p2).hto(p2));
}
// Draw node name.
DnaSequence seq = tree.seq (index);
if (seq != null) drawName (seq.name(), p);
// Draw branch length.
Double brlen = tree.branchLength (index);
if (brlen != null) drawBranchLength (brlen, p, isTip);
return p;
}
/**
* Draw a node name.
*
* @param name Node name, or null if none.
* @param p Node's anchor point.
*/
private void drawName
(String name,
Point p)
{
if (name != null)
{
group.append (new Text().text(name).w(p.e(GAP)));
}
}
/**
* Draw a branch length.
*
* @param brlen Branch length.
* @param p Node's anchor point.
* @param isTip True if node is a tip node, false otherwise.
*/
private void drawBranchLength
(double brlen,
Point p,
boolean isTip)
{
if (isTip)
{
group.append
(new Text().text(format.format(brlen)).se(p.n(VGAP).w(GAP)));
}
else
{
group.append
(new Text().text(format.format(brlen)).s(p.n(VGAP).w(H/2)));
}
}
/**
* Parse a node.
*
* @return Point to which to attach line from parent.
*
* @exception SyntaxException
* Thrown if a syntax error occurred.
*/
private Point parseNode()
throws SyntaxException
{
if (! "(".equals (token)) syntaxError ("( expected");
nextToken();
Point p = parseChildList();
if (! ")".equals (token)) syntaxError (") expected");
nextToken();
parseNameLength (p, false);
return p;
}
/**
* Parse a name and/or length.
*
* @param p Point at which to anchor name and branch length.
* @param isTip True if node is a tip node, false otherwise.
*
* @exception SyntaxException
* Thrown if a syntax error occurred.
*/
private void parseNameLength
(Point p,
boolean isTip)
throws SyntaxException
{
if (isName (token))
{
drawName (token.replaceAll ("_", " "), p);
nextToken();
}
if (":".equals (token))
{
nextToken();
double brlen = 0.0;
try
{
brlen = new Double (token);
}
catch (NullPointerException exc)
{
syntaxError ("Branch length expected");
}
catch (NumberFormatException exc)
{
syntaxError ("Branch length expected");
}
nextToken();
drawBranchLength (brlen, p, isTip);
}
}
/**
* Determine if the given token is a name.
*
* @param token Token.
*
* @return True if token is a name, false otherwise.
*/
private boolean isName
(String token)
{
return
token != null &&
! "(".equals (token) &&
! ")".equals (token) &&
! ",".equals (token) &&
! ":".equals (token) &&
! ";".equals (token);
}
/**
* Parse a child list.
*
* @return Point to which to attach line from parent.
*
* @exception SyntaxException
* Thrown if a syntax error occurred.
*/
private Point parseChildList()
throws SyntaxException
{
LinkedList childList = new LinkedList();
double x = 0.0;
double ymin = 0.0;
double ymax = 0.0;
for (;;)
{
Point p = parseChild();
childList.add (p);
x = Math.min (x, p.x());
if (! ",".equals (token)) break;
nextToken();
}
x -= H;
for (Point p : childList)
{
group.append (new Line().to(p).hto(x));
}
ymin = childList.get(0).y();
ymax = childList.get(childList.size()-1).y();
group.append (new Line().to(x,ymin).to(x,ymax));
return new Point (x, (ymin+ymax)/2);
}
/**
* Parse a child.
*
* @return Point to which to attach line from parent.
*
* @exception SyntaxException
* Thrown if a syntax error occurred.
*/
private Point parseChild()
throws SyntaxException
{
if ("(".equals (token))
{
return parseNode();
}
else
{
return parseTip();
}
}
/**
* Parse a tip.
*
* @return Point to which to attach line from parent.
*
* @exception SyntaxException
* Thrown if a syntax error occurred.
*/
private Point parseTip()
throws SyntaxException
{
Point p = new Point (0, tipCount * V);
++ tipCount;
parseNameLength (p, true);
return p;
}
/**
* Get the next token being parsed.
*/
private void nextToken()
{
if (matcher.find())
{
token = treestring.substring (matcher.start(), matcher.end());
index = matcher.start();
}
else
{
token = null;
index = treestring.length();
}
}
/**
* Report a syntax error.
*
* @param msg Error message.
*
* @exception SyntaxException
* Thrown if a syntax error occurred.
*/
private void syntaxError
(String msg)
throws SyntaxException
{
throw new SyntaxException (treestring, index, msg);
}
// Helper classes.
/**
* Class TreeDrawing.SyntaxException is an exception thrown if there was a
* syntax error in a tree string.
*
* @author Alan Kaminsky
* @version 15-Jul-2008
*/
public static class SyntaxException
extends Exception
{
private String treestring;
private int index;
/**
* Construct a new syntax exception.
*/
private SyntaxException
(String treestring,
int index,
String msg)
{
super (msg);
this.treestring = treestring;
this.index = index;
}
/**
* Print a syntax error message on the given print stream.
*
* @param out Print stream.
*/
public void printSyntaxError
(PrintStream out)
{
synchronized (out)
{
out.println ("Syntax error: " + getMessage());
out.println (treestring);
for (int i = 0; i < index; ++ i) out.print (' ');
out.println ('^');
}
}
}
}