import java.util.Map;
import java.util.TreeMap;



/**
 * calculates the cost functions for a given query graph (ff - for a array of filter factors 
 * 2 dimensions
 * rel for the cardinality of the containing relations numbered from 1 to n (0 to n-1)
 * @author fender
 *
 */
public class CalculatePlan {
	private int card;
	private int cout;
	private long cnlj;
	private double chj;
	private double csmj;
	
	private String joinedRelations;
	
	private static float[][] ff;
	private static int[] rel;
	private static Map<Long, String> sortedOutput;

	
	/*
	 * returns the relations which are coded in a binary int
	 */
	public static String getRelationsMembers(int i) {
		String members = "";
		
		if(i<=0)
			return members;
		
		int limit = (int)(Math.log(i) / Math.log(2)) + 1;
		
		for(int c = 1; c <= limit; c ++ ) {
		    		
			if((i & (1 << (c - 1))) == (1 << (c - 1)))
				members += "R" + c + ":";
		}			
		return members.substring(0, members.length() - 1 );		
	}
	
	/*
	 * calculate the filter factor between left and right
	 */
	private static float getFilterFactor(int left, int right) {
		float filterFactor = 1.0f;
		int leftLimit = (int)(Math.log(left) / Math.log(2)) + 1;
		int rightLimit = (int)(Math.log(right) / Math.log(2)) + 1;
		
		for(int c = 1; c <= leftLimit; c ++ ) 
			if((left & (1 << (c - 1))) == (1 << (c - 1)))
				for(int d = 1; d <= rightLimit; d ++ ) 
					if((right & (1 << (d - 1))) == (1 << (d - 1))) {
						filterFactor *= ff[c-1][d-1];									
					}								
		return filterFactor;		
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {

	/*	
		ff = new float[3][3];
		ff[0][0] = 1.0f;
		ff[1][0] = 0.1f;
		ff[2][0] = 1.0f;
		
		ff[0][1] = 0.1f;
		ff[1][1] = 1.0f;
		ff[2][1] = 0.2f;
		
		ff[0][2] = 1.0f;
		ff[1][2] = 0.2f;
		ff[2][2] = 1.0f;
		
		rel = new int[3];
		rel[0] = 10;
		rel[1] = 100;
		rel[2] = 1000;
*/
		
		ff = new float[4][4];
		ff[0][0] = 1.0f;
		ff[1][0] = 0.1f;
		ff[2][0] = 0.4f;
		ff[3][0] = 1.0f;
		
		ff[0][1] = 0.1f;
		ff[1][1] = 1.0f;
		ff[2][1] = 0.2f;
		ff[3][1] = 1.0f;
		
		ff[0][2] = 0.4f;
		ff[1][2] = 0.2f;
		ff[2][2] = 1.0f;
		ff[3][2] = 0.1f;
		
		ff[0][3] = 1.0f;
		ff[1][3] = 1.0f;
		ff[2][3] = 0.1f;
		ff[3][3] = 1.0f;
		
		rel = new int[4];
		rel[0] = 10;
		rel[1] = 100;
		rel[2] = 1000;
		rel[3] = 25;
		
		sortedOutput = new TreeMap<Long, String>();
		
		// array of possible subsets (2^n) 		
		CalculatePlan[] subSets = new CalculatePlan[1 << rel.length]; 
			
		// initialisation run
		// ..
		for(int i = 0; i < rel.length; ++i) {
			// left shift with s digits = 2^i
			int plan = (1 << i);
			subSets[plan] = new CalculatePlan();
			subSets[plan].card = rel[i];	
			subSets[plan].joinedRelations = "R_" + (i + 1);
			
			subSets[plan].cnlj = 0;
			subSets[plan].chj = 0.0;
			subSets[plan].csmj = 0.0;
		}
		
		/*
		 * S1 = S & -S
		 * do {
		 *    S1 = S & (S1 - S)
		 * } while (S1 != S)
		 */
		for(int plan = 3; plan < (1 << rel.length); plan++) {
			for(int left= plan&(-plan); left!=0; left=plan&(left-plan)) {
				// Bitwise XOR --> returns the opostite set to left with 
				int right = left^plan;

				if (right == 0 || left == 0)
					continue;				
								
				if (subSets[plan] == null) {
					subSets[plan] = new CalculatePlan();
				
					subSets[plan].card = (int) (subSets[left].card * subSets[right].card * getFilterFactor(left, right));
				}
				
				int coutCurrent = subSets[plan].card + subSets[left].cout + subSets[right].cout;
				long cnljCurrent = subSets[left].card * subSets[right].card + subSets[left].cnlj + subSets[right].cnlj;
				
				// if join method is hash join, but there no connecting edges in the query graph --> calculation with Crossproduct (cnlj)
				double chjCurrent = getFilterFactor(left, right) == 1.0 ? subSets[left].card * subSets[right].card + subSets[left].chj + 
						subSets[right].chj : subSets[left].card * 1.2 + subSets[left].chj + subSets[right].chj;
				
				// if join method is sort merge join, but there no connecting edges in the query graph --> calculation with Crossproduct (cnlj)
				double csmjCurrent = getFilterFactor(left, right) == 1.0 ? subSets[left].card * subSets[right].card + subSets[left].csmj + 
						subSets[right].csmj : subSets[left].csmj + subSets[left].card * Math.log(subSets[left].card) / Math.log(2.0) 
					+ subSets[right].csmj + subSets[right].card * Math.log(subSets[right].card) / Math.log(2.0);
				
				if(coutCurrent < subSets[plan].cout || subSets[plan].cout == 0) {
					subSets[plan].cout = coutCurrent;
					subSets[plan].joinedRelations = "(" + subSets[left].joinedRelations + (getFilterFactor(left, right) == 1.0f ? " \\times " : " \\Join ") + subSets[right].joinedRelations + ")";
				}
				
				if(cnljCurrent < subSets[plan].cnlj || subSets[plan].cnlj == 0) 
					subSets[plan].cnlj = cnljCurrent;
				
				if(chjCurrent < subSets[plan].chj || subSets[plan].chj == 0) 
					subSets[plan].chj = chjCurrent;
				
				if(csmjCurrent < subSets[plan].csmj || subSets[plan].csmj == 0) 
					subSets[plan].csmj = csmjCurrent;
				
				// formated latex output
				String outputLine = "      $" + subSets[left].joinedRelations + (getFilterFactor(left, right) == 1.0f ? " \\times " : " \\Join ") + subSets[right].joinedRelations + "$"
					+ " & " + subSets[plan].card + " & " + coutCurrent + " & " + cnljCurrent + " & " + ((long)(chjCurrent)) + " & " + Math.floor(csmjCurrent * 100.0) / 100.0 + " \\\\";
				
				// number of ones (binary) (number of relations)
				int count = 0;
				for(int c = plan; c != 0; c = (c >> 1)) {
					if((c & 1) == 1)
						count++;
				}
				
				// number of ones (binary) of left side (number of relations)
				int countL = 0;
				for(int c = left; c != 0; c = (c >> 1)) {
					if((c & 1) == 1)
						countL++;
				}
				
				Long order = new Long( (long)Math.pow(10, count + 2) - (long)Math.pow(10, countL + 1) + left * 100 + right);				
				sortedOutput.put(order, outputLine);				
			}
		}
		
		for (String output : sortedOutput.values())
			System.out.println(output);
	}

}