Mercurial > repos > rliterman > csp2

annotate CSP2/CSP2_env/env-d9b9114564458d9d-741b3de822f2aaca6c6caa4325c4afce/opt/bbmap-39.01-1/current/kmer/HashArray2D.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 shared.KillSwitch;
jpayne@68 7 import shared.Primes;
jpayne@68 8 import shared.Shared;
jpayne@68 9 import shared.Tools;
jpayne@68 10
jpayne@68 11 /**
jpayne@68 12 * Stores kmers in a long[] and values in an int[][], with a victim cache.
jpayne@68 13 * @author Brian Bushnell
jpayne@68 14 * @date Nov 7, 2014
jpayne@68 15 *
jpayne@68 16 */
jpayne@68 17 public final class HashArray2D extends HashArray {
jpayne@68 18
jpayne@68 19 /*--------------------------------------------------------------*/
jpayne@68 20 /*---------------- Initialization ----------------*/
jpayne@68 21 /*--------------------------------------------------------------*/
jpayne@68 22
jpayne@68 23 public HashArray2D(int[] schedule_, long coreMask_){
jpayne@68 24 super(schedule_, coreMask_, true);
jpayne@68 25 values=allocInt2D(prime+extra);
jpayne@68 26 }
jpayne@68 27
jpayne@68 28 // public HashArray2D(int initialSize, int maxSize, long mask, boolean autoResize_){
jpayne@68 29 // super(initialSize, maxSize, mask, autoResize_, true);
jpayne@68 30 // values=allocInt2D(prime+extra);
jpayne@68 31 // }
jpayne@68 32
jpayne@68 33 /*--------------------------------------------------------------*/
jpayne@68 34 /*---------------- Public Methods ----------------*/
jpayne@68 35 /*--------------------------------------------------------------*/
jpayne@68 36
jpayne@68 37 @Deprecated
jpayne@68 38 @Override
jpayne@68 39 public int increment(final long kmer, final int incr){
jpayne@68 40 throw new RuntimeException("Unsupported.");
jpayne@68 41 }
jpayne@68 42
jpayne@68 43 @Deprecated
jpayne@68 44 @Override
jpayne@68 45 public int incrementAndReturnNumCreated(final long kmer, final int incr){
jpayne@68 46 throw new RuntimeException("Unsupported.");
jpayne@68 47 }
jpayne@68 48
jpayne@68 49 /*--------------------------------------------------------------*/
jpayne@68 50 /*---------------- Nonpublic Methods ----------------*/
jpayne@68 51 /*--------------------------------------------------------------*/
jpayne@68 52
jpayne@68 53 @Override
jpayne@68 54 protected final int readCellValue(int cell) {
jpayne@68 55 int[] set=values[cell];
jpayne@68 56 return set==null ? 0 : set[0];
jpayne@68 57 }
jpayne@68 58
jpayne@68 59 @Override
jpayne@68 60 protected final int[] readCellValues(int cell, int[] singleton) {
jpayne@68 61 return values[cell];
jpayne@68 62 }
jpayne@68 63
jpayne@68 64 /** Returns number of values added */
jpayne@68 65 @Override
jpayne@68 66 protected final void insertValue(final long kmer, final int v, final int cell){
jpayne@68 67 assert(array[cell]==kmer);
jpayne@68 68 if(values[cell]==null){
jpayne@68 69 values[cell]=new int[] {v, NOT_PRESENT};
jpayne@68 70 return;
jpayne@68 71 }
jpayne@68 72 int[] set=values[cell];
jpayne@68 73 assert(set!=null);
jpayne@68 74
jpayne@68 75 for(int i=0; i<set.length; i++){
jpayne@68 76 if(set[i]==v){return;}
jpayne@68 77 else if(set[i]<0){set[i]=v;return;}
jpayne@68 78 }
jpayne@68 79 final int oldSize=set.length;
jpayne@68 80 final int newSize=(int)Tools.min(Shared.MAX_ARRAY_LEN, oldSize*2L);
jpayne@68 81 assert(newSize>set.length) : "Overflow.";
jpayne@68 82 set=KillSwitch.copyOf(set, newSize);
jpayne@68 83 set[oldSize]=v;
jpayne@68 84 Arrays.fill(set, oldSize+1, newSize, NOT_PRESENT);
jpayne@68 85 values[cell]=set;
jpayne@68 86 }
jpayne@68 87
jpayne@68 88 /** Returns number of values added */
jpayne@68 89 @Override
jpayne@68 90 protected final void insertValue(final long kmer, final int[] vals, final int cell, final int vlen){
jpayne@68 91 assert(array[cell]==kmer);
jpayne@68 92 if(values[cell]==null){
jpayne@68 93 values[cell]=vals;
jpayne@68 94 }else{
jpayne@68 95 for(int v : vals){
jpayne@68 96 if(v<0){break;}
jpayne@68 97 insertValue(kmer, v, cell);
jpayne@68 98 }
jpayne@68 99 }
jpayne@68 100 }
jpayne@68 101
jpayne@68 102 /*--------------------------------------------------------------*/
jpayne@68 103 /*---------------- Resizing and Rebalancing ----------------*/
jpayne@68 104 /*--------------------------------------------------------------*/
jpayne@68 105
jpayne@68 106 @Override
jpayne@68 107 public final boolean canRebalance() {return false;}
jpayne@68 108
jpayne@68 109 @Override
jpayne@68 110 protected synchronized void resize(){
jpayne@68 111 // assert(false);
jpayne@68 112 // System.err.println("Resizing from "+prime+"; load="+(size*1f/prime));
jpayne@68 113 if(prime>=maxPrime){
jpayne@68 114 // sizeLimit=0xFFFFFFFFFFFFL;
jpayne@68 115 // return;
jpayne@68 116 KillSwitch.memKill(new OutOfMemoryError());
jpayne@68 117 }
jpayne@68 118
jpayne@68 119 final long oldSize=size, oldVSize=victims.size;
jpayne@68 120 if(schedule!=null){
jpayne@68 121 final long oldPrime=prime;
jpayne@68 122 prime=nextScheduleSize();
jpayne@68 123 if(prime<=oldPrime){KillSwitch.memKill(new OutOfMemoryError());}
jpayne@68 124 sizeLimit=(long)((atMaxSize() ? maxLoadFactorFinal : maxLoadFactor)*prime);
jpayne@68 125 }else{//Old method
jpayne@68 126 final long totalSize=oldSize+oldVSize;
jpayne@68 127
jpayne@68 128 final long maxAllowedByLoadFactor=(long)(totalSize*minLoadMult);
jpayne@68 129 final long minAllowedByLoadFactor=(long)(totalSize*maxLoadMult);
jpayne@68 130
jpayne@68 131 // sizeLimit=Tools.min((long)(maxLoadFactor*prime), maxPrime);
jpayne@68 132
jpayne@68 133 assert(maxAllowedByLoadFactor>=minAllowedByLoadFactor);
jpayne@68 134 if(maxAllowedByLoadFactor<prime){
jpayne@68 135 sizeLimit=(long)(maxLoadFactor*prime);
jpayne@68 136 return;
jpayne@68 137 }
jpayne@68 138
jpayne@68 139 long x=10+(long)(prime*resizeMult);
jpayne@68 140 x=Tools.max(x, minAllowedByLoadFactor);
jpayne@68 141 x=Tools.min(x, maxAllowedByLoadFactor);
jpayne@68 142
jpayne@68 143 int prime2=(int)Tools.min(maxPrime, Primes.primeAtLeast(x));
jpayne@68 144
jpayne@68 145 if(prime2<=prime){
jpayne@68 146 sizeLimit=(long)(maxLoadFactor*prime);
jpayne@68 147 assert(prime2==prime) : "Resizing to smaller array? "+totalSize+", "+prime+", "+x;
jpayne@68 148 return;
jpayne@68 149 }
jpayne@68 150 // System.err.println("Resizing from "+prime+" to "+prime2+"; size="+size);
jpayne@68 151
jpayne@68 152 prime=prime2;
jpayne@68 153 sizeLimit=(long)(maxLoadFactor*prime);
jpayne@68 154 }
jpayne@68 155
jpayne@68 156 // System.err.println("Resized to "+prime+"; load="+(size*1f/prime));
jpayne@68 157 long[] oldk=array;
jpayne@68 158 int[][] oldc=values;
jpayne@68 159 KmerNode[] oldv=victims.array;
jpayne@68 160 array=allocLong1D(prime+extra);
jpayne@68 161 Arrays.fill(array, NOT_PRESENT);
jpayne@68 162 values=allocInt2D(prime+extra);
jpayne@68 163 ArrayList<KmerNode> list=new ArrayList<KmerNode>((int)(victims.size)); //Can fail if more than Integer.MAX_VALUE
jpayne@68 164 for(int i=0; i<oldv.length; i++){
jpayne@68 165 if(oldv[i]!=null){oldv[i].traverseInfix(list);}
jpayne@68 166 }
jpayne@68 167 Arrays.fill(oldv, null);
jpayne@68 168 victims.size=0;
jpayne@68 169 size=0;
jpayne@68 170
jpayne@68 171 final int[] singleton=new int[] {NOT_PRESENT};
jpayne@68 172
jpayne@68 173 for(int i=0; i<oldk.length; i++){
jpayne@68 174 if(oldk[i]>NOT_PRESENT){
jpayne@68 175 // assert(!contains(oldk[i]));
jpayne@68 176 set(oldk[i], oldc[i], -1);
jpayne@68 177 // assert(contains(oldk[i]));
jpayne@68 178 // assert(Tools.equals(getValues(oldk[i], singleton), oldc[i]));
jpayne@68 179 }
jpayne@68 180 }
jpayne@68 181
jpayne@68 182 for(KmerNode n : list){
jpayne@68 183 if(n.pivot>NOT_PRESENT){
jpayne@68 184 // assert(!contains(n.pivot));
jpayne@68 185 set(n.pivot, n.values(singleton), n.numValues());
jpayne@68 186 // assert(contains(n.pivot));
jpayne@68 187 // assert(Tools.equals(getValues(n.pivot, singleton), n.values(singleton)));
jpayne@68 188 }
jpayne@68 189 }
jpayne@68 190
jpayne@68 191 assert(oldSize+oldVSize==size+victims.size) : oldSize+", "+oldVSize+" -> "+size+", "+victims.size;
jpayne@68 192 }
jpayne@68 193
jpayne@68 194 @Deprecated
jpayne@68 195 @Override
jpayne@68 196 public void rebalance(){
jpayne@68 197 throw new RuntimeException("Unimplemented.");
jpayne@68 198 }
jpayne@68 199
jpayne@68 200 @Deprecated
jpayne@68 201 @Override
jpayne@68 202 public long regenerate(final int limit){
jpayne@68 203 assert(false) : "This is not tested or intended for use.";
jpayne@68 204 long sum=0;
jpayne@68 205 assert(owners==null) : "Clear ownership before regeneration.";
jpayne@68 206 for(int pos=0; pos<values.length; pos++){
jpayne@68 207 final long key=array[pos];
jpayne@68 208 if(key>=0){
jpayne@68 209 final int[] value=values[pos];
jpayne@68 210 values[pos]=null;
jpayne@68 211 array[pos]=NOT_PRESENT;
jpayne@68 212 size--;
jpayne@68 213 if(value!=null){
jpayne@68 214 assert(value[0]>0);
jpayne@68 215 set(key, value, -1);
jpayne@68 216 }else{
jpayne@68 217 sum++;
jpayne@68 218 }
jpayne@68 219 }
jpayne@68 220 }
jpayne@68 221
jpayne@68 222 ArrayList<KmerNode> nodes=victims.toList();
jpayne@68 223 victims.clear();
jpayne@68 224 for(KmerNode node : nodes){
jpayne@68 225 set(node.pivot, node.values(null), node.numValues());//TODO: Probably unsafe or unwise. Should test for singletons, etc.
jpayne@68 226 }
jpayne@68 227
jpayne@68 228 return sum;
jpayne@68 229 }
jpayne@68 230
jpayne@68 231 /*--------------------------------------------------------------*/
jpayne@68 232 /*---------------- Fields ----------------*/
jpayne@68 233 /*--------------------------------------------------------------*/
jpayne@68 234
jpayne@68 235 private int[][] values;
jpayne@68 236
jpayne@68 237
jpayne@68 238
jpayne@68 239 }