package com.hfg.bio.phylogeny;

import java.awt.Color;
import java.awt.Dimension;
import java.awt.Font;
import java.awt.Frame;
import java.awt.Graphics2D;
import java.awt.Point;
import java.awt.Rectangle;
import java.awt.font.FontRenderContext;
import java.awt.geom.AffineTransform;
import java.awt.geom.Point2D;
import java.awt.geom.Rectangle2D;
import java.awt.image.BufferedImage;
import java.io.InputStream;
import java.io.IOException;
import java.io.ByteArrayInputStream;
import java.io.OutputStream;
import java.util.*;
import java.util.List;

import com.hfg.css.CSS;
import com.hfg.css.CSSRule;
import com.hfg.exception.ProgrammingException;
import com.hfg.graphics.ColorUtil;
import com.hfg.graphics.TextUtil;
import com.hfg.graphics.units.GfxSize;
import com.hfg.graphics.units.GfxUnits;
import com.hfg.graphics.units.Pixels;
import com.hfg.graphics.units.Points;
import com.hfg.html.Span;
import com.hfg.html.Pre;
import com.hfg.html.HTMLTag;
import com.hfg.html.StyleTag;
import com.hfg.html.attribute.HTMLColor;
import com.hfg.image.ImageIO_Util;
import com.hfg.math.SimpleSampleStats;
import com.hfg.network.Edge;
import com.hfg.svg.*;
import com.hfg.svg.path.SvgPathEllipticalArcCmd;
import com.hfg.svg.path.SvgPathMoveToCmd;
import com.hfg.util.AttributeMgr;
import com.hfg.util.StringBuilderPlus;
import com.hfg.util.StringUtil;
import com.hfg.util.collection.CollectionUtil;
import com.hfg.util.collection.DataColumn;
import com.hfg.util.collection.DataTable;
import com.hfg.util.io.StreamUtil;
import com.hfg.xml.XMLName;
import com.hfg.xml.XMLNamespace;
import com.hfg.xml.XMLTag;

//------------------------------------------------------------------------------
/**
 Object representation of a phylogenetic tree.
 Does not work with negative distance values.
 <div>
  @see <a href='http://evolution.genetics.washington.edu/phylip/newicktree.html'>The Newick tree format</a>
 </div>
 <div>
  @author J. Alex Taylor, hairyfatguy.com
 </div>
 */
//------------------------------------------------------------------------------
// com.hfg XML/HTML Coding Library
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.
//
// This library 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
// Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License along with this library; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
//
// J. Alex Taylor, President, Founder, CEO, COO, CFO, OOPS hairyfatguy.com
// jataylor@hairyfatguy.com
//------------------------------------------------------------------------------
// http://artedi.ebc.uu.se/course/X3-2004/Phylogeny/Phylogeny-Fundamentals/Phylogeny-Basics.html
//
public class PhylogeneticTree
{
   public static enum Flag
   {
      ASSIGN_GROUPS_TO_SINGLETONS
   }

   /**
    The ID used for the branch traversal limit ('branchLimit').
    */
   public static final String BRANCH_TRAVERSAL_LIMIT_BASE_ID = "branchLimit";
   private static int branchTraversalLimitIdSrc = 1;

   private PhyloNode mRootNode;
   private TreeDisplaySettings mSettings;
   private String    mTitle;
   private DataTable mMetaDataTable;
   private AttributeMgr mAttributeMgr;

   private int       mImageTopPadding  = 50;
   private int       mImageLeftPadding = 50;
   private int       mAsciiWidth       = sDefaultAsciiWidth;

   // Cached
   private List<PhyloNode> mAllNodes;
   private List<PhyloNode> mLeafNodes;

   private static int sDefaultAsciiWidth = 75;

   private static FontRenderContext sFRC = new FontRenderContext(new AffineTransform(), true, true);

   //##########################################################################
   // CONSTRUCTORS
   //##########################################################################

   //--------------------------------------------------------------------------
   public PhylogeneticTree()
   {
   }

   //--------------------------------------------------------------------------
   public PhylogeneticTree(String inTree)
   {
      parseNewick(new ByteArrayInputStream(inTree.getBytes()));
   }

   //--------------------------------------------------------------------------
   public PhylogeneticTree(InputStream inStream)
   {
      parseNewick(inStream);
   }

   //##########################################################################
   // PUBLIC METHODS
   //##########################################################################

   //--------------------------------------------------------------------------
   public PhylogeneticTree setTitle(String inValue)
   {
      mTitle = inValue;
      return this;
   }

   //--------------------------------------------------------------------------
   public String getTitle()
   {
      return mTitle;
   }


   //--------------------------------------------------------------------------
   public static void setDefaultAsciiWidth(int inValue)
   {
      sDefaultAsciiWidth = inValue;
   }

   //--------------------------------------------------------------------------
   public PhylogeneticTree setAsciiWidth(int inValue)
   {
      mAsciiWidth = inValue;
      return this;
   }

   //--------------------------------------------------------------------------
   // 2 child nodes indicates a rooted tree. 3 indicates an unrooted tree.
   public boolean isRooted()
   {
      return (mRootNode != null
              && mRootNode.getLeafFacingEdges().size() == 2
              && null == mRootNode.getParentNode());
   }

   //--------------------------------------------------------------------------
   public PhyloNode getRootNode()
   {
      return mRootNode;
   }

   //--------------------------------------------------------------------------
   public void setRootNode(PhyloNode inValue)
   {
      mRootNode = inValue;
      inValue.makeRoot();
   }

   //--------------------------------------------------------------------------
   public List<PhyloNode> getLeafNodes()
   {
      if (null == mLeafNodes)
      {
         List<PhyloNode> leaves = new ArrayList<>();

         recursivelyRakeLeaves(leaves, mRootNode);

         mLeafNodes = leaves;
      }

      return mLeafNodes;
   }

   //--------------------------------------------------------------------------
   public List<PhyloNode> getAllNodes()
   {
      if (null == mAllNodes)
      {
         List<PhyloNode> nodes = new ArrayList<>();

         recursivelyAddNodes(nodes, mRootNode);

         mAllNodes = nodes;
      }

      return mAllNodes;
   }

   //--------------------------------------------------------------------------
   public void orderByNodeCount()
   {
      for (PhyloNode node : getAllNodes())
      {
         node.orderEdgesByLeafCount();
      }
   }

   //--------------------------------------------------------------------------
   public Float getRootedTreeDistance()
   {
      return mRootNode.getMaxDistanceToLeaf();
   }

   //--------------------------------------------------------------------------
   public void removeNode(PhyloNode inNode)
   {
      List<Edge<PhyloNode>> edges = inNode.getEdges();
      if (CollectionUtil.hasValues(edges))
      {
         for (int i = 0; i < edges.size(); i++)
         {
            Edge<PhyloNode> edge = edges.get(i);

            if (edge.getTo().equals(inNode))
            {
               PhyloNode preceedingNode = edge.getFrom();
               preceedingNode.removeEdge(edge);
               i--;

               if (! CollectionUtil.hasValues(preceedingNode.getLeafFacingEdges()))
               {
                  removeNode(preceedingNode);
               }
            }
         }
      }

      // Clear caches
      mAllNodes = null;
      mLeafNodes = null;
   }

   //--------------------------------------------------------------------------
   public PhyloNode getClosestLeaf(PhyloNode inNode)
   {
      PhyloNode closestLeaf = null;
      float closestDistance = Float.MAX_VALUE;

      for (PhyloNode leaf : getLeafNodes())
      {
         float distance = leaf.distanceTo(inNode);
         if (! leaf.equals(inNode)
             && (null == closestLeaf
                 || distance < closestDistance))
         {
            closestLeaf = leaf;
            closestDistance = distance;
         }
      }

      return closestLeaf;
   }

