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

public class Chapter1_SimpleStringSearch {

	// Brute-force search
	public static void bruteSearch(	int[] target, int[] query ) {
		// "target.length" returns the size of the array target.
		int targetLen = target.length;	
		int queryLen = query.length;		
		for(int i = 0; i + queryLen <= targetLen; i++){ // i++ means i=i+1.
			int j = 0;
			while(j < queryLen && target[i+j] == query[j])
				j = j+1;
			if(j == queryLen)
				System.out.print(i+" ");
		}
		System.out.println();
	}	
	
	// Brute-force search with integers
	public static void intBruteSearch( int[] target, int[] query ) {
		// Exit if the target is shorter than the query.
		if(target.length < query.length) return; 
		// Generate k-mer integer representations of the target and query.
		int[] intTarget = generateIntTarget(target, query.length);
		int intQuery = generateIntQuery(query);
		// Search intTarget for the query.
		for(int i = 0; i < intTarget.length; i++)
			if(intTarget[i] == intQuery) System.out.print(i+" ");
		System.out.println();
	}
	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;
	}

	// Binary search 
	public static void binarySearch( int[] target,  int[] query ){
		// Exit if the target is shorter than the query.
		if(target.length < query.length) 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 the original positions in posTarget.
		int targetLen = intTarget.length;
		int[] posTarget = new int[targetLen];
		for(int i=0; i<targetLen; i++) posTarget[i]=i;
		randomQuickSort(intTarget, posTarget, 0, targetLen-1);
		// Search for the block of occurrences of intQuery.
		int left, right, middle;		
		// Search for the left boundary. 
		for(left=0, right=targetLen; left < right; ){ 
			middle = (left + right) / 2;
			if( intTarget[middle] < intQuery) left = middle + 1;
			else right = middle;	
		}
		int leftBoundary = left;
		// Search for the right boundary. 
		// We use "right" to approach the index next to the right boundary.  
		for(left=0, right=targetLen; left < right; ){ 
			middle = (left + right) / 2;  
			if( intTarget[middle] <= intQuery ) left = middle + 1; 
			else right = middle; 	
		}
		// Print positions in the range between the two boundaries.
		for(int i = leftBoundary; i < right; i++)
			System.out.print(posTarget[i]+" ");
		System.out.println();
	}	
	
	// A variant of binary search such that left < leftBoundary <= right
	public static void binarySearch_variant( int[] target,  int[] query ){
		// Exit if the target is shorter than the query.
		if(target.length < query.length) 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 the original positions in posTarget.
		int targetLen = intTarget.length;
		int[] posTarget = new int[targetLen];
		for(int i=0; i<targetLen; i++) posTarget[i]=i;
		randomQuickSort(intTarget, posTarget, 0, targetLen-1);
		// Exit if the query is outside the scope.
		if(intQuery < intTarget[0] || intTarget[targetLen-1] < intQuery) return;			
		// Search for the left boundary. Check if the query occurs in the first position.
		int left, right, middle, leftBoundary, rightBoundary;
		if(intQuery == intTarget[0]) leftBoundary = 0;	
		else{
			for(left=0, right=targetLen-1; left+1 < right; ){ 
				middle = (left + right) / 2;
				if( intTarget[middle] < intQuery) left = middle;
				else right = middle;	
			}		
			if(intTarget[right] == intQuery) leftBoundary = right;
			else return;	// No occurrences of intQuery.
		}
		// Search for the right boundary. Check if the query occurs in the last position.
		if(intQuery == intTarget[targetLen-1]) rightBoundary = targetLen-1;
		else{
			for(left=0, right=targetLen-1; left+1 < right; ){ 
				middle = (left + right) / 2;  
				if( intQuery < intTarget[middle] ) right = middle; 
				else left = middle; 	
			}
			rightBoundary = left;
		}
		// Print the two boundaries.
		for(int i=leftBoundary; i<=rightBoundary; i++)
			System.out.print(posTarget[i]+" ");
		System.out.println();
	}
				
	public static void randomQuickSort(int[] target, int[] posTarget, int left, int right ) {
		if (left < right) {
			int i = partition(target, posTarget, left, right);
			randomQuickSort(target, posTarget, left, i - 1);
			randomQuickSort(target, posTarget, i + 1, right);
		}
	}
	
	public static int partition( int[] target, int[] posTarget, int left, int right ) {
		// Select a number between left and right at random using the java Math library.
		int random = left + (int)Math.floor(Math.random()*(right-left+1));
		// Exchange target[r] and target[random].
		int tmp = target[right];  target[right] = target[random];  target[random] = tmp;
		tmp = posTarget[right];  posTarget[right] = posTarget[random];  posTarget[random] = tmp;
		
		int pivot = target[right];
		int i = left-1;   // i scans the array from the left.
		int j = right; 	  // j scans the array from the right. 		
		for (;;) {
			// Move from the left until hitting a value >= pivot. 
			for(i++; target[i] < pivot; i++){} 
			// Move from the right until hitting a value =< pivot.
			for(j--; pivot < target[j] && i < j; j--){}
			if (i >= j)  break; 
			// Exchange a[i] and a[j]. 
			tmp = target[i];  target[i] = target[j];  target[j] = tmp;
			tmp = posTarget[i];  posTarget[i] = posTarget[j];  posTarget[j] = tmp;
		}
		// Exchange a[i] and a[r]. 
		tmp = target[i];  target[i] = target[right];  target[right] = tmp;
		tmp = posTarget[i];  posTarget[i] = posTarget[right];  posTarget[right] = tmp;		
		return i;
	}

	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");
//		target = nucleotides2IntArray("");		
//		query  = nucleotides2IntArray("AA");
		
		// Generate the target and query at random.
//		target = generateRandomNumbers(500000);
//		query  = generateRandomNumbers(8);		
		
		// Perform brute-force search.
		System.out.println("Perform brute-force search.");
		bruteSearch(target, query);	
		
		// Perform brute-force search while generating k-mer integers.
		System.out.println("Perform brute-force search while generating k-mer integers.");	
		intBruteSearch(target, query);
		
		// Perform binary search.
		System.out.println("Perform binary search.");
		binarySearch(target, query);
	}
		
}