#include <windows.h>
#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include <conio.h>

typedef struct _DNF
{
	unsigned int mask;
	unsigned int np;
}DNF;

//подсчитывает число бит в двойном слове
int CalcBits(unsigned int data)
{
	int cnt = 0;
	int	i;

	for (i=0; i<32; i++, data>>=1)
		cnt += (1 == (data & 1));
	return cnt;
}

//определяет минимальную СДНФ по сокращенной
//параметры:
//адрес массива СДНФ, адрес индекса сокращенной СДНФ, адрес массива количеств имликант
void GetMinSDNF(DNF** pdnf, int* current, int* N)
{
	int		i, j, mi, ni, mj, nj;
	int		cnt, k;
	int		cb1, cb2;
	int		*NonNucleus = NULL;		//матрица для поиска импликант, которые не являются ядром
									//импликантная матрица для поиска минимальной СДНФ
									//добавлены нулевые элементы для состояния строк и столбцов
	int		*Implicants = (int*)calloc((N[*current]+1)*(N[0]+1)*sizeof(int), sizeof(int));

//формируем импликантную марицу
	printf("Implicants array:\n");	//выведем заголовок

	for(i=1; i<=N[*current]; i++)	//по всем импликантам сокращенной СДНФ
	{
		mi = pdnf[*current][i-1].mask;	//маска элементов импликанты
		ni = pdnf[*current][i-1].np;	//значения элементов импликанты
		for(j=1; j<=N[0]; j++)		//по всем импликантам исходной СДНФ
		{
			mj = pdnf[0][j-1].mask;		//маска
			nj = pdnf[0][j-1].np;		//значения
										//пишем 1, если импликанта исходной СДНФ поглощается
										//импликантой сокращенной СДНФ, или 0, если иначе
			Implicants[i*(N[0]+1)+j] = (mi & nj) == (mi & ni);
			printf("%d ", Implicants[i*(N[0]+1)+j]);	//выведем
		}
		printf("\n");
	}

//ищем ядро СДНФ (столбики матрицы, в которых ровно одна единица)	
	for(j=1; j<=N[0]; j++)			//по столбикам импликантной матрицы
	{
		cnt = 0;					//считаем
		for(i=1; i<=N[*current]; i++)	//по строкам
			cnt += Implicants[i*(N[0]+1)+j];
		if (cnt == 1)
			Implicants[j] = 1;		//пометим, что импликанта исходной СДНФ поглощается 
	}								// импликантой сокращенной, которая в ядре!
									//будем формировать минимальную СДНФ в другом массиве
	N[(*current)^3] = 0;			//обнулим счетчик
	
	//найдем импликанты сокращенной СДНФ, которые в ядре
	for(j=1; j<=N[0]; j++)			//по всем столбцам импликантной матрицы 
	{								// (по всем импликантам исходной СДНФ)
		if(Implicants[j]==1)		//ядро?
		{
			//найдем индекс импликанты сокращенной СДНФ, которая в ядре
			for(i=1; i<=N[*current]; i++)		//по всем импликантам сокращенной СДНФ
			{
				if (Implicants[i*(N[0]+1)+j])	//признак поглощения есть?
					break;
			}
			
			Implicants[i*(N[0]+1)] = 1;			//помечаем импликанту сокращенной СДНФ, которая в ядре
			
			//скопируем в минимальную СДНФ маску и значения импликанту, которая в ядре
			pdnf[(*current)^3][N[(*current)^3]].mask = pdnf[*current][i-1].mask;
			pdnf[(*current)^3][N[(*current)^3]++].np = pdnf[*current][i-1].np;	//увеличиваем счетчик

			//найдем и пометим импликанты основной СДНФ, которые поглощаются "ядровой" импликантой
			for(k=1; k<=N[0]; k++)		//по всем импликантам основной СДНФ
			{
				if (k != j)				//в ядре - обходим
				{
					if (Implicants[i*(N[0]+1)+k])	//поглощается?
						Implicants[k] = 2;			//помечаем!
				}
			}
		}
	}

	//осталось просмотреть те импликанты основной СДНФ, 
	//которые не поглощаются "ядровыми" импликантами сокращенной СДНФ
	//ищем те импликанты сокращенной СДНФ, которые поглощают максимум импликант основной СДНФ
	//если одинаковые, то берем ту импликанту, в которой меньше элементов импликанты
	//иначе берем первую попавшуюся
	do
	{
		//построим дополнительный массив (для удобства расчета) 
		//для тех импликант основной СДНФ, 
		//которые не поглощаются "ядровыми" импликантами и для тех
		//импликант сокращенной СДНФ, которые не являются ядром
		//посчитаем количество тех и других, т.е. размерность матрицы
		ni = nj = 0;
		for(j=1; j<=N[0]; j++)
			nj += (0==Implicants[j]);			//количество импликант основной СДНФ
		for(i=1; i<=N[*current]; i++)
			ni += (0==Implicants[i*(N[0]+1)]);	//количество импликант сокращенной СДНФ
		
		//проверим, все ли ипликанты основной СДНФ поглощены
		// если =0, то значит сокращенная СДНФ уже является минимальной СДНФ
		if (nj)
		{
			//выделим память под матрицу
			NonNucleus = (int*)realloc(NonNucleus, ni*nj*sizeof(int));

			//заполним массив, mi - индекс строк
			for(mi=0,i=1; i<=N[*current]; i++)	//по всем строкам импл матрицы
			{
				if (0 == Implicants[i*(N[0]+1)])	//не в ядре?
				{
					for(mj=0,j=1; j<=N[0]; j++)		//по всем столбцам, mj - индекс столбца
					{	//только для имликант основной СДНФ, которые еще не учтены
						if (0 == Implicants[j])
							//запишем в ячейку признак поглощения и индексы в импл матрице!
							NonNucleus[mi*nj+mj++] = Implicants[i*(N[0]+1)+j] + ((i-1)<<24) + (j<<16);
					}
					mi++;	//на следующую строку
				}
			}

			//найдем строку, в которой отмечены макс количество поглощений!
			//посчитаем для первой, считаем ее максимальной
			for(cnt=j=0; j<nj; j++)
				cnt += NonNucleus[j] & 0xff;		//считаем число поглощений
			i = 0;									//номер строки с макс суммой

			for(k=1; k<ni; k++)						//по всем остальным
			{
				for(mj=j=0; j<nj; j++)
					mj += NonNucleus[k*nj+j] & 0xff;//считаем
				if (mj > cnt)						//и сравниваем
				{
					cnt = mj;						//новый максимум
					i = k;							// и индекс строки
				}
				if (mj == cnt)						//если равно
				{									//сравним число элементов импликантов
													//для этого считаем число бит маски
					cb1 = CalcBits(pdnf[*current][(NonNucleus[k*nj]>>24)&0xff].mask);
					cb2 = CalcBits(pdnf[*current][(NonNucleus[i*nj]>>24)&0xff].mask);

					if (cb1 < cb2)
					{
						cnt = mj;					//новые значения
						i = k;
					}
				}
			}
			//запишем найденную импликанту в минимальную СДНФ (используем сохраненный индекс строки)
			pdnf[(*current)^3][N[(*current)^3]].mask = pdnf[*current][(NonNucleus[i*nj]>>24)&0xff].mask;
			pdnf[(*current)^3][N[(*current)^3]++].np = pdnf[*current][(NonNucleus[i*nj]>>24)&0xff].np;
			
			//пометим все поглощенные имликанты основной СДНФ
			//могут остаться еще непоглащенные!
			for(j=0; j<nj; j++)
				Implicants[(NonNucleus[i*nj+j]>>16)&0xff] = 3*(NonNucleus[i*nj+j]&0xff);
		}
		else
			break;	//если все поглощаются, то выход!
	}while (true);	//на повтор анализа
	
	*current ^= 3;	//минимальная СДНФ становится текущей!
	free(Implicants);	//освобождаем память!
	free(NonNucleus);
}