   //--------------------------------------------------------------------------
   public Edge getClosestLeafPair()
   {
      Edge closestLeafPair = null;

      List<PhyloNode> leaves = getLeafNodes();
      if (leaves.size() > 1)
      {
         for (int i = 0; i < leaves.size() - 1; i++)
         {
            PhyloNode leaf1 = leaves.get(i);
            for (int j = i + 1; j < leaves.size(); j++)
            {
               PhyloNode leaf2 = leaves.get(j);
               float distance = leaf1.distanceTo(leaf2);
               if (null == closestLeafPair
                   || distance < closestLeafPair.getDistance())
               {
                  closestLeafPair = new Edge<>(leaf1, leaf2, distance);
               }
            }
         }
      }

      return closestLeafPair;
   }

   //--------------------------------------------------------------------------
   public List<Edge<PhyloNode>> getMaxLeaf2LeafEdgeTrail()
   {
      List<Edge<PhyloNode>> edgeTrail = null;

      List<PhyloNode> leaves = getLeafNodes();
      if (leaves.size() > 1)
      {
         Edge<PhyloNode> maxEdge = null;
         for (int i = 0; i < leaves.size() - 1; i++)
         {
            PhyloNode leaf1 = leaves.get(i);
            for (int j = i + 1; j < leaves.size(); j++)
            {
               PhyloNode leaf2 = leaves.get(j);
               float distance = leaf1.distanceTo(leaf2);
               if (null == maxEdge
                     || maxEdge.getDistance() < distance)
               {
                  maxEdge = new Edge<>(leaf1, leaf2, distance);
               }
            }
         }

         edgeTrail = new ArrayList<>();
         Edge<PhyloNode> edge = maxEdge.getFrom().getParentEdge();
         while(edge != null)
         {
            edgeTrail.add(edge);
            edge = edge.getFrom().getParentEdge();
         }

         List<Edge<PhyloNode>> trailingTrail = new ArrayList<>();
         edge = maxEdge.getTo().getParentEdge();
         while(edge != null)
         {
            trailingTrail.add(edge);
            edge = edge.getFrom().getParentEdge();
         }

         for (int i = trailingTrail.size() - 1; i >= 0; i--)
         {
            edgeTrail.add(trailingTrail.get(i));
         }
      }

      return edgeTrail;
   }

   //--------------------------------------------------------------------------
   public void rootTreeByMidpointMethod()
   {
      List<Edge<PhyloNode>> maxEdgeTrail = getMaxLeaf2LeafEdgeTrail();
      if (maxEdgeTrail != null)
      {
         float distance = 0.0f;
         Edge<PhyloNode> prevEdge = null;
         for (Edge<PhyloNode> edge : maxEdgeTrail)
         {
            distance += edge.getDistance() != null ? edge.getDistance() : 0.0f;
            if (null == prevEdge
                  || prevEdge.getTo() != edge.getFrom())
            {
               edge.switchDirection();
            }
            prevEdge = edge;
         }

         // Find the midpoint
         distance /= 2;

         for (Edge<PhyloNode> edge : maxEdgeTrail)
         {
            if (edge.getDistance() != null
                  && edge.getDistance() > distance)
            {
               // Insert the new root in this edge.
               PhyloNode newRoot = new PhyloNode();
               newRoot.addEdge(edge.getTo(), distance);
               newRoot.addEdge(edge.getFrom(), edge.getDistance() - distance);
               // This will remove the edge from BOTH attached nodes.
               edge.getTo().removeEdge(edge);

               setRootNode(newRoot);

               break;
            }
            else if (edge.getDistance() != null
                  && edge.getDistance() == distance)
            {
               setRootNode(edge.getTo());
            }
            else
            {
               distance -= edge.getDistance();
            }
         }
      }
   }

   //--------------------------------------------------------------------------
   public List<List<PhyloNode>> groupNodes(float inBranchLengthTraversalLimit, Flag... inFlags)
   {
      Set<Flag> flags = new HashSet<>(5);
      if (inFlags != null)
      {
         for (Flag flag : inFlags)
         {
            flags.add(flag);
         }
      }

      List<List<PhyloNode>> groups = new ArrayList<>();

      for (PhyloNode leaf : getLeafNodes())
      {
         Float bestFit = null;
         List<PhyloNode> bestGroup = null;

         for (List<PhyloNode> group : groups)
         {
            for (PhyloNode node : group)
            {
               float distance = leaf.distanceTo(node);
               if (distance <= inBranchLengthTraversalLimit)
               {
                  if (null == bestFit
                      || distance < bestFit)
                  {
                     bestFit = distance;
                     bestGroup = group;
                  }
               }
            }
         }

         if (bestGroup != null)
         {
            bestGroup.add(leaf);
         }
         else
         {
            // Create a new group
            List<PhyloNode> group = new ArrayList<>();
            group.add(leaf);
            groups.add(group);
         }
      }

      // Remove singletons ?
      if (! flags.contains(Flag.ASSIGN_GROUPS_TO_SINGLETONS))
      {
         for (int i = groups.size() - 1; i >= 0; i--)
         {
            if (groups.get(i).size() == 1)
            {
               groups.remove(i);
            }
         }
      }

      return groups;
   }

   //--------------------------------------------------------------------------
   /**
    Note that this DistanceMatrix may not be equivalent to the DistanceMatrix
    originally used to construct the tree.
    @return the DistanceMatrix for the tree
    */
   public DistanceMatrix toDistanceMatrix()
   {
      DistanceMatrix matrix = new DistanceMatrix();
      for (PhyloNode node1 : getLeafNodes())
      {
         for (PhyloNode node2 : getLeafNodes())
         {
            if (node1 != node2)
            {
               matrix.setDistance(node1.getLabel(), node2.getLabel(), node1.distanceTo(node2));
            }
         }
      }

      return matrix;
   }

   //--------------------------------------------------------------------------
   /**
    Returns a Newick format representation of the tree.
    @return Newick format string representation of the tree
    */
   @Override
   public String toString()
   {
      return toNewick();
   }

   //--------------------------------------------------------------------------
   /**
    Returns a Newick format representation of the tree.
    @return Newick format string representation of the tree
    */
   public String toNewick()
   {
      StringBuilder buffer = new StringBuilder();
      if (mRootNode != null) buffer.append(mRootNode);
      buffer.append(";");

      return buffer.toString();
   }

   //--------------------------------------------------------------------------
   /**
    Constructs a phylogram in ASCII format.
    @return an ASCII representation of the tree
    */
   public String toASCII()
   {
      int numLines = getLeafNodes().size() * 2 - 1;
      List<StringBuilder> lines = new ArrayList<>(numLines);
      // Initialize the lines.
      for (int i  = 0; i < numLines; i++)
      {
         StringBuilder line = new StringBuilder();
         line.append(StringUtil.polyChar(' ', mAsciiWidth + 100));
         lines.add(line);
      }

      int leftPadding = 3;

      // Determine the scale.
      double scalingFactor = mAsciiWidth / getRootedTreeDistance();

      assignLineIndexes();


      for (PhyloNode node : getAllNodes())
      {
         Edge<PhyloNode> parentEdge = node.getParentEdge();
//         if (null == parentEdge || null == parentEdge.getFrom()) continue;

         float distance = (parentEdge != null && parentEdge.getDistance() != null ? parentEdge.getDistance() : 0.0f);
         int branchStart  = leftPadding + (int)((node.getDistanceFromRoot() - distance) * scalingFactor);
         int branchEnd    = leftPadding + (int) (node.getDistanceFromRoot() * scalingFactor);
         int branchLength = branchEnd - branchStart + 1;

         // Branch
         lines.get(node.getLineIndex()).replace(branchStart, branchEnd + 1, "+" + StringUtil.polyChar('-', branchLength - 1));

         if (node.isLeaf())
         {
            if (StringUtil.isSet(node.getLabel()))
            {
               lines.get(node.getLineIndex()).replace(branchEnd + 2, branchEnd + 2 + node.getLabel().length(), node.getLabel());
            }
         }
         else
         {
            for (int lineIndex = node.getVericalLineStartIndex() + 1; lineIndex < node.getVericalLineEndIndex(); lineIndex++)
            {
               if (branchLength > 1 || lineIndex != node.getLineIndex()) lines.get(lineIndex).replace(branchEnd, branchEnd + 1, "|");
            }
         }
      }

      StringBuilder output = new StringBuilder();
      for (StringBuilder line : lines)
      {
         output.append(StringUtil.trimTrailingWhitespace(line));
         output.append(System.getProperty("line.separator"));
      }

      return output.toString();
   }

