jpayne@68: package bbmin;
jpayne@68: 
jpayne@68: import java.util.Arrays;
jpayne@68: import java.util.Random;
jpayne@68: 
jpayne@68: /**
jpayne@68:  * @author Brian Bushnell
jpayne@68:  * @date July 6, 2016
jpayne@68:  *
jpayne@68:  */
jpayne@68: public final class LongHashSet{
jpayne@68: 	
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	/*----------------        Initialization        ----------------*/
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	
jpayne@68: 	public LongHashSet(){
jpayne@68: 		this(256);
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	public LongHashSet(int initialSize){
jpayne@68: 		this(initialSize, 0.7f);
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	public LongHashSet(int initialSize, float loadFactor_){
jpayne@68: 		invalid=randy.nextLong()|MINMASK;
jpayne@68: 		assert(invalid<0);
jpayne@68: 		assert(initialSize>0) : "Attempting to initialize a "+getClass().getSimpleName()+" of size<1.";
jpayne@68: 		assert(loadFactor_>0 && loadFactor_<1) : "Attempting to initialize a "+getClass().getSimpleName()+" with invalid load factor: "+loadFactor_;
jpayne@68: 		loadFactor=mid(0.25f, loadFactor_, 0.90f);
jpayne@68: 		resize(initialSize);
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	/*----------------        Public Methods        ----------------*/
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	
jpayne@68: 	public void clear(){
jpayne@68: 		if(size<1){return;}
jpayne@68: 		Arrays.fill(array, invalid);
jpayne@68: 		size=0;
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	public boolean contains(long value){
jpayne@68: 		return value==invalid ? false : findCell(value)>=0;
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	/**
jpayne@68: 	 * Add this value to the set.
jpayne@68: 	 * @param value
jpayne@68: 	 * @return true if the value was added, false if it was already contained.
jpayne@68: 	 */
jpayne@68: 	public boolean add(long value){
jpayne@68: 		if(value==invalid){resetInvalid();}
jpayne@68: 		int cell=findCellOrEmpty(value);
jpayne@68: 		if(array[cell]==invalid){
jpayne@68: 			array[cell]=value;
jpayne@68: 			size++;
jpayne@68: 			if(size>sizeLimit){resize();}
jpayne@68: 			return true;
jpayne@68: 		}
jpayne@68: 		assert(array[cell]==value);
jpayne@68: 		return false;
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	/**
jpayne@68: 	 * Remove this value from the set.
jpayne@68: 	 * @param value
jpayne@68: 	 * @return true if the value was removed, false if it was not present.
jpayne@68: 	 */
jpayne@68: 	public boolean remove(long value){
jpayne@68: 		if(value==invalid){return false;}
jpayne@68: 		final int cell=findCell(value);
jpayne@68: 		if(cell<0){return false;}
jpayne@68: 		assert(array[cell]==value);
jpayne@68: 		array[cell]=invalid;
jpayne@68: 		size--;
jpayne@68: 		
jpayne@68: 		rehashFrom(cell);
jpayne@68: 		return true;
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	public int size(){return size;}
jpayne@68: 	
jpayne@68: 	public boolean isEmpty(){return size==0;}
jpayne@68: 	
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	/*----------------        String Methods        ----------------*/
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	
jpayne@68: 	@Override
jpayne@68: 	public String toString(){
jpayne@68: 		return toStringListView();
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	public String toStringSetView(){
jpayne@68: 		StringBuilder sb=new StringBuilder();
jpayne@68: 		sb.append('[');
jpayne@68: 		String comma="";
jpayne@68: 		for(int i=0; i<array.length; i++){
jpayne@68: 			if(array[i]!=invalid){
jpayne@68: 				sb.append(comma+"("+i+", "+array[i]+")");
jpayne@68: 				comma=", ";
jpayne@68: 			}
jpayne@68: 		}
jpayne@68: 		sb.append(']');
jpayne@68: 		return sb.toString();
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	public String toStringListView(){
jpayne@68: 		StringBuilder sb=new StringBuilder();
jpayne@68: 		sb.append('[');
jpayne@68: 		String comma="";
jpayne@68: 		for(int i=0; i<array.length; i++){
jpayne@68: 			if(array[i]!=invalid){
jpayne@68: 				sb.append(comma+array[i]);
jpayne@68: 				comma=", ";
jpayne@68: 			}
jpayne@68: 		}
jpayne@68: 		sb.append(']');
jpayne@68: 		return sb.toString();
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	public long[] toArray(){
jpayne@68: 		long[] x=new long[array.length];
jpayne@68: 		int i=0;
jpayne@68: 		for(long v : array){
jpayne@68: 			x[i]=v;
jpayne@68: 			i++;
jpayne@68: 		}
jpayne@68: 		return x;
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	/*----------------        Private Methods       ----------------*/
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	
jpayne@68: 	public boolean verify(){
jpayne@68: 		int numValues=0;
jpayne@68: 		int numFound=0;
jpayne@68: 		for(int i=0; i<array.length; i++){
jpayne@68: 			final long value=array[i];
jpayne@68: 			if(value!=invalid){
jpayne@68: 				numValues++;
jpayne@68: 				final int cell=findCell(value);
jpayne@68: 				if(i==cell){
jpayne@68: 					numFound++;
jpayne@68: 				}else{
jpayne@68: 					return false;
jpayne@68: 				}
jpayne@68: 			}
jpayne@68: 		}
jpayne@68: 		return numValues==numFound && numValues==size;
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	private void rehashFrom(int initial){
jpayne@68: 		if(size<1){return;}
jpayne@68: 		final int limit=array.length;
jpayne@68: 		for(int cell=initial+1; cell<limit; cell++){
jpayne@68: 			final long x=array[cell];
jpayne@68: 			if(x==invalid){return;}
jpayne@68: 			rehashCell(cell);
jpayne@68: 		}
jpayne@68: 		for(int cell=0; cell<initial; cell++){
jpayne@68: 			final long x=array[cell];
jpayne@68: 			if(x==invalid){return;}
jpayne@68: 			rehashCell(cell);
jpayne@68: 		}
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	private boolean rehashCell(final int cell){
jpayne@68: 		final long value=array[cell];
jpayne@68: 		assert(value!=invalid);
jpayne@68: 		if(value==invalid){resetInvalid();}
jpayne@68: 		final int dest=findCellOrEmpty(value);
jpayne@68: 		if(cell==dest){return false;}
jpayne@68: 		assert(array[dest]==invalid);
jpayne@68: 		array[cell]=invalid;
jpayne@68: 		array[dest]=value;
jpayne@68: 		return true;
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	private void resetInvalid(){
jpayne@68: 		final long old=invalid;
jpayne@68: 		long x=invalid;
jpayne@68: 		while(x==old || contains(x)){x=randy.nextLong()|MINMASK;}
jpayne@68: 		assert(x<0);
jpayne@68: 		invalid=x;
jpayne@68: 		for(int i=0; i<array.length; i++){
jpayne@68: 			if(array[i]==old){array[i]=invalid;}
jpayne@68: 		}
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	private int findCell(final long value){
jpayne@68: 		if(value==invalid){return -1;}
jpayne@68: 		
jpayne@68: 		final int limit=array.length, initial=(int)((value&MASK)%modulus);
jpayne@68: 		for(int cell=initial; cell<limit; cell++){
jpayne@68: 			final long x=array[cell];
jpayne@68: 			if(x==value){return cell;}
jpayne@68: 			if(x==invalid){return -1;}
jpayne@68: 		}
jpayne@68: 		for(int cell=0; cell<initial; cell++){
jpayne@68: 			final long x=array[cell];
jpayne@68: 			if(x==value){return cell;}
jpayne@68: 			if(x==invalid){return -1;}
jpayne@68: 		}
jpayne@68: 		return -1;
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	private int findCellOrEmpty(final long value){
jpayne@68: 		assert(value!=invalid) : "Collision - this should have been intercepted.";
jpayne@68: 		
jpayne@68: 		final int limit=array.length, initial=(int)((value&MASK)%modulus);
jpayne@68: 		for(int cell=initial; cell<limit; cell++){
jpayne@68: 			final long x=array[cell];
jpayne@68: 			if(x==value || x==invalid){return cell;}
jpayne@68: 		}
jpayne@68: 		for(int cell=0; cell<initial; cell++){
jpayne@68: 			final long x=array[cell];
jpayne@68: 			if(x==value || x==invalid){return cell;}
jpayne@68: 		}
jpayne@68: 		throw new RuntimeException("No empty cells - size="+size+", limit="+limit);
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	public final void resizeDestructive(int newSize){
jpayne@68: 		size=0;
jpayne@68: 		sizeLimit=0;
jpayne@68: 		array=null;
jpayne@68: 		resize(newSize);
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	private final void resize(){
jpayne@68: 		assert(size>=sizeLimit);
jpayne@68: 		resize(array.length*2L+1);
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	private final void resize(final long size2){
jpayne@68: 		assert(size2>size) : size+", "+size2;
jpayne@68: 		
jpayne@68: 		//This is supposed to be a prime but the primes code is ripped out in this version.
jpayne@68: 		//Any odd number is fine in most cases.
jpayne@68: 		long newPrime=size2|1;
jpayne@68: 		if(newPrime+extra>Integer.MAX_VALUE){
jpayne@68: 			newPrime=(Integer.MAX_VALUE-extra-2)|1;
jpayne@68: 		}
jpayne@68: 		assert(newPrime>modulus) : "Overflow: "+size+", "+size2+", "+modulus+", "+newPrime;
jpayne@68: 		modulus=(int)newPrime;
jpayne@68: 		
jpayne@68: 		final int size3=(int)(newPrime+extra);
jpayne@68: 		sizeLimit=(int)(modulus*loadFactor);
jpayne@68: 		final long[] old=array;
jpayne@68: 		array=new long[size3];
jpayne@68: 		Arrays.fill(array, invalid);
jpayne@68: 		
jpayne@68: //		System.err.println("Resizing "+(old==null ? "null" : ""+old.length)+" to "+size3);
jpayne@68: 		
jpayne@68: 		if(size<1){return;}
jpayne@68: 		
jpayne@68: 		size=0;
jpayne@68: 		for(long value : old){
jpayne@68: 			if(value!=invalid){
jpayne@68: 				add(value);
jpayne@68: 			}
jpayne@68: 		}
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	/*----------------      Stuff From BBTools      ----------------*/
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	
jpayne@68: 	public static final float mid(float x, float y, float z){
jpayne@68: 		return x<y ? (x<z ? min(y, z) : x) : (y<z ? min(x, z) : y);
jpayne@68: 	}
jpayne@68: 	public static final float min(float x, float y){return x<y ? x : y;}
jpayne@68: 	public static final float max(float x, float y){return x>y ? x : y;}
jpayne@68: 	
jpayne@68: 	/** Number of values that can be held without resizing */
jpayne@68: 	public int capacity(){
jpayne@68: 		return sizeLimit;
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	/*----------------            Fields            ----------------*/
jpayne@68: 	/*--------------------------------------------------------------*/
jpayne@68: 	
jpayne@68: 	private long[] array;
jpayne@68: 	private int size=0;
jpayne@68: 	/** Value for empty cells */
jpayne@68: 	private long invalid;
jpayne@68: 	private int modulus;
jpayne@68: 	private int sizeLimit;
jpayne@68: 	private final float loadFactor;
jpayne@68: 	
jpayne@68: 	private static final Random randy=new Random(1);
jpayne@68: 	private static final long MASK=Long.MAX_VALUE;
jpayne@68: 	private static final long MINMASK=Long.MIN_VALUE;
jpayne@68: 	
jpayne@68: 	private static final int extra=10;
jpayne@68: 	
jpayne@68: }