content: /*
  
   * This program 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 2 of the License, or
   * (at your option) any later version.
   *
   * This program 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.
   *
   * You should have received a copy of the GNU General Public License
   * along with this program; if not, write to the Free Software
   * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
   */
  /*
   * HierarchicalClusterer.java
   * Copyright (C) 2009 University of Waikato, Hamilton, New Zealand
  */
  
  package weka.gui.hierarchyvisualizer;
  /**
   * Shows cluster trees represented in Newick format as dendrograms.
   *
   * @author Remco Bouckaert (rrb@xm.co.nz, remco@cs.waikato.ac.nz)
   * @version $Revision: 5996 $
   */
  import java.awt.Color;
  import java.awt.Container;
  import java.awt.Graphics;
  import java.awt.Graphics2D;
  import java.awt.event.ComponentEvent;
  import java.awt.event.ComponentListener;
  import java.util.Vector;
  
  import javax.swing.JFrame;
  
  import weka.gui.visualize.PrintablePanel;
  
  public class HierarchyVisualizer extends PrintablePanel implements ComponentListener {
  	private static final long serialVersionUID = 1L;
  
  	String m_sNewick;
  	Node m_tree;
  	int m_nLeafs;
  	double m_fHeight;
  	double m_fScaleX = 10;
  	double m_fScaleY = 10;
  
  	public HierarchyVisualizer(String sNewick) {
  		try {
  			parseNewick(sNewick);
  		} catch (Exception e) {
  			e.printStackTrace();
  			System.exit(0);
  		}
  		addComponentListener(this);
  	} // c'tor
  
  	int positionLeafs(Node node, int nPosX) {
  		if (node.isLeaf()) {
  			node.m_fPosX = nPosX + 0.5;
  			nPosX++;
  			return nPosX;
  		} else {
  			for (int i = 0; i < node.m_children.length; i++) {
  				nPosX = positionLeafs(node.m_children[i], nPosX);
  			}
  		}
  		return nPosX;
  	}
  	double positionRest(Node node) {
  		if (node.isLeaf()) {
  			return node.m_fPosX;
  		} else {
  			double fPosX = 0;
  			for (int i = 0; i < node.m_children.length; i++) {
  				fPosX += positionRest(node.m_children[i]);
  			}
  			fPosX /= node.m_children.length;
  			node.m_fPosX = fPosX;
  			return fPosX;
  		}
  	}
  	double positionHeight(Node node, double fOffSet) {
  		if (node.isLeaf()) {
  			node.m_fPosY = fOffSet + node.m_fLength;
  			return node.m_fPosY;
  		} else {
  			double fPosY = fOffSet + node.m_fLength;
  			double fYMax = 0;
  			for (int i = 0; i < node.m_children.length; i++) {
  				fYMax = Math.max(fYMax, positionHeight(node.m_children[i], fPosY));
  			}
  			node.m_fPosY = fPosY;
  			return fYMax;
  		}
  	}
  
  	//Vector<String> m_sMetaDataNames;
  	/** class for nodes in building tree data structure **/
  	class Node {
  		double m_fLength = -1;
  		double m_fPosX = 0;
  		double m_fPosY = 0;
  		String m_sLabel;
  		//Vector<String> m_sMetaDataValues;
  		String m_sMetaData;
  
  
  		/** list of children of this node **/
  		Node[] m_children;
  		/** parent node in the tree, null if root **/
  		Node m_Parent = null;
  
  		Node getParent() {
  			return m_Parent;
  		}
  
  		void setParent(Node parent) {
  			m_Parent = parent;
  		}
  
  		/** check if current node is root node **/
  		boolean isRoot() {
  			return m_Parent == null;
  		}
  		boolean isLeaf() {
  			return m_children == null;
  		}
  
  		/** return nr of children **/
  		int getChildCount() {
  //			}
  			if (m_children == null) {return 0;}
  			return m_children.length;
  		}
  
  		Node getChild(int iChild) {
  			return m_children[iChild];
  		}
  
  
  		/** count number of nodes in tree, starting with current node **/
  		int getNodeCount() {
  			if (m_children == null) {
  				return 1;
  			}
  			int n = 1;
  			for (int i = 0; i < m_children.length; i++) {
  				n += m_children[i].getNodeCount();
  			}
  			return n;
  		}
  		public String toString() {
  			StringBuffer buf = new StringBuffer();
  			if (m_children != null) {
  				buf.append("(");
  				for (int i = 0; i < m_children.length-1; i++) {
  					buf.append(m_children[i].toString());
  					buf.append(',');
  				}
  				buf.append(m_children[m_children.length - 1].toString());
  				buf.append(")");
  			} else {
  				buf.append(m_sLabel);
  			}
  			if (m_sMetaData != null) {
  				buf.append('[');
  				buf.append(m_sMetaData);
  				buf.append(']');
  			}
  			buf.append(":" + m_fLength);
  			return buf.toString();
  		}
  
  		double draw(Graphics g) {
  			if (isLeaf()) {
  				int x = (int)(m_fPosX * m_fScaleX);
  				int y = (int)(m_fPosY * m_fScaleY);
  				g.drawString(m_sLabel, x, y);
  				g.drawLine((int)(m_fPosX * m_fScaleX), (int)(m_fPosY * m_fScaleY), (int)(m_fPosX * m_fScaleX), (int)((m_fPosY - m_fLength) * m_fScaleY));
  			} else {
  				double fPosX1 = Double.MAX_VALUE;
  				double fPosX2 = -Double.MAX_VALUE;
  				for (int i = 0; i < m_children.length; i++) {
  					double f = m_children[i].draw(g);
  					if (f < fPosX1) {fPosX1 = f;}
  					if (f > fPosX2) {fPosX2 = f;}
  				}
  				g.drawLine((int)(m_fPosX * m_fScaleX), (int)(m_fPosY * m_fScaleY), (int)(m_fPosX * m_fScaleX), (int)((m_fPosY - m_fLength) * m_fScaleY));
  				g.drawLine((int)(fPosX1 * m_fScaleX), (int)(m_fPosY * m_fScaleY), (int)(fPosX2 * m_fScaleX), (int)(m_fPosY* m_fScaleY));
  			}
  			return m_fPosX;
  		}
  	} // class Node
  
  	/** helper method for parsing Newick tree **/
  	int nextNode(String sStr, int i) {
  		int nBraces = 0;
  		char c = sStr.charAt(i);
  		do {
  			i++;
  			if (i < sStr.length()) {
  				c = sStr.charAt(i);
  				// skip meta data block
  				if (c == '[') {
  					while (i < sStr.length() && sStr.charAt(i)!=']') {
  						i++;
  					}
  					i++;
  					if(i < sStr.length()) {
  						c = sStr.charAt(i);
  					}
  				}
  
  				switch (c) {
  				case '(':
  					nBraces++;
  					break;
  				case ')':
  					nBraces--;
  					break;
  				default:
  					break;
  				}
  			}
  		} while (i < sStr.length()
  				&& (nBraces > 0 || (c != ','&&c != ')'&&c != '(')));
  		if (i >= sStr.length() || nBraces < 0) {
  			return -1;
  		} else if (sStr.charAt(i) == ')') {
  			i++;
  			if (sStr.charAt(i) == '[') {
  				while (i < sStr.length() && sStr.charAt(i)!=']') {
  					i++;
  				}
  				i++;
  				if (i >= sStr.length()) {
  					return -1;
  				}
  			}
  			if (sStr.charAt(i) == ':') {
  				i++;
  				c = sStr.charAt(i);
  				while (i < sStr.length() && (c=='.' || Character.isDigit(c))) {
  					i++;
  					if (i < sStr.length()) {
  						c = sStr.charAt(i);
  					}
  				}
  			}
  		}
  		return i;
  	}
  
  	/**
  	 * convert string containing Newick tree into tree datastructure but only in
  	 * the limited format as contained in m_sTrees
  	 *
  	 * @param sStr
  	 * @return tree consisting of a Node
  	 */
  	void parseNewick(String sNewick) throws Exception {
  		m_sNewick = sNewick;
  		int i = m_sNewick.indexOf('(');
  		if (i > 0) {
  			m_sNewick = m_sNewick.substring(i);
  		}
  		System.err.println(m_sNewick);
  		m_tree = parseNewick2(m_sNewick);
  		System.err.println(m_tree.toString());
  		m_nLeafs = positionLeafs(m_tree, 0);
  		positionRest(m_tree);
  		m_fHeight = positionHeight(m_tree, 0);
  	}
  
  	Node parseNewick2(String sStr) throws Exception {
  		// System.out.println(sStr);
  		if (sStr == null || sStr.length() == 0) {
  			return null;
  		}
  		Node node = new Node();
  		if (sStr.startsWith("(")) {
  			int i1 = nextNode(sStr, 0);
  			int i2 = nextNode(sStr, i1);
  			node.m_children = new Node[2];
  			node.m_children[0] = parseNewick2(sStr.substring(1, i1));
  			node.m_children[0].m_Parent = node;
  			String sStr2 = sStr.substring(i1+1, (i2>0?i2:sStr.length()));
  			node.m_children[1] = parseNewick2(sStr2);
  			node.m_children[1].m_Parent = node;
  			if (sStr.lastIndexOf('[') > sStr.lastIndexOf(')')) {
  				sStr = sStr.substring(sStr.lastIndexOf('['));
  				i2 = sStr.indexOf(']');
  				if (i2 < 0) {
  					throw new Exception("unbalanced square bracket found:" + sStr);
  				}
  				sStr2 = sStr.substring(1, i2);
  				node.m_sMetaData = sStr2;
  			}
  			if (sStr.lastIndexOf(':') > sStr.lastIndexOf(')')) {
  				sStr = sStr.substring(sStr.lastIndexOf(':'));
  				sStr = sStr.replaceAll("[,\\):]", "");
  				node.m_fLength = new Double(sStr);
  			} else {
  				node.m_fLength = 1;
  			}
  		} else {
  			// it is a leaf
  			if (sStr.contains("[")) {
  				// grab metadata
  				int i1 = sStr.indexOf('[');
  				int i2 = sStr.indexOf(']');
  				if (i2 < 0) {
  					throw new Exception("unbalanced square bracket found:" + sStr);
  				}
  				String sStr2 = sStr.substring(i1+1, i2);
  				sStr = sStr.substring(0, i1) +sStr.substring(i2+1);
  				node.m_sMetaData = sStr2;
  			}
  			if (sStr.indexOf(')') >= 0) {
  				sStr = sStr.substring(0, sStr.indexOf(')'));
  			}
  			sStr = sStr.replaceFirst("[,\\)]", "");
  			// System.out.println("parsing <<"+sStr+">>");
  			if (sStr.length() > 0) {
  				if (sStr.indexOf(':') >= 0) {
  					int iColon = sStr.indexOf(':');
  					node.m_sLabel = sStr.substring(0, iColon);
  					if (sStr.indexOf(':', iColon+1) >= 0) {
  						int iColon2 = sStr.indexOf(':', iColon+1);
  						node.m_fLength = new Double(sStr.substring(iColon+1, iColon2));
  						m_fTmpLength = new Double(sStr.substring(iColon2+1));
  					} else {
  						node.m_fLength = new Double(sStr.substring(iColon+1));
  					}
  				} else {
  					node.m_sLabel = sStr;
  					node.m_fLength = 1;
  				}
  			} else {
  				return null;
  			}
  		}
  		return node;
  	}
  	double m_fTmpLength;
  
  	/**
  	 * Fits the tree to the current screen size. Call this after window has been
  	 * created to get the entire tree to be in view upon launch.
  	 */
  	public void fitToScreen() {
  		m_fScaleX = 10;
  		int nW = getWidth();
  		if (m_nLeafs > 0) {
  			m_fScaleX = nW / m_nLeafs;
  		}
  		m_fScaleY = 10;
  		int nH = getHeight();
  		if (m_fHeight > 0) {
  			m_fScaleY = (nH - 10) / m_fHeight;
  		}
  		repaint();
  	}
  
  	/**
  	 * Updates the screen contents.
  	 *
  	 * @param g
  	 *            the drawing surface.
  	 */
  	public void paintComponent(Graphics g) {
  		Color oldBackground = ((Graphics2D) g).getBackground();
  		// if (m_BackgroundColor != null)
  		((Graphics2D) g).setBackground(Color.WHITE);
  		g.clearRect(0, 0, getSize().width, getSize().height);
  		((Graphics2D) g).setBackground(oldBackground);
  		g.setClip(3, 7, getWidth() - 6, getHeight() - 10);
  		m_tree.draw(g);
  		g.setClip(0, 0, getWidth(), getHeight());
  	}
  
  
  	public void componentHidden(ComponentEvent e) {}
  
  	public void componentMoved(ComponentEvent e) {}
  
  	public void componentResized(ComponentEvent e) {
  		fitToScreen();
  	}
  
  	public void componentShown(ComponentEvent e) {}
  
  	/**
  	 * Main method for testing this class.
  	 */
  	public static void main(String[] args) {
  	      //HierarchyVisualizer a = new HierarchyVisualizer("((((human:2.0,(chimp:1.0,bonobo:1.0):1.0):1.0,gorilla:3.0):1.0,siamang:4.0):1.0,orangutan:5.0)");
  	      //HierarchyVisualizer a = new HierarchyVisualizer("(((human:2.0,(chimp:1.0,bonobo:1.0):1.0):1.0,gorilla:3.0):1.0,siamang:4.0)");
  	      HierarchyVisualizer a = new HierarchyVisualizer(" (((5[theta=0.121335,lxg=0.122437]:0.00742795,3[theta=0.0972485,lxg=0.152762]:0.00742795)[theta=0.490359,lxg=0.0746703]:0.0183076,((2[theta=0.0866056,lxg=0.2295]:0.00993801,4[theta=0.135512,lxg=0.146674]:0.00993801)[theta=0.897783,lxg=0.0200762]:0.00901206,1[theta=0.200265,lxg=0.18925]:0.0189501)[theta=0.0946195,lxg=0.143427]:0.00678551)[theta=0.185562,lxg=0.139681]:0.0129598,(7[theta=0.176022,lxg=0.364039]:0.0320395,((0[theta=0.224286,lxg=0.156485]:0.0175487,8[theta=0.223313,lxg=0.157166]:0.0175487)[theta=0.631287,lxg=0.024042]:0.00758871,6[theta=0.337871,lxg=0.148799]:0.0251374)[theta=0.33847,lxg=0.040784]:0.00690208)[theta=0.209238,lxg=0.0636202]:0.00665587)[theta=0.560453,lxg=-0.138086]:0.01");
  		  //HierarchyVisualizer a = new HierarchyVisualizer(" ((5[theta=0.121335,lxg=0.122437]:0.00742795,3[theta=0.0972485,lxg=0.152762]:0.00742795)[theta=0.490359,lxg=0.0746703]:0.0183076,2[theta=0.0866056,lxg=0.2295]:0.00993801)[theta=0.897783,lxg=0.0200762]:0.00901206");
  	      a.setSize(800 ,600);
  	      JFrame f;
  	      f = new JFrame();
  	      Container contentPane = f.getContentPane();
  	      contentPane.add(a);
  	      f.setDefaultCloseOperation(JFrame.DISPOSE_ON_CLOSE);
  	      f.setSize(800,600);
  	      f.setVisible(true);
  	      a.fitToScreen();
  	  }
  
  } // class HierarchyVisualizer
  