   //--------------------------------------------------------------------------
   /**
    Constructs a phylogram in HTML format.
    @return an HTML representation of the tree
    */
   public HTMLTag toHTMLTag()
   {
      int numLines = getLeafNodes().size() * 2 - 1;
      List<StringBuilder> lines = new ArrayList<>(numLines);
      // Initialize the lines.
      for (int i  = 0; i < numLines; i++)
      {
         StringBuilder line = new StringBuilder();
         line.append(StringUtil.polyChar(' ', mAsciiWidth + 100));
         lines.add(line);
      }

      int leftPadding = 3;

      // Determine the scale.
      double scalingFactor = mAsciiWidth / getRootedTreeDistance();

      assignLineIndexes();


      for (PhyloNode node : getAllNodesOrderedByDistance())
      {
         Edge<PhyloNode> parentEdge = node.getParentEdge();
         float distance = (parentEdge != null && parentEdge.getDistance() != null ? parentEdge.getDistance() : 0.0f);
         int branchStart  = leftPadding + (int)((node.getDistanceFromRoot() - distance) * scalingFactor);
         int branchEnd    = leftPadding + (int) (node.getDistanceFromRoot() * scalingFactor);
         int branchLength = branchEnd - branchStart + 1;

         // Branch
         Span branchSpan = new Span("+");
         if (branchLength > 1) branchSpan.addContent(StringUtil.polyChar('-', branchLength - 2) + (node.isLeaf() ? "-" : "|"));
         if (distance != 0.0f)
         {
            branchSpan.setTitle(distance + "");
         }

         StringBuilder line = lines.get(node.getLineIndex());
         for (int i = branchEnd; i >= branchStart; i--)
         {
            if (line.charAt(i) != ' ' && line.charAt(i) != '|')
            {
               branchEnd--;
               branchLength--;
               branchSpan.setContent(branchSpan.getContent().substring(0, branchSpan.getContent().length() - 1));
            }
            else
            {
               break;
            }
         }
         if (branchLength > 0)
         {
            line.replace(branchStart, branchEnd + 1, branchSpan.toHTML());
         }

         int tagEnd = branchStart + branchSpan.toHTML().length();

         if (node.isLeaf())
         {
            if (StringUtil.isSet(node.getLabel()))
            {
               Span nodeSpan = new Span(node.getLabel());
               if (node.getColor() != null)
               {
                  nodeSpan.setStyle(CSS.bgColor(node.getColor()) + CSS.color(HTMLColor.getContrastingColor(node.getColor())));
               }
               line.replace(tagEnd + 2, tagEnd + 2 + node.getLabel().length(), nodeSpan.toHTML());
            }
         }
         else
         {
            for (int lineIndex = node.getVericalLineStartIndex() + 1; lineIndex < node.getVericalLineEndIndex(); lineIndex++)
            {
               if (lineIndex != node.getLineIndex()
                   && lines.get(lineIndex).charAt(branchEnd) == ' ')
               {
                  lines.get(lineIndex).replace(branchEnd, branchEnd + 1, "|");
               }
            }
         }
      }

      StringBuilder output = new StringBuilder();
      for (StringBuilder line : lines)
      {
         output.append(line);
         output.append(System.getProperty("line.separator"));
      }

      //TODO: add the scale to the bottom.

      Pre pre = new Pre();
      pre.addContentWithoutEscaping(output.toString());

      return pre;
   }

   //--------------------------------------------------------------------------
   public void setMetaDataForDisplay(DataTable inMetaData)
   {
      mMetaDataTable = inMetaData;
   }

   //--------------------------------------------------------------------------
   public SVG toSVG()
   {
      return toSVG(new TreeDisplaySettings());
   }

   //--------------------------------------------------------------------------
   public SVG toSVG(TreeDisplaySettings inDisplaySettings)
   {
      SVG svg;

      switch (inDisplaySettings.getCladogramStyle())
      {
         case Rectangular:
            svg = toRectangularCladogramSVG(inDisplaySettings);
            break;
         case Circular:
            svg = toCircularCladogramSVG(inDisplaySettings);
            break;
         default:
            throw new ProgrammingException(StringUtil.singleQuote(inDisplaySettings.getCladogramStyle()) + " is not a recognized CladogramStyle!");
      }

      return svg;
   }

