Mercurial > repos > rliterman > csp2

comparison 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
comparison
equal deleted inserted replaced
67:0e9998148a16 68:5028fdace37b
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
22 protected KmerNode(long pivot_){
23 pivot=pivot_;
24 }
25
26 public abstract KmerNode makeNode(long pivot_, int value_);
27 public abstract KmerNode makeNode(long pivot_, int[] values_, int vlen_);
28
29 /*--------------------------------------------------------------*/
30 /*---------------- Public Methods ----------------*/
31 /*--------------------------------------------------------------*/
32
33 @Override
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
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
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
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
135 public final int getValue(long kmer){
136 KmerNode n=get(kmer);
137 return n==null ? -1 : n.value();
138 }
139
140 @Override
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
147 public final boolean contains(long kmer){
148 KmerNode node=get(kmer);
149 return node!=null;
150 }
151
152 /*--------------------------------------------------------------*/
153 /*---------------- Nonpublic Methods ----------------*/
154 /*--------------------------------------------------------------*/
155
156 public KmerNode left(){return left;}
157 public KmerNode right(){return right;}
158 public long pivot(){return pivot;}
159 public int owner(){return owner;}
160
161 public int count(){return value();}
162 protected abstract int value();
163 protected abstract int[] values(int[] singleton);
164 /** Returns new value */
165 public abstract int set(int value_);
166 protected abstract int set(int[] values_, int vlen);
167
168 @Override
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
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
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
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
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
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
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
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
271 public long regenerate(final int limit){
272 throw new RuntimeException("Not supported.");
273 }
274
275 /*--------------------------------------------------------------*/
276 /*---------------- Info Dumping ----------------*/
277 /*--------------------------------------------------------------*/
278
279 @Override
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
285 protected abstract StringBuilder dumpKmersAsText(StringBuilder sb, int k, int mincount, int maxcount);
286
287 protected abstract ByteBuilder dumpKmersAsText(ByteBuilder bb, int k, int mincount, int maxcount);
288
289 @Override
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
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
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
316 abstract boolean TWOD();
317 abstract int numValues();
318
319 /*--------------------------------------------------------------*/
320 /*---------------- Ownership ----------------*/
321 /*--------------------------------------------------------------*/
322
323 @Override
324 public final void initializeOwnership(){
325 owner=-1;
326 if(left!=null){left.initializeOwnership();}
327 if(right!=null){right.initializeOwnership();}
328 }
329
330 @Override
331 public final void clearOwnership(){initializeOwnership();}
332
333 @Override
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
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
361 public final int getOwner(final long kmer){
362 KmerNode n=get(kmer);
363 assert(n!=null);
364 return n.owner;
365 }
366
367 public long calcMem() {//48 is a guess
368 return 48+(left==null ? 0 : left.calcMem())+(right==null ? 0 : right.calcMem());
369 }
370
371 /*--------------------------------------------------------------*/
372 /*---------------- Invalid Methods ----------------*/
373 /*--------------------------------------------------------------*/
374
375 /*--------------------------------------------------------------*/
376 /*---------------- Fields ----------------*/
377 /*--------------------------------------------------------------*/
378
379 long pivot;
380 int owner=-1;
381 KmerNode left, right;
382
383 }