Mercurial > repos > rliterman > csp2

annotate CSP2/CSP2_env/env-d9b9114564458d9d-741b3de822f2aaca6c6caa4325c4afce/opt/bbmap-39.01-1/current/bbmin/LongHashSet.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 bbmin;
jpayne@68 2
jpayne@68 3 import java.util.Arrays;
jpayne@68 4 import java.util.Random;
jpayne@68 5
jpayne@68 6 /**
jpayne@68 7 * @author Brian Bushnell
jpayne@68 8 * @date July 6, 2016
jpayne@68 9 *
jpayne@68 10 */
jpayne@68 11 public final class LongHashSet{
jpayne@68 12
jpayne@68 13 /*--------------------------------------------------------------*/
jpayne@68 14 /*---------------- Initialization ----------------*/
jpayne@68 15 /*--------------------------------------------------------------*/
jpayne@68 16
jpayne@68 17 public LongHashSet(){
jpayne@68 18 this(256);
jpayne@68 19 }
jpayne@68 20
jpayne@68 21 public LongHashSet(int initialSize){
jpayne@68 22 this(initialSize, 0.7f);
jpayne@68 23 }
jpayne@68 24
jpayne@68 25 public LongHashSet(int initialSize, float loadFactor_){
jpayne@68 26 invalid=randy.nextLong()|MINMASK;
jpayne@68 27 assert(invalid<0);
jpayne@68 28 assert(initialSize>0) : "Attempting to initialize a "+getClass().getSimpleName()+" of size<1.";
jpayne@68 29 assert(loadFactor_>0 && loadFactor_<1) : "Attempting to initialize a "+getClass().getSimpleName()+" with invalid load factor: "+loadFactor_;
jpayne@68 30 loadFactor=mid(0.25f, loadFactor_, 0.90f);
jpayne@68 31 resize(initialSize);
jpayne@68 32 }
jpayne@68 33
jpayne@68 34 /*--------------------------------------------------------------*/
jpayne@68 35 /*---------------- Public Methods ----------------*/
jpayne@68 36 /*--------------------------------------------------------------*/
jpayne@68 37
jpayne@68 38 public void clear(){
jpayne@68 39 if(size<1){return;}
jpayne@68 40 Arrays.fill(array, invalid);
jpayne@68 41 size=0;
jpayne@68 42 }
jpayne@68 43
jpayne@68 44 public boolean contains(long value){
jpayne@68 45 return value==invalid ? false : findCell(value)>=0;
jpayne@68 46 }
jpayne@68 47
jpayne@68 48 /**
jpayne@68 49 * Add this value to the set.
jpayne@68 50 * @param value
jpayne@68 51 * @return true if the value was added, false if it was already contained.
jpayne@68 52 */
jpayne@68 53 public boolean add(long value){
jpayne@68 54 if(value==invalid){resetInvalid();}
jpayne@68 55 int cell=findCellOrEmpty(value);
jpayne@68 56 if(array[cell]==invalid){
jpayne@68 57 array[cell]=value;
jpayne@68 58 size++;
jpayne@68 59 if(size>sizeLimit){resize();}
jpayne@68 60 return true;
jpayne@68 61 }
jpayne@68 62 assert(array[cell]==value);
jpayne@68 63 return false;
jpayne@68 64 }
jpayne@68 65
jpayne@68 66 /**
jpayne@68 67 * Remove this value from the set.
jpayne@68 68 * @param value
jpayne@68 69 * @return true if the value was removed, false if it was not present.
jpayne@68 70 */
jpayne@68 71 public boolean remove(long value){
jpayne@68 72 if(value==invalid){return false;}
jpayne@68 73 final int cell=findCell(value);
jpayne@68 74 if(cell<0){return false;}
jpayne@68 75 assert(array[cell]==value);
jpayne@68 76 array[cell]=invalid;
jpayne@68 77 size--;
jpayne@68 78
jpayne@68 79 rehashFrom(cell);
jpayne@68 80 return true;
jpayne@68 81 }
jpayne@68 82
jpayne@68 83 public int size(){return size;}
jpayne@68 84
jpayne@68 85 public boolean isEmpty(){return size==0;}
jpayne@68 86
jpayne@68 87 /*--------------------------------------------------------------*/
jpayne@68 88 /*---------------- String Methods ----------------*/
jpayne@68 89 /*--------------------------------------------------------------*/
jpayne@68 90
jpayne@68 91 @Override
jpayne@68 92 public String toString(){
jpayne@68 93 return toStringListView();
jpayne@68 94 }
jpayne@68 95
jpayne@68 96 public String toStringSetView(){
jpayne@68 97 StringBuilder sb=new StringBuilder();
jpayne@68 98 sb.append('[');
jpayne@68 99 String comma="";
jpayne@68 100 for(int i=0; i<array.length; i++){
jpayne@68 101 if(array[i]!=invalid){
jpayne@68 102 sb.append(comma+"("+i+", "+array[i]+")");
jpayne@68 103 comma=", ";
jpayne@68 104 }
jpayne@68 105 }
jpayne@68 106 sb.append(']');
jpayne@68 107 return sb.toString();
jpayne@68 108 }
jpayne@68 109
jpayne@68 110 public String toStringListView(){
jpayne@68 111 StringBuilder sb=new StringBuilder();
jpayne@68 112 sb.append('[');
jpayne@68 113 String comma="";
jpayne@68 114 for(int i=0; i<array.length; i++){
jpayne@68 115 if(array[i]!=invalid){
jpayne@68 116 sb.append(comma+array[i]);
jpayne@68 117 comma=", ";
jpayne@68 118 }
jpayne@68 119 }
jpayne@68 120 sb.append(']');
jpayne@68 121 return sb.toString();
jpayne@68 122 }
jpayne@68 123
jpayne@68 124 public long[] toArray(){
jpayne@68 125 long[] x=new long[array.length];
jpayne@68 126 int i=0;
jpayne@68 127 for(long v : array){
jpayne@68 128 x[i]=v;
jpayne@68 129 i++;
jpayne@68 130 }
jpayne@68 131 return x;
jpayne@68 132 }
jpayne@68 133
jpayne@68 134 /*--------------------------------------------------------------*/
jpayne@68 135 /*---------------- Private Methods ----------------*/
jpayne@68 136 /*--------------------------------------------------------------*/
jpayne@68 137
jpayne@68 138 public boolean verify(){
jpayne@68 139 int numValues=0;
jpayne@68 140 int numFound=0;
jpayne@68 141 for(int i=0; i<array.length; i++){
jpayne@68 142 final long value=array[i];
jpayne@68 143 if(value!=invalid){
jpayne@68 144 numValues++;
jpayne@68 145 final int cell=findCell(value);
jpayne@68 146 if(i==cell){
jpayne@68 147 numFound++;
jpayne@68 148 }else{
jpayne@68 149 return false;
jpayne@68 150 }
jpayne@68 151 }
jpayne@68 152 }
jpayne@68 153 return numValues==numFound && numValues==size;
jpayne@68 154 }
jpayne@68 155
jpayne@68 156 private void rehashFrom(int initial){
jpayne@68 157 if(size<1){return;}
jpayne@68 158 final int limit=array.length;
jpayne@68 159 for(int cell=initial+1; cell<limit; cell++){
jpayne@68 160 final long x=array[cell];
jpayne@68 161 if(x==invalid){return;}
jpayne@68 162 rehashCell(cell);
jpayne@68 163 }
jpayne@68 164 for(int cell=0; cell<initial; cell++){
jpayne@68 165 final long x=array[cell];
jpayne@68 166 if(x==invalid){return;}
jpayne@68 167 rehashCell(cell);
jpayne@68 168 }
jpayne@68 169 }
jpayne@68 170
jpayne@68 171 private boolean rehashCell(final int cell){
jpayne@68 172 final long value=array[cell];
jpayne@68 173 assert(value!=invalid);
jpayne@68 174 if(value==invalid){resetInvalid();}
jpayne@68 175 final int dest=findCellOrEmpty(value);
jpayne@68 176 if(cell==dest){return false;}
jpayne@68 177 assert(array[dest]==invalid);
jpayne@68 178 array[cell]=invalid;
jpayne@68 179 array[dest]=value;
jpayne@68 180 return true;
jpayne@68 181 }
jpayne@68 182
jpayne@68 183 private void resetInvalid(){
jpayne@68 184 final long old=invalid;
jpayne@68 185 long x=invalid;
jpayne@68 186 while(x==old || contains(x)){x=randy.nextLong()|MINMASK;}
jpayne@68 187 assert(x<0);
jpayne@68 188 invalid=x;
jpayne@68 189 for(int i=0; i<array.length; i++){
jpayne@68 190 if(array[i]==old){array[i]=invalid;}
jpayne@68 191 }
jpayne@68 192 }
jpayne@68 193
jpayne@68 194 private int findCell(final long value){
jpayne@68 195 if(value==invalid){return -1;}
jpayne@68 196
jpayne@68 197 final int limit=array.length, initial=(int)((value&MASK)%modulus);
jpayne@68 198 for(int cell=initial; cell<limit; cell++){
jpayne@68 199 final long x=array[cell];
jpayne@68 200 if(x==value){return cell;}
jpayne@68 201 if(x==invalid){return -1;}
jpayne@68 202 }
jpayne@68 203 for(int cell=0; cell<initial; cell++){
jpayne@68 204 final long x=array[cell];
jpayne@68 205 if(x==value){return cell;}
jpayne@68 206 if(x==invalid){return -1;}
jpayne@68 207 }
jpayne@68 208 return -1;
jpayne@68 209 }
jpayne@68 210
jpayne@68 211 private int findCellOrEmpty(final long value){
jpayne@68 212 assert(value!=invalid) : "Collision - this should have been intercepted.";
jpayne@68 213
jpayne@68 214 final int limit=array.length, initial=(int)((value&MASK)%modulus);
jpayne@68 215 for(int cell=initial; cell<limit; cell++){
jpayne@68 216 final long x=array[cell];
jpayne@68 217 if(x==value || x==invalid){return cell;}
jpayne@68 218 }
jpayne@68 219 for(int cell=0; cell<initial; cell++){
jpayne@68 220 final long x=array[cell];
jpayne@68 221 if(x==value || x==invalid){return cell;}
jpayne@68 222 }
jpayne@68 223 throw new RuntimeException("No empty cells - size="+size+", limit="+limit);
jpayne@68 224 }
jpayne@68 225
jpayne@68 226 public final void resizeDestructive(int newSize){
jpayne@68 227 size=0;
jpayne@68 228 sizeLimit=0;
jpayne@68 229 array=null;
jpayne@68 230 resize(newSize);
jpayne@68 231 }
jpayne@68 232
jpayne@68 233 private final void resize(){
jpayne@68 234 assert(size>=sizeLimit);
jpayne@68 235 resize(array.length*2L+1);
jpayne@68 236 }
jpayne@68 237
jpayne@68 238 private final void resize(final long size2){
jpayne@68 239 assert(size2>size) : size+", "+size2;
jpayne@68 240
jpayne@68 241 //This is supposed to be a prime but the primes code is ripped out in this version.
jpayne@68 242 //Any odd number is fine in most cases.
jpayne@68 243 long newPrime=size2|1;
jpayne@68 244 if(newPrime+extra>Integer.MAX_VALUE){
jpayne@68 245 newPrime=(Integer.MAX_VALUE-extra-2)|1;
jpayne@68 246 }
jpayne@68 247 assert(newPrime>modulus) : "Overflow: "+size+", "+size2+", "+modulus+", "+newPrime;
jpayne@68 248 modulus=(int)newPrime;
jpayne@68 249
jpayne@68 250 final int size3=(int)(newPrime+extra);
jpayne@68 251 sizeLimit=(int)(modulus*loadFactor);
jpayne@68 252 final long[] old=array;
jpayne@68 253 array=new long[size3];
jpayne@68 254 Arrays.fill(array, invalid);
jpayne@68 255
jpayne@68 256 // System.err.println("Resizing "+(old==null ? "null" : ""+old.length)+" to "+size3);
jpayne@68 257
jpayne@68 258 if(size<1){return;}
jpayne@68 259
jpayne@68 260 size=0;
jpayne@68 261 for(long value : old){
jpayne@68 262 if(value!=invalid){
jpayne@68 263 add(value);
jpayne@68 264 }
jpayne@68 265 }
jpayne@68 266 }
jpayne@68 267
jpayne@68 268 /*--------------------------------------------------------------*/
jpayne@68 269 /*---------------- Stuff From BBTools ----------------*/
jpayne@68 270 /*--------------------------------------------------------------*/
jpayne@68 271
jpayne@68 272 public static final float mid(float x, float y, float z){
jpayne@68 273 return x<y ? (x<z ? min(y, z) : x) : (y<z ? min(x, z) : y);
jpayne@68 274 }
jpayne@68 275 public static final float min(float x, float y){return x<y ? x : y;}
jpayne@68 276 public static final float max(float x, float y){return x>y ? x : y;}
jpayne@68 277
jpayne@68 278 /** Number of values that can be held without resizing */
jpayne@68 279 public int capacity(){
jpayne@68 280 return sizeLimit;
jpayne@68 281 }
jpayne@68 282
jpayne@68 283 /*--------------------------------------------------------------*/
jpayne@68 284 /*---------------- Fields ----------------*/
jpayne@68 285 /*--------------------------------------------------------------*/
jpayne@68 286
jpayne@68 287 private long[] array;
jpayne@68 288 private int size=0;
jpayne@68 289 /** Value for empty cells */
jpayne@68 290 private long invalid;
jpayne@68 291 private int modulus;
jpayne@68 292 private int sizeLimit;
jpayne@68 293 private final float loadFactor;
jpayne@68 294
jpayne@68 295 private static final Random randy=new Random(1);
jpayne@68 296 private static final long MASK=Long.MAX_VALUE;
jpayne@68 297 private static final long MINMASK=Long.MIN_VALUE;
jpayne@68 298
jpayne@68 299 private static final int extra=10;
jpayne@68 300
jpayne@68 301 }