/*******************************************************************************
 * Copyright (c) 2009 Elliott Baron
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors:
 *    Elliott Baron - initial API and implementation
 *******************************************************************************/
package org.eclipse.cdt.codan.extension;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

public class QuineMcCluskeySimplifier<E> {
	protected ITruthTable<E> truthTable;
	protected List<Minterm<E>> implicantCover;
	private Map<Minterm<E>, List<Minterm<E>>> implications;
	
	public QuineMcCluskeySimplifier(ITruthTable<E> tt) {
		this.truthTable = tt;
		List<Minterm<E>> minterms = tt.getMinterms();
		List<Minterm<E>> inputMinterms = new ArrayList<Minterm<E>>(minterms);
		List<Minterm<E>> primeImplicants = new ArrayList<Minterm<E>>(minterms);
				
		boolean change = true;
		while (change && minterms.size() > 1) { // Iterate until we achieve a steady state
			change = false;
			Queue<Minterm<E>> primary = new LinkedList<Minterm<E>>();
			primary.addAll(minterms);			
			while (!primary.isEmpty()) { // Iterate through all combinations
				Minterm<E> one = primary.remove();			
				Queue<Minterm<E>> secondary = new LinkedList<Minterm<E>>();
				secondary.addAll(minterms);
				while (!secondary.isEmpty()) {
					Minterm<E> two = secondary.remove();
					Minterm<E> combined = one.combineTerms(two);
					if (combined != null) {
						if (!minterms.contains(combined)) {
							change = true;
							minterms.add(combined);
						}
						// Combined one and two so neither are prime implicants
						primeImplicants.remove(one);
						primeImplicants.remove(two);
						if (!primeImplicants.contains(combined)) {
							primeImplicants.add(combined);
						}
					}
				}
			}
		}
		
		implications = new HashMap<Minterm<E>, List<Minterm<E>>>();
		for (Minterm<E> implicant : primeImplicants) {
			implications.put(implicant, new ArrayList<Minterm<E>>());
			for (Minterm<E> minterm : inputMinterms) {
				if (implicant.implies(minterm)) {
					implications.get(implicant).add(minterm);
				}
			}
		}
		
		implicantCover = new ArrayList<Minterm<E>>();
		// remove minterms which are implied by an essential implicant
		List<Minterm<E>> mintermsCopy = new ArrayList<Minterm<E>>(inputMinterms);
		for (Minterm<E> minterm : mintermsCopy) {
			Minterm<E> implicant = null;
			int numImplications = 0;
			for (Minterm<E> pi : primeImplicants) {
				List<Minterm<E>> impl = implications.get(pi);
				if (impl.contains(minterm)) {
					implicant = pi;
					numImplications++;
				}
			}
			// essential implicant
			if (numImplications == 1) {
				inputMinterms.removeAll(implications.get(implicant));
				if (!implicantCover.contains(implicant)) {
					implicantCover.add(implicant);
				}
			}
		}
		
		// Remove essential implicants from our list
		primeImplicants.removeAll(implicantCover);
		
		// find a cover for the remaining minterms
		while (inputMinterms.size() > 0) {
			Minterm<E> maxImplicant = null;
			for (Minterm<E> pi : primeImplicants) {
				if (maxImplicant == null
						|| implications.get(pi).size() >= implications.get(maxImplicant).size()) {
					maxImplicant = pi;
				}
			}
			inputMinterms.removeAll(implications.get(maxImplicant));
			primeImplicants.remove(maxImplicant);
			implicantCover.add(maxImplicant);
		}
	}
	
	public List<Minterm<E>> getImplicantCover() {
		return implicantCover;
	}
	
	public List<Minterm<E>> getImplications(Minterm<E> primeImplicant) {
		return implications.get(primeImplicant);
	}

}