   //--------------------------------------------------------------------------
   private SVG toRectangularCladogramSVG(TreeDisplaySettings inDisplaySettings)
   {
      Font font = inDisplaySettings.getFont();

      // Determine the scale.
      int treeWidth = inDisplaySettings.getTreeWidth();
      float treeDistance = getRootedTreeDistance();
      double scalingFactor = treeWidth / treeDistance;
      int leafLabelLeftPadding = inDisplaySettings.getLeafLabelLeftPadding().toInt(GfxUnits.pixels);
      int scalePaddingTop = inDisplaySettings.getScalePaddingTop().toInt(GfxUnits.pixels);

      // Determine a top-to-bottom node order
      assignLineIndexes();

      int maxLeafX = 0;

      int lineHeight = (int) TextUtil.getStringRect("A", font).getHeight();

      SVG svg = new SVG()
         .setFont(font);

      svg.addSubtag(generateScopedStyleTag());

      float maxLabelWidth =  getMaxLabelWidth(font);

      SvgGroup treeGroup = svg.addGroup().setClass("tree");
//      treeGroup.setAttribute("transform", "scale(1)");

      // Add rectangle behind the tree which can be used as a drag handle if panning and zooming
      treeGroup.addRect(new Rectangle2D.Float(mImageLeftPadding, mImageTopPadding, treeWidth + leafLabelLeftPadding + maxLabelWidth, getLeafNodes().size() * 2 * lineHeight)).setOpacity(0);


      for (PhyloNode node : getAllNodes())
      {
         Edge<PhyloNode> parentEdge = node.getParentEdge();
         float distance = (parentEdge != null && parentEdge.getDistance() != null ? parentEdge.getDistance() : 0.0f);
         int branchStart  = mImageLeftPadding + (int)((node.getDistanceFromRoot() - distance) * scalingFactor);
         int branchEnd    = mImageLeftPadding + (int) (node.getDistanceFromRoot() * scalingFactor);

         int branchY = mImageTopPadding + ((node.getLineIndex() + 1) * lineHeight) - (lineHeight / 2);

         // Branch
         SvgLine branch = treeGroup.addLine(new Point(branchStart, branchY), new Point(branchEnd, branchY));

         if (distance != 0.0f)
         {
            branch.setTitle(distance + "");
         }

         if (node.isLeaf())
         {
            SvgNode svgNode = treeGroup.addCircle().setCx(branchEnd).setCy(branchY).setR(2).setId(node.getId()).addClass("leaf");
            PhyloNode parentNode = node.getParentNode();
            if (parentNode != null)
            {
               svgNode.setAttribute("parentId", parentNode.getId());
//               svgNode.setAttribute("dist", node.getParentEdge().getDistance());
            }

            if (StringUtil.isSet(node.getLabel()))
            {
               int labelX;
               if (inDisplaySettings.getAlignLeaftNodeLabels())
               {
                  // Add a guide line to better match the label to the node
                  int guideStartX = branchEnd + leafLabelLeftPadding;
                  if (guideStartX > mImageLeftPadding + treeWidth)
                  {
                     guideStartX = mImageLeftPadding + treeWidth;
                  }

                  int guideEndX = mImageLeftPadding + treeWidth;

                  treeGroup.addLine(new Point2D.Double(guideStartX, branchY), new Point2D.Double(guideEndX, branchY)).addStyle("stroke:#" + ColorUtil.colorToHex(HTMLColor.LIGHT_GRAY));

                  labelX = guideEndX + leafLabelLeftPadding;
               }
               else
               {
                  labelX = branchEnd + leafLabelLeftPadding;
               }

               Rectangle2D textBoundBox = TextUtil.getStringRect(node.getLabel(), font);

               // Create a colored rectangle to go behind the text.
               SvgRect rect = treeGroup.addRect(new Rectangle(new Point(labelX - 2,
                                                                        branchY - (int) (textBoundBox.getHeight()/2) - 3),
                     new Dimension((int)textBoundBox.getMaxX() + 4, (int)textBoundBox.getHeight() + 4)));
//                  rect.setStyle("stroke-width: 0.5; stroke: #000000; fill:#" + ColorUtil.colorToHex(node.getColor()) + ";");
               rect.addStyle("border:none; fill:" + (node.getColor() != null ? "#" + ColorUtil.colorToHex(node.getColor()) : "none") + ";");
               rect.setId(node.getId() + "_labelBox");

               // Create the label text
               SvgText label = treeGroup.addText(node.getLabel(), font, new Point(labelX, branchY + (lineHeight / 2) - 2))
                     .setId(node.getId() + "_label");
               int labelRightX = branchEnd + leafLabelLeftPadding + (int) textBoundBox.getMaxX();
               if (labelRightX > maxLeafX)
               {
                  maxLeafX = labelRightX;
               }

               if (node.getColor() != null)
               {
                  label.setFill(new HTMLColor(node.getColor()).getContrastingColor());
               }

               if (node.getTooltip() != null)
               {
                  // For the browser to show a tooltip, add a subtag of title.
                  // Since the label sits on top of the rect, we'll title both.
                  rect.addSubtag(new XMLTag("title").setContent(node.getTooltip()));
                  label.addSubtag(new XMLTag("title").setContent(node.getTooltip()));
               }
            }
         }
         else
         {
            // Add the vertical connector line
            treeGroup.addLine(new Point(branchEnd, mImageTopPadding + ((node.getVericalLineStartIndex() + 1) * lineHeight) - (lineHeight / 2)),
                              new Point(branchEnd, mImageTopPadding + ((node.getVericalLineEndIndex() + 1) * lineHeight) - (lineHeight / 2)));
         }
      }

      if (inDisplaySettings.getShowScale()
            || inDisplaySettings.getEnableDynamicGrouping())
      {
         // Add the scale to the bottom.
         svg.addSubtag(generateSvgScale(inDisplaySettings, svg, new Point2D.Double(mImageLeftPadding, treeGroup.getBoundsBox().getHeight() + mImageTopPadding + scalePaddingTop)));
      }

      if (inDisplaySettings.getShowBranchLengthTraversalLimit())
      {
         // Make sure a BLTL value is set
         if (null == inDisplaySettings.getBranchLengthTraversalLimit())
         {
            // Default to 25%
            inDisplaySettings.setBranchLengthTraversalLimit(0.25f * getRootedTreeDistance());
         }
         else
         {
            inDisplaySettings.boundsCheckBranchLengthTraversalLimit(this);
         }

         int bltl_x = treeWidth - (int) ((inDisplaySettings.getBranchLengthTraversalLimit() * scalingFactor) / 2f);
         treeGroup.addLine(new Point(mImageLeftPadding + bltl_x, mImageTopPadding),
                           new Point(mImageLeftPadding + bltl_x, (getLeafNodes().size() + 1) * 2 * lineHeight + 5))
               .setOpacity(30)
               .addStyle("stroke:red")
               .setId(BRANCH_TRAVERSAL_LIMIT_BASE_ID);
      }

      if (mMetaDataTable != null)
      {
         SvgGroup dataGroup = treeGroup.addGroup();

         for (DataColumn col : mMetaDataTable.getDataColumns())
         {
            int leftX = maxLeafX + 40;
            int y = mImageTopPadding - (2 * lineHeight);

            Rectangle colTitleTextBoundBox = TextUtil.getStringRect(col.getTitle(), font);
            if (leftX + colTitleTextBoundBox.getMaxX() > maxLeafX)
            {
               maxLeafX = leftX + (int) colTitleTextBoundBox.getMaxX();
            }

            SvgText label = dataGroup.addText(col.getTitle(), font, new Point(leftX, y));
            // Underline the column header
            dataGroup.addLine(new Point(leftX, y + 2),
                               new Point(leftX + (int) colTitleTextBoundBox.getMaxX(), y + 2));

            for (PhyloNode leafNode : getLeafNodes())
            {
               Object dataValue = mMetaDataTable.get(leafNode.getId(), col);
               if (dataValue != null)
               {
                  String dataValueString = dataValue.toString();

                  Rectangle textBoundBox = TextUtil.getStringRect(dataValueString, font);
                  if (leftX + textBoundBox.getMaxX() > maxLeafX)
                  {
                     maxLeafX = leftX + (int) textBoundBox.getMaxX();
                  }

                  int x = leftX;
                  if (dataValue instanceof Number)
                  {
                     // Right justify
                     x += (int) (colTitleTextBoundBox.getMaxX() - textBoundBox.getMaxX()) - 4;
                  }

                  y = mImageTopPadding + (leafNode.getLineIndex() + 1) * lineHeight - 2;

                  // Display the data value
                  dataGroup.addText(dataValueString, font, new Point(x, y));
               }
            }
         }
      }

      return svg;
   }

   //--------------------------------------------------------------------------
   private StyleTag generateScopedStyleTag()
   {
      StyleTag styleTag = new StyleTag().setScoped();

      styleTag.addRule(new CSSRule(".tree path, .tree line, .scale path, .scale line { stroke:#333333; stroke-width:0.8 !important; stroke-linecap:round }"));
      styleTag.addRule(new CSSRule(".tree .guide { stroke:#" + ColorUtil.colorToHex(HTMLColor.LIGHT_GRAY) + " }"));

      return styleTag;
   }

