package logic;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

import language.Literal;
import language.NegLiteral;
import language.PosLiteral;

import data.Constraint;
import data.FinishedProduct;
import data.Quality;
import data.RawMaterial;
import data.Variable;
import input.InputReader;
import org.w3c.dom.Document;

/**
 * class to solve the Raw Material
 * 
 * @author Rukmal Fernando
 * @author Hardik Kotecha
 * @author Radhika Srinivasan
 */
public class IterativeBruteForceSolver {
	private static final int MAX_VARS = 8;
	private FinishedProduct bestAssignment;
	private static final boolean DEBUG = false;
	
	/**
	 * default constructor
	 */
	public IterativeBruteForceSolver(RawMaterial pRawMaterial) {
		this.bestAssignment = solve(pRawMaterial);
    }

	private FinishedProduct solve(RawMaterial pRawMaterial) {
		if(DEBUG) System.out.println("Started the solver");
		List<Constraint> constraints = pRawMaterial.getConstraints();

		// Sort constraints by desc order of weight
		TreeSet<Constraint> sortedConstraints = new TreeSet<Constraint>(new WeightComparator<Constraint>());
		sortedConstraints.addAll(constraints);
		
		// What is already set by previous passes
		Set<String> positiveVars = new TreeSet<String>();
		Set<String> negativeVars = new TreeSet<String>();
		
		// Top-loop: Solve by splitting into sub-problems
		while (sortedConstraints.size() > 0) {
			// There are more constraints to consider 
			// STEP 1: Create a sub-problem
			Set<String> subProblemVars = new TreeSet<String>();
			ArrayList<Constraint> subProblemConstraints = new ArrayList<Constraint>();
			
			// Determines whether/not a complete sub-set of vars was found
			boolean foundCompleteSubset = false;
			
			while ((!foundCompleteSubset) && (sortedConstraints.size() > 0) && (subProblemVars.size() < MAX_VARS)) {
				
				// Get the constraints in descending order
				Iterator<Constraint> descConstraints = sortedConstraints.iterator();
				
				// Go through the constraints
				boolean skipped = false;
				foundCompleteSubset = true;
				while (descConstraints.hasNext()) {
					Constraint c = (Constraint)descConstraints.next();

					// Get the variables in the constraint
					Set<String> constraintVars = getVariableSet(c);

					// Remove variables that are already set
					boolean overlap = false;
					overlap = overlap || constraintVars.removeAll(positiveVars);
					overlap = overlap || constraintVars.removeAll(negativeVars);
					overlap = overlap || constraintVars.removeAll(subProblemVars);

					// If the sub-problem is empty, or if there is an overlap
					// with assigned or free variables in the
					// current sub-problem, consider this constraint too
					if ((subProblemVars.size() == 0) || overlap) {
						// Since we added something, this is not a complete sub-set yet
						foundCompleteSubset = false;
						
						// Add this to the sub-problem. Remove from available constraints
						subProblemConstraints.add(c);
						
						// Remove the current item from the iterator
						descConstraints.remove();

						// Add the variables to the list
						subProblemVars.addAll(constraintVars);
						
						// Go back from the top to find more constraints
						// This is for something like (a, b, c), (d, e, f), (a, b, d)
						// In the first pass, (d, e, f) will be skipped, but after adding
						// (a, b, d), you need to go back
						if (skipped) {
							break;
						}
					} else {
						// Since a constraint got skipped, we may have to revisit from the top
						skipped = true;
					}
				}
				
			}
				
			// STEP 2: Solve the sub-problem. This will add the subProblemVars to either
			// positiveVars or negativeVars
			solveByBruteForce(pRawMaterial, subProblemConstraints, subProblemVars, positiveVars, negativeVars);
		}
		
		FinishedProduct fp = getFinishedProduct(positiveVars, negativeVars);
		float quality = fp.determineQuality(pRawMaterial).getValue().floatValue();
		fp.setQuality(new Quality(new Float(quality)));
		
		if(DEBUG) System.out.println("Solver completed");
		return fp;
	}

