Mercurial > repos > rliterman > csp2

annotate CSP2/CSP2_env/env-d9b9114564458d9d-741b3de822f2aaca6c6caa4325c4afce/opt/bbmap-39.01-1/current/tax/IDNode.java @ 68:5028fdace37b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
planemo upload commit 2e9511a184a1ca667c7be0c6321a36dc4e3d116d
author jpayne
date Tue, 18 Mar 2025 16:23:26 -0400
parents
children
rev   line source
jpayne@68 1 package tax;
jpayne@68 2
jpayne@68 3 import java.util.ArrayList;
jpayne@68 4 import java.util.BitSet;
jpayne@68 5 import java.util.Locale;
jpayne@68 6 import java.util.PriorityQueue;
jpayne@68 7
jpayne@68 8 import shared.Tools;
jpayne@68 9
jpayne@68 10 /**
jpayne@68 11 * Support class for IDTree.
jpayne@68 12 * @author Brian Bushnell
jpayne@68 13 * @date July 1, 2016
jpayne@68 14 *
jpayne@68 15 */
jpayne@68 16 public class IDNode implements Comparable<IDNode>{
jpayne@68 17
jpayne@68 18 public static IDNode makeTree(IDNode[] nodes){
jpayne@68 19
jpayne@68 20 PriorityQueue<IDNode> heap=new PriorityQueue<IDNode>(nodes.length);
jpayne@68 21 ArrayList<IDNode> list=new ArrayList<IDNode>(2*nodes.length);
jpayne@68 22 for(IDNode n : nodes){
jpayne@68 23 list.add(n);
jpayne@68 24 heap.add(n);
jpayne@68 25 }
jpayne@68 26
jpayne@68 27 while(heap.size()>1){
jpayne@68 28 IDNode a=heap.poll();
jpayne@68 29 // System.err.println("Found A node "+a);
jpayne@68 30 if(a.parent==null){
jpayne@68 31 IDNode b=nodes[a.maxPos];
jpayne@68 32 if(b.parent!=null){
jpayne@68 33 // System.err.println("Skipped node "+b);
jpayne@68 34 }
jpayne@68 35 while(b.parent!=null){
jpayne@68 36 b=b.parent;
jpayne@68 37 // System.err.println("to parent "+b);
jpayne@68 38 }
jpayne@68 39 // System.err.println("Found B node "+b);
jpayne@68 40 IDNode c=new IDNode(a, b, list.size());
jpayne@68 41 list.add(c);
jpayne@68 42 heap.add(c);
jpayne@68 43 // System.err.println("Made C node "+c);
jpayne@68 44 // System.err.println(c.toNewick());
jpayne@68 45 }
jpayne@68 46
jpayne@68 47 // System.err.println();
jpayne@68 48 }
jpayne@68 49
jpayne@68 50 return heap.poll();
jpayne@68 51 }
jpayne@68 52
jpayne@68 53 @Override
jpayne@68 54 public int compareTo(IDNode idn) {
jpayne@68 55 if(max==idn.max){return number-idn.number;}
jpayne@68 56 return max<idn.max ? 1 : -1;
jpayne@68 57 }
jpayne@68 58
jpayne@68 59 public IDNode(double[] array_, int number_, String name_){
jpayne@68 60 array=array_;
jpayne@68 61 number=number_;
jpayne@68 62 name=name_;
jpayne@68 63 left=right=null;
jpayne@68 64 maxPos=(array.length>0 ? Tools.maxIndex(array) : 0);
jpayne@68 65 max=(maxPos>=array.length ? 0 : array[maxPos]);
jpayne@68 66 bs=new BitSet(number+1);
jpayne@68 67 bs.set(number);
jpayne@68 68 }
jpayne@68 69
jpayne@68 70 double[] shorter(double[] a, double[] b){
jpayne@68 71 return a.length<b.length ? a : b;
jpayne@68 72 }
jpayne@68 73
jpayne@68 74 double[] longer(double[] a, double[] b){
jpayne@68 75 return a.length<b.length ? b : a;
jpayne@68 76 }
jpayne@68 77
jpayne@68 78 public IDNode(IDNode a, IDNode b, int number_){
jpayne@68 79 assert(a!=b) : a+"; "+a.parent+"; "+a.left+"; "+a.right;
jpayne@68 80 assert(a.parent==null);
jpayne@68 81 assert(b.parent==null);
jpayne@68 82 assert(a.max>=b.max);
jpayne@68 83
jpayne@68 84 number=number_;
jpayne@68 85
jpayne@68 86 double[] array1=longer(a.array, b.array);
jpayne@68 87 double[] array2=shorter(a.array, b.array);
jpayne@68 88 assert(array1!=array2) : a.array.length+", "+b.array.length+", "+a.array+", "+b.array;
jpayne@68 89
jpayne@68 90 bs=new BitSet();
jpayne@68 91 bs.or(a.bs);
jpayne@68 92 bs.or(b.bs);
jpayne@68 93 array=array1.clone();
jpayne@68 94 for(int i=0; i<array2.length; i++){
jpayne@68 95 array[i]=Tools.max(array[i], array2[i]);
jpayne@68 96 }
jpayne@68 97 array[a.maxPos]=0;
jpayne@68 98 for(int i=0; i<array.length; i++){
jpayne@68 99 if(bs.get(i)){array[i]=0;}
jpayne@68 100 }
jpayne@68 101 maxPos=Tools.maxIndex(array);
jpayne@68 102 max=array[maxPos];
jpayne@68 103 left=a;
jpayne@68 104 right=b;
jpayne@68 105 a.parent=b.parent=this;
jpayne@68 106 }
jpayne@68 107
jpayne@68 108 public StringBuilder toNewick(){
jpayne@68 109 StringBuilder sb=new StringBuilder();
jpayne@68 110 toNewick(sb);
jpayne@68 111 return sb;
jpayne@68 112 }
jpayne@68 113
jpayne@68 114 private void toNewick(StringBuilder sb){
jpayne@68 115 if(left!=null){
jpayne@68 116 sb.append('(');
jpayne@68 117 left.toNewick(sb);
jpayne@68 118 sb.append(',');
jpayne@68 119 right.toNewick(sb);
jpayne@68 120 sb.append(')');
jpayne@68 121 }
jpayne@68 122 if(name!=null){
jpayne@68 123 for(int i=0; i<name.length(); i++){
jpayne@68 124 char c=name.charAt(i);
jpayne@68 125 if(c=='(' || c==')' || c==':' || c==',' || c==';' || Character.isWhitespace(c)){c='_';}
jpayne@68 126 sb.append(c);
jpayne@68 127 }
jpayne@68 128 }
jpayne@68 129 // sb.append(String.format(Locale.ROOT, ":%.4f", max));
jpayne@68 130 if(parent!=null){
jpayne@68 131 sb.append(':');
jpayne@68 132
jpayne@68 133 double len;
jpayne@68 134 if(left==null){
jpayne@68 135 len=1-Tools.max(parent.left.max, parent.right.max);
jpayne@68 136 }else{
jpayne@68 137 len=Tools.max(left.max, right.max)-max;
jpayne@68 138 }
jpayne@68 139
jpayne@68 140 sb.append(String.format(Locale.ROOT, "%.4f", len));
jpayne@68 141 // assert(Tools.max(parent.left.max, parent.right.max)-parent.max<0.4) : parent+"\n"+parent.left+"\n"+parent.right+"\n";
jpayne@68 142 }
jpayne@68 143 }
jpayne@68 144
jpayne@68 145 @Override
jpayne@68 146 public String toString(){
jpayne@68 147 return "("+number+/*" "+name+*/" "+String.format(Locale.ROOT, "%.4f", max)+" "+toString(array)+")";
jpayne@68 148 }
jpayne@68 149
jpayne@68 150 private static String toString(double[] array){
jpayne@68 151 StringBuilder sb=new StringBuilder();
jpayne@68 152 sb.append('[');
jpayne@68 153 sb.append(' ');
jpayne@68 154 for(double d : array){
jpayne@68 155 sb.append(String.format(Locale.ROOT, "%.4f ", d));
jpayne@68 156 }
jpayne@68 157 sb.append(']');
jpayne@68 158 return sb.toString();
jpayne@68 159 }
jpayne@68 160
jpayne@68 161 public String name;
jpayne@68 162 public double[] array;
jpayne@68 163 public final int number;
jpayne@68 164 public final int maxPos;
jpayne@68 165 public final double max;
jpayne@68 166 public final BitSet bs;
jpayne@68 167
jpayne@68 168 public IDNode parent;
jpayne@68 169 public final IDNode left;
jpayne@68 170 public final IDNode right;
jpayne@68 171
jpayne@68 172 }