package combinations;

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

public class MonoPolarityBitSequences {
	
	int numberOfFields;
	
	// length of the frame field, in bits ..
	// NOTE: CAN 2.0A ~ 11-bit field
	//       CAN 2.0B ~ 29-bit field
	int fieldLength;
	
	// number of bits in the field that are constrained to be that same polarity
	// (all zeros or all ones), and contiguous
	// (i.e.: 11111010101, 11 bits, 5 constrained - 5/11) ..
	int bitsConstrained;
	
	int count;
	
	Vector<Integer> fieldLengthCollection;
	Vector<Integer> bitsConstrainedCollection;
	Vector<Integer> countCollection;
	
	Vector<String> uniqueCombos;
	Vector<String> allCombos;
	
	int numberOfRows;
	
	public MonoPolarityBitSequences(){
		
		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>();
		
		numberOfRows = -1;
		
	}

	public Vector<String> getCombo_AllBitsConstrained( int fieldLength ){
		
		// there are always only 2 combinations for "all bits constrained" ..
		// 1) field is all 0's, or
		// 2) field is all 1's ..
		
		// i.e.: fieldLength = 3, bitsConstrained = 1 => "1/3" ..
		// xxx
		// 111: 111		000: 000
		
		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 ){
		
		// return the "count" of the number of unique combos of bit-sequences which
		// have mono-polarity bit-sequences embedded within them ..
		
		// there are always only 2 combinations for "all bits constrained" ..
		
		Vector<String> combos = getCombo_AllBitsConstrained( fieldLength );
	
		return combos.size();
		
	}
	
	public int convertBinaryToInt( String binaryString ){
		
		// miscellaneous utility method (not yet used) ..
		
		// returns the integer value of a binary string ..
		// (i.e.: 0101 bin ~ 5 dec) ..
		
		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);
			
			// DEBUGGING ..
			//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 );
			
