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