/*
 * quine.c
 * Boolean expression minimization program
 * Uses concepts of Quine-McCluskey algorithm to reduce a boolean expression to
 * its minimal size by finding all prime implicants, keeping all essential
 * prime implicants, and discarding any redundant prime implicants
 * 
 * Started Oct 01
 * Last modified 09 Jan 02
 * Copyleft 2002 Chris Williams.
 */

#include <stdio.h>
#include <stdlib.h>
#include "implicants.h"
#include "lists.h"
#include "types.h"
#include "error.h"

#define NUMLITERALS 4
int num_literals = NUMLITERALS;
extern literals_t MSb;

int main () {
	char implic_str[100];
	list_t minterms = {NULL};
	implicant_t *A, *B;
	boolean_t reduced;
	
	puts("Boolean minimization program (under development)\n");
	puts("Getting minterm list...");
	if ((num_literals = get_minterm_list (&minterms)) < 0)
		return error ("Could not obtain minterm list");
	puts ("Success");
	
	puts("Before:");
	A = (implicant_t *)minterms.first;
	do {
		implicanttoa(A, implic_str);
		printf("%s\n", implic_str);
		A = (implicant_t *)((node_t *)A)->next;
	} while (((node_t *)A) != minterms.first);

	/* reduce implicants to prime implicants by combining small implicants
	 * into larger implicants, if possible.
	 */
	/* go through list of imlicants and group implicants */
	do {
		reduced = false;
		A = (implicant_t *)minterms.first;
		do {
			B = (implicant_t *)((node_t *)A)->next;
			do {
				if (can_group(A, B)) {
					remove_node(&B->node);
					
					/* group A and B together */
					A->care &= ~(A->expr ^ B->expr);
					A->expr &= ~(A->expr ^ B->expr);
					reduced = true;
					continue;
				}
				if (A != B) {
					if (covers(A, B)) {
						remove_node(&B->node);
						reduced = true;
					}
					else if (covers(B, A)) {
						remove_node(&A->node);
						reduced = true;
					}
				}
				
				B = (implicant_t *)((node_t *)B)->next;
			} while (((node_t *)B) != minterms.first);
			A = (implicant_t *)((node_t *)A)->next;
		} while (((node_t *)A) != minterms.first);
	} while (reduced);
	
	puts("\nPrime Implicants (Essential and Non-essential):");
	A = (implicant_t *)minterms.first;
	do {
		implicanttoa(A, implic_str);
		printf("%s\n", implic_str);
		A = (implicant_t *)((node_t *)A)->next;
	} while (((node_t *)A) != minterms.first);

	/* find which of the prime implicants are essential and keep those */
	/*
	 * discard any prime implicants that aren't essential and are completely
	 * covered by two or more other PI's (if covered by only one other, then
	 * it either isn't a PI itself or is redundant and should've been removed
	 * by previous operation)
	 */
	
	return 0;
}