// Copyright(c) 2006, Shinichi Morishita. All Rights Reserved.

public class Chapter3_LookupTables {

	
	public static int[] buildDirectAddressTable( int[] intTarget, int queryLen ){
		// Assume that the elements in intTarget are sorted. 
		int directTableLen = 1; // directTableLen is the queryLen-th power of 4.
		for(int i=0; i<queryLen; i++) directTableLen *= 4;
		directTableLen++; 
		// Initialize all elements in directTable to -1 
		int directTable[] = new int[directTableLen];
		for(int i=0; i<directTableLen; i++) directTable[i] = -1;		
		// Map all values in intTaget to directTable
		for(int i=0; i<intTarget.length; i++){
			if( !(intTarget[i] < directTableLen) ) return null;
			if(i == 0 || (0 < i && intTarget[i-1] < intTarget[i]))
				directTable[intTarget[i]] = i;
		}
		// Fill the remaining elements in directTable
		int nextIndex = intTarget.length;
		for(int i=directTableLen-1; 0 <= i; i--)
			if(directTable[i] == -1) directTable[i] = nextIndex;
			else nextIndex = directTable[i];	
		return directTable;
	}	
	public static void queryDirectAddressTable( 
			int[] directAddressTable, int[] posTarget, int intQuery ){
		if(directAddressTable == null) return;
		for(int i=directAddressTable[intQuery]; 
			i<directAddressTable[intQuery+1]; i++)
			System.out.print(posTarget[i]+"\t");
		System.out.println();
	}
	
	public static int[][] buildHashTable( int[] intTarget, int primeNumber ){		
		// Create and initialize hashTable.
		int hashTable[][] = new int[primeNumber][3];
		for(int i=0; i<primeNumber; i++) hashTable[i][0] = -1;	
		// Hash all elements in intTarget.
		int tLen = intTarget.length;
		for(int i=0, counter=1; i<tLen; i++, counter++){
			if(i == tLen-1 || (i < tLen-1 && intTarget[i] < intTarget[i+1])){
				// Scan hashTable until an available slot is found.
				int j = intTarget[i]%primeNumber;
				for(int k=0; hashTable[j][0] != -1; j = (j+1)%primeNumber, k++)
					if(primeNumber <= k) return null; // No empty slots are available.
				// Set the value, count, and start index to the empty slot.
				hashTable[j][0] = intTarget[i];
				hashTable[j][1] = counter;
				hashTable[j][2] = i-counter+1;
				counter = 0;
			}
		}	
		return hashTable;
	}
	
	public static void queryHashTable(int[][] hashTable, int[] posTarget, 
									  int intQuery, int primeNumber){
		for(int j=intQuery%primeNumber, 
			m=0; m<primeNumber && hashTable[j][0] != -1; j = (j+1)%primeNumber, m++)
			// Probe hashTable from the hash value of intTarget sequentially.
	         if(hashTable[j][0] == intQuery){
	            // If intQuery is found, scan posTarget to print 
	            // the contiguous block positions of intQuery.
				for(int k=hashTable[j][2]; k<hashTable[j][2]+hashTable[j][1]; k++)
					System.out.print(posTarget[k]+"\t");
				System.out.println();
				break;
			}
	}
	
