jpayne@68: package tax;
jpayne@68: 
jpayne@68: import java.util.ArrayList;
jpayne@68: import java.util.BitSet;
jpayne@68: import java.util.Locale;
jpayne@68: import java.util.PriorityQueue;
jpayne@68: 
jpayne@68: import shared.Tools;
jpayne@68: 
jpayne@68: /**
jpayne@68:  * Support class for IDTree.
jpayne@68:  * @author Brian Bushnell
jpayne@68:  * @date July 1, 2016
jpayne@68:  *
jpayne@68:  */
jpayne@68: public class IDNode implements Comparable<IDNode>{
jpayne@68: 	
jpayne@68: 	public static IDNode makeTree(IDNode[] nodes){
jpayne@68: 		
jpayne@68: 		PriorityQueue<IDNode> heap=new PriorityQueue<IDNode>(nodes.length);
jpayne@68: 		ArrayList<IDNode> list=new ArrayList<IDNode>(2*nodes.length);
jpayne@68: 		for(IDNode n : nodes){
jpayne@68: 			list.add(n);
jpayne@68: 			heap.add(n);
jpayne@68: 		}
jpayne@68: 		
jpayne@68: 		while(heap.size()>1){
jpayne@68: 			IDNode a=heap.poll();
jpayne@68: //			System.err.println("Found A node "+a);
jpayne@68: 			if(a.parent==null){
jpayne@68: 				IDNode b=nodes[a.maxPos];
jpayne@68: 				if(b.parent!=null){
jpayne@68: //					System.err.println("Skipped node "+b);
jpayne@68: 				}
jpayne@68: 				while(b.parent!=null){
jpayne@68: 					b=b.parent;
jpayne@68: //					System.err.println("to parent    "+b);
jpayne@68: 				}
jpayne@68: //				System.err.println("Found B node "+b);
jpayne@68: 				IDNode c=new IDNode(a, b, list.size());
jpayne@68: 				list.add(c);
jpayne@68: 				heap.add(c);
jpayne@68: //				System.err.println("Made C node  "+c);
jpayne@68: //				System.err.println(c.toNewick());
jpayne@68: 			}
jpayne@68: 
jpayne@68: //			System.err.println();
jpayne@68: 		}
jpayne@68: 		
jpayne@68: 		return heap.poll();
jpayne@68: 	}
jpayne@68: 
jpayne@68: 	@Override
jpayne@68: 	public int compareTo(IDNode idn) {
jpayne@68: 		if(max==idn.max){return number-idn.number;}
jpayne@68: 		return max<idn.max ? 1 : -1;
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	public IDNode(double[] array_, int number_, String name_){
jpayne@68: 		array=array_;
jpayne@68: 		number=number_;
jpayne@68: 		name=name_;
jpayne@68: 		left=right=null;
jpayne@68: 		maxPos=(array.length>0 ? Tools.maxIndex(array) : 0);
jpayne@68: 		max=(maxPos>=array.length ? 0 : array[maxPos]);
jpayne@68: 		bs=new BitSet(number+1);
jpayne@68: 		bs.set(number);
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	double[] shorter(double[] a, double[] b){
jpayne@68: 		return a.length<b.length ? a : b;
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	double[] longer(double[] a, double[] b){
jpayne@68: 		return a.length<b.length ? b : a;
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	public IDNode(IDNode a, IDNode b, int number_){
jpayne@68: 		assert(a!=b) : a+"; "+a.parent+"; "+a.left+"; "+a.right;
jpayne@68: 		assert(a.parent==null);
jpayne@68: 		assert(b.parent==null);
jpayne@68: 		assert(a.max>=b.max);
jpayne@68: 		
jpayne@68: 		number=number_;
jpayne@68: 
jpayne@68: 		double[] array1=longer(a.array, b.array);
jpayne@68: 		double[] array2=shorter(a.array, b.array);
jpayne@68: 		assert(array1!=array2) : a.array.length+", "+b.array.length+", "+a.array+", "+b.array;
jpayne@68: 
jpayne@68: 		bs=new BitSet();
jpayne@68: 		bs.or(a.bs);
jpayne@68: 		bs.or(b.bs);
jpayne@68: 		array=array1.clone();
jpayne@68: 		for(int i=0; i<array2.length; i++){
jpayne@68: 			array[i]=Tools.max(array[i], array2[i]);
jpayne@68: 		}
jpayne@68: 		array[a.maxPos]=0;
jpayne@68: 		for(int i=0; i<array.length; i++){
jpayne@68: 			if(bs.get(i)){array[i]=0;}
jpayne@68: 		}
jpayne@68: 		maxPos=Tools.maxIndex(array);
jpayne@68: 		max=array[maxPos];
jpayne@68: 		left=a;
jpayne@68: 		right=b;
jpayne@68: 		a.parent=b.parent=this;
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	public StringBuilder toNewick(){
jpayne@68: 		StringBuilder sb=new StringBuilder();
jpayne@68: 		toNewick(sb);
jpayne@68: 		return sb;
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	private void toNewick(StringBuilder sb){
jpayne@68: 		if(left!=null){
jpayne@68: 			sb.append('(');
jpayne@68: 			left.toNewick(sb);
jpayne@68: 			sb.append(',');
jpayne@68: 			right.toNewick(sb);
jpayne@68: 			sb.append(')');
jpayne@68: 		}
jpayne@68: 		if(name!=null){
jpayne@68: 			for(int i=0; i<name.length(); i++){
jpayne@68: 				char c=name.charAt(i);
jpayne@68: 				if(c=='(' || c==')' || c==':' || c==',' || c==';' || Character.isWhitespace(c)){c='_';}
jpayne@68: 				sb.append(c);
jpayne@68: 			}
jpayne@68: 		}
jpayne@68: //		sb.append(String.format(Locale.ROOT, ":%.4f", max));
jpayne@68: 		if(parent!=null){
jpayne@68: 			sb.append(':');
jpayne@68: 			
jpayne@68: 			double len;
jpayne@68: 			if(left==null){
jpayne@68: 				len=1-Tools.max(parent.left.max, parent.right.max);
jpayne@68: 			}else{
jpayne@68: 				len=Tools.max(left.max, right.max)-max;
jpayne@68: 			}
jpayne@68: 			
jpayne@68: 			sb.append(String.format(Locale.ROOT, "%.4f", len));
jpayne@68: //			assert(Tools.max(parent.left.max, parent.right.max)-parent.max<0.4) : parent+"\n"+parent.left+"\n"+parent.right+"\n";
jpayne@68: 		}
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	@Override
jpayne@68: 	public String toString(){
jpayne@68: 		return "("+number+/*" "+name+*/" "+String.format(Locale.ROOT, "%.4f", max)+" "+toString(array)+")";
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	private static String toString(double[] array){
jpayne@68: 		StringBuilder sb=new StringBuilder();
jpayne@68: 		sb.append('[');
jpayne@68: 		sb.append(' ');
jpayne@68: 		for(double d : array){
jpayne@68: 			sb.append(String.format(Locale.ROOT, "%.4f ", d));
jpayne@68: 		}
jpayne@68: 		sb.append(']');
jpayne@68: 		return sb.toString();
jpayne@68: 	}
jpayne@68: 
jpayne@68: 	public String name;
jpayne@68: 	public double[] array;
jpayne@68: 	public final int number;
jpayne@68: 	public final int maxPos;
jpayne@68: 	public final double max;
jpayne@68: 	public final BitSet bs;
jpayne@68: 	
jpayne@68: 	public IDNode parent;
jpayne@68: 	public final IDNode left;
jpayne@68: 	public final IDNode right;
jpayne@68: 
jpayne@68: }