jpayne@68: package bloom;
jpayne@68: 
jpayne@68: import java.util.Locale;
jpayne@68: 
jpayne@68: /**
jpayne@68:  * @author Brian Bushnell
jpayne@68:  * @date Jul 5, 2012
jpayne@68:  */
jpayne@68: public class KCountArray2 {
jpayne@68: 	
jpayne@68: 	public static void main(String[] args){
jpayne@68: 		KCountArray2 kca=new KCountArray2(1024, 16);
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	public KCountArray2(long cells_, int bits_){
jpayne@68: 		this(cells_, bits_, 0);
jpayne@68: 	}
jpayne@68: 		
jpayne@68: 	public KCountArray2(long cells_, int bits_, int gap_){
jpayne@68: 		gap=gap_;
jpayne@68: 		assert(bits_<=32);
jpayne@68: 		assert(Integer.bitCount(bits_)==1);
jpayne@68: 		assert(Long.bitCount(cells_)==1);
jpayne@68: 		
jpayne@68: 		while(bits_*cells_<32*numArrays){
jpayne@68: 			assert(false);
jpayne@68: 			bits_*=2;
jpayne@68: 		} //Increases bits per cell so that at minimum each array is size 1
jpayne@68: 		
jpayne@68: 		assert(bits_!=32);
jpayne@68: 		
jpayne@68: 		cells=cells_;
jpayne@68: 		cellBits=bits_;
jpayne@68: 		valueMask=~((-1)<<cellBits);
jpayne@68: 		maxValue=min(Integer.MAX_VALUE, ~((-1)<<min(cellBits,31)));
jpayne@68: 		cellsPerWord=32/cellBits;
jpayne@68: 		indexShift=Integer.numberOfTrailingZeros(cellsPerWord);
jpayne@68: 		long words=cells/cellsPerWord;
jpayne@68: 		int wordsPerArray=(int)(words/numArrays);
jpayne@68: 		matrix=new int[numArrays][wordsPerArray];
jpayne@68: 		
jpayne@68: 		if(verbose){
jpayne@68: 			System.out.println("cells:   \t"+cells);
jpayne@68: 			System.out.println("cellBits:\t"+cellBits);
jpayne@68: 			System.out.println("valueMask:\t"+Long.toHexString(valueMask));
jpayne@68: 			System.out.println("maxValue:\t"+maxValue);
jpayne@68: 			System.out.println("cellsPerWord:\t"+cellsPerWord);
jpayne@68: 			System.out.println("indexShift:\t"+indexShift);
jpayne@68: 			System.out.println("words:   \t"+words);
jpayne@68: 			System.out.println("wordsPerArray:\t"+wordsPerArray);
jpayne@68: 			System.out.println("numArrays:\t"+numArrays);
jpayne@68: 
jpayne@68: 
jpayne@68: 			long mem=words*4;
jpayne@68: 			if(mem<(1<<30)){
jpayne@68: 				System.out.println("memory:   \t"+String.format(Locale.ROOT, "%.2f MB", mem*1d/(1<<20)));
jpayne@68: 			}else{
jpayne@68: 				System.out.println("memory:   \t"+String.format(Locale.ROOT, "%.2f GB", mem*1d/(1<<30)));
jpayne@68: 			}
jpayne@68: 		}
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	public int read(long key){
jpayne@68: //		System.out.println("key="+key);
jpayne@68: 		int arrayNum=(int)(key&arrayMask);
jpayne@68: //		System.out.println("array="+arrayNum);
jpayne@68: 		key>>>=arrayBits;
jpayne@68: //		System.out.println("key2="+key);
jpayne@68: 		int[] array=matrix[arrayNum];
jpayne@68: 		int index=(int)(key>>>indexShift);
jpayne@68: //		System.out.println("index="+index);
jpayne@68: 		int word=array[index];
jpayne@68: //		System.out.println("word="+Integer.toHexString(word));
jpayne@68: 		int cellShift=(int)(cellBits*key);
jpayne@68: //		System.out.println("cellShift="+cellShift);
jpayne@68: 		return (int)((word>>>cellShift)&valueMask);
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	public void write(long key, int value){
jpayne@68: 		int arrayNum=(int)(key&arrayMask);
jpayne@68: 		key>>>=arrayBits;
jpayne@68: 		int[] array=matrix[arrayNum];
jpayne@68: 		int index=(int)(key>>>indexShift);
jpayne@68: 		int word=array[index];
jpayne@68: 		int cellShift=(int)(cellBits*key);
jpayne@68: 		word=(value<<cellShift)|(word&~((valueMask)<<cellShift));
jpayne@68: 		array[index]=word;
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	public int increment(long key, int incr){
jpayne@68: 		int arrayNum=(int)(key&arrayMask);
jpayne@68: 		key>>>=arrayBits;
jpayne@68: 		int[] array=matrix[arrayNum];
jpayne@68: 		int index=(int)(key>>>indexShift);
jpayne@68: 		int word=array[index];
jpayne@68: 		int cellShift=(int)(cellBits*key);
jpayne@68: 		int value=((word>>>cellShift)&valueMask);
jpayne@68: 		if(value==0 && incr>0){cellsUsed++;}
jpayne@68: 		else if(incr<0 && value+incr==0){cellsUsed--;}
jpayne@68: 		value=min(value+incr, maxValue);
jpayne@68: 		word=(value<<cellShift)|(word&~((valueMask)<<cellShift));
jpayne@68: 		array[index]=word;
jpayne@68: 		return (int)value;
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	/** Returns unincremented value */
jpayne@68: 	public int increment2(long key, int incr){
jpayne@68: 		int arrayNum=(int)(key&arrayMask);
jpayne@68: 		key>>>=arrayBits;
jpayne@68: 		int[] array=matrix[arrayNum];
jpayne@68: 		int index=(int)(key>>>indexShift);
jpayne@68: 		int word=array[index];
jpayne@68: 		int cellShift=(int)(cellBits*key);
jpayne@68: 		final int value=((word>>>cellShift)&valueMask);
jpayne@68: 		final int value2=min(value+incr, maxValue);
jpayne@68: 		word=(value2<<cellShift)|(word&~((valueMask)<<cellShift));
jpayne@68: 		array[index]=word;
jpayne@68: 		return value;
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	public long[] transformToFrequency(){
jpayne@68: 		long[] freq=new long[100000];
jpayne@68: 		int maxFreq=freq.length-1;
jpayne@68: 
jpayne@68: 		if(cellBits!=32){
jpayne@68: 			assert(cellBits>0);
jpayne@68: 			for(int[] array : matrix){
jpayne@68: 				for(int i=0; i<array.length; i++){
jpayne@68: 					int word=array[i];
jpayne@68: 					int j=cellsPerWord;
jpayne@68: 					//				System.out.println("initial: word = "+word+", j = "+Integer.toHexString(j)+", cellbits="+cellBits);
jpayne@68: 					for(; word!=0; j--){
jpayne@68: 						int x=word&valueMask;
jpayne@68: 						int x2=(int)min(x, maxFreq);
jpayne@68: 						freq[x2]++;
jpayne@68: 						word=(word>>>cellBits);
jpayne@68: 						//					System.out.println("word = "+word+", j = "+Integer.toHexString(j)+", cellbits="+cellBits);
jpayne@68: 					}
jpayne@68: 					freq[0]+=j;
jpayne@68: 				}
jpayne@68: 			}
jpayne@68: 		}else{
jpayne@68: 			for(int[] array : matrix){
jpayne@68: 				for(int i=0; i<array.length; i++){
jpayne@68: 					int word=array[i];
jpayne@68: 					int x2=(int)min(word, maxFreq);
jpayne@68: 					freq[x2]++;
jpayne@68: 				}
jpayne@68: 			}
jpayne@68: 		}
jpayne@68: 		return freq;
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	@Override
jpayne@68: 	public String toString(){
jpayne@68: 		StringBuilder sb=new StringBuilder();
jpayne@68: 		sb.append("[");
jpayne@68: 		String comma="";
jpayne@68: 		for(int[] array : matrix){
jpayne@68: 			for(int i=0; i<array.length; i++){
jpayne@68: 				int word=array[i];
jpayne@68: 				for(int j=0; j<cellsPerWord; j++){
jpayne@68: 					int x=word&valueMask;
jpayne@68: 					sb.append(comma);
jpayne@68: 					sb.append(x);
jpayne@68: 					word>>>=cellBits;
jpayne@68: 					comma=", ";
jpayne@68: 				}
jpayne@68: 			}
jpayne@68: 		}
jpayne@68: 		sb.append("]");
jpayne@68: 		return sb.toString();
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	public double usedFraction(){return cellsUsed/(double)cells;}
jpayne@68: 	
jpayne@68: 	public double usedFraction(int mindepth){return cellsUsed(mindepth)/(double)cells;}
jpayne@68: 	
jpayne@68: 	public long cellsUsed(int mindepth){
jpayne@68: 		long count=0;
jpayne@68: 		for(int[] array : matrix){
jpayne@68: 			if(array!=null){
jpayne@68: 				for(int word : array){
jpayne@68: 					while(word>0){
jpayne@68: 						int x=word&valueMask;
jpayne@68: 						if(x>=mindepth){count++;}
jpayne@68: 						word>>>=cellBits;
jpayne@68: 					}
jpayne@68: 				}
jpayne@68: 			}
jpayne@68: 		}
jpayne@68: 		return count;
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	public String mem(){
jpayne@68: 		long mem=(cells*cellBits)/8;
jpayne@68: 		if(mem<(1<<20)){
jpayne@68: 			return (String.format(Locale.ROOT, "%.2f KB", mem*1d/(1<<10)));
jpayne@68: 		}else if(mem<(1<<30)){
jpayne@68: 			return (String.format(Locale.ROOT, "%.2f MB", mem*1d/(1<<20)));
jpayne@68: 		}else{
jpayne@68: 			return (String.format(Locale.ROOT, "%.2f GB", mem*1d/(1<<30)));
jpayne@68: 		}
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	public static final int min(int x, int y){return x<y ? x : y;}
jpayne@68: 	public static final int max(int x, int y){return x>y ? x : y;}
jpayne@68: 	public static final long min(long x, long y){return x<y ? x : y;}
jpayne@68: 	public static final long max(long x, long y){return x>y ? x : y;}
jpayne@68: 	
jpayne@68: 	private long cellsUsed;
jpayne@68: 	
jpayne@68: 	public final long cells;
jpayne@68: 	public final int cellBits;
jpayne@68: 	public final int maxValue;
jpayne@68: 	public final int gap; //Set this for convenience on gapped tables to make sure you're using the right table.
jpayne@68: 	
jpayne@68: 	private final int cellsPerWord;
jpayne@68: 	private final int indexShift;
jpayne@68: 	private final int valueMask;
jpayne@68: 	private final int[][] matrix;
jpayne@68: 	
jpayne@68: 	private static final int arrayBits=2;
jpayne@68: 	private static final int numArrays=1<<arrayBits;
jpayne@68: 	private static final int arrayMask=numArrays-1;
jpayne@68: 	
jpayne@68: 	public static boolean verbose=false;
jpayne@68: 	
jpayne@68: 	
jpayne@68: }