	public static void sortIntTargetByCounting( int[] intTarget, int posTarget[], int queryLen ) {
		// Assume that the input intTarget is not sorted yet.
		// Set variable tableLen to the queryLen-th power of 4
		int tableLen = 1;
		for(int i=0; i<queryLen; i++) tableLen *= 4;		
		// Count the frequency and the cumulation for each integer representation.
		int[] frequency = new int[tableLen];
		for(int i=0; i<tableLen; i++)		frequency[i] = 0;
		int intTargetLen = intTarget.length;
		for(int i=0; i<intTargetLen; i++) // Exit if intTarget[i] >= tableLen.  
			if(intTarget[i] < tableLen) frequency[intTarget[i]]++; else return;
		int[] cumulation = frequency;  // Reuse the frequency table space.
		for(int i=1; i<tableLen; i++)
			cumulation[i] = cumulation[i-1] + frequency[i];
		// Adjust to zero-origin indexing.
		for(int i=0; i<tableLen; i++) cumulation[i]--; 
		// Generate posTarget and another instance of intTarget named intTarget1
		int intTargetSorted[] = new int[intTargetLen];
		for(int i = intTargetLen-1; 0 <= i; i--){
			intTargetSorted[cumulation[intTarget[i]]] = intTarget[i];
			posTarget[cumulation[intTarget[i]]] = i;
			cumulation[intTarget[i]]--;
		}
		for(int i=0; i<intTargetLen; i++)
			intTarget[i] = intTargetSorted[i];
	}	
	
	
	
// 	Subroutines defined in Chapter 1.	
	public static int[] generateIntTarget( int[] target, int queryLen){
		// Exit if the target is shorter than the query.
		if(target.length < queryLen) return null; 		
		int intTargetLen = target.length-queryLen+1;
		int[] intTarget = new int[intTargetLen];
		// Generate intTarget array.
		int tmp = 0;
		int encode = 1;
		for(int i = 0; i < intTargetLen; i++){
			if(i == 0){ // Initialize variables.
				for(int j=0; j<queryLen; j++){
					tmp = 4*tmp + target[j];	
					encode = encode*4;
				}				
			}else // Compute the next value of tmp from the previous value.
				tmp = 4*tmp- encode*target[i-1] + target[i+queryLen-1] ;
			intTarget[i] = tmp;
		}
		return intTarget;
	}	
	public static int generateIntQuery(int[] query){
		int intQuery = 0;
		for(int i = 0; i < query.length; i++) intQuery = 4*intQuery + query[i];
		return intQuery;
	}
	
	public static int[] nucleotides2IntArray(String targetString){
		int targetLen = targetString.length();
		int[] targetIntArray = new int[targetLen];
		for(int i = 0; i < targetLen; i++)
			targetIntArray[i] = encode_char(targetString.charAt(i));
		return targetIntArray;
	}
	
	public static int encode_char( char c ){
		switch (c){
		case 'A':	return 0;
		case 'C':	return 1;
		case 'G':	return 2;
		case 'T':	return 3;
		default:	return -1;
		}
	}	

	public static int[] generateRandomNumbers(int targetLen){
		// Generate an array in which elements are selected from {0,1,2,3} at random.
		int[] target = new int[targetLen];
		for(int i=0; i<targetLen; i++) target[i] = (int)(Math.random()*4);
		return target;
	}
	
	public static void main(String[] args) {
		int[] target, query;

		target = nucleotides2IntArray("ATAATACGATAATAA");
		query  = nucleotides2IntArray("ATAA");

		
//		target = nucleotides2IntArray("AAAAAAATTTTTTT");
//		query  = nucleotides2IntArray("AAAA");
//		query  = nucleotides2IntArray("TTTT");
		
		// Generate the target and query at random. 
//		target = generateRandomNumbers(500000);
//		query  = generateRandomNumbers(8);		

		if(target.length < query.length){
			System.out.println("The target is shorter than the query.");
			return;
		}
		
		// Generate k-mer integer representations of target and query.
		int[] intTarget = generateIntTarget(target, query.length);
		int intQuery = generateIntQuery(query);
		
		// Sort elements in intTarget and memorize original positions in posTarget.
		int[] posTarget = new int[intTarget.length];
		sortIntTargetByCounting(intTarget, posTarget, query.length);
		
		// Generate the direct-address table.
		int[] directAddressTable = buildDirectAddressTable(intTarget, query.length);
		System.out.println("direct address table");
		queryDirectAddressTable(directAddressTable, posTarget, intQuery);
		
		//�@Generate the hash table.
		int primeNumber = 524287;  // Try 5 to see the failure of producing a hash table.
		    // 8,191 (2^13-1) 131,071 (2^17-1) 524,287 (2^19-1) 39,916,801 (11!+1) 479,001,599 (12!-1)
		int[][] hashTable = buildHashTable(intTarget, primeNumber);
		if(hashTable == null){
			System.out.println("Failure to produce a hash table.");
			return;
		}
		System.out.println("hash table");
		queryHashTable(hashTable, posTarget, intQuery, primeNumber);
		
	}
	
	
}