jpayne@68: package kmer;
jpayne@68: 
jpayne@68: import java.util.ArrayList;
jpayne@68: import java.util.Arrays;
jpayne@68: 
jpayne@68: import fileIO.TextStreamWriter;
jpayne@68: import shared.Tools;
jpayne@68: import structures.ByteBuilder;
jpayne@68: import structures.SuperLongList;
jpayne@68: 
jpayne@68: /**
jpayne@68:  * @author Brian Bushnell
jpayne@68:  * @date Oct 22, 2013
jpayne@68:  *
jpayne@68:  */
jpayne@68: public abstract class KmerNode extends AbstractKmerTable {
jpayne@68: 	
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	/*----------------        Initialization        ----------------*/
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	
jpayne@68: 	protected KmerNode(long pivot_){
jpayne@68: 		pivot=pivot_;
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	public abstract KmerNode makeNode(long pivot_, int value_);
jpayne@68: 	public abstract KmerNode makeNode(long pivot_, int[] values_, int vlen_);
jpayne@68: 	
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	/*----------------        Public Methods        ----------------*/
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	
jpayne@68: 	@Override
jpayne@68: 	public final int increment(final long kmer, final int incr){
jpayne@68: 		if(pivot<0){pivot=kmer; return set(incr);} //Allows initializing empty nodes to -1
jpayne@68: 		if(kmer<pivot){
jpayne@68: 			if(left==null){left=makeNode(kmer, incr); return incr;}
jpayne@68: 			return left.increment(kmer, incr);
jpayne@68: 		}else if(kmer>pivot){
jpayne@68: 			if(right==null){right=makeNode(kmer, incr); return incr;}
jpayne@68: 			return right.increment(kmer, incr);
jpayne@68: 		}else{
jpayne@68: 			if(value()<Integer.MAX_VALUE){set(value()+incr);}
jpayne@68: 			return value();
jpayne@68: 		}
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	@Override
jpayne@68: 	public final int incrementAndReturnNumCreated(final long kmer, final int incr) {
jpayne@68: 		int x=increment(kmer, incr);
jpayne@68: 		return x==1 ? 1 : 0;
jpayne@68: 	}
jpayne@68: 	
jpayne@68: //	public final int set_Test(final long kmer, final int v){
jpayne@68: //		assert(TESTMODE);
jpayne@68: //		final int x;
jpayne@68: //		if(TWOD()){
jpayne@68: //			int[] old=getValues(kmer, null);
jpayne@68: //			assert(old==null || contains(kmer, old));
jpayne@68: //			x=set0(kmer, v);
jpayne@68: //			assert(old==null || contains(kmer, old));
jpayne@68: //			assert(contains(kmer, v));
jpayne@68: //		}else{
jpayne@68: //			int old=getValue(kmer);
jpayne@68: //			assert(old==0 || old==-1 || contains(kmer, old));
jpayne@68: //			x=set0(kmer, v);
jpayne@68: //			assert(contains(kmer, v)) : "old="+old+", v="+v+", kmer="+kmer+", get(kmer)="+getValue(kmer);
jpayne@68: //			assert(v==old || !contains(kmer, old));
jpayne@68: //		}
jpayne@68: //		return x;
jpayne@68: //	}
jpayne@68: //
jpayne@68: //	public final int setIfNotPresent_Test(long kmer, int v){
jpayne@68: //		assert(TESTMODE);
jpayne@68: //		final int x;
jpayne@68: //		if(TWOD()){
jpayne@68: ////			int[] vals=getValues(kmer, null);
jpayne@68: ////			assert(vals==null || contains(kmer, vals));
jpayne@68: ////			x=setIfNotPresent(kmer, v);
jpayne@68: ////			assert(contains(kmer, vals));
jpayne@68: ////			assert(contains(kmer, v));
jpayne@68: //			x=0;
jpayne@68: //			assert(false);
jpayne@68: //		}else{
jpayne@68: //			int old=getValue(kmer);
jpayne@68: //			assert(old==0 || old==-1 || contains(kmer, old));
jpayne@68: //			x=setIfNotPresent0(kmer, v);
jpayne@68: //			assert((old<1 && contains(kmer, v)) || (old>0 && contains(kmer, old))) : kmer+", "+old+", "+v;
jpayne@68: //		}
jpayne@68: //		return x;
jpayne@68: //	}
jpayne@68: 	
jpayne@68: 	
jpayne@68: 	/** Returns number of nodes added */
jpayne@68: 	@Override
jpayne@68: 	public final int set(long kmer, int value){
jpayne@68: 		if(verbose){System.err.println("Set0: kmer="+kmer+", v="+value+", old="+Arrays.toString(values(new int[1])));}
jpayne@68: 		if(pivot<0){pivot=kmer; set(value); return 1;} //Allows initializing empty nodes to -1
jpayne@68: 		if(verbose){System.err.println("A");}
jpayne@68: 		if(kmer<pivot){
jpayne@68: 			if(verbose){System.err.println("B");}
jpayne@68: 			if(left==null){left=makeNode(kmer, value); return 1;}
jpayne@68: 			if(verbose){System.err.println("C");}
jpayne@68: 			return left.set(kmer, value);
jpayne@68: 		}else if(kmer>pivot){
jpayne@68: 			if(verbose){System.err.println("D");}
jpayne@68: 			if(right==null){right=makeNode(kmer, value); return 1;}
jpayne@68: 			if(verbose){System.err.println("E");}
jpayne@68: 			return right.set(kmer, value);
jpayne@68: 		}else{
jpayne@68: 			if(verbose){System.err.println("F");}
jpayne@68: 			set(value);
jpayne@68: 		}
jpayne@68: 		if(verbose){System.err.println("G");}
jpayne@68: 		return 0;
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	
jpayne@68: 	/** Returns number of nodes added */
jpayne@68: 	@Override
jpayne@68: 	public final int setIfNotPresent(long kmer, int value){
jpayne@68: 		if(verbose){System.err.println("setIfNotPresent0: kmer="+kmer+", v="+value+", old="+Arrays.toString(values(new int[0])));}
jpayne@68: 		if(pivot<0){pivot=kmer; set(value); return 1;} //Allows initializing empty nodes to -1
jpayne@68: 		if(kmer<pivot){
jpayne@68: 			if(left==null){left=makeNode(kmer, value); return 1;}
jpayne@68: 			return left.setIfNotPresent(kmer, value);
jpayne@68: 		}else if(kmer>pivot){
jpayne@68: 			if(right==null){right=makeNode(kmer, value); return 1;}
jpayne@68: 			return right.setIfNotPresent(kmer, value);
jpayne@68: 		}
jpayne@68: 		return 0;
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	@Override
jpayne@68: 	public final int getValue(long kmer){
jpayne@68: 		KmerNode n=get(kmer);
jpayne@68: 		return n==null ? -1 : n.value();
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	@Override
jpayne@68: 	public final int[] getValues(long kmer, int[] singleton){
jpayne@68: 		KmerNode n=get(kmer);
jpayne@68: 		return n==null ? null : n.values(singleton);
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	@Override
jpayne@68: 	public final boolean contains(long kmer){
jpayne@68: 		KmerNode node=get(kmer);
jpayne@68: 		return node!=null;
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	/*----------------      Nonpublic Methods       ----------------*/
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 
jpayne@68: 	public KmerNode left(){return left;}
jpayne@68: 	public KmerNode right(){return right;}
jpayne@68: 	public long pivot(){return pivot;}
jpayne@68: 	public int owner(){return owner;}
jpayne@68: 	
jpayne@68: 	public int count(){return value();}
jpayne@68: 	protected abstract int value();
jpayne@68: 	protected abstract int[] values(int[] singleton);
jpayne@68: 	/** Returns new value */
jpayne@68: 	public abstract int set(int value_);
jpayne@68: 	protected abstract int set(int[] values_, int vlen);
jpayne@68: 	
jpayne@68: 	@Override
jpayne@68: 	final KmerNode get(long kmer){
jpayne@68: //		if(kmer<pivot){
jpayne@68: //			return left==null ? null : left.get(kmer);
jpayne@68: //		}else if(kmer>pivot){
jpayne@68: //			return right==null ? null : right.get(kmer);
jpayne@68: //		}else{
jpayne@68: //			return this;
jpayne@68: //		}
jpayne@68: 		KmerNode n=this;
jpayne@68: 		while(n!=null && n.pivot!=kmer){
jpayne@68: 			n=(kmer<n.pivot ? n.left : n.right);
jpayne@68: 		}
jpayne@68: 		return n;
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	final KmerNode getNodeOrParent(long kmer){
jpayne@68: 		if(pivot==kmer || pivot<0){return this;}
jpayne@68: 		if(kmer<pivot){return left==null ? this : left.getNodeOrParent(kmer);}
jpayne@68: 		return right==null ? this : right.getNodeOrParent(kmer);
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	final boolean insert(KmerNode n){
jpayne@68: 		assert(pivot!=-1);
jpayne@68: 		if(n.pivot<pivot){
jpayne@68: 			if(left==null){left=n; return true;}
jpayne@68: 			return left.insert(n);
jpayne@68: 		}else if(n.pivot>pivot){
jpayne@68: 			if(right==null){right=n; return true;}
jpayne@68: 			return right.insert(n);
jpayne@68: 		}else{
jpayne@68: 			return false;
jpayne@68: 		}
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	final void traversePrefix(ArrayList<KmerNode> list){
jpayne@68: 		if(left!=null){left.traversePrefix(list);}
jpayne@68: 		list.add(this);
jpayne@68: 		if(right!=null){right.traversePrefix(list);}
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	final void traverseInfix(ArrayList<KmerNode> list){
jpayne@68: 		list.add(this);
jpayne@68: 		if(left!=null){left.traverseInfix(list);}
jpayne@68: 		if(right!=null){right.traverseInfix(list);}
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	/*----------------       Private Methods        ----------------*/
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	/*----------------   Resizing and Rebalancing   ----------------*/
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	
jpayne@68: 	@Override
jpayne@68: 	public final long size() {
jpayne@68: 		if(value()<1){return 0;}
jpayne@68: 		long size=1;
jpayne@68: 		if(left!=null){size+=left.size();}
jpayne@68: 		if(right!=null){size+=right.size();}
jpayne@68: 		return size;
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	final KmerNode rebalance(ArrayList<KmerNode> list){
jpayne@68: 		assert(list.isEmpty());
jpayne@68: 		traversePrefix(list);
jpayne@68: 		KmerNode n=this;
jpayne@68: 		if(list.size()>2){
jpayne@68: 			n=rebalance(list, 0, list.size()-1);
jpayne@68: 		}
jpayne@68: 		list.clear();
jpayne@68: 		return n;
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	private static final KmerNode rebalance(ArrayList<KmerNode> list, int a, int b){
jpayne@68: 		final int size=b-a+1;
jpayne@68: 		final int middle=a+size/2;
jpayne@68: 		final KmerNode n=list.get(middle);
jpayne@68: 		if(size<4){
jpayne@68: 			if(size==1){
jpayne@68: 				n.left=n.right=null;
jpayne@68: 			}else if(size==2){
jpayne@68: 				KmerNode n1=list.get(a);
jpayne@68: 				n.left=n1;
jpayne@68: 				n.right=null;
jpayne@68: 				n1.left=n1.right=null;
jpayne@68: 			}else{
jpayne@68: 				assert(size==3);
jpayne@68: 				KmerNode n1=list.get(a), n2=list.get(b);
jpayne@68: 				n.left=n1;
jpayne@68: 				n.right=n2;
jpayne@68: 				n1.left=n1.right=null;
jpayne@68: 				n2.left=n2.right=null;
jpayne@68: 			}
jpayne@68: 		}else{
jpayne@68: 			n.left=rebalance(list, a, middle-1);
jpayne@68: 			n.right=rebalance(list, middle+1, b);
jpayne@68: 		}
jpayne@68: 		return n;
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	@Override
jpayne@68: 	public long regenerate(final int limit){
jpayne@68: 		throw new RuntimeException("Not supported.");
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	/*----------------         Info Dumping         ----------------*/
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	
jpayne@68: 	@Override
jpayne@68: 	public final boolean dumpKmersAsText(TextStreamWriter tsw, int k, int mincount, int maxcount) {
jpayne@68: 		tsw.print(dumpKmersAsText(new StringBuilder(32), k, mincount, maxcount));
jpayne@68: 		return true;
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	protected abstract StringBuilder dumpKmersAsText(StringBuilder sb, int k, int mincount, int maxcount);
jpayne@68: 	
jpayne@68: 	protected abstract ByteBuilder dumpKmersAsText(ByteBuilder bb, int k, int mincount, int maxcount);
jpayne@68: 	
jpayne@68: 	@Override
jpayne@68: 	public final void fillHistogram(long[] ca, int max){
jpayne@68: 		final int value=value();
jpayne@68: 		if(value<1){return;}
jpayne@68: 		ca[Tools.min(value, max)]++;
jpayne@68: 		if(left!=null){left.fillHistogram(ca, max);}
jpayne@68: 		if(right!=null){right.fillHistogram(ca, max);}
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	@Override
jpayne@68: 	public final void fillHistogram(SuperLongList sll){
jpayne@68: 		final int value=value();
jpayne@68: 		if(value<1){return;}
jpayne@68: 		sll.add(value);
jpayne@68: 		if(left!=null){left.fillHistogram(sll);}
jpayne@68: 		if(right!=null){right.fillHistogram(sll);}
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	@Override
jpayne@68: 	public void countGC(long[] gcCounts, int max){
jpayne@68: 		final int value=value();
jpayne@68: 		if(value<1){return;}
jpayne@68: 		gcCounts[Tools.min(value, max)]+=gc(pivot);
jpayne@68: 		if(left!=null){left.countGC(gcCounts, max);}
jpayne@68: 		if(right!=null){right.countGC(gcCounts, max);}
jpayne@68: 	}
jpayne@68: 
jpayne@68: 	abstract boolean TWOD();
jpayne@68: 	abstract int numValues();
jpayne@68: 	
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	/*----------------          Ownership           ----------------*/
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	
jpayne@68: 	@Override
jpayne@68: 	public final void initializeOwnership(){
jpayne@68: 		owner=-1;
jpayne@68: 		if(left!=null){left.initializeOwnership();}
jpayne@68: 		if(right!=null){right.initializeOwnership();}
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	@Override
jpayne@68: 	public final void clearOwnership(){initializeOwnership();}
jpayne@68: 	
jpayne@68: 	@Override
jpayne@68: 	public final int setOwner(final long kmer, final int newOwner){
jpayne@68: 		KmerNode n=get(kmer);
jpayne@68: 		assert(n!=null);
jpayne@68: 		if(n.owner<=newOwner){
jpayne@68: 			synchronized(n){
jpayne@68: 				if(n.owner<newOwner){
jpayne@68: 					n.owner=newOwner;
jpayne@68: 				}
jpayne@68: 			}
jpayne@68: 		}
jpayne@68: 		return n.owner;
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	@Override
jpayne@68: 	public final boolean clearOwner(final long kmer, final int owner){
jpayne@68: 		KmerNode n=get(kmer);
jpayne@68: 		assert(n!=null);
jpayne@68: 		synchronized(n){
jpayne@68: 			if(n.owner==owner){
jpayne@68: 				n.owner=-1;
jpayne@68: 				return true;
jpayne@68: 			}
jpayne@68: 		}
jpayne@68: 		return false;
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	@Override
jpayne@68: 	public final int getOwner(final long kmer){
jpayne@68: 		KmerNode n=get(kmer);
jpayne@68: 		assert(n!=null);
jpayne@68: 		return n.owner;
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	public long calcMem() {//48 is a guess
jpayne@68: 		return 48+(left==null ? 0 : left.calcMem())+(right==null ? 0 : right.calcMem());
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	/*----------------       Invalid Methods        ----------------*/
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	/*----------------            Fields            ----------------*/
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	
jpayne@68: 	long pivot;
jpayne@68: 	int owner=-1;
jpayne@68: 	KmerNode left, right;
jpayne@68: 	
jpayne@68: }