import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;

public class Primeimp  {

	LinkedList<String> min0 = new LinkedList<String>(); //group of 0 ones
	LinkedList<String> min1 = new LinkedList<String>(); //group of 1 ones
	LinkedList<String> min2 = new LinkedList<String>();//group of 2 ones
	LinkedList<String> min3 = new LinkedList<String>();//group of 3 ones
	LinkedList<String> min4 = new LinkedList<String>();//group of 4 ones
	LinkedList<String> min2nd = new LinkedList<String>();// group of 1st phase combination
	LinkedList<String> min3rd = new LinkedList<String>();//group of 2nd phase combination
	LinkedList<String> primeImplicants = new LinkedList<String>(); // prime implicants

    int minTermsNo = 0;
	int [] minterms;
	String [] mintermStr,PrimeImps;
	Scanner in = new Scanner(System.in);
	boolean [] min0marked,min1marked,min2marked,min3marked,min4marked;
	boolean [] [] primeTable;

	public String[] getPrimeImplicants() {
		// TODO Auto-generated method stub

		System.out.println("\n============================================================================");
		for(int i = 0;i<primeImplicants.size();i++)
		{
			String s = primeImplicants.get(i);
			String a="",b="",c="",d="",printed="";
			switch(s.charAt(0))
			{
			case '1': a = "A"; break;
			case '0': a = "A'"; break;
			default:
			}
			switch(s.charAt(1))
			{
			case '1': b = "B"; break;
			case '0': b = "B'"; break;
			default:
			}
			switch(s.charAt(2))
			{
			case '1': c = "C"; break;
			case '0': c = "C'"; break;
			default:
			}
			switch(s.charAt(3))
			{
			case '1': d = "D"; break;
			case '0': d = "D'"; break;
			default:
			}
			printed= a+b+c+d;
			PrimeImps[i]=printed;
			System.out.println(printed + "|");
		}

		return PrimeImps;
	}


	public void grouping() {
		// TODO Auto-generated method stub
		System.out.println("Enter the no of minterms:");
		minTermsNo = Integer.parseInt(in.next());
		minterms = new int[minTermsNo];
		mintermStr = new String[minTermsNo];

		System.out.println("Enter the minterms separated by space");
		for(int i = 0;i<minTermsNo;i++)
		{
			minterms[i]=Integer.parseInt(in.next());

		}
		System.out.println("Minterms entered:");

		for(int i = 0;i<minTermsNo;i++)
		{
			System.out.print(minterms[i] + "  ");
		}
		System.out.println("");
		for(int i = 0;i<minTermsNo;i++)
		{
			mintermStr[i] =BinStr(Integer.toBinaryString(minterms[i]));
		}
		for(int i=0;i<minTermsNo;i++)
		{
			int cntmin = cntOnes(mintermStr[i]);
			switch(cntmin)
			{
			case 0:{
				min0.add(mintermStr[i]);break;
			}
			case 1:{
				min1.add(mintermStr[i]);break;
			}
			case 2:{
				min2.add(mintermStr[i]);break;
			}
			case 3:{
				min3.add(mintermStr[i]);break;
			}
			case 4:{
				min4.add(mintermStr[i]);break;
			}
			}
		}
		//print check //developing stuff
		printLL(min0);
		if(!min0.isEmpty())System.out.println("=====================================");
		printLL(min1);
		if(!min1.isEmpty())System.out.println("=====================================");
		printLL(min2);
		if(!min2.isEmpty())System.out.println("=====================================");
		printLL(min3);
		if(!min3.isEmpty())System.out.println("=====================================");
		printLL(min4);
		if(!min4.isEmpty())System.out.println("=====================================");

		//
		int TEMPORARY=min0.size();
		boolean [] min0marked = new boolean[TEMPORARY];
		TEMPORARY = min1.size();
		boolean [] min1marked = new boolean[TEMPORARY];
		TEMPORARY = min2.size();
		boolean [] min2marked = new boolean[TEMPORARY];
		TEMPORARY = min3.size();
		boolean [] min3marked = new boolean[TEMPORARY];
		TEMPORARY = min4.size();
		boolean [] min4marked = new boolean[TEMPORARY];
		//initialize boolean arrays with zero
		Arrays.fill(min4marked,false);
		Arrays.fill(min3marked,false);
		Arrays.fill(min2marked,false);
		Arrays.fill(min1marked,false);
		Arrays.fill(min0marked,false);


	}