//поиск сокращенной СДНФ
//*current		- индекс текущей СДНФ
//(*current)^3	- индекс, куда пишем результат
void GetShortSDNF(DNF** pdnf, int* current, int* N)
{
	int i, j, k=1, l, mask;
	int	mi, ni, mj, nj;
	
	while(k)	//циклим, пока что-то склеивается
	{
		//проверяем по всем парам импликант, склеиваются ли они 
		for(i=k=0; i<N[*current]-1; i++)	//по всем импликантам СДНФ
		{
			for(j=i+1; j<N[*current]; j++)
			{
				//только для одинаковых элементов импликант
				if (pdnf[*current][i].mask == pdnf[*current][j].mask)
				{
					//смотрим, чем отличаются
					mask =	(pdnf[*current][i].np & pdnf[*current][i].mask) ^
							(pdnf[*current][j].np & pdnf[*current][j].mask);
					switch (mask)	//если изменение только в одном бите, значит
					{				// импликанты склеиваются!
						case 0x01:
						case 0x02:
						case 0x04:
						case 0x08:
						case 0x10:
						case 0x20:
						case 0x40:
						case 0x80:
							//есть склеивание! - пишем в результат
							//оставляем общие элементы
							//количество пока не увеличиваем!
							pdnf[(*current)^3][k].mask = pdnf[*current][i].mask & ~mask;
							pdnf[(*current)^3][k].np = pdnf[*current][i].np;
							//проверим на совпадение!
							for(l=0; l<k; l++)
							{
								mi = pdnf[(*current)^3][l].mask;
								ni = pdnf[(*current)^3][l].np;
								mj = pdnf[(*current)^3][k].mask;
								nj = pdnf[(*current)^3][k].np;
								
								if ((mi == mj) && (mi & ni) == (mj & nj))
									break;	//такое уже есть! - выходим
							}
							if (l==k)		//если дошли до конца - совпадения нет
								k++;		//увеличиваем счетчик
							break;
					}
				}
			}
		}
		if (k)		//что-то склеилось?
		{			//проверим на поглощение
			for(i=0; i<N[*current]; i++)	//по всем текущей СДНФ
			{
				mi = pdnf[*current][i].mask;//маска
				ni = pdnf[*current][i].np;	//значения
				
				for(j=0; j<k; j++)			//по всем результата
				{
					mj = pdnf[(*current)^3][j].mask;
					nj = pdnf[(*current)^3][j].np;
					//поглощается?
					if (((mi | mj) == mi) && ((mj & ni) == (mj & nj))) 
						break;		//да!
				}
				if (j == k)			//дошли до конца - не поглощается
				{					//значит - копируем в результат
					pdnf[(*current)^3][k].mask = pdnf[*current][i].mask;
					pdnf[(*current)^3][k++].np = pdnf[*current][i].np;
				}

			}

			(*current) ^= 3;		//меняем текущего на результат
			N[*current] = k;		//и сохраняем количество
		}
	}
}