   //--------------------------------------------------------------------------
   private SVG toCircularCladogramSVG(TreeDisplaySettings inDisplaySettings)
   {
      List<PhyloNode> leafNodes = getLeafNodes();

      double degreesPerNode = 360f/(leafNodes.size() + 1);

      int minLabelHeight = 2;
      float minRadius = calculateMinRadius(degreesPerNode, minLabelHeight);
      int scalePaddingTop = inDisplaySettings.getScalePaddingTop().toInt(GfxUnits.pixels);

      // Determine the scale.
      float radius = inDisplaySettings.getTreeWidth() / 2;
      if (radius < minRadius)
      {
         radius = minRadius;
      }

      float treeDistance = getRootedTreeDistance();
      if (treeDistance <= 0)
      {
         treeDistance = 0.0001f;
      }
      double scalingFactor = radius / treeDistance;

      // Scale down the label font if necessary
      float maxLabelSize = calculateMaxLabelSize(degreesPerNode, radius);
      Font font = inDisplaySettings.getFont();
      if (new Points(font.getSize()).to(GfxUnits.pixels) > maxLabelSize)
      {
         font = new Font(font.getName(), font.getStyle(), (int) new Pixels(maxLabelSize).to(GfxUnits.points));
      }


      float nodeCircleRadius = 0.5f;

      double labelBoxOffsetRadians = -0.0005f;
//      double labelBoxOffsetRadians = -maxLabelSize * 0.01;

      float maxLabelWidth = getMaxLabelWidth(font);

      Point2D centerPoint = new Point2D.Float(mImageLeftPadding + maxLabelWidth + radius,
                                              mImageTopPadding + maxLabelWidth + radius);


      // Assign angles to the leaves
      int leafCount = 0;
      for (PhyloNode leafNode : leafNodes)
      {
         leafCount++;
         double angle = 180 + (-degreesPerNode * leafCount);
         double angleInRadians = Math.toRadians(angle);
         leafNode.setAngle(angleInRadians);
      }


      SVG svg = new SVG()
         .setFont(font);

      svg.addSubtag(generateScopedStyleTag());

      SvgGroup treeGroup = svg.addGroup().setClass("tree");
//      treeGroup.setAttribute("transform", "scale(1)");

      // Add circle behind the tree which can be used as a drag handle if panning and zooming
      treeGroup.addCircle().setCenter(centerPoint).setR((int) (maxLabelWidth + radius)).setOpacity(0);

      for (PhyloNode node : getAllNodes())
      {
         Edge<PhyloNode> parentEdge = node.getParentEdge();
         float distance = (parentEdge != null && parentEdge.getDistance() != null ? parentEdge.getDistance() : 0.0f);

         if (node.isLeaf())
         {
            double angleInRadians = node.getAngle();
            double startX   = centerPoint.getX() + ((node.getDistanceFromRoot() - distance) * scalingFactor) * Math.sin(angleInRadians);
            double startY   = centerPoint.getY() + ((node.getDistanceFromRoot() - distance) * scalingFactor) * Math.cos(angleInRadians);
            double endX   = centerPoint.getX() + (node.getDistanceFromRoot() * scalingFactor) * Math.sin(angleInRadians);
            double endY   = centerPoint.getY() + (node.getDistanceFromRoot() * scalingFactor) * Math.cos(angleInRadians);

            treeGroup.addLine(new Point2D.Double(startX, startY), new Point2D.Double(endX, endY));
            SvgNode svgNode = treeGroup.addCircle().setCx(endX).setCy(endY).setR(nodeCircleRadius).setId(node.getId()).addClass("leaf");
            PhyloNode parentNode = node.getParentNode();
            if (parentNode != null)
            {
               svgNode.setAttribute("parentId", parentNode.getId());
//               svgNode.setAttribute("dist", node.getParentEdge().getDistance());
            }

            float labelRadius;
            if (inDisplaySettings.getAlignLeaftNodeLabels())
            {
               // Add a guide line to better match the label to the node
               float guideRadius = (float) (node.getDistanceFromRoot() * scalingFactor) + 10;
               if (guideRadius < radius)
               {
                  double guideStartX = centerPoint.getX() + guideRadius * Math.sin(angleInRadians);
                  double guideStartY = centerPoint.getY() + guideRadius * Math.cos(angleInRadians);
                  double guideEndX = centerPoint.getX() + radius * Math.sin(angleInRadians);
                  double guideEndY = centerPoint.getY() + radius * Math.cos(angleInRadians);

                  treeGroup.addLine(new Point2D.Double(guideStartX, guideStartY), new Point2D.Double(guideEndX, guideEndY)).setClass("guide");
               }

               labelRadius = radius + 2;
            }
            else
            {
               labelRadius = (float) (node.getDistanceFromRoot() * scalingFactor) + 2f;
            }

            if (StringUtil.isSet(node.getLabel()))
            {
               Rectangle2D textBoundBox = TextUtil.getStringRect(node.getLabel(), font);

               double labelX = centerPoint.getX() + labelRadius * Math.sin(angleInRadians);
               double labelY = centerPoint.getY() + labelRadius * Math.cos(angleInRadians);

               String labelTransform = "rotate(" + SVG.formatCoordinate(360 - Math.toDegrees(angleInRadians) + 90) + " " + SVG.formatCoordinate(labelX) + " " + SVG.formatCoordinate(labelY) + ")";


               // Create a colored rectangle to go behind the text.
               double labelBoxX = centerPoint.getX() + labelRadius * Math.sin(angleInRadians + labelBoxOffsetRadians);
               double labelBoxY = centerPoint.getY() + labelRadius * Math.cos(angleInRadians + labelBoxOffsetRadians);

               SvgRect rect = treeGroup.addRect(new Rectangle2D.Double(labelBoxX, labelBoxY - textBoundBox.getHeight(), textBoundBox.getWidth(), textBoundBox.getHeight()));

               // We always need to create the label box even if the label has no color
               // because we need to support dynamic grouping via javascript.
               rect.addStyle("stroke-width:" + SVG.formatCoordinate(0.15 * textBoundBox.getHeight()) + "px;"); // Add a 15% border to better frame the text
               rect.addStyle("stroke:" + (node.getColor() != null ? "#" + ColorUtil.colorToHex(node.getColor()) : "none") + ";");
               rect.addStyle("fill:" + (node.getColor() != null ? "#" + ColorUtil.colorToHex(node.getColor()) : "none") + ";");
               rect.setTransform("rotate(" + SVG.formatCoordinate(360 - Math.toDegrees(angleInRadians + labelBoxOffsetRadians) + 90) + " " + SVG.formatCoordinate(labelBoxX) + " " + SVG.formatCoordinate(labelBoxY) + ")");
               rect.setId(node.getId() + "_labelBox");

               // Create the label text
               SvgText label = treeGroup.addText(node.getLabel(), font, new Point2D.Float((float) labelX, (float) labelY))
                     .setTransform(labelTransform)
                     .setId(node.getId() + "_label");

               if (node.getColor() != null)
               {
                  label.setFill(new HTMLColor(node.getColor()).getContrastingColor());
               }

               if (node.getTooltip() != null)
               {
                  // For the browser to show a tooltip, add a subtag of title.
                  // Since the label sits on top of the rect, we'll title both.
                  rect.addSubtag(new XMLTag("title").setContent(node.getTooltip()));
                  label.addSubtag(new XMLTag("title").setContent(node.getTooltip()));
               }
            }
         }
         else
         {
            if (null == node.getAngle())
            {
               recursivelyAssignAngles(node);
            }

            List<PhyloNode> childNodes = node.getChildNodes();
            double startAngleInRadians = childNodes.get(0).getAngle();
            double endAngleInRadians = childNodes.get(childNodes.size() - 1).getAngle();
            double deltaAngleInRadians = childNodes.get(0).getAngle() - childNodes.get(childNodes.size() - 1).getAngle();

            double startX   = centerPoint.getX() + (node.getDistanceFromRoot() * scalingFactor) * Math.sin(startAngleInRadians);
            double startY   = centerPoint.getY() + (node.getDistanceFromRoot() * scalingFactor) * Math.cos(startAngleInRadians);
            double endX   = centerPoint.getX() + (node.getDistanceFromRoot() * scalingFactor) * Math.sin(endAngleInRadians);
            double endY   = centerPoint.getY() + (node.getDistanceFromRoot() * scalingFactor) * Math.cos(endAngleInRadians);

            // Like Noah, we need to build an arc
            SvgPath path = treeGroup.addPath().setFill(null).setStroke(Color.BLACK);//TODO .setStrokeWidth(1);
            path.addPathCommand(new SvgPathMoveToCmd().addPoint(new Point2D.Double(startX, startY)));
            List<Float> arcNumbers = new ArrayList<>(7);
            arcNumbers.add((float) (node.getDistanceFromRoot() * scalingFactor)); // rx
            arcNumbers.add((float) (node.getDistanceFromRoot() * scalingFactor)); // ry
            arcNumbers.add(0f); // x-rotation
            arcNumbers.add(deltaAngleInRadians > Math.PI ? 1f : 0f); // large-arc-sweep-flag
            arcNumbers.add(1f); // sweep-flag
            arcNumbers.add((float)endX);
            arcNumbers.add((float)endY);
            path.addPathCommand(new SvgPathEllipticalArcCmd().setRawNumbers(arcNumbers));



            // Now add the connector back to the previous node
            double angleInRadians = (startAngleInRadians + endAngleInRadians) / 2f;
            node.setAngle(angleInRadians);
            startX   = centerPoint.getX() + ((node.getDistanceFromRoot() - distance) * scalingFactor) * Math.sin(angleInRadians);
            startY   = centerPoint.getX() + ((node.getDistanceFromRoot() - distance) * scalingFactor) * Math.cos(angleInRadians);
            endX   = centerPoint.getX() + (node.getDistanceFromRoot() * scalingFactor) * Math.sin(angleInRadians);
            endY   = centerPoint.getX() + (node.getDistanceFromRoot() * scalingFactor) * Math.cos(angleInRadians);
            treeGroup.addLine(new Point2D.Double(startX, startY), new Point2D.Double(endX, endY));

            SvgNode svgNode = treeGroup.addCircle().setCx(endX).setCy(endY).setR(nodeCircleRadius).setId(node.getId());
            PhyloNode parentNode = node.getParentNode();
            if (parentNode != null)
            {
               svgNode.setAttribute("parentId", parentNode.getId());
//               svgNode.setAttribute("dist", node.getParentEdge().getDistance());
            }
         }
      }

      if (inDisplaySettings.getShowScale())
      {
         // Add the scale to the bottom.

         Rectangle2D treeBox = treeGroup.getBoundsBox();
         Point2D topLeft = new Point2D.Double(centerPoint.getX() - radius,
                                              treeBox.getHeight() + treeBox.getY() + mImageTopPadding + scalePaddingTop);
         svg.addSubtag(generateSvgScale(inDisplaySettings, svg, topLeft));
      }

      if (inDisplaySettings.getShowBranchLengthTraversalLimit())
      {
         // Make sure a BLTL value is set
         if (null == inDisplaySettings.getBranchLengthTraversalLimit())
         {
            // Default to 25%
            inDisplaySettings.setBranchLengthTraversalLimit(0.25f * getRootedTreeDistance());
         }
         else
         {
            inDisplaySettings.boundsCheckBranchLengthTraversalLimit(this);
         }

         // Add circle behind the tree which can be used as a drag handle if panning and zooming
         treeGroup.addCircle().setCenter(centerPoint).setR((int) ((getRootedTreeDistance() - (inDisplaySettings.getBranchLengthTraversalLimit() / 2)) * scalingFactor))
               .setOpacity(30)
               .addStyle("stroke:red")
               .setFill(null)
               .setId(BRANCH_TRAVERSAL_LIMIT_BASE_ID);
      }


      Rectangle2D contentRect = svg.getContentBoundsBox();
      if (contentRect.getMinX() < 0
            || contentRect.getMinY() < 0)
      {
         int xOffset = (int) (contentRect.getX() < 0 ? -contentRect.getX() : 0);
         int yOffset = (int) (contentRect.getY() < 0 ? -contentRect.getY() : 0);
         contentRect.setRect(contentRect.getX() + xOffset, contentRect.getY() + yOffset, contentRect.getWidth(), contentRect.getHeight());
         svg.setViewBox(contentRect);
         svg.setTransform("translate(" + xOffset + "," + yOffset + ")");
      }

      return svg;
   }

