package combinations;

import java.util.Vector;
import java.util.HashSet;

public class Driver {
	
	int numberOfFields;
	
	int fieldLength;
	
	int bitsConstrained;
	
	int count;
	
	Vector<Integer> fieldLengthCollection;
	
	Vector<Integer> bitsConstrainedCollection;
	
	Vector<Integer> countCollection;
	
	Vector<String> uniqueCombos;
	
	Vector<String> allCombos;
	
	int numberRows;
	
	public Driver(){
		
		numberOfFields = 5;
		
		fieldLength = -1;
		
		bitsConstrained = -1;
		
		count = -1;
		
		fieldLengthCollection = new Vector<Integer>();
		
		bitsConstrainedCollection = new Vector<Integer>();
		
		countCollection = new Vector<Integer>();
		
		uniqueCombos = new Vector<String>();
		
		allCombos = new Vector<String>();
		
		numberRows = -1;
		
	}

	public Vector<String> getCombo_AllBitsConstrained( int fieldLength ){
		
		Vector<String> combos = new Vector<String>();
		
		String combo = "";
		
		for(int i=0; i<2; i++){
		
			for(int j=0; j<fieldLength; j++){
			
				if( i == 0 )
					combo += "0";
				else
					combo += "1";
			
			}
			
			combos.add( combo );
			combo = new String();
			
		}
		
		return combos;
		
	}
	
	public int getCount_AllBitsConstrained( int fieldLength ){
		
		Vector<String> combos = getCombo_AllBitsConstrained( fieldLength );
	
		return combos.size();
		
	}
	
	public int convertBinaryToInt( String binaryString ){
		
		double sum = 0.0d;
		
		int binaryStringLength = binaryString.length();
		
		int bitIndexStart = -1;
		int bitIndexEnd = -1;
		
		
		for(int i=0; i<binaryStringLength; i++){
			
			bitIndexEnd = binaryStringLength - i;
			bitIndexStart = binaryStringLength - (i+1);
			
			//System.out.println( "binaryString.substring( start("+bitIndexStart+"), e("+bitIndexEnd+") ): " + binaryString.substring( i, i+1 ) );
			
			if( new Integer( binaryString.substring( bitIndexStart, bitIndexEnd ) ).intValue() > 0 )
				sum += Math.pow( 2.0, (double)i );
			
			//System.out.println( "sum: " + sum );
			
			
		}
		
		return (int)sum;
		
	}
	
	public Vector<String> generateBinaryStrings( int fieldSize, int numberStrings ){
		
		Vector<String> binaryStrings = new Vector<String>();
		
		String binaryString = null;
		
		String padString = null;
		
		int numberOfPadDigits = 0;
		
		for(int i=0; i<numberStrings; i++){
			
			binaryString = Integer.toBinaryString( i );
			
			//System.out.println( "binaryString: " + binaryString );
			
			if( binaryString.length() < fieldSize ){
				
				padString = new String();
				numberOfPadDigits = ( fieldSize - binaryString.length() );
				for(int j=0; j<numberOfPadDigits;j++)
					padString += "0";

				// add the padding to the binary string ..
				padString += binaryString;
				
				//System.out.println( "padString: " + padString );
				
				// update with the new padded version ..
				binaryString = padString;
				
			}
			
			//System.out.println( "unconstrained bit combo: " + binaryString );
			
			// add to the collection ..
			binaryStrings.add( binaryString );

		}
		
		return binaryStrings;
		
	}
	