			// DEBUGGING ..
			//System.out.println( "sum: " + sum );
			
			
		}
		
		return (int)sum;
		
	}

	private Vector<String> generateBinaryStrings( int fieldSize, int numberOfCombos ){
		
		// helper method for "makeCombos_SomeBitsConstrained()" ..
		
		// based on the "fieldSize" and the "numberOfcombos"
		// (which corresponds to the number of unconstrained bit combos per row),
		// this method generates all of the binary string combinations
		// for a given "fieldLength" and "bitsConstrained" pair ..
		
		Vector<String> binaryStrings = new Vector<String>();
		
		String binaryString = null;
		String padString = null;
		
		int numberOfPadDigits = 0;
		
		for(int i=0; i<numberOfCombos; i++){
			
			// workaround to avoid "java.lang.OutOfMemoryError: Java heap space" ..
			System.gc();
			
			binaryString = Integer.toBinaryString( i );
			
			// DEBUGGING ..
			//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;
				
				// DEBUGGING ..
				//System.out.println( "padString: " + padString );
				
				// update with the new padded version ..
				binaryString = padString;
				
			}
			
			// DEBUGGING ..
			//System.out.println( "unconstrained bit combo: " + binaryString );
			
			// add to the collection ..
			binaryStrings.add( binaryString );

		}
		
		return binaryStrings;
		
	}
	
	public void makeCombos_SomeBitsConstrained( int fieldLength, int bitsConstrained ){
		
		// FIELD:
		//     "fieldLength" = size of the field
		// "bitsConstrained" = number of bits that are constrained to be all 0's or all 1's
		// i.e.: "n" is an unconstrained bit, "i" is a constrained bit (all i's must be 0 or 1) ..
		//       [nnnn]iiii ~ [0101]0000 .. [nnnn] is all combos between 0 and 2^(fieldLength-bitsConstrained)
		//        while "iiii" is always all 0's or all 1's ..
		
		// i.e. fieldLength = 3, bitsConstrained = 1 => "1/3" ..
		// xxx								xxx
		// 1nn: 1[00], 1[01], 1[10], 1[11]	0nn: 0[00], 0[01], 0[10], 0[11] => row 1 ..
		// n1n: 0[10], 0[11], 1[10], 1[11]	n0n: 0[00], 0[01], 1[00], 1[01] => row 2 ..
		// nn1: 0[01], 0[11], 1[01], 1[11]	nn0: 0[00], 0[10], 1[00], 1[10] => row 3 ..
		
		// all combinations of bit-sequences with mono-polarity bit-sequences embedded within,
		// which are unique (no duplicates) ..
		uniqueCombos = new Vector<String>();
		
		// all combinations of bit-sequences with mono-polarity bit-sequences embedded within,
		// includes duplicates ..
		allCombos = new Vector<String>();
		
		String combo = "";
		
		// i.e.: fieldLength = 3, bitsContrained = 2, numberRows = (3 - 2 + 1) = 2
		// 		 xxx
		// 		 11n	row 1 ..
		// 		 n11	row 2 ..
		numberOfRows = fieldLength - bitsConstrained + 1;
		
		// DEBUGGING ..
		//System.out.println( "numberRows: " + numberRows );
		
		// number of bit-sequence combinations for each "row" ..
		// i.e.: 1nnn: 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111 || 0nnn: 0111, .. => row 1
		//       n1nn: 0100, 0101, 0110, 0111, 1100, 1101, 1110, 1111 || n0nn: 1011, .. => row 2
		int numberCombosPerRow = (int) Math.pow( 2.0, ((double)numberOfRows) );
		
		// size of the portion of the field with bits that are "unconstrained" (can be either 0 or 1) ..
		// ( i.e.: 2 bits unconstrained, 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 unique set needed) )
		// ( i.e.: 0nn => 0[00], 0[01], 0[10], 0[11] is the other row ) ..
		int unconstrainedBitFieldSize = ( fieldLength - bitsConstrained );
		
		// ( i.e.: from above, 00, 01, 10, 11 => 4 ) ..
		int numberUnconstrainedBitCombosPerRow = (int) Math.pow( 2.0, ( (double)unconstrainedBitFieldSize ) );
		
		// DEBUGGING ..
/*
		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++ ) );

*/
		
		// generate the portion of the binary strings that are "unconstrained" ..
		// ( i.e.: from above, {00, 01, 10, 11} ) ..
		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<numberOfRows; i++){
		
			// number of combos per "row" ..
			for(int j=0; j<numberCombosPerRow; j++){
				
				// workaround to avoid "java.lang.OutOfMemoryError: Java heap space" ..
				System.gc();
				
				// 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;
				
				// DEBUGGING ..
				//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() );
				
				// DEBUGGING ..
				//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;
				
				// DEBUGGING ..
				//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 ){
		
		// return the "count" of the number of unique combos of bit-sequences which
		// have mono-polarity bit-sequences embedded within them ..
		
		makeCombos_SomeBitsConstrained( fieldLength, bitsConstrained );
	
		return getUniqueCombos().size();
		
	}
	
	public Vector<String> getUniqueCombos(){
		
		return uniqueCombos;
		
	}
	
	public Vector<String> getAllCombos(){
		
		return allCombos;
		
	}
	
	public void printAllCombosTable( Vector<String> combos ){
		
		// print the combos as a table ..
		
		int numberCombosPerRow = 0;
		if( numberOfRows > 0 )
			numberCombosPerRow = combos.size() / numberOfRows;
		
		int comboIndex = -1;
		
		for(int i=0; i<numberOfRows; 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 printAllCombosAsOneRow( 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 printUniqueCombosTable( Vector<String> allCombos ){
		
		// print the "unique" combos as a table (non-unique combos replaced with placeholder) ..
		
		// track combos so that they are only printed 1 time ..
		HashSet<String> uniqueCombosFound = new HashSet<String>();
		
		int numberCombosPerRow = 0;
		if( numberOfRows > 0 )
			numberCombosPerRow = allCombos.size() / numberOfRows;
		
		// index used to locate a combo from its collection ..
		int comboIndex = -1;
		
		String combo = null;
		
		// replace non-unique combos with a non-digit,
		// to indicate that the combo was removed ..
		String comboPlaceHolder = new String();
		String comboPlaceHolderDigit = "-";
		
		// only used once in conjunction with "comboPlaceHolder" ..
		int comboLength = -1;
		
		for(int i=0; i<numberOfRows; 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 );
				
				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 void printCounts( int fieldLength ){
		
		// print out the "counts" of the number of combinations of bit-sequences having 
		// mono-polarity bit sequences embedded within (unique combo count only) ..
		
		// print out only "counts" for "fieldLength" given ..
		
		// i.e.: "maxFieldLength = 3" ..
		// count[1/3]: 8
		// count[2/3]: 6
		// count[3/3]: 2
		
		// DEBUGGING ..
		double startTime = System.currentTimeMillis();
		
		int bitsConstrained = 0;
		
		int count = -1;
		
			
		for(int i=0; i<fieldLength; i++){
				
			bitsConstrained = i+1;
				
			makeCombos_SomeBitsConstrained( fieldLength, bitsConstrained );
				
			count = getUniqueCombos().size();
				
			System.out.println( "count["+bitsConstrained+"/"+fieldLength+"]: " + count );
				
		}
		
		// DEBUGGING ..
		double endTime = System.currentTimeMillis();
		System.out.println( "elapsedTime: " + ((endTime - startTime)/1000) );
		
	}
	
	public void printAllCounts( int maxFieldLength ){
		
		// print out the "counts" of the number of combinations of bit-sequences having 
		// mono-polarity bit sequences embedded within (only unique combos are counted) ..
		
		// print out the "counts" for ALL fieldLengths, from 1 up to "maxFieldLength" ..
		
		// i.e.: "maxFieldLength = 3" ..
		// count[1/1]: 2
		// =============
		// count[1/2]: 4
		// count[2/2]: 2
		// =============
		// count[1/3]: 8
		// count[2/3]: 6
		// count[3/3]: 2
		
		// DEBUGGING ..
		double startTime = System.currentTimeMillis();
		double nextStartTime = 0.0d;
		double nextEndTime = 0.0d;
		
		int fieldLength = 0;
		
		int bitsConstrained = 0;
		
		int count = -1;
		
		for(int i=0; i<maxFieldLength; i++){
			
			fieldLength = i+1;
			
			nextStartTime = System.currentTimeMillis();
			
			for(int j=0; j<fieldLength; j++){
				
				bitsConstrained = j+1;
				
				makeCombos_SomeBitsConstrained( fieldLength, bitsConstrained );
				
				count = getUniqueCombos().size();
				
				System.out.println( "count["+bitsConstrained+"/"+fieldLength+"]: " + count );
				
			}
			
			nextEndTime = System.currentTimeMillis();
			System.out.println( "elapsedTime: " + ((nextEndTime - nextStartTime)/1000) );
			
			if( i<(maxFieldLength-1) )
				System.out.println( "=============" );
			
			
		}
		
		// DEBUGGING ..
		double endTime = System.currentTimeMillis();
		System.out.println( "total elapsedTime: " + ((endTime - startTime)/1000) );
		
	}
	
	public static void main(String[] args){
		
		MonoPolarityBitSequences mpbs = new MonoPolarityBitSequences();
		
		// uncomment section to use it ..
		
		/**
		 * PRINT "COUNTS"
		 */
		
///*
		// print the "counts" of unique mono-polarity bit sequences,
		// in the format: "number of constrained bits" / "field length in bits"
		 
		// i.e.: m bits constrained, 3-bit field length: "m/3" ..
		// count[1/3]: 8
		// count[2/3]: 6
		// count[3/3]: 2
		 
		// i.e.: m bits constrained, 11-bit field length: "m/11" ..
		 
		int maxFieldLengths = 11;
		mpbs.printAllCounts( maxFieldLengths );
		
		// i.e.: m bits constrained, 29-bit field length: "m/29" ..
		//int fieldLength = 11;
		//mpbs.printCounts( fieldLength );
//*/
		
		/**
		 * PRINT "COMBINATIONS"
		 */
		
/*
		
		// DEBUGGING ..
		//int value = mpbs.convertBinaryToInt( "10000" );
		//System.out.println( "value: " + value );
		
		// print the combinations of bit sequences,  
		// which have mono-polarity bit sequences embedded within ..
		// i.e.: "1/3":
		//		 1nn: 100, 101, 110, 111	0nn: 000, 001, 010, 011
		//		 n1n: 010, 011, 110, 111	n0n: 000, 001, 100, 101
		//		 nn1: 001, 011, 101, 111	nn0: 000, 010, 100, 110
		int bitsConstrained = 1;
		int fieldLength = 3;
		
		// get the "count" for the "fieldLength" and number of "bitsConstrained" ..
		// (invokes "makeCombos_SomeBitsConstrained()") ..
		//int count = mpbs.getCount_SomeBitsConstrained( fieldLength, bitsConstrained );
		//System.out.println( "bitsConstrained: " + bitsConstrained + ", fieldLength: " + fieldLength + ", count: " + count );
		
		// make the combos collection first ..
		// (these print methods need to be passed in "allCombos" collection) ..
		mpbs.makeCombos_SomeBitsConstrained( fieldLength, bitsConstrained );
		
		// DEBUGGING ..
		//Vector<String> uniqueCombos = mpbs.getUniqueCombos();
		//System.out.println( "unique count: " + uniqueCombos.size() );
		
		Vector<String> allCombos = d.getAllCombos();
		
		// print the combos as a table ..
		//mpbs.printAllCombosTable( allCombos );
		
		// print the combos as a single row ..
		//mpbs.printAllCombosAsOneRow( allCombos );
		
		// print the "unique" combos as a table (non-unique combos replaced with placeholder) ..
		//mpbs.printUniqueCombosTable( allCombos );
		
*/
		
	}

}