   //--------------------------------------------------------------------------
   // Calculates the maximum label size (height) given the number of labels on the circle
   // and the circle's radius.
   private float calculateMaxLabelSize(double inDegreesPerNode, float inLabelRadius)
   {
      double angle1 = inDegreesPerNode;
      double angleInRadians1 = Math.toRadians(angle1);
      double angle2 = inDegreesPerNode * 2;
      double angleInRadians2 = Math.toRadians(angle2);

      double pt1_x   = inLabelRadius * Math.sin(angleInRadians1);
      double pt1_y   = inLabelRadius * Math.cos(angleInRadians1);

      double pt2_x   = inLabelRadius * Math.sin(angleInRadians2);
      double pt2_y   = inLabelRadius * Math.cos(angleInRadians2);

      double distance = Math.sqrt((pt1_x -= pt2_x) * pt1_x + (pt1_y -= pt2_y) * pt1_y);

      return 0.8f * (float) distance;
   }

   //--------------------------------------------------------------------------
   // Calculates the minimum circle radius to achieve a minimum label size (height)
   // given the number of labels on the circle expressed as degrees per node.
   private float calculateMinRadius(double inDegreesPerNode, float inMinLabelHeight)
   {
      double angleInRadians = Math.toRadians(inDegreesPerNode);

      return (float) ((inMinLabelHeight / 2) / Math.sin(angleInRadians/2));
   }

   //--------------------------------------------------------------------------
   private float getMaxLabelWidth(Font inFont)
   {
      float maxLabelWidth = 0f;
      for (PhyloNode leafNode : getLeafNodes())
      {
         if (StringUtil.isSet(leafNode.getLabel()))
         {
            Rectangle textBoundBox = TextUtil.getStringRect(leafNode.getLabel(), inFont);
            if (textBoundBox.getWidth() > maxLabelWidth)
            {
               maxLabelWidth = (float) textBoundBox.getWidth();
            }
         }
      }

      return maxLabelWidth;
   }

   //--------------------------------------------------------------------------
   private void recursivelyAssignAngles(PhyloNode inStartingNode)
   {
      SimpleSampleStats stats = new SimpleSampleStats();

      for (PhyloNode childNode : inStartingNode.getChildNodes())
      {
         if (null == childNode.getAngle())
         {
            recursivelyAssignAngles(childNode);
         }

         stats.add(childNode.getAngle());
      }

      inStartingNode.setAngle(stats.getMean());
   }