	public void makeCombos_SomeBitsConstrained( int fieldLength, int bitsConstrained ){
		
		uniqueCombos = new Vector<String>();
		allCombos = new Vector<String>();
		
		String combo = "";
		
		numberRows = fieldLength - bitsConstrained + 1;
		
		//System.out.println( "numberRows: " + numberRows );
		
		int numberCombosPerRow = (int) Math.pow( 2.0, ((double)numberRows) );
		
		// (i.e.: 2 bits constrained, 4 combos
		// (      1nn => 1[00], 1[01], 1[10], 1[11] => 4 = pow(2, bits),
		//        where these "bit combos" will repeat in a row (but only one repeat needed)
		// (i.e.: 0nn => 0[00], 0[01], 0[10], 0[11] is the rest of the row) ..
		int unconstrainedBitFieldSize = ( fieldLength - bitsConstrained );
		
		int numberUnconstrainedBitCombosPerRow = (int) Math.pow( 2.0, ( (double)unconstrainedBitFieldSize ) );
		
		// generate the portion of the binary strings that are "unconstrained" ..
		/*
		int unconstrainedCount = 0;
		Vector<String> unconstrainedStrings = new Vector<String>();
		for(int i=0; i<numberUnconstrainedBitCombosPerRow; i++){
			
			System.out.println( "unconstrained bit combos: " + Integer.toBinaryString( unconstrainedCount ) );
			
			unconstrainedStrings.add( Integer.toBinaryString( unconstrainedCount++ ) );

		*/
		Vector<String> unconstrainedStrings = generateBinaryStrings( unconstrainedBitFieldSize, numberUnconstrainedBitCombosPerRow );
		
		String constrainedBit = "";
		
		String unconstrainedBitsLeft = "";
		String constrainedBits = null;
		String unconstrainedBitsRight = "";
		
		int unconstrainedBitsIndexStart = -1;
		int unconstrainedBitsIndexEnd = -1;
		int unconstrainedStringIndex = -1;
		
		String unconstrainedStringLeft = "";
		String unconstrainedStringRight = "";
		
		// number of "rows" ..
		for(int i=0; i<numberRows; i++){
		
			// number of combos per "row" ..
			for(int j=0; j<numberCombosPerRow; j++){
				
				// a single combo ..
				
				// 1st row, #left_bits = null, 2nd row, #left_bits = 1, etc ..
				// 1st row, #right_bits = total, 2nd row, #right_bits = total - 1, etc ..
				unconstrainedBitsIndexStart = 0;
				// row i=0 => 00nn => 00[00], 00[01], 00[10], 00[11] ..
				// row i=1 => n00n => 0[00]0, 0[00]1, 1[00]0, 1[00]1 ..
				// row i=2 => nn00 => 00[00], 01[00], 10[00], 11[00] ..
				// leftString = substring(0, i)       => i=0 is 00,   i=1 is 0, i=2 is null
				// rightString = substring(i, length) => i=0 is null, i=1 is 0, i=2 is 00
				unconstrainedBitsIndexEnd = i;
				
				// index repeats after "numberUnconstrainedBitCombosPerRow" times ..
				unconstrainedStringIndex = j % numberUnconstrainedBitCombosPerRow;
				
				//System.out.println( "   unconstrainedStringIndex: " + unconstrainedStringIndex );
				//System.out.println( "unconstrainedBitsIndexStart: " + unconstrainedBitsIndexStart );
				//System.out.println( "  unconstrainedBitsIndexEnd: " + unconstrainedBitsIndexEnd );
				
				unconstrainedStringLeft = unconstrainedStrings.get( unconstrainedStringIndex );
				unconstrainedBitsLeft = unconstrainedStringLeft.substring( unconstrainedBitsIndexStart, unconstrainedBitsIndexEnd );

				unconstrainedStringRight = unconstrainedStrings.get( unconstrainedStringIndex );
				unconstrainedBitsRight = unconstrainedStringRight.substring( unconstrainedBitsIndexEnd, unconstrainedStringRight.length() );
				
				//System.out.println( "unconstrainedStringRight.length(): " + unconstrainedStringRight.length() );
				
				//System.out.println( "unconstrainedBitsLeft: " + unconstrainedBitsLeft +", unconstrainedBitsRight: " + unconstrainedBitsRight );
				
				// generate a combination ..
				// combo = constrained bits + unconstrained bits
				// more specifically,
				// combo = unconstrained bits (left) + constrained bits + unconstrained bits (right)
				// (where "left" and "right" have 0 or more bits) ..
				constrainedBits = new String();
				constrainedBits += unconstrainedBitsLeft;
				
				// 1st half of # of combos, bits = 0, other half bits = 1 ..
				// (i.e.: 0[00], 1[00], 0[11], 1[11] with numberCombosPerRow = 4) ..
				if( j >= (numberCombosPerRow/2) )
					constrainedBit = "1";
				else
					constrainedBit = "0";
				
				// add in the "constrained bits" to the total ..
				for(int k=0; k<bitsConstrained; k++)
					constrainedBits += constrainedBit;
				
				constrainedBits += unconstrainedBitsRight;
				
				//System.out.println( "constrainedBits: " + constrainedBits );
				
				// point "combo" to the constructed bits ..
				combo = constrainedBits;
				
				// only add this combo if it is not a duplicate ..
				if( uniqueCombos.contains( combo ) == false )
					uniqueCombos.add( combo );
				
				allCombos.add( combo );
			
			}
			
		}
		
	}
	