	private void solveByBruteForce(RawMaterial pRawMaterial,
			ArrayList<Constraint> constraints, Set<String> freeVars,
			Set<String> positiveVars, Set<String> negativeVars) {
		RawMaterial subProblem = new RawMaterial();
		subProblem.setConstraints(constraints);
		
		int numVars = freeVars.size();
		
		float bestQuality = 0f;
		Set<String> bestNegativeVars = freeVars;
		Set<String> bestPositiveVars = new TreeSet<String>();
		
		List<String> freeVarList = new ArrayList<String>(freeVars);
		
		for (int i=0; i < (int)Math.pow(2, numVars); i++) {
			Set<String> testPositiveVars = new TreeSet<String>();
			Set<String> testNegativeVars = new TreeSet<String>();
			
			int iCopy = i;
			for (int j = 0; j < numVars; j++) {
				if (iCopy % 2 == 0) {
					// The j-th bit is not set
					testNegativeVars.add(freeVarList.get(j));
				} else {
					testPositiveVars.add(freeVarList.get(j));
				}
				
				iCopy = iCopy / 2;
			}
			
			// Now add the known positive and negative vars
			testPositiveVars.addAll(positiveVars);
			testNegativeVars.addAll(negativeVars);
			
			// Determine the quality
			FinishedProduct fp = getFinishedProduct(testPositiveVars, testNegativeVars);
			float quality = fp.determineQuality(subProblem).getValue().floatValue();
			fp.setQuality(new Quality(new Float(quality)));
			
			if (quality > bestQuality) {
				// This is the best assignment yet
				bestQuality = quality;
				bestNegativeVars = testNegativeVars;
				bestPositiveVars = testPositiveVars;
			}
		}
		
		// Update the result. Since sets avoid dups it is ok to addAll
		negativeVars.addAll(bestNegativeVars);
		positiveVars.addAll(bestPositiveVars);
	}
	
	private FinishedProduct getFinishedProduct(Set<String> positiveVars, Set<String> negativeVars) {
		// Create the finished product
		FinishedProduct fp = new FinishedProduct();
		
		// Set the literals
		TreeSet<String> allVars = new TreeSet<String>();
		allVars.addAll(positiveVars);
		allVars.addAll(negativeVars);
		
		Iterator<String> iter = allVars.iterator();
		while (iter.hasNext()) {
			String varName = (String)iter.next();
			Literal lit = new Literal(new generated.Literal());
			
			if (positiveVars.contains(varName)) {
				lit.setLit(new PosLiteral(varName));
			} else {
				lit.setLit(new NegLiteral(varName));
			}
			
			fp.addLiteral(lit);
		}
		
		return fp;
	}
	
	private Set<String> getVariableSet(Constraint c) {
		Set<String> vars = new TreeSet<String>();
		Iterator<Variable> iter = c.getVariableList().iterator();
		while (iter.hasNext()) {
			vars.add(((Variable)iter.next()).getVariableName());
		}
		
		return vars;
	}
	
	public FinishedProduct getBestAssignment() {
		return bestAssignment;
	}
	
	private class WeightComparator<T> implements Comparator<T> {
		public int compare(Object o1, Object o2) {
			Constraint c1 = (Constraint)o1;
			Constraint c2 = (Constraint)o2;
			
			Integer w1 = new Integer(c1.getWeight().getWeight());
			Integer w2 = new Integer(c2.getWeight().getWeight());
			
			// Sort in descending order of weights
			int comp = w2.compareTo(w1);
			if (comp != 0) return comp;
			
			// Use default compare using hash-codes
			comp = new Integer(c1.hashCode()).compareTo(new Integer(c2.hashCode()));
			if (comp != 0) return comp;
			
			// Some default
			return -1;
		}
	}
	
	// TESTING ONLY
	public static void main(String[] args) throws Exception {
//		edu.neu.ccs.evergreen.ir.Relation relation = new edu.neu.ccs.evergreen.ir.Relation(3, 22);
//		System.out.println(relation.ones());
//		System.out.println(relation.reduce(2, 0));
//		System.out.println(relation.reduce(1, 0));
//		System.out.println(relation.reduce(0, 0));
//
//		if (1 == 1) return;
		
		String fileName = args[0];

		InputReader xmlReader = InputReader.initialize();
		Document rmDoc = xmlReader.prepareDocument(fileName);
		RawMaterial rm = xmlReader.parseRawMaterial(rmDoc);
		
		IterativeBruteForceSolver solver = new IterativeBruteForceSolver(rm);
		FinishedProduct soln = solver.getBestAssignment();
		System.out.println("SOLUTION: ");
		System.out.println(soln.generateXML());
		System.out.println("Quality: " + soln.getQuality().getValue());
	}
	
}