Mercurial > repos > rliterman > csp2

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