	public void combine() {
		// TODO Auto-generated method stub
		for(int i = 0;i<min1.size();i++)
		{
			if(min0.isEmpty()) break;
			if(compareBin(min0.getFirst(), min1.get(i))==1)
			{
				int ind = getIndexDiff(min0.getFirst(), min1.get(i));
				char [] c =min0.getFirst().toCharArray();
				c[ind]='-';
				min2nd.add(String.valueOf(c));
				min0marked[0]=true;
				min1marked[i]=true;
			}
		}
		for(int i = 0;i<min1.size();i++)
		{
			for(int j = 0;j<min2.size();j++)
			{
				if(compareBin(min1.get(i), min2.get(j))==1)
				{
					int ind = getIndexDiff(min1.get(i), min2.get(j));
					char [] c =min1.get(i).toCharArray();
					c[ind]='-';
					min2nd.add(String.valueOf(c));
					min2marked[j]=true;
					min1marked[i]=true;
				}
			}
		}
		for(int i = 0;i<min2.size();i++)
		{
			for(int j = 0;j<min3.size();j++)
			{
				if(compareBin(min2.get(i), min3.get(j))==1)
				{
					int ind = getIndexDiff(min2.get(i), min3.get(j));
					char [] c =min2.get(i).toCharArray();
					c[ind]='-';
					min2nd.add(String.valueOf(c));
					min3marked[j]=true;
					min2marked[i]=true;
				}
			}
		}
		for(int i = 0;i<min3.size();i++)
		{
			for(int j = 0;j<min4.size();j++)
			{
				if(compareBin(min3.get(i), min4.get(j))==1)
				{
					int ind = getIndexDiff(min3.get(i), min4.get(j));
					char [] c =min3.get(i).toCharArray();
					c[ind]='-';
					min2nd.add(String.valueOf(c));
					min4marked[j]=true;
					min3marked[i]=true;
				}
			}
		}
		deleteRep(min2nd);
		printLL(min2nd);
		System.out.println("=====================================");
		int TEMPORARY = min2nd.size();
		boolean [] min2ndmarked = new boolean[TEMPORARY];
		Arrays.fill(min2ndmarked,false);

		//check 3rd
		for(int i = 0;i<min2nd.size();i++)
		{
			for(int j = i+1;j<min2nd.size();j++)
			{
				if(compareBin(min2nd.get(i), min2nd.get(j))==1)
				{
					int ind = getIndexDiff(min2nd.get(i), min2nd.get(j));
					char [] c =min2nd.get(i).toCharArray();
					c[ind]='-';
					min3rd.add(String.valueOf(c));
					min2ndmarked[j]=true;
					min2ndmarked[i]=true;
				}
			}
		}
		TEMPORARY = min3rd.size();
		boolean [] min3rdmarked = new boolean[TEMPORARY];
		Arrays.fill(min3rdmarked,false);
		// gathering prime implicants
		for(int i = 0;i<min3rdmarked.length;i++)
		{
			if(!min3rdmarked[i]) primeImplicants.add(min3rd.get(i));
		}
		for(int i = 0;i<min2ndmarked.length;i++)
		{
			if(!min2ndmarked[i]) primeImplicants.add(min2nd.get(i));
		}
		for(int i = 0;i<min4marked.length;i++)
		{
			if(!min4marked[i]) primeImplicants.add(min4.get(i));
		}
		for(int i = 0;i<min3marked.length;i++)
		{
			if(!min3marked[i]) primeImplicants.add(min3.get(i));
		}
		for(int i = 0;i<min2marked.length;i++)
		{
			if(!min2marked[i]) primeImplicants.add(min2.get(i));
		}
		for(int i = 0;i<min1marked.length;i++)
		{
			if(!min1marked[i]) primeImplicants.add(min1.get(i));
		}
		for(int i = 0;i<min0marked.length;i++)
		{
			if(!min0marked[i]) primeImplicants.add(min0.get(i));
		}

	}


	public boolean[][] getTable() {
		// TODO Auto-generated method stub
		primeTable=new boolean[primeImplicants.size()][minTermsNo];
		Arrays.fill(primeTable, false);
		//check if prime implicant cover minterm
		for(int i=0;i<primeImplicants.size();i++)
		{
			for(int j=0;j<minTermsNo;j++)
			{
				if(compareBinModified(primeImplicants.get(i), BinStr(Integer.toBinaryString(minterms[j]))))
				{
					primeTable[i][j]=true;
				}
			}
		}
		return null;
	}

	// some extra quite useful methods
	public String BinStr(String s) { //get "0010" string from "10" string
		// TODO Auto-generated method stub
		int x = Integer.parseInt(s);
		if(x == 0)return "0000";
		else if(x == 1) return "0001";
		else if(x<100)  return "00" + Integer.toString(x);
		else if(x<1000) return "0"  + Integer.toString(x);
		return Integer.toString(x);
	}
	public int compareBin(String a ,String b) //return no. of differences if 1 then they can be combined
	{
		int counter = 0;
		for(int i = 0;i<a.length();i++)
		{
			if(!(a.charAt(i)==b.charAt(i)))
			{
				counter++;
			}
		}
		return counter;

	}
	public boolean compareBinModified(String a ,String b) //for getting prime table
	{

		for(int i = 0;i<a.length();i++)
		{
			if(a.charAt(i)==1||a.charAt(i)==0)
			{
				if(!(a.charAt(i)==b.charAt(i)))	return false;
				else continue;
			}

		}
		return true;

	}
	public Integer getIndexDiff(String a,String b) //performed only on 1differnce found
	{

		for(int i = 0;i<a.length();i++)
		{
			if(!(a.charAt(i)==b.charAt(i)))
			{
				return i;
			}
		}
		System.out.println("error getting index different");
		return null;

	}
	public int cntOnes(String x) //count ones in a boolean string
	{
		int counter = 0;
		for(int i = 0;i<x.length();i++)
		{
			if(x.charAt(i)=='1') counter++;
		}
		return counter;
	}
	public void deleteRep(LinkedList<String> x) //delete repeated nodes in linkedlist
	{
		for(int i = 0;i<x.size();i++)
		{
			for(int j=i+1;j<x.size();j++)
			{
				if(x.get(i).equals(x.get(j)))
				{
					x.remove(j);
				}
			}
		}
	}
	public void printLL(LinkedList<String> x)
	{
		for(int i = 0;i<x.size();i++)
		{
			System.out.println(x.get(i));
		}
	}


}