1 package kmer; 2 3 import java.util.ArrayList; 4 import java.util.Arrays; 5 6 import fileIO.TextStreamWriter; 7 import shared.Tools; 8 import structures.ByteBuilder; 9 import structures.SuperLongList; 10 11 /** 12 * @author Brian Bushnell 13 * @date Oct 22, 2013 14 * 15 */ 16 public abstract class KmerNode extends AbstractKmerTable { 17 18 /*--------------------------------------------------------------*/ 19 /*---------------- Initialization ----------------*/ 20 /*--------------------------------------------------------------*/ 21 KmerNode(long pivot_)22 protected KmerNode(long pivot_){ 23 pivot=pivot_; 24 } 25 makeNode(long pivot_, int value_)26 public abstract KmerNode makeNode(long pivot_, int value_); makeNode(long pivot_, int[] values_, int vlen_)27 public abstract KmerNode makeNode(long pivot_, int[] values_, int vlen_); 28 29 /*--------------------------------------------------------------*/ 30 /*---------------- Public Methods ----------------*/ 31 /*--------------------------------------------------------------*/ 32 33 @Override increment(final long kmer, final int incr)34 public final int increment(final long kmer, final int incr){ 35 if(pivot<0){pivot=kmer; return set(incr);} //Allows initializing empty nodes to -1 36 if(kmer<pivot){ 37 if(left==null){left=makeNode(kmer, incr); return incr;} 38 return left.increment(kmer, incr); 39 }else if(kmer>pivot){ 40 if(right==null){right=makeNode(kmer, incr); return incr;} 41 return right.increment(kmer, incr); 42 }else{ 43 if(value()<Integer.MAX_VALUE){set(value()+incr);} 44 return value(); 45 } 46 } 47 48 @Override incrementAndReturnNumCreated(final long kmer, final int incr)49 public final int incrementAndReturnNumCreated(final long kmer, final int incr) { 50 int x=increment(kmer, incr); 51 return x==1 ? 1 : 0; 52 } 53 54 // public final int set_Test(final long kmer, final int v){ 55 // assert(TESTMODE); 56 // final int x; 57 // if(TWOD()){ 58 // int[] old=getValues(kmer, null); 59 // assert(old==null || contains(kmer, old)); 60 // x=set0(kmer, v); 61 // assert(old==null || contains(kmer, old)); 62 // assert(contains(kmer, v)); 63 // }else{ 64 // int old=getValue(kmer); 65 // assert(old==0 || old==-1 || contains(kmer, old)); 66 // x=set0(kmer, v); 67 // assert(contains(kmer, v)) : "old="+old+", v="+v+", kmer="+kmer+", get(kmer)="+getValue(kmer); 68 // assert(v==old || !contains(kmer, old)); 69 // } 70 // return x; 71 // } 72 // 73 // public final int setIfNotPresent_Test(long kmer, int v){ 74 // assert(TESTMODE); 75 // final int x; 76 // if(TWOD()){ 77 //// int[] vals=getValues(kmer, null); 78 //// assert(vals==null || contains(kmer, vals)); 79 //// x=setIfNotPresent(kmer, v); 80 //// assert(contains(kmer, vals)); 81 //// assert(contains(kmer, v)); 82 // x=0; 83 // assert(false); 84 // }else{ 85 // int old=getValue(kmer); 86 // assert(old==0 || old==-1 || contains(kmer, old)); 87 // x=setIfNotPresent0(kmer, v); 88 // assert((old<1 && contains(kmer, v)) || (old>0 && contains(kmer, old))) : kmer+", "+old+", "+v; 89 // } 90 // return x; 91 // } 92 93 94 /** Returns number of nodes added */ 95 @Override set(long kmer, int value)96 public final int set(long kmer, int value){ 97 if(verbose){System.err.println("Set0: kmer="+kmer+", v="+value+", old="+Arrays.toString(values(new int[1])));} 98 if(pivot<0){pivot=kmer; set(value); return 1;} //Allows initializing empty nodes to -1 99 if(verbose){System.err.println("A");} 100 if(kmer<pivot){ 101 if(verbose){System.err.println("B");} 102 if(left==null){left=makeNode(kmer, value); return 1;} 103 if(verbose){System.err.println("C");} 104 return left.set(kmer, value); 105 }else if(kmer>pivot){ 106 if(verbose){System.err.println("D");} 107 if(right==null){right=makeNode(kmer, value); return 1;} 108 if(verbose){System.err.println("E");} 109 return right.set(kmer, value); 110 }else{ 111 if(verbose){System.err.println("F");} 112 set(value); 113 } 114 if(verbose){System.err.println("G");} 115 return 0; 116 } 117 118 119 /** Returns number of nodes added */ 120 @Override setIfNotPresent(long kmer, int value)121 public final int setIfNotPresent(long kmer, int value){ 122 if(verbose){System.err.println("setIfNotPresent0: kmer="+kmer+", v="+value+", old="+Arrays.toString(values(new int[0])));} 123 if(pivot<0){pivot=kmer; set(value); return 1;} //Allows initializing empty nodes to -1 124 if(kmer<pivot){ 125 if(left==null){left=makeNode(kmer, value); return 1;} 126 return left.setIfNotPresent(kmer, value); 127 }else if(kmer>pivot){ 128 if(right==null){right=makeNode(kmer, value); return 1;} 129 return right.setIfNotPresent(kmer, value); 130 } 131 return 0; 132 } 133 134 @Override getValue(long kmer)135 public final int getValue(long kmer){ 136 KmerNode n=get(kmer); 137 return n==null ? -1 : n.value(); 138 } 139 140 @Override getValues(long kmer, int[] singleton)141 public final int[] getValues(long kmer, int[] singleton){ 142 KmerNode n=get(kmer); 143 return n==null ? null : n.values(singleton); 144 } 145 146 @Override contains(long kmer)147 public final boolean contains(long kmer){ 148 KmerNode node=get(kmer); 149 return node!=null; 150 } 151 152 /*--------------------------------------------------------------*/ 153 /*---------------- Nonpublic Methods ----------------*/ 154 /*--------------------------------------------------------------*/ 155 left()156 public KmerNode left(){return left;} right()157 public KmerNode right(){return right;} pivot()158 public long pivot(){return pivot;} owner()159 public int owner(){return owner;} 160 count()161 public int count(){return value();} value()162 protected abstract int value(); values(int[] singleton)163 protected abstract int[] values(int[] singleton); 164 /** Returns new value */ set(int value_)165 public abstract int set(int value_); set(int[] values_, int vlen)166 protected abstract int set(int[] values_, int vlen); 167 168 @Override get(long kmer)169 final KmerNode get(long kmer){ 170 // if(kmer<pivot){ 171 // return left==null ? null : left.get(kmer); 172 // }else if(kmer>pivot){ 173 // return right==null ? null : right.get(kmer); 174 // }else{ 175 // return this; 176 // } 177 KmerNode n=this; 178 while(n!=null && n.pivot!=kmer){ 179 n=(kmer<n.pivot ? n.left : n.right); 180 } 181 return n; 182 } 183 getNodeOrParent(long kmer)184 final KmerNode getNodeOrParent(long kmer){ 185 if(pivot==kmer || pivot<0){return this;} 186 if(kmer<pivot){return left==null ? this : left.getNodeOrParent(kmer);} 187 return right==null ? this : right.getNodeOrParent(kmer); 188 } 189 insert(KmerNode n)190 final boolean insert(KmerNode n){ 191 assert(pivot!=-1); 192 if(n.pivot<pivot){ 193 if(left==null){left=n; return true;} 194 return left.insert(n); 195 }else if(n.pivot>pivot){ 196 if(right==null){right=n; return true;} 197 return right.insert(n); 198 }else{ 199 return false; 200 } 201 } 202 traversePrefix(ArrayList<KmerNode> list)203 final void traversePrefix(ArrayList<KmerNode> list){ 204 if(left!=null){left.traversePrefix(list);} 205 list.add(this); 206 if(right!=null){right.traversePrefix(list);} 207 } 208 traverseInfix(ArrayList<KmerNode> list)209 final void traverseInfix(ArrayList<KmerNode> list){ 210 list.add(this); 211 if(left!=null){left.traverseInfix(list);} 212 if(right!=null){right.traverseInfix(list);} 213 } 214 215 /*--------------------------------------------------------------*/ 216 /*---------------- Private Methods ----------------*/ 217 /*--------------------------------------------------------------*/ 218 219 /*--------------------------------------------------------------*/ 220 /*---------------- Resizing and Rebalancing ----------------*/ 221 /*--------------------------------------------------------------*/ 222 223 @Override size()224 public final long size() { 225 if(value()<1){return 0;} 226 long size=1; 227 if(left!=null){size+=left.size();} 228 if(right!=null){size+=right.size();} 229 return size; 230 } 231 rebalance(ArrayList<KmerNode> list)232 final KmerNode rebalance(ArrayList<KmerNode> list){ 233 assert(list.isEmpty()); 234 traversePrefix(list); 235 KmerNode n=this; 236 if(list.size()>2){ 237 n=rebalance(list, 0, list.size()-1); 238 } 239 list.clear(); 240 return n; 241 } 242 rebalance(ArrayList<KmerNode> list, int a, int b)243 private static final KmerNode rebalance(ArrayList<KmerNode> list, int a, int b){ 244 final int size=b-a+1; 245 final int middle=a+size/2; 246 final KmerNode n=list.get(middle); 247 if(size<4){ 248 if(size==1){ 249 n.left=n.right=null; 250 }else if(size==2){ 251 KmerNode n1=list.get(a); 252 n.left=n1; 253 n.right=null; 254 n1.left=n1.right=null; 255 }else{ 256 assert(size==3); 257 KmerNode n1=list.get(a), n2=list.get(b); 258 n.left=n1; 259 n.right=n2; 260 n1.left=n1.right=null; 261 n2.left=n2.right=null; 262 } 263 }else{ 264 n.left=rebalance(list, a, middle-1); 265 n.right=rebalance(list, middle+1, b); 266 } 267 return n; 268 } 269 270 @Override regenerate(final int limit)271 public long regenerate(final int limit){ 272 throw new RuntimeException("Not supported."); 273 } 274 275 /*--------------------------------------------------------------*/ 276 /*---------------- Info Dumping ----------------*/ 277 /*--------------------------------------------------------------*/ 278 279 @Override dumpKmersAsText(TextStreamWriter tsw, int k, int mincount, int maxcount)280 public final boolean dumpKmersAsText(TextStreamWriter tsw, int k, int mincount, int maxcount) { 281 tsw.print(dumpKmersAsText(new StringBuilder(32), k, mincount, maxcount)); 282 return true; 283 } 284 dumpKmersAsText(StringBuilder sb, int k, int mincount, int maxcount)285 protected abstract StringBuilder dumpKmersAsText(StringBuilder sb, int k, int mincount, int maxcount); 286 dumpKmersAsText(ByteBuilder bb, int k, int mincount, int maxcount)287 protected abstract ByteBuilder dumpKmersAsText(ByteBuilder bb, int k, int mincount, int maxcount); 288 289 @Override fillHistogram(long[] ca, int max)290 public final void fillHistogram(long[] ca, int max){ 291 final int value=value(); 292 if(value<1){return;} 293 ca[Tools.min(value, max)]++; 294 if(left!=null){left.fillHistogram(ca, max);} 295 if(right!=null){right.fillHistogram(ca, max);} 296 } 297 298 @Override fillHistogram(SuperLongList sll)299 public final void fillHistogram(SuperLongList sll){ 300 final int value=value(); 301 if(value<1){return;} 302 sll.add(value); 303 if(left!=null){left.fillHistogram(sll);} 304 if(right!=null){right.fillHistogram(sll);} 305 } 306 307 @Override countGC(long[] gcCounts, int max)308 public void countGC(long[] gcCounts, int max){ 309 final int value=value(); 310 if(value<1){return;} 311 gcCounts[Tools.min(value, max)]+=gc(pivot); 312 if(left!=null){left.countGC(gcCounts, max);} 313 if(right!=null){right.countGC(gcCounts, max);} 314 } 315 TWOD()316 abstract boolean TWOD(); numValues()317 abstract int numValues(); 318 319 /*--------------------------------------------------------------*/ 320 /*---------------- Ownership ----------------*/ 321 /*--------------------------------------------------------------*/ 322 323 @Override initializeOwnership()324 public final void initializeOwnership(){ 325 owner=-1; 326 if(left!=null){left.initializeOwnership();} 327 if(right!=null){right.initializeOwnership();} 328 } 329 330 @Override clearOwnership()331 public final void clearOwnership(){initializeOwnership();} 332 333 @Override setOwner(final long kmer, final int newOwner)334 public final int setOwner(final long kmer, final int newOwner){ 335 KmerNode n=get(kmer); 336 assert(n!=null); 337 if(n.owner<=newOwner){ 338 synchronized(n){ 339 if(n.owner<newOwner){ 340 n.owner=newOwner; 341 } 342 } 343 } 344 return n.owner; 345 } 346 347 @Override clearOwner(final long kmer, final int owner)348 public final boolean clearOwner(final long kmer, final int owner){ 349 KmerNode n=get(kmer); 350 assert(n!=null); 351 synchronized(n){ 352 if(n.owner==owner){ 353 n.owner=-1; 354 return true; 355 } 356 } 357 return false; 358 } 359 360 @Override getOwner(final long kmer)361 public final int getOwner(final long kmer){ 362 KmerNode n=get(kmer); 363 assert(n!=null); 364 return n.owner; 365 } 366 367 /*--------------------------------------------------------------*/ 368 /*---------------- Invalid Methods ----------------*/ 369 /*--------------------------------------------------------------*/ 370 371 /*--------------------------------------------------------------*/ 372 /*---------------- Fields ----------------*/ 373 /*--------------------------------------------------------------*/ 374 375 long pivot; 376 int owner=-1; 377 KmerNode left, right; 378 379 } 380