   //--------------------------------------------------------------------------
   private void attachDistanceMatrixAsMetadata(SVG inSVG, TreeDisplaySettings inDisplaySettings)
   {
      XMLNamespace hfgNamespace = XMLNamespace.getNamespace("hfg", "http://hairyfatguy.com");
      inSVG.addXMLNamespaceDeclaration(hfgNamespace);

      // Build a distance matrix
      XMLTag distMatrixTag = new XMLTag(new XMLName("distancematrix", hfgNamespace));

      List<PhyloNode> leafNodes = getLeafNodes();
      for (int i = 0; i < leafNodes.size(); i++)
      {
         PhyloNode leaf1 = leafNodes.get(i);

         StringBuilderPlus buffer = new StringBuilderPlus().setDelimiter(" ");

         for (int j = 0; j <= i; j++)
         {
            PhyloNode leaf2 = leafNodes.get(j);

            buffer.delimitedAppend(String.format("%.5f", leaf1.distanceTo(leaf2)));
         }

         buffer.insert(0, leaf1.getId() + ":");
         buffer.appendln();

         distMatrixTag.addContent(buffer);
      }

      inSVG.getMetadata().addSubtag(distMatrixTag);


      XMLTag settingsTag = new XMLTag(new XMLName("settings", hfgNamespace));

      XMLTag settingTag = new XMLTag(new XMLName("setting", hfgNamespace));
      settingTag.setAttribute("name", "assignGroupsToSingletons");
      settingTag.setAttribute("value", inDisplaySettings.getAssignGroupsToSingletons());
      settingsTag.addSubtag(settingTag);

      if (inDisplaySettings.getBLTL_OnChangeCallback() != null)
      {
         settingTag = new XMLTag(new XMLName("setting", hfgNamespace));
         settingTag.setAttribute("name", "bltlOnChangeCallback");
         settingTag.setAttribute("value", inDisplaySettings.getBLTL_OnChangeCallback());
         settingsTag.addSubtag(settingTag);
      }

      if (inDisplaySettings.getBLTL_SelectionCompleteCallback() != null)
      {
         settingTag = new XMLTag(new XMLName("setting", hfgNamespace));
         settingTag.setAttribute("name", "bltlSelectionCompleteCallback");
         settingTag.setAttribute("value", inDisplaySettings.getBLTL_SelectionCompleteCallback());
         settingsTag.addSubtag(settingTag);
      }

      inSVG.getMetadata().addSubtag(settingsTag);
   }

   //--------------------------------------------------------------------------
   public static String generateSvgJavascript()
      throws IOException
   {
      String rsrcName = "rsrc/cladogram_bltl.js";
      InputStream rsrcStream = PhylogeneticTree.class.getResourceAsStream(rsrcName);
      if (null == rsrcStream)
      {
         throw new IOException("The javascript rsrc " + StringUtil.singleQuote(rsrcName) + " couldn't be found!");
      }

      String js = StreamUtil.inputStreamToString(rsrcStream);

      return js;
   }

   //--------------------------------------------------------------------------
   public void toJPG(TreeDisplaySettings inDisplaySettings, OutputStream inStream)
   throws IOException
   {
      ImageIO_Util.writeBufferedImageAsJpeg(getBufferedImage(inDisplaySettings), inStream);
   }

   //--------------------------------------------------------------------------
   public BufferedImage getBufferedImage(TreeDisplaySettings inDisplaySettings)
   {
      SVG svg = (SVG) toSVG(inDisplaySettings);
      // Add padding to the right
      svg.setWidth(svg.getWidth() + mImageLeftPadding);

      Frame frame = new Frame();
      frame.addNotify();
      BufferedImage bufferedImage = new BufferedImage(svg.getWidth(),
                                                      svg.getHeight(),
                                                      BufferedImage.TYPE_INT_RGB);

      Graphics2D g2 = (Graphics2D) bufferedImage.getGraphics();
      svg.draw(g2);

      return bufferedImage;
   }

   //--------------------------------------------------------------------------
   public BufferedImage getBufferedImageWithMaxWidth(TreeDisplaySettings inDisplaySettings, GfxSize inMaxWidth)
   {
      SVG svg = (SVG) toSVG(inDisplaySettings);
      // Add padding to the right
      svg.setWidth(svg.getWidth() + mImageLeftPadding);

      if (svg.getWidth() > inMaxWidth.to(GfxUnits.pixels))
      {
         float scalingFactor = inMaxWidth.to(GfxUnits.pixels) / svg.getWidth();
         svg.scale(scalingFactor);
      }

      Frame frame = new Frame();
      frame.addNotify();
      BufferedImage bufferedImage = new BufferedImage(svg.getWidth(),
                                                      svg.getHeight(),
                                                      BufferedImage.TYPE_INT_RGB);

      Graphics2D g2 = (Graphics2D) bufferedImage.getGraphics();
      svg.draw(g2);

      return bufferedImage;
   }

   //--------------------------------------------------------------------------
   public List<PhyloNode> getAllNodesOrderedByDistance()
   {
      List<PhyloNode> nodes = new ArrayList<>(getAllNodes());

      Collections.sort(nodes, new NodeDistanceComparator());

      return nodes;
   }

   // Attribute methods

   //--------------------------------------------------------------------------
   public void setAttribute(String inName, Object inValue)
   {
      getOrInitAttributeMgr().setAttribute(inName, inValue);
   }

   //--------------------------------------------------------------------------
   public boolean hasAttribute(String inName)
   {
      return mAttributeMgr != null && getOrInitAttributeMgr().hasAttribute(inName);
   }

   //--------------------------------------------------------------------------
   public Object getAttribute(String inName)
   {
      return getOrInitAttributeMgr().getAttribute(inName);
   }

   //--------------------------------------------------------------------------
   public Collection<String> getAttributeNames()
   {
      return getOrInitAttributeMgr().getAttributeNames();
   }

   //--------------------------------------------------------------------------
   public void clearAttributes()
   {
      if (mAttributeMgr != null)
      {
         mAttributeMgr.clearAttributes();
      }
   }

   //--------------------------------------------------------------------------
   public Object removeAttribute(String inName)
   {
      Object attr = null;
      if (mAttributeMgr != null)
      {
         attr  = getOrInitAttributeMgr().removeAttribute(inName);
      }

      return attr;
   }


   //##########################################################################
   // PRIVATE METHODS
   //##########################################################################


   //--------------------------------------------------------------------------
   private AttributeMgr getOrInitAttributeMgr()
   {
      if (null == mAttributeMgr)
      {
         mAttributeMgr = new AttributeMgr();
      }

      return mAttributeMgr;
   }
   
   //--------------------------------------------------------------------------
   private String getFormatString(float inValue)
   {
      String formatString = "%";

      if (inValue > 1000)
      {
         formatString += ".2e";
      }
      else if (inValue < 0.01)
      {
         formatString += ".2e";
      }
      else
      {
         formatString += ".2f";
      }

      return formatString;
   }

   //--------------------------------------------------------------------------
   private void parseNewick(InputStream inStream)
   {
      try
      {
         StringBuilder buffer = new StringBuilder();
         PhyloNode currentNode = null;
         int prevChar = 0;
         int theChar;

         while ((theChar = inStream.read()) != -1
                && theChar != ';')
         {
            if (Character.isWhitespace(theChar)) continue;

            if (prevChar == ','
                || prevChar == ')')
            {
               currentNode = currentNode.getParentNode();
            }

            if (theChar == '(')
            {
               if (null == currentNode)
               {
                  currentNode = new PhyloNode();
                  mRootNode = currentNode;
               }
               else
               {
                  PhyloNode newNode = new PhyloNode();
                  currentNode.addEdge(newNode, null);
                  currentNode = newNode;
               }
            }
            else if (prevChar == ')')
            {
//               currentNode = currentNode.getParentNode();

               // Read the label (if present).
               buffer.setLength(0);
               if (theChar != ':'
                   && theChar != ',')
               {
                  do
                  {
                     buffer.append((char) theChar);
                  }
                  while ((theChar = inStream.read()) != -1
                        && theChar != ':'
                        && theChar != ','
                        && theChar != ';');

                  if (StringUtil.isSet(buffer.toString()))
                  {
                     currentNode.setId(buffer.toString());
                     currentNode.setLabel(buffer.toString());
                  }
               }
            }
            else if (prevChar == '('
                     || prevChar == ',')
            {
               PhyloNode newNode = new PhyloNode();
               currentNode.addEdge(newNode, null);
               currentNode = newNode;

               // Read the label (if present).
               buffer.setLength(0);
               do
               {
//                  buffer.append(theChar == '_' ? ' ' : (char) theChar);
                  buffer.append((char) theChar);
               }
               while ((theChar = inStream.read()) != -1
                      && theChar != ':'
                      && theChar != ','
                      && theChar != ';');

               if (StringUtil.isSet(buffer.toString()))
               {
                  currentNode.setId(buffer.toString());
                  currentNode.setLabel(buffer.toString());
               }
            }
            else if (prevChar == ':')
            {
               // Read the distance value (branch length)
               buffer.setLength(0);
               do
               {
                  buffer.append((char) theChar);
               }
               while ((theChar = inStream.read()) != -1
                     && theChar != ')'
                     && theChar != ','
                     && theChar != ';');

               if (StringUtil.isSet(buffer.toString()))
               {
                  Edge<PhyloNode> parentEdge = currentNode.getParentEdge();
                  if (null == parentEdge)
                  {
                     Edge<PhyloNode> edge = new Edge<PhyloNode>(null, currentNode, Float.parseFloat(buffer.toString()));
                     currentNode.addEdge(edge);
                  }
                  else
                  {
                     parentEdge.setDistance(Float.parseFloat(buffer.toString()));
                  }
               }
            }

            prevChar = theChar;
         }


         // Assign node ids
         int nodeCount = 0;
         for (PhyloNode node : getAllNodes())
         {
            node.setId(++nodeCount);
         }
      }
      catch (IOException e)
      {
         throw new RuntimeException(e);
      }
   }