	public int getCount_SomeBitsConstrained( int fieldLength, int bitsConstrained ){
		
		makeCombos_SomeBitsConstrained( fieldLength, bitsConstrained );
	
		return getUniqueCombos().size();
		
	}
	
	public Vector<String> getUniqueCombos(){
		
		return uniqueCombos;
		
	}
	
	public Vector<String> getAllCombos(){
		
		return allCombos;
		
	}
	
	public void printAllCombos( Vector<String> combos ){
		
		int numberCombosPerRow = combos.size() / numberRows;
		
		int comboIndex = -1;
		
		for(int i=0; i<numberRows; i++){
			
			for(int j=0; j<numberCombosPerRow; j++){
				
				//     j = 0 1 2  (numberCombosPerRow=3)
				//    ===========
				// i=0     0 1 2
				// i=1     3 4 5  <= comboIndex
				// i=2     6 7 8
				comboIndex = ( (i * numberCombosPerRow ) + j );
				
				System.out.print( combos.get( comboIndex ) );
				
				if( j<(numberCombosPerRow-1)  )
					System.out.print( ", " );
				else
					System.out.println();
				
			}
			
		}
		
	}
	
	public void printCombos( Vector<String> combos ){
		
		// print "combos" out as a single line ..
		
		int numberCombos = combos.size();
		
		for(int i=0; i<numberCombos; i++){
				
			System.out.print( combos.get( i ) );
				
			if( i<(numberCombos-1)  )
				System.out.print( ", " );
			else
				System.out.println();
			
		}
		
	}
	
	public void printUniqueCombos( Vector<String> allCombos ){
		
		HashSet uniqueCombosFound = new HashSet();
		
		int numberCombosPerRow = allCombos.size() / numberRows;
		
		int numberUniqueCombosPerRow = -1;
		
		int numberUniqueRows = numberRows;
		
		if( uniqueCombos.size() < allCombos.size() ){
			
			// this means that there are fewer unique combos than the total number
			// in the collection "allCombos" ..
			
			// if the unique combos dont even fill up 1 row, 
			// just se its size as the row length ..
			if( uniqueCombos.size() < numberCombosPerRow )
				numberUniqueCombosPerRow = uniqueCombos.size();
			
		}
		
		int comboIndex = -1;
		
		int comboLength = -1;
		
		String combo = null;
		String comboPlaceHolder = new String();
		String comboPlaceHolderDigit = "x";
		
		for(int i=0; i<numberUniqueRows; i++){
			
			for(int j=0; j<numberUniqueCombosPerRow; j++){
				
				//     j = 0 1 2  (numberCombosPerRow=3)
				//    ===========
				// i=0     0 1 2
				// i=1     3 4 5  <= comboIndex
				// i=2     6 7 8
				comboIndex = ( (i * numberCombosPerRow ) + j );
				
				combo = allCombos.get( comboIndex );
				
				// create the "comboPlaceHolder" only once ..
				// (we know how long it is when we look at the first "combo" ..
				if( comboLength < 0 ) {
					
					comboLength = combo.length();
					for(int k=0; k<comboLength; k++)
						comboPlaceHolder += comboPlaceHolderDigit;
					
				}
				
				if( uniqueCombosFound.contains( combo ) == false ) {
					
					System.out.print( combo );
					
					// track this combo so we only print it once ..
					uniqueCombosFound.add( combo );
					
				} else {
					
					// placeholder for the non-unique combo
					// (duplicates are not printed, 
					//  but rather a placeholder is printed) ..
					System.out.print( comboPlaceHolder );
					
				}
					
				if( j<(numberCombosPerRow-1)  )
					System.out.print( ", " );
				else
					System.out.println();
				
			}
			
		}
		
	}
	
	public static void main(String[] args){
		
		Driver d = new Driver();
		
		//int value = d.convertBinaryToInt( "10000" );
		//System.out.println( "value: " + value );
		
		int bitsConstrained = 3;
		int fieldLength = 6;

		
		//int count = d.getCount_SomeBitsConstrained( fieldLength, bitsConstrained );
		
		d.makeCombos_SomeBitsConstrained( fieldLength, bitsConstrained );
		
		Vector<String> uniqueCombos = d.getUniqueCombos();
		
		System.out.println( "count: " + uniqueCombos.size() );
		
		Vector<String> allCombos = d.getAllCombos();
		
		//d.printAllCombos( allCombos );
		//d.printCombos( allCombos );
		d.printUniqueCombos( uniqueCombos );
		
	}

}