//получение исходной СДНФ по строке таблицы истинности
int GetSDNF(char* sTrueTable, DNF** ppdnf, int *pcnt)
{
	int len = strlen(sTrueTable);	//длина строки
	int	i, count, imask;

	switch (len)					//ждем степень двойки
	{

		case 2:
			*pcnt = 1;
			break;
		case 4:
			*pcnt = 2;				//количество элементов импликант
			break;
		case 8:
			*pcnt = 3;
			break;
		case 16:
			*pcnt = 4;
			break;
		case 32:
			*pcnt = 5;
			break;
		case 64:
			*pcnt = 6;
			break;
		case 128:
			*pcnt = 7;
			break;
		case 256:
			*pcnt = 8;
			break;
		default:
			return -1;				//ошибка!
	}
	//выделяем память под СДНФ
	ppdnf[0] = (DNF*)realloc(ppdnf[0], 2*len*sizeof(DNF));		//исходная
	ppdnf[1] = (DNF*)realloc(ppdnf[1], 2*len*sizeof(DNF));		//два массива для сокращенной СДНФ
	ppdnf[2] = (DNF*)realloc(ppdnf[2], 2*len*sizeof(DNF));		//выбирается *current
																//здесь же и минимальная
	imask = (1<<*pcnt)-1;			//маска для всех *pcnt элементов
	for(count=i=0; i<len; i++)		//по всем символам строки
	{
		if (sTrueTable[i] == '1')	//1 - импликанта участвует в СДНФ
		{	//запишем в массив [0] - основная СДНФ
			//и в массив [1] для дальнейших расчетов
			ppdnf[0][count].mask = imask;	//все элементы
			ppdnf[0][count].np = i;			//значения
			ppdnf[1][count].mask = imask;	//запишем и в массив с индексом 1
			ppdnf[1][count++].np = i;		// для поиска сокращенной СДНФ
		}
		else if (sTrueTable[i] != '0')		//ждем только 0 или 1
			return -1;					//ошибка!
	}
	return count;					//вернем количество импликант основной СДНФ
}

