import java.io.*;
import java.util.*;
import edu.neu.ccs.evergreen.ir.*;
import edu.neu.ccs.evergreen.*;

/**
 * 
 * @author Vlad-Alexandru Slavici
 *
 */
class Decide{
	
	static Vector sortedVariables=new Vector();
	static int c=0;
	
	/**
	 * choose what variable to decide based on the values of the lookahead polynomials
	 *  
	 * @param csp
	 * 			the current CSP instance
	 * @param initial
	 * 			is it a first call to the method after restart
	 * 
	 * @return the <variable,assignment> object
	 */
	public static VarAssign/*<Integer,Integer>*/ choose(CSP csp, boolean initial){
	
			Random r=new Random();
			if (sortedVariables.size()>0)
				while (csp.unassigned.indexOf(((VarAssign)sortedVariables.get(0)).getVar())<0)
				{
					sortedVariables.remove(0);
					if (sortedVariables.size()==0) break;
				}
	
			//we choose to sort the numbers with a csp.p probability
			if (r.nextInt(1000)*1.0/1000<=csp.p || sortedVariables.size()==0){
				//we must sort the numbers according to the biases
				Vector sortedVar=new Vector();
				Vector sortedValues=new Vector();
				
				Vector unassigned=new Vector(csp.unassigned);
				Vector assignment=new Vector(csp.assignment.keySet());
				
				
				
				for (int i=0;i<unassigned.size();i++){
					
					c++;
					
					//we'll see which option yield a larger maximum value of the
					//lookahead polynomial: setting the next unassigned value to 0 or 1
					csp.assignment.put(csp.unassigned.get(i),new Integer(0));
					
					CSP csp_aux=new CSP();
					
					Iterator it=csp.assignment.keySet().iterator();
					
					while (it.hasNext()){
						Integer v=(Integer)it.next();
						csp_aux.assignment.put(new Integer(v.intValue()),new Integer(((Integer)csp.assignment.get(v)).intValue()));
					}
					
					it=csp.previous_best.keySet().iterator();
					
					while (it.hasNext()){
						Integer v=(Integer)it.next();
						csp_aux.previous_best.put(new Integer(v.intValue()),new Integer(((Integer)csp.previous_best.get(v)).intValue()));
					}
					
					for (int k=0;k<csp.relations.size();k++){
						csp_aux.relations.add(new Rel3((Rel3)csp.relations.get(k)));
					}
					
					csp_aux.num_rel=csp.num_rel;
					csp_aux.num_var=csp.num_var;
					csp_aux.total_nr=csp.total_nr;
					
					//reducing the relations
					
					for (int j=0;j<csp_aux.relations.size();j++){
						Rel3 relation=(Rel3)csp_aux.relations.get(j);
						
						int relationNumber=relation.number;
						
						if (csp_aux.assignment.get(new Integer(relation.x))!=null)
							relationNumber=Relation1.reduce(relationNumber,2,((Integer)csp_aux.assignment.get(new Integer(relation.x))).intValue());
						if (csp_aux.assignment.get(new Integer(relation.y))!=null)
							relationNumber=Relation1.reduce(relationNumber,1,((Integer)csp_aux.assignment.get(new Integer(relation.y))).intValue());
						if (csp_aux.assignment.get(new Integer(relation.z))!=null)
							relationNumber=Relation1.reduce(relationNumber, 0, ((Integer)csp_aux.assignment.get(new Integer(relation.z))).intValue());
						
						relation.number=relationNumber;
						
						csp_aux.relations.remove(j);
						
						
						csp_aux.relations.add(j,relation);
					}
									
					it=csp_aux.previous_best.keySet().iterator();
					
					//n-Mapping the current constraints with respect to the previous best assignment
					
					Vector nMappable=new Vector();
					
					while (it.hasNext()){
						Integer var=(Integer)it.next();
						
						if (((Integer)csp_aux.previous_best.get(var)).intValue()==1){
							nMappable.add(var);
						}
					}
					
					for (int j=0;j<csp_aux.relations.size();j++){
						Rel3 relation=(Rel3)csp_aux.relations.get(j);
						Relation rels=new Relation(3,relation.number);
						if (nMappable.contains(new Integer(relation.x))){
							rels=new Relation(3,rels.nMap(2));
						}
						if (nMappable.contains(new Integer(relation.y))){
							rels=new Relation(3,rels.nMap(1));
						}
						if (nMappable.contains(new Integer(relation.z))){
							rels=new Relation(3,rels.nMap(0));
						}
						relation.number=rels.getRelationNumber();
						
						csp_aux.relations.remove(j);
						csp_aux.relations.add(j,relation);
					}
					
					Check.computePairs(true, csp_aux);
					
					//getting the maximum bias for the lookahead plynomial and
					//then evaluating the value of the polynomial at the maximum bias
					Output outp=(Output)SATSolverUtil.calculateBias(csp_aux);
					int j;
					for (j=0;j<sortedVar.size();j++){
						if (outp.getPolynomial().eval(outp.getMaxBias())
							 > ((Output)sortedValues.get(j)).getPolynomial().eval(((Output)sortedValues.get(j)).getMaxBias()))
						
							break;
					}
					

					sortedVar.add(j,new VarAssign((Integer)unassigned.get(i),new Integer(0)));
					sortedValues.add(j,outp);
					
					
					csp.assignment.put(csp.unassigned.get(i),new Integer(1));
					
					csp_aux=new CSP();
					it=csp.assignment.keySet().iterator();
					
					while (it.hasNext()){
						Integer v=(Integer)it.next();
						csp_aux.assignment.put(new Integer(v.intValue()),new Integer(((Integer)csp.assignment.get(v)).intValue()));
					}
					
					it=csp.previous_best.keySet().iterator();
					
					while (it.hasNext()){
						Integer v=(Integer)it.next();
						csp_aux.previous_best.put(new Integer(v.intValue()),new Integer(((Integer)csp.previous_best.get(v)).intValue()));
					}
					
					for (int k=0;k<csp.relations.size();k++){
						csp_aux.relations.add(new Rel3((Rel3)csp.relations.get(k)));
					}
					
					csp_aux.num_rel=csp.num_rel;
					csp_aux.num_var=csp.num_var;
					csp_aux.total_nr=csp.total_nr;
					
					
					for (j=0;j<csp_aux.relations.size();j++){
						Rel3 relation=(Rel3)csp_aux.relations.get(j);
						
						int relationNumber=relation.number;
						if (csp_aux.assignment.get(new Integer(relation.x))!=null)
							relationNumber=Relation1.reduce(relationNumber,2,((Integer)csp_aux.assignment.get(new Integer(relation.x))).intValue());
						if (csp_aux.assignment.get(new Integer(relation.y))!=null)
							relationNumber=Relation1.reduce(relationNumber,1,((Integer)csp_aux.assignment.get(new Integer(relation.y))).intValue());
						if (csp_aux.assignment.get(new Integer(relation.z))!=null)
							relationNumber=Relation1.reduce(relationNumber, 0, ((Integer)csp_aux.assignment.get(new Integer(relation.z))).intValue());
						
						relation.number=relationNumber;
						
						csp_aux.relations.remove(j);
						
						
						csp_aux.relations.add(j,relation);
					}
					
					
					it=csp_aux.previous_best.keySet().iterator();
					
					nMappable=new Vector();
					
					while (it.hasNext()){
						Integer var=(Integer)it.next();
						
						if (((Integer)csp_aux.previous_best.get(var)).intValue()==1){
							nMappable.add(var);
						}
					}
					
					for (j=0;j<csp_aux.relations.size();j++){
						Rel3 relation=(Rel3)csp_aux.relations.get(j);
						Relation rels=new Relation(3,relation.number);
						if (nMappable.contains(new Integer(relation.x))){
							rels=new Relation(3,rels.nMap(2));
						}
						if (nMappable.contains(new Integer(relation.y))){
							rels=new Relation(3,rels.nMap(1));
						}
						if (nMappable.contains(new Integer(relation.z))){
							rels=new Relation(3,rels.nMap(0));
						}
						relation.number=rels.getRelationNumber();
						
						
						
						csp_aux.relations.remove(j);
						csp_aux.relations.add(j,relation);
					}
					
					Check.computePairs(true, csp_aux);
					
					outp=(Output)SATSolverUtil.calculateBias(csp_aux);
					for (j=0;j<sortedVar.size();j++){
						if (outp.getPolynomial().eval(outp.getMaxBias())
							 > ((Output)sortedValues.get(j)).getPolynomial().eval(((Output)sortedValues.get(j)).getMaxBias()))
						
							break;
					}
					
					sortedVar.add(j,new VarAssign((Integer)unassigned.get(i),new Integer(1)));
					sortedValues.add(j,outp);
					
					
					
					csp.assignment.remove(unassigned.get(i));
					
				}
	
				sortedVariables=new Vector(sortedVar);
				sortedVariables.remove(0);
			
				return (VarAssign)sortedVar.get(0);
			}
			else{
					return (VarAssign)sortedVariables.remove(0);
			}
			
			
	}
	
	
	
}