   //--------------------------------------------------------------------------
   private void recursivelyRakeLeaves(List<PhyloNode> inLeaves, PhyloNode inNode)
   {
      if (inNode != mRootNode
          && inNode.isLeaf())
      {
         inLeaves.add(inNode);
      }
      else
      {
         List<Edge<PhyloNode>> leafFacingEdges = inNode.getLeafFacingEdges();
         for (Edge<PhyloNode> edge : leafFacingEdges)
         {
            recursivelyRakeLeaves(inLeaves, edge.getTo());
         }
      }
   }

   //--------------------------------------------------------------------------
   private void recursivelyAddNodes(List<PhyloNode> inNodes, PhyloNode inNode)
   {
      inNodes.add(inNode);

      List<Edge<PhyloNode>> leafFacingEdges = inNode.getLeafFacingEdges();
      if (CollectionUtil.hasValues(leafFacingEdges))
      {
         for (Edge<PhyloNode> edge : leafFacingEdges)
         {
            recursivelyAddNodes(inNodes, edge.getTo());
         }
      }
   }

   //--------------------------------------------------------------------------
   private void assignLineIndexes()
   {
      int leafIndex = 0;
      List<PhyloNode> leafNodes = getLeafNodes();
      for (PhyloNode leaf : leafNodes)
      {
         leaf.setLineIndex(leafIndex++ * 2);
      }

      for (PhyloNode leaf : leafNodes)
      {
         PhyloNode node = leaf.getParentNode();
         if (node != null)
         {
            do
            {
               if (node.getLineIndex() != null) break;

               // Find the line index range of the child nodes
               List<Edge<PhyloNode>> leafFacingEdges = node.getLeafFacingEdges();
               Integer lowerBound = leafFacingEdges.get(0).getTo().getLineIndex();
               Integer upperBound = leafFacingEdges.get(leafFacingEdges.size() - 1).getTo().getLineIndex();

               // Can't assign yet if the bounds aren't set.
               if (null == lowerBound || null == upperBound) break;

               node.setLineIndex(lowerBound + (upperBound - lowerBound) / 2);
               node.setVerticalLineStartIndex(lowerBound);
               node.setVerticalLineEndIndex(upperBound);

               node = node.getParentNode();
            }
            while (node != null);
         }
      }
   }

   //--------------------------------------------------------------------------
   private SvgGroup generateSvgScale(TreeDisplaySettings inDisplaySettings, SVG inSVG, Point2D inStartPoint)
   {
      Font font = inDisplaySettings.getFont();

      int treeWidth = inDisplaySettings.getTreeWidth();
      float treeDistance = getRootedTreeDistance();
      double scalingFactor = treeWidth / treeDistance;
      int tickHeight = inDisplaySettings.getScaleTickHeight();

      SvgGroup scalegroup = new SvgGroup().setClass("scale");

      // Horizontal axis
      SvgLine axis = scalegroup.addLine(inStartPoint, new Point2D.Double(inStartPoint.getX() + treeWidth, inStartPoint.getY()));

      // Tick marks
      int numTicks = 4;
      for (int i = 0; i <= numTicks; i++)
      {
         scalegroup.addLine(new Point2D.Double(inStartPoint.getX() + (i * treeWidth/numTicks), inStartPoint.getY()),
                            new Point2D.Double(inStartPoint.getX() + (i * treeWidth/numTicks), (int) inStartPoint.getY() + tickHeight));
      }

      // Labels
      String formatString = getFormatString(treeDistance);
      for (int i = 0; i <= numTicks; i++)
      {
         String label = String.format(formatString, treeDistance - (treeDistance * i/numTicks));
         Rectangle2D textBoundBox = TextUtil.getStringRect(label, font);
         scalegroup.addText(label, font, new Point2D.Double(inStartPoint.getX() + (i * treeWidth/numTicks) - (textBoundBox.getWidth()/2),
                                                             inStartPoint.getY() + tickHeight + textBoundBox.getHeight()));
      }

      if (inDisplaySettings.getEnableDynamicGrouping())
      {
         axis.addStyle("stroke-width:4px; stroke-linecap:round");

         if (null == inDisplaySettings.getBranchLengthTraversalLimit())
         {
            inDisplaySettings.setBranchLengthTraversalLimit(0.25f * getRootedTreeDistance());
         }
         else
         {
            inDisplaySettings.boundsCheckBranchLengthTraversalLimit(this);
         }

         attachDistanceMatrixAsMetadata(inSVG, inDisplaySettings);

         // The value is divided by 2 because the distance includes out and back
         float sliderPosition = treeWidth - ((float) (inDisplaySettings.getBranchLengthTraversalLimit() * scalingFactor) / 2f);

         // Handle for adjusting the BLTL
         SvgCircle handle = scalegroup.addCircle().setCx((int) (inStartPoint.getX() + sliderPosition)).setCy((int) inStartPoint.getY()).setR(8).setId("bltl_slider_handle");
         handle.addStyle(" fill:#ffffff");
         handle.addStyle(" stroke:#000000");
         handle.addStyle(" stroke-width:4px");
         handle.addStyle(" cursor:grab");
         handle.addStyle(" cursor:-moz-grab");
         handle.addStyle(" cursor:-webkit-grab");
         handle.setAttribute("x", (int) inStartPoint.getX() + sliderPosition);
         handle.setAttribute("min_x", (int) inStartPoint.getX());
         handle.setAttribute("max_x", (int) inStartPoint.getX() + treeWidth);
         handle.setAttribute("scaling_factor", scalingFactor);
         handle.setOnMouseOver("branchTraversalLimitHandleOnMouseOver(this);");
         handle.setOnMouseOut("branchTraversalLimitHandleOnMouseOut(this);");
         handle.setOnMouseDown("branchTraversalLimitHandleDragStart(evt, this)");

         if (inDisplaySettings.getCladogramStyle().equals(CladogramStyle.Circular))
         {
            handle.setAttribute("tree_distance", getRootedTreeDistance());
            handle.setAttribute("tree_radius", inDisplaySettings.getTreeWidth() / 2);
         }
      }

      return scalegroup;
   }

   //##########################################################################
   // INNER CLASSES
   //##########################################################################

   private class NodeDistanceComparator implements Comparator<PhyloNode>
   {
      public int compare(PhyloNode node1, PhyloNode node2)
      {
         return - node1.getDistanceFromRoot().compareTo(node2.getDistanceFromRoot());
      }
   }

}