jpayne@68: package kmer;
jpayne@68: 
jpayne@68: import java.util.ArrayList;
jpayne@68: import java.util.Arrays;
jpayne@68: 
jpayne@68: import shared.KillSwitch;
jpayne@68: import shared.Primes;
jpayne@68: import shared.Shared;
jpayne@68: import shared.Tools;
jpayne@68: 
jpayne@68: /**
jpayne@68:  * Stores kmers in a long[] and values in an int[][], with a victim cache.
jpayne@68:  * @author Brian Bushnell
jpayne@68:  * @date Nov 7, 2014
jpayne@68:  *
jpayne@68:  */
jpayne@68: public final class HashArray2D extends HashArray {
jpayne@68: 	
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	/*----------------        Initialization        ----------------*/
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	
jpayne@68: 	public HashArray2D(int[] schedule_, long coreMask_){
jpayne@68: 		super(schedule_, coreMask_, true);
jpayne@68: 		values=allocInt2D(prime+extra);
jpayne@68: 	}
jpayne@68: 	
jpayne@68: //	public HashArray2D(int initialSize, int maxSize, long mask, boolean autoResize_){
jpayne@68: //		super(initialSize, maxSize, mask, autoResize_, true);
jpayne@68: //		values=allocInt2D(prime+extra);
jpayne@68: //	}
jpayne@68: 	
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	/*----------------        Public Methods        ----------------*/
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	
jpayne@68: 	@Deprecated
jpayne@68: 	@Override
jpayne@68: 	public int increment(final long kmer, final int incr){
jpayne@68: 		throw new RuntimeException("Unsupported.");
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	@Deprecated
jpayne@68: 	@Override
jpayne@68: 	public int incrementAndReturnNumCreated(final long kmer, final int incr){
jpayne@68: 		throw new RuntimeException("Unsupported.");
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	/*----------------      Nonpublic Methods       ----------------*/
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	
jpayne@68: 	@Override
jpayne@68: 	protected final int readCellValue(int cell) {
jpayne@68: 		int[] set=values[cell];
jpayne@68: 		return set==null ? 0 : set[0];
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	@Override
jpayne@68: 	protected final int[] readCellValues(int cell, int[] singleton) {
jpayne@68: 		return values[cell];
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	/** Returns number of values added */
jpayne@68: 	@Override
jpayne@68: 	protected final void insertValue(final long kmer, final int v, final int cell){
jpayne@68: 		assert(array[cell]==kmer);
jpayne@68: 		if(values[cell]==null){
jpayne@68: 			values[cell]=new int[] {v, NOT_PRESENT};
jpayne@68: 			return;
jpayne@68: 		}
jpayne@68: 		int[] set=values[cell];
jpayne@68: 		assert(set!=null);
jpayne@68: 		
jpayne@68: 		for(int i=0; i<set.length; i++){
jpayne@68: 			if(set[i]==v){return;}
jpayne@68: 			else if(set[i]<0){set[i]=v;return;}
jpayne@68: 		}
jpayne@68: 		final int oldSize=set.length;
jpayne@68: 		final int newSize=(int)Tools.min(Shared.MAX_ARRAY_LEN, oldSize*2L);
jpayne@68: 		assert(newSize>set.length) : "Overflow.";
jpayne@68: 		set=KillSwitch.copyOf(set, newSize);
jpayne@68: 		set[oldSize]=v;
jpayne@68: 		Arrays.fill(set, oldSize+1, newSize, NOT_PRESENT);
jpayne@68: 		values[cell]=set;
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	/** Returns number of values added */
jpayne@68: 	@Override
jpayne@68: 	protected final void insertValue(final long kmer, final int[] vals, final int cell, final int vlen){
jpayne@68: 		assert(array[cell]==kmer);
jpayne@68: 		if(values[cell]==null){
jpayne@68: 			values[cell]=vals;
jpayne@68: 		}else{
jpayne@68: 			for(int v : vals){
jpayne@68: 				if(v<0){break;}
jpayne@68: 				insertValue(kmer, v, cell);
jpayne@68: 			}
jpayne@68: 		}
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	/*----------------   Resizing and Rebalancing   ----------------*/
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	
jpayne@68: 	@Override
jpayne@68: 	public final boolean canRebalance() {return false;}
jpayne@68: 	
jpayne@68: 	@Override
jpayne@68: 	protected synchronized void resize(){
jpayne@68: //		assert(false);
jpayne@68: //		System.err.println("Resizing from "+prime+"; load="+(size*1f/prime));
jpayne@68: 		if(prime>=maxPrime){
jpayne@68: //			sizeLimit=0xFFFFFFFFFFFFL;
jpayne@68: //			return;
jpayne@68: 			KillSwitch.memKill(new OutOfMemoryError());
jpayne@68: 		}
jpayne@68: 		
jpayne@68: 		final long oldSize=size, oldVSize=victims.size;
jpayne@68: 		if(schedule!=null){
jpayne@68: 			final long oldPrime=prime;
jpayne@68: 			prime=nextScheduleSize();
jpayne@68: 			if(prime<=oldPrime){KillSwitch.memKill(new OutOfMemoryError());}
jpayne@68: 			sizeLimit=(long)((atMaxSize() ? maxLoadFactorFinal : maxLoadFactor)*prime);
jpayne@68: 		}else{//Old method
jpayne@68: 			final long totalSize=oldSize+oldVSize;
jpayne@68: 
jpayne@68: 			final long maxAllowedByLoadFactor=(long)(totalSize*minLoadMult);
jpayne@68: 			final long minAllowedByLoadFactor=(long)(totalSize*maxLoadMult);
jpayne@68: 
jpayne@68: 			//		sizeLimit=Tools.min((long)(maxLoadFactor*prime), maxPrime);
jpayne@68: 
jpayne@68: 			assert(maxAllowedByLoadFactor>=minAllowedByLoadFactor);
jpayne@68: 			if(maxAllowedByLoadFactor<prime){
jpayne@68: 				sizeLimit=(long)(maxLoadFactor*prime);
jpayne@68: 				return;
jpayne@68: 			}
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){
jpayne@68: 				sizeLimit=(long)(maxLoadFactor*prime);
jpayne@68: 				assert(prime2==prime) : "Resizing to smaller array? "+totalSize+", "+prime+", "+x;
jpayne@68: 				return;
jpayne@68: 			}
jpayne@68: 			//		System.err.println("Resizing from "+prime+" to "+prime2+"; size="+size);
jpayne@68: 
jpayne@68: 			prime=prime2;
jpayne@68: 			sizeLimit=(long)(maxLoadFactor*prime);
jpayne@68: 		}
jpayne@68: 
jpayne@68: //		System.err.println("Resized to "+prime+"; load="+(size*1f/prime));
jpayne@68: 		long[] oldk=array;
jpayne@68: 		int[][] oldc=values;
jpayne@68: 		KmerNode[] oldv=victims.array;
jpayne@68: 		array=allocLong1D(prime+extra);
jpayne@68: 		Arrays.fill(array, NOT_PRESENT);
jpayne@68: 		values=allocInt2D(prime+extra);
jpayne@68: 		ArrayList<KmerNode> list=new ArrayList<KmerNode>((int)(victims.size)); //Can fail if more than Integer.MAX_VALUE
jpayne@68: 		for(int i=0; i<oldv.length; i++){
jpayne@68: 			if(oldv[i]!=null){oldv[i].traverseInfix(list);}
jpayne@68: 		}
jpayne@68: 		Arrays.fill(oldv, null);
jpayne@68: 		victims.size=0;
jpayne@68: 		size=0;
jpayne@68: 		
jpayne@68: 		final int[] singleton=new int[] {NOT_PRESENT};
jpayne@68: 		
jpayne@68: 		for(int i=0; i<oldk.length; i++){
jpayne@68: 			if(oldk[i]>NOT_PRESENT){
jpayne@68: //				assert(!contains(oldk[i]));
jpayne@68: 				set(oldk[i], oldc[i], -1);
jpayne@68: //				assert(contains(oldk[i]));
jpayne@68: //				assert(Tools.equals(getValues(oldk[i], singleton), oldc[i]));
jpayne@68: 			}
jpayne@68: 		}
jpayne@68: 		
jpayne@68: 		for(KmerNode n : list){
jpayne@68: 			if(n.pivot>NOT_PRESENT){
jpayne@68: //				assert(!contains(n.pivot));
jpayne@68: 				set(n.pivot, n.values(singleton), n.numValues());
jpayne@68: //				assert(contains(n.pivot));
jpayne@68: //				assert(Tools.equals(getValues(n.pivot, singleton), n.values(singleton)));
jpayne@68: 			}
jpayne@68: 		}
jpayne@68: 		
jpayne@68: 		assert(oldSize+oldVSize==size+victims.size) : oldSize+", "+oldVSize+" -> "+size+", "+victims.size;
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	@Deprecated
jpayne@68: 	@Override
jpayne@68: 	public void rebalance(){
jpayne@68: 		throw new RuntimeException("Unimplemented.");
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	@Deprecated
jpayne@68: 	@Override
jpayne@68: 	public long regenerate(final int limit){
jpayne@68: 		assert(false) : "This is not tested or intended for use.";
jpayne@68: 		long sum=0;
jpayne@68: 		assert(owners==null) : "Clear ownership before regeneration.";
jpayne@68: 		for(int pos=0; pos<values.length; pos++){
jpayne@68: 			final long key=array[pos];
jpayne@68: 			if(key>=0){
jpayne@68: 				final int[] value=values[pos];
jpayne@68: 				values[pos]=null;
jpayne@68: 				array[pos]=NOT_PRESENT;
jpayne@68: 				size--;
jpayne@68: 				if(value!=null){
jpayne@68: 					assert(value[0]>0);
jpayne@68: 					set(key, value, -1);
jpayne@68: 				}else{
jpayne@68: 					sum++;
jpayne@68: 				}
jpayne@68: 			}
jpayne@68: 		}
jpayne@68: 		
jpayne@68: 		ArrayList<KmerNode> nodes=victims.toList();
jpayne@68: 		victims.clear();
jpayne@68: 		for(KmerNode node : nodes){
jpayne@68: 			set(node.pivot, node.values(null), node.numValues());//TODO: Probably unsafe or unwise.  Should test for singletons, etc.
jpayne@68: 		}
jpayne@68: 		
jpayne@68: 		return sum;
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	/*----------------            Fields            ----------------*/
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	
jpayne@68: 	private int[][] values;
jpayne@68: 	
jpayne@68: 
jpayne@68: 	
jpayne@68: }