Mercurial > repos > rliterman > csp2

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