//вывод одной СДНФ, с адресом pdnf, N - количесво импликант, 
//cnt - максимальное количество элементов импликант
void OutSDNF(DNF *pdnf, int N, int cnt)
{
	int i, j, k;

	if ((N == 1) && (0 == pdnf[0].mask))
		printf ("1\n");				//тождественная истина
	else
	{
		for(i=0; i<N; i++)			//по всем импликантам
		{
			for(k='a',j=cnt-1; j>=0; j--,k++)	//в обратном порядке
			{
				if (pdnf[i].mask & (1<<j))		//если задан в маске
				{
					if (pdnf[i].np & (1<<j))	//если 1
						printf("%c",k);
					else
						printf("~%c",k);		// отрицание, или 0
				}
			}
			printf(" V ");			//знак дизъюнкции
		}
		printf("\x8\x8\x8   \n");	//вытрем последнюю дизъюнкцию
	}
}

int main(int argc, char *argv[])
{
	int		N[3], cnt;
	int		current = 1;
	DNF		*pdnf[3] = {NULL, NULL, NULL};	//три массива СДНФ
	char	sTrueTable[512];				//строка для ввода таблицы истинности

	while(1)								//продолжаем, пока не откажемся
	{
		printf("\nEnter true table: ");
		scanf("%s", sTrueTable);			//вводим строку из 0 и 1

		if ((N[0] = N[1] = GetSDNF(sTrueTable, pdnf, &cnt)) < 0)	//формируем основную СДНФ
		{
			printf("Enter correct data!\n");//ошибка!
			continue;						//и на повтор
		}

		printf("Source SDNF:\n");
		OutSDNF(pdnf[0], N[0], cnt);		//выведем основную СДНФ

		GetShortSDNF(pdnf, ¤t, N);	//формируем сокращенную СДНФ
		printf("Short SDNF:\n");
		OutSDNF(pdnf[current], N[current], cnt);	//выведем сокращенную СДНФ

		GetMinSDNF(pdnf, ¤t, N);		//формируем минимальную СДНФ
		printf("Min SDNF:\n");
		OutSDNF(pdnf[current], N[current], cnt);	//выведем минимальную СДНФ

		printf("Continue ? (Y,N) ");		//спрашиваем продолжать ли дальше?
		cnt = toupper(_getche());
		printf("\n");

		if (cnt != 'Y')
			break;							//выходим
	}

	free (pdnf[0]);							//освобождаем память
	free (pdnf[1]);
	free (pdnf[2]);

	return 0;
}