jpayne@68: package kmer;
jpayne@68: 
jpayne@68: import java.util.ArrayList;
jpayne@68: import java.util.concurrent.atomic.AtomicLong;
jpayne@68: import java.util.concurrent.locks.Lock;
jpayne@68: import java.util.concurrent.locks.ReentrantLock;
jpayne@68: 
jpayne@68: import fileIO.ByteStreamWriter;
jpayne@68: import fileIO.TextStreamWriter;
jpayne@68: import shared.Primes;
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 23, 2013
jpayne@68:  *
jpayne@68:  */
jpayne@68: public final class KmerTable extends AbstractKmerTable {
jpayne@68: 	
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	/*----------------        Initialization        ----------------*/
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	
jpayne@68: 	public KmerTable(int initialSize, boolean autoResize_){
jpayne@68: 		if(initialSize>1){
jpayne@68: 			initialSize=(int)Tools.min(maxPrime, Primes.primeAtLeast(initialSize));
jpayne@68: 		}else{
jpayne@68: 			initialSize=1;
jpayne@68: 		}
jpayne@68: 		prime=initialSize;
jpayne@68: 		sizeLimit=(long) (initialSize*resizeMult);
jpayne@68: 		array=new KmerLink[prime];
jpayne@68: 		autoResize=autoResize_;
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	/*----------------        Public Methods        ----------------*/
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	
jpayne@68: 	@Override
jpayne@68: 	public int increment(final long kmer, final int incr){
jpayne@68: 		final int cell=(int)(kmer%prime);
jpayne@68: 		KmerLink n=array[cell], prev=null;
jpayne@68: 		while(n!=null && n.pivot!=kmer){
jpayne@68: 			prev=n;
jpayne@68: 			n=n.next;
jpayne@68: 		}
jpayne@68: 		if(n==null){
jpayne@68: 			n=new KmerLink(kmer, incr);
jpayne@68: 			size++;
jpayne@68: 			if(prev==null){
jpayne@68: 				array[cell]=n;
jpayne@68: 			}else{
jpayne@68: 				prev.next=n;
jpayne@68: 			}
jpayne@68: 			if(autoResize && size>sizeLimit){resize();}
jpayne@68: 		}else{
jpayne@68: 			n.value+=incr;
jpayne@68: 			if(n.value<0){n.value=Integer.MAX_VALUE;}
jpayne@68: 		}
jpayne@68: 		return n.value;
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	@Override
jpayne@68: 	public int incrementAndReturnNumCreated(final long kmer, final int incr){
jpayne@68: 		final int cell=(int)(kmer%prime);
jpayne@68: 		KmerLink n=array[cell], prev=null;
jpayne@68: 		while(n!=null && n.pivot!=kmer){
jpayne@68: 			prev=n;
jpayne@68: 			n=n.next;
jpayne@68: 		}
jpayne@68: 		if(n==null){
jpayne@68: 			n=new KmerLink(kmer, incr);
jpayne@68: 			size++;
jpayne@68: 			if(prev==null){
jpayne@68: 				array[cell]=n;
jpayne@68: 			}else{
jpayne@68: 				prev.next=n;
jpayne@68: 			}
jpayne@68: 			if(autoResize && size>sizeLimit){resize();}
jpayne@68: 			return 1;
jpayne@68: 		}else{
jpayne@68: 			n.value+=incr;
jpayne@68: 			if(n.value<0){n.value=Integer.MAX_VALUE;}
jpayne@68: 			return 0;
jpayne@68: 		}
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	@Override
jpayne@68: 	public int set(long kmer, int value){
jpayne@68: 		int x=1, cell=(int)(kmer%prime);
jpayne@68: 		final KmerLink n=array[cell];
jpayne@68: 		if(n==null){
jpayne@68: 			array[cell]=new KmerLink(kmer, value);
jpayne@68: 		}else{
jpayne@68: 			x=n.set(kmer, value);
jpayne@68: 		}
jpayne@68: 		size+=x;
jpayne@68: 		if(autoResize && size>sizeLimit){resize();}
jpayne@68: 		return x;
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	@Override
jpayne@68: 	public int set(long kmer, int[] vals, int vlen) {
jpayne@68: 		throw new RuntimeException("Unimplemented.");
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	@Override
jpayne@68: 	public int setIfNotPresent(long kmer, int value){
jpayne@68: 		int x=1, cell=(int)(kmer%prime);
jpayne@68: 		final KmerLink n=array[cell];
jpayne@68: 		if(n==null){
jpayne@68: 			array[cell]=new KmerLink(kmer, value);
jpayne@68: 		}else{
jpayne@68: 			x=n.setIfNotPresent(kmer, value);
jpayne@68: 		}
jpayne@68: 		size+=x;
jpayne@68: 		if(autoResize && size>sizeLimit){resize();}
jpayne@68: 		return x;
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	@Override
jpayne@68: 	public int getValue(long kmer){
jpayne@68: 		int cell=(int)(kmer%prime);
jpayne@68: 		KmerLink n=array[cell];
jpayne@68: 		while(n!=null && n.pivot!=kmer){n=n.next;}
jpayne@68: 		return n==null ? 0 : n.value;
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	@Override
jpayne@68: 	public int[] getValues(long kmer, int[] singleton){
jpayne@68: 		assert(array.length==0);
jpayne@68: 		singleton[0]=getValue(kmer);
jpayne@68: 		return singleton;
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	@Override
jpayne@68: 	public boolean contains(long kmer){
jpayne@68: 		KmerLink node=get(kmer);
jpayne@68: 		return node!=null;
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	/*----------------          Ownership           ----------------*/
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	
jpayne@68: 	@Override
jpayne@68: 	public final void initializeOwnership(){
jpayne@68: 		for(KmerLink n : array){
jpayne@68: 			if(n!=null){n.initializeOwnership();}
jpayne@68: 		}
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	@Override
jpayne@68: 	public final void clearOwnership(){
jpayne@68: 		for(KmerLink n : array){
jpayne@68: 			if(n!=null){n.clearOwnership();}
jpayne@68: 		}
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	@Override
jpayne@68: 	public final int setOwner(final long kmer, final int newOwner){
jpayne@68: 		final int cell=(int)(kmer%prime);
jpayne@68: 		KmerLink n=array[cell];
jpayne@68: 		assert(n!=null);
jpayne@68: 		return n.setOwner(kmer, newOwner);
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	@Override
jpayne@68: 	public final boolean clearOwner(final long kmer, final int owner){
jpayne@68: 		final int cell=(int)(kmer%prime);
jpayne@68: 		KmerLink n=array[cell];
jpayne@68: 		assert(n!=null);
jpayne@68: 		return n.clearOwner(kmer, owner);
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	@Override
jpayne@68: 	public final int getOwner(final long kmer){
jpayne@68: 		final int cell=(int)(kmer%prime);
jpayne@68: 		KmerLink n=array[cell];
jpayne@68: 		assert(n!=null);
jpayne@68: 		return n.getOwner(kmer);
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	/*----------------      Nonpublic Methods       ----------------*/
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	
jpayne@68: 	@Override
jpayne@68: 	KmerLink get(long kmer){
jpayne@68: 		int cell=(int)(kmer%prime);
jpayne@68: 		KmerLink n=array[cell];
jpayne@68: 		while(n!=null && n.pivot!=kmer){n=n.next;}
jpayne@68: 		return n;
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	boolean insert(KmerLink n){
jpayne@68: 		n.next=null;
jpayne@68: 		int cell=(int)(n.pivot%prime);
jpayne@68: 		if(array[cell]==null){
jpayne@68: 			array[cell]=n;
jpayne@68: 			return true;
jpayne@68: 		}
jpayne@68: 		return array[cell].insert(n);
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	/*----------------       Private Methods        ----------------*/
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	/*----------------       Invalid Methods        ----------------*/
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	/*----------------   Resizing and Rebalancing   ----------------*/
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	
jpayne@68: 	@Override
jpayne@68: 	boolean canResize() {return true;}
jpayne@68: 	
jpayne@68: 	@Override
jpayne@68: 	public boolean canRebalance() {return false;}
jpayne@68: 	
jpayne@68: 	@Override
jpayne@68: 	public long size() {return size;}
jpayne@68: 	
jpayne@68: 	@Override
jpayne@68: 	public int arrayLength() {return array.length;}
jpayne@68: 	
jpayne@68: 	@Override
jpayne@68: 	synchronized void resize(){
jpayne@68: //		assert(false);
jpayne@68: //		System.err.println("Resizing from "+prime+"; load="+(size*1f/prime));
jpayne@68: 		sizeLimit=Tools.max((long)(size*1.4), (long)(maxLoadFactor*prime));
jpayne@68: 
jpayne@68: 		final long maxAllowedByLoadFactor=(long)(size*minLoadMult);
jpayne@68: 		final long minAllowedByLoadFactor=(long)(size*maxLoadMult);
jpayne@68: 		assert(maxAllowedByLoadFactor>=minAllowedByLoadFactor);
jpayne@68: 		if(maxAllowedByLoadFactor<prime){return;}
jpayne@68: 		
jpayne@68: 		long x=10+(long)(prime*resizeMult);
jpayne@68: 		x=Tools.max(x, minAllowedByLoadFactor);
jpayne@68: 		x=Tools.min(x, maxAllowedByLoadFactor);
jpayne@68: 		
jpayne@68: 		int prime2=(int)Tools.min(maxPrime, Primes.primeAtLeast(x));
jpayne@68: 		
jpayne@68: 		if(prime2<=prime){return;}
jpayne@68: 		
jpayne@68: 		prime=prime2;
jpayne@68: //		System.err.println("Resized to "+prime+"; load="+(size*1f/prime));
jpayne@68: 		KmerLink[] old=array;
jpayne@68: 		array=new KmerLink[prime2];
jpayne@68: 		ArrayList<KmerLink> list=new ArrayList<KmerLink>(1000);
jpayne@68: 		for(int i=0; i<old.length; i++){
jpayne@68: 			if(old[i]!=null){
jpayne@68: 				old[i].traverseInfix(list);
jpayne@68: 				for(KmerLink n : list){insert(n);}
jpayne@68: 				list.clear();
jpayne@68: 			}
jpayne@68: 		}
jpayne@68: 		sizeLimit=Tools.max((long)(size*1.4), (long)(maxLoadFactor*prime));
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	@Override
jpayne@68: 	public void rebalance(){
jpayne@68: 		ArrayList<KmerLink> list=new ArrayList<KmerLink>(1000);
jpayne@68: 		for(int i=0; i<array.length; i++){
jpayne@68: 			if(array[i]!=null){array[i]=array[i].rebalance(list);}
jpayne@68: 		}
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	/*----------------         Info Dumping         ----------------*/
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	
jpayne@68: 	@Deprecated
jpayne@68: 	@Override
jpayne@68: 	public boolean dumpKmersAsText(TextStreamWriter tsw, int k, int mincount, int maxcount){
jpayne@68: 		throw new RuntimeException("TODO");
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	@Override
jpayne@68: 	public boolean dumpKmersAsBytes_MT(final ByteStreamWriter bsw, final ByteBuilder bb, final int k, final int mincount, int maxcount, AtomicLong remaining){
jpayne@68: 		for(int i=0; i<array.length; i++){
jpayne@68: 			KmerLink node=array[i];
jpayne@68: 			if(node!=null && node.value>=mincount){
jpayne@68: 				node.dumpKmersAsBytes_MT(bsw, bb, k, mincount, maxcount, remaining);
jpayne@68: 			}
jpayne@68: 		}
jpayne@68: 		return true;
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	@Deprecated
jpayne@68: 	@Override
jpayne@68: 	public boolean dumpKmersAsBytes(ByteStreamWriter bsw, int k, int mincount, int maxcount, AtomicLong remaining){
jpayne@68: 		throw new RuntimeException("TODO");
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	@Deprecated
jpayne@68: 	@Override
jpayne@68: 	public void fillHistogram(long[] ca, int max){
jpayne@68: 		throw new RuntimeException("TODO");
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	@Deprecated
jpayne@68: 	@Override
jpayne@68: 	public void fillHistogram(SuperLongList sll){
jpayne@68: 		throw new RuntimeException("TODO");
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	@Deprecated
jpayne@68: 	@Override
jpayne@68: 	public void countGC(long[] gcCounts, int max){
jpayne@68: 		throw new RuntimeException("TODO");
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	@Deprecated
jpayne@68: 	@Override
jpayne@68: 	public long regenerate(final int limit){
jpayne@68: 		throw new RuntimeException("TODO - remove zero-value links.");
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	/*----------------            Fields            ----------------*/
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	
jpayne@68: 	KmerLink[] array;
jpayne@68: 	int prime;
jpayne@68: 	long size=0;
jpayne@68: 	long sizeLimit;
jpayne@68: 	final boolean autoResize;
jpayne@68: 	private final Lock lock=new ReentrantLock();
jpayne@68: 	
jpayne@68: 	@Override
jpayne@68: 	final Lock getLock(){return lock;}
jpayne@68: 	
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	/*----------------        Static Fields         ----------------*/
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	
jpayne@68: 	final static int maxPrime=(int)Primes.primeAtMost(Integer.MAX_VALUE);
jpayne@68: 	final static float resizeMult=2f; //Resize by a minimum of this much
jpayne@68: 	final static float minLoadFactor=0.5f; //Resize by enough to get the load above this factor
jpayne@68: 	final static float maxLoadFactor=0.98f; //Resize by enough to get the load under this factor
jpayne@68: 	final static float minLoadMult=1/minLoadFactor;
jpayne@68: 	final static float maxLoadMult=1/maxLoadFactor;
jpayne@68: 	
jpayne@68: }