/*
 * ECatalog is a database front-end, with two main features:
 * 1. Use of preferences
 *  A preference-based approach, where the user is allowed to define the importance of each criterion.
 *  Then the items are ranked accordingly to his criteria.
 * 2. Trade-off analysis
 *  A cooperative database approach, where the system "argues" with the user about his criteria.
 *  When there are no matching items, the system explains the minimal conflicting set and
 *  give some possible strong and weak relaxations about his criteria.
 * This package also containts the software and the set-up details used for our User Study,
 * comparing the use or not of the two previous features mentioned above.
 *
 * Copyright (C) 2006 David Portabella Clotet, Artificial Intelligence Laboratory, EPFL
 * 
 * This file is part of ecatalog-1.0.zip
 * 
 * ECatalog is free software and a free user study set-up;
 * you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 * 
 * ECatalog is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with ECatalog; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 * 
 * @version 1.0
 * @author David Portabella
 * To contact the author:
 * email: david@portabella.name and david.portabella@epfl.ch
 * 
 * More information about ECatalog:
 *  http://sourceforge.net/projects/ecatalog/
 *  http://icwww.epfl.ch/~portabel/ecatalogs/
 */

package ecatalog.db;

/**
The Orbital library is a Java class library providing object-oriented representations and algorithms for logic, mathematics and artificial intelligence. It comprises theorem proving, computer algebra, search and planning, as well as machine learning algorithms.
http://www.functologic.com/orbital/index.html
>I use it for the class public static Combinatorical getCombinations(int r, int n, boolean repetition);


TODO: This needs desperately to be completly rewritten!!

TODO: change the variables/function names to use the right terminology.
      instead of problem -> set. 
      instead of contained -> subset, superset.
      look at: http://en.wikipedia.org/wiki/Subset

      look at: Minimal Unsolvable Subproblem (MUS), email from akira,
      paper from Carlos: http://icwww.epfl.ch/publications/documents/IC_TECH_REPORT_200346.pdf 

      
*/

import ecatalog.ECatalog;
import ecatalog.ECatalogLog;

import java.util.*;
import java.io.*;
import java.sql.*;

import orbital.algorithm.Combinatorical;

import dpc.utils.SqlUtil;
import dpc.utils.HttpUtil;
import dpc.utils.ArrayConverter;
import dpc.utils.TextUtil;

public class DBAnalysis
{
    Database db;

    Vector<Constraint> constraints;
    String[] constraintsSqlClause;
    //int[] constraintsIndex;
    int nbrConstraints;


    Vector<boolean[]> problems;
    int maxProblems;

    boolean cancel = false;
 
    /** computes nbrConstraints, constraint, constrainNum */
    public DBAnalysis(Database db, Vector<Constraint> allConstraints) {
	this.db = db;

	//Take the constraints that are defined
	constraints = new Vector<Constraint>();

	Vector<String> constraintsSqlClauseVector = new Vector<String>();
	for (int i = 0; i < allConstraints.size(); i++) {
	    Constraint constraint = allConstraints.get(i);
	    if (!constraint.areDetailsDefined())
		continue;
	    constraints.add(constraint);
	    constraintsSqlClauseVector.add(constraint.getSqlClauseTerm());
	}
	nbrConstraints = constraints.size();
	constraintsSqlClause = (String[]) constraintsSqlClauseVector.toArray(new String[nbrConstraints]);
    }

    public void cancel() {
	//ECatalog.lowlevelMsg("Analysis.cancel()");
	cancel = true;
    }


    /***************************************************************************************************
     *  GET POSSIBLE RELAXATIONS 
     ***************************************************************************************************/



    public class ConstraintRelaxation {
	public Constraint oldConstraint;
	public Constraint relaxedConstraint;
	public ConstraintRelaxation(Constraint oldConstraint, Constraint relaxedConstraint) {
	    this.oldConstraint = oldConstraint;
	    this.relaxedConstraint = relaxedConstraint;
	}
    }

    public class ConstraintRelaxationSet {
	public Vector<ConstraintRelaxation> constraintRelaxations = new Vector<ConstraintRelaxation>();
    }

    public class PossibleRelaxations {
	public Vector<ConstraintRelaxationSet> constraintRelaxationSetVector = new Vector<ConstraintRelaxationSet>();
	public String text;
    }


    /** Returns the list of possible relaxations: 
     *  Applying any of the ConstraintRelaxationSets will move to the database to a non-overconstrained situation.
     *  The type of relaxation for each constraint can be only: removeDetails, or set a new min or new max detail,
     *  but the type of constraint is never going to change.
     *	    @param relaxationListMaxSize           the maximum number of relaxations. if -1, then unlimited.
     *      @param maxNbrOfCombinedRelaxations     the maximum number of combined relaxations. if -1, then it is the number of constraints
     */
    public PossibleRelaxations getPossibleRelaxations(int relaxationListMaxSize, int maxNbrOfCombinedRelaxations, String textHeader, String hrefHeader) throws SQLException {
	Vector<ConstraintRelaxationSet> constraintRelaxationSetVector = getPossibleRelaxationsF(relaxationListMaxSize, maxNbrOfCombinedRelaxations);
	if (cancel) return null;

	PossibleRelaxations possibleRelaxations = new PossibleRelaxations(); 
	possibleRelaxations.constraintRelaxationSetVector = constraintRelaxationSetVector;

	if (possibleRelaxations.constraintRelaxationSetVector.size() == 0) {  //TODO minor: this template message should be somewhere else
	    possibleRelaxations.text = "You would need to relax more than " + maxNbrOfCombinedRelaxations + " criterias.<br>" +
		"Tip: Restart and solve the tradeoffs while adding new criteria<br>";
	} else {
	    possibleRelaxations.text = getPossibleRelaxationsText(textHeader, hrefHeader, possibleRelaxations);
	}

	return possibleRelaxations;
    }


    Vector<ConstraintRelaxationSet> getPossibleRelaxationsF(int relaxationListMaxSize, int maxNbrOfCombinedRelaxations) throws SQLException {

	Vector<ConstraintRelaxationSet> constraintRelaxationSetVector = new Vector<ConstraintRelaxationSet>();
	//Vector<Vector<Constraint>> relaxationListC = new Vector<Vector<Constraint>>();

	Vector<boolean[]> relaxationList = new Vector<boolean[]>();

	if (maxNbrOfCombinedRelaxations == -1)
	    maxNbrOfCombinedRelaxations = nbrConstraints;
	else
	    maxNbrOfCombinedRelaxations = Math.min(nbrConstraints, maxNbrOfCombinedRelaxations);

	for (int nbrOfCombinedRelaxations = 1; nbrOfCombinedRelaxations <= maxNbrOfCombinedRelaxations; nbrOfCombinedRelaxations++) {
	    if (cancel) return null;
	    Combinatorical cs = Combinatorical.getCombinations(nbrOfCombinedRelaxations, nbrConstraints, false);
	    while (cs.hasNext()) {
		if (cancel) return null;
		boolean[] relaxation = intSetToBooleanSet(nbrConstraints, cs.next());

		if (existSubSet(relaxation, relaxationList))
		    continue;
		//System.out.print("[" + id + ", " + cancel + "] ");

		String query = "SELECT COUNT(*) FROM " + db.fromClause + " WHERE " + db.whereClause;
		for (int i = 0; i < nbrConstraints; i++) if (!relaxation[i]) query += " AND " + constraintsSqlClause[i];
		if (SqlUtil.getUniqueInt(db.executeQuery(query)) == 0)
		    continue;   // This relaxation does not give any results


		relaxationList.add(relaxation);

		boolean usefulRelaxationFound = false;

		// a possible relaxation is to: relax location and rent
                // is this case, there is an inequaility constraint, so we can transform the relaxation to: relax location and rent to <=1300.
		int[] inequalitiesConstraints = getInequalityConstraints(relaxation);
		if (inequalitiesConstraints.length > 0) {
		    if (cancel) return null;
		    for (int i = 0; i < inequalitiesConstraints.length; i++) {
			if (cancel) return null;
			//get the value for the inequality constraint
			int constraintIndex = inequalitiesConstraints[i];
			AttributeConstraint constraint = (AttributeConstraint) constraints.get(constraintIndex);
			String minmax = (constraint instanceof LessThanOrEqualConstraint) ? "MIN" : "MAX";
			query = "SELECT " + minmax + "(" + constraint.getAttribute().getId() + ") FROM " + db.fromClause + " WHERE " + db.whereClause;
			for (int j = 0; j < nbrConstraints; j++)
			    if (!relaxation[j]) query += " AND " + constraintsSqlClause[j];
			double minmaxNum = SqlUtil.getUniqueDouble(db.executeQuery(query));

			if (   (constraint instanceof MoreThanOrEqualConstraint && minmaxNum == ((NumberAttribute)((MoreThanOrEqualConstraint)constraint).getAttribute()).getMinValueId())
			    || (constraint instanceof LessThanOrEqualConstraint && minmaxNum == ((NumberAttribute)((LessThanOrEqualConstraint)constraint).getAttribute()).getMaxValueId()))
			    continue;           // relaxing to rooms>=1 is useless. better just say relax rooms.
			
			usefulRelaxationFound = true;
			       
			//Construct the relaxation andd add it to the list
			ConstraintRelaxationSet constraintRelaxationSet = new ConstraintRelaxationSet();
			for (int j = 0; j < nbrConstraints; j++) {
			    if (!relaxation[j]) continue;
			   
			    try {
				Constraint oldC = constraints.get(j);
				Constraint newC = (Constraint) oldC.clone();
				if (j == inequalitiesConstraints[i]) {
				    SimpleAttributeConstraint newSC = (SimpleAttributeConstraint)newC;
				    newSC.setValueIndex(((NumberAttribute)newSC.getAttribute()).getValueIndex(minmaxNum));
				} else {
				    newC.removeDetails();
				}
				constraintRelaxationSet.constraintRelaxations.add(new ConstraintRelaxation(oldC, newC));
			    } catch (CloneNotSupportedException e) { 
				//ECatalog.error(e); 
				//throw new Error(); //it is already done, but to avoid the java compiling error
				throw new Error(e);
			    }
			}
			constraintRelaxationSetVector.add(constraintRelaxationSet);
			if (relaxationListMaxSize != -1 && constraintRelaxationSetVector.size() >= relaxationListMaxSize) {
			    return constraintRelaxationSetVector;
			}
		    }
		}

		if (usefulRelaxationFound == false) {
		    //Construct the relaxation andd add it to the list

		    ConstraintRelaxationSet constraintRelaxationSet = new ConstraintRelaxationSet();
		    //Vector<Constraint> relaxationC = new Vector<Constraint>();
		    for (int j = 0; j < nbrConstraints; j++) {
			if (!relaxation[j]) continue;
			
			try {
			    Constraint oldC = constraints.get(j);
			    Constraint newC = (Constraint) oldC.clone();
			    newC.removeDetails();
			    constraintRelaxationSet.constraintRelaxations.add(new ConstraintRelaxation(oldC, newC));
			} catch (CloneNotSupportedException e) { 
			    //ECatalog.error(e); 
			    //throw new Error(); //it is already done, but to avoid the java compiling error
			    throw new Error(e);
			}
		    }
		    constraintRelaxationSetVector.add(constraintRelaxationSet);
		    if (relaxationListMaxSize != -1 && constraintRelaxationSetVector.size() >= relaxationListMaxSize) {
			return constraintRelaxationSetVector;
		    }
		}
	    }
	}
	return constraintRelaxationSetVector;
    }

    int[] getInequalityConstraints(boolean[] relaxation) {
	Vector<Integer> inequalities = new Vector<Integer>();
	for (int i = 0; i < nbrConstraints; i++) {
	    if (relaxation[i] && (constraints.get(i) instanceof LessThanOrEqualConstraint || constraints.get(i) instanceof MoreThanOrEqualConstraint))
		inequalities.add(i);
	}
	return ArrayConverter.toIntegers(inequalities);
    }

    static String getPossibleRelaxationsText(String textHeader, String hrefHeader, PossibleRelaxations possibleRelaxations) {
	if (possibleRelaxations.constraintRelaxationSetVector.size() == 0)
	    return "Nothing to relax";

	StringBuffer text = new StringBuffer(textHeader);
		    
	for (int i = 0; i < possibleRelaxations.constraintRelaxationSetVector.size(); i++) {
	    ConstraintRelaxationSet constraintRelaxationSet = possibleRelaxations.constraintRelaxationSetVector.get(i);
	    if (i!=0) text.append(" or ");
	    text.append("<a href=\"" + hrefHeader + i + "\">" + HttpUtil.encodeHtml(getRelaxationText(constraintRelaxationSet)) + "</a>");
	}
	return text.toString();
    }


    static String getRelaxationText(ConstraintRelaxationSet constraintRelaxationSet) {
	StringBuffer text = new StringBuffer();
	boolean first = true;
	for (ConstraintRelaxation cr : constraintRelaxationSet.constraintRelaxations) {
	    if (!first) text.append(" AND "); else first = false;
		
	    String term;
	    if (cr.relaxedConstraint.areDetailsDefined() == false) {
		term = "clear " + ((AttributeConstraint)cr.relaxedConstraint).getAttribute().getLabel();
	    } else {
		SimpleAttributeConstraint c = (SimpleAttributeConstraint) cr.oldConstraint;
		String op;
		if (c instanceof LessThanOrEqualConstraint) op = "<=";
		else if (c instanceof MoreThanOrEqualConstraint) op = ">=";
		else throw new Error("unexpected constraint type: " + c);
		String oldValue = c.getAttribute().getValueString(c.getValueIndex());
		term = "change " + cr.relaxedConstraint.getRelaxConstraintString() + " (instead of " + op + " " + oldValue + ")";
	    }
	    text.append(dpc.utils.HttpUtil.encodeHtml(term));
	}
	return text.toString();
    }	


    /** The input  set intSet has the items intSet[0], intSet[1]...
        The output set booleanSet has the items 'i' if booleanSet[i]==true   */
    static boolean[] intSetToBooleanSet(int setLength, int[] intSet) {
	boolean[] booleanSet = new boolean[setLength];
	for (int itemIndex : intSet)
	    booleanSet[itemIndex] = true;
	return booleanSet;

    }


    /** returns whether superSet is indeed a super set of any of the sets in subSet **/
    static boolean existSubSet(boolean[] superSet, Vector<boolean[]> subSets) {
	for (int i = 0; i < subSets.size(); i++)
	    if (isSuperSet(superSet, (boolean[]) subSets.get(i)))
		return true;
	return false;
    }

    /** returns whether superSet is indeed a super set of subSet **/
    static boolean isSuperSet(boolean[] superSet, boolean[] subSet) {
	for (int i = 0; i < superSet.length; i++)
	    if (subSet[i]==true && superSet[i]==false)
		return false;
	return true;
    }





    /***************************************************************************************************
     *  GET MINIMAL POSSIBLE RELAXATIONS 
     ***************************************************************************************************/

    public class MinimalUnsolvableSubproblem {
	public Vector<Constraint> constraints;
	//public int[] constraintsIndex;
	//public Vector<boolean[]> problems;
	public Vector<Problem> problems;
	public String text;
    }
    public class Problem {
	public boolean[] problem;
	public PossibleRelaxations possibleRelaxations;
    }


    /***************************************************************************************************/
    /** compute the minimal constraining set, and returns a textual (html) description.
     * if maxProblems == -1, it only returns the first (more compact) items of the set.
     */

    public MinimalUnsolvableSubproblem getMinimalUnsolvableSubproblem(int minimalUnsolvableSubproblemMaxSize) throws SQLException {
	maxProblems = minimalUnsolvableSubproblemMaxSize;
	getProblems();

	if (cancel) return null;

	MinimalUnsolvableSubproblem minimalUnsolvableSubproblem = new MinimalUnsolvableSubproblem();
	minimalUnsolvableSubproblem.constraints = constraints;
	minimalUnsolvableSubproblem.problems = new Vector<Problem>();
	for (int i = 0; i < problems.size(); i++) { //boolean[] bproblem : problems) {
	    if (cancel) return null;

	    Problem problem = new Problem();
	    problem.problem = problems.get(i);
	    String hrefHeader = String.valueOf(i) + " ";
	    problem.possibleRelaxations = computeProblemPossibleRelaxation(problems.get(i), hrefHeader);
	    minimalUnsolvableSubproblem.problems.add(problem);
	}
	minimalUnsolvableSubproblem.text = getMinimalUnsolvableSubproblemText(minimalUnsolvableSubproblem);

	return minimalUnsolvableSubproblem;
    }
    
    PossibleRelaxations computeProblemPossibleRelaxation(boolean[] problem, String hrefHeader) throws SQLException {
	Vector<Constraint> problemConstraints = new Vector<Constraint>();
	for (int i = 0; i < problem.length; i++)
	    if (problem[i])
		problemConstraints.add(constraints.get(i));

	final String textHeader = "&nbsp;&nbsp;&nbsp;To solve: ";
	DBAnalysis analysis = new DBAnalysis(db, problemConstraints);
	PossibleRelaxations possibleRelaxations = analysis.getPossibleRelaxations(problemConstraints.size(), 1, textHeader, hrefHeader);
	return possibleRelaxations;
    }

    void getProblems() throws SQLException {
	problems = new Vector<boolean[]>();
	boolean[] selectedConstraints = new boolean[nbrConstraints];
	for (int nbrWantedConstraints = 1; nbrWantedConstraints <= nbrConstraints; nbrWantedConstraints++) {
	    if (cancel) return;
	    //	    System.out.println("nbrWantedConstraints: " + nbrWantedConstraints);
	    checkRecursive(selectedConstraints, -1, nbrWantedConstraints, -1);
	}
    }


    //returns false if not solution, returns true if there is at least one solution
    void checkRecursive(boolean[] selectedConstraints, int start, int nbrWantedConstraints, int nbrCurrentConstraints) throws SQLException {
	if (start != -1)
	    selectedConstraints[start] = true;

	if (existSubSet(selectedConstraints))
	    return;

	if (start != -1 && nbrWantedConstraints==nbrCurrentConstraints+1) {
	    if (checkConstraints(selectedConstraints) == 0) {
		problems.add(selectedConstraints);
		//printConstraints(selectedConstraints);
		return;
	    }
	}
	if (start == nbrConstraints-1)
	    return;
	for (int j = start+1; j < nbrConstraints; j++) {
	    if (cancel) return;
	    checkRecursive((boolean[]) selectedConstraints.clone(), j, nbrWantedConstraints, nbrCurrentConstraints+1);
	    if (maxProblems != -1 && problems.size() > maxProblems)
		break;
	}

	return;
    }



    /** returns whether superSet is indeed a super set of any of the sets in 'problems' **/
    boolean existSubSet(boolean[] superSet) {
	return existSubSet(superSet, problems);
    }


    int checkConstraints(boolean[] constraints) throws SQLException {
	//	System.out.println("check::"); printConstraints(constraints);
	//build query
	String query = "SELECT COUNT(*) FROM " + db.fromClause + " WHERE " + db.whereClause;
	for (int i = 0; i < nbrConstraints; i++)
	    if (constraints[i])
		query += " AND " + constraintsSqlClause[i];

	///	    String text = attribute[i].userConstraint.getSqlClauseTerm();

	int rows = SqlUtil.getUniqueInt(db.executeQuery(query));
	return rows;
    }

    /*
    void printConstraints(boolean[] constraints) {
	System.out.println("constraint: " +  getDescription(constraints));
    }	
    */

    String getDescription(Problem problem) {
	StringBuffer text = new StringBuffer("There are no items with: ");
	boolean first = true;
	for (int i = 0; i < problem.problem.length; i++)
	    if (problem.problem[i]) {
		if (!first)
		    text.append(" and ");
		else
		    first = false;
		
		String term = constraints.get(i).getWithConstraintString();
		text.append("<u>" + dpc.utils.HttpUtil.encodeHtml(term) + "</u>");
	    }
	text.append("<br>\n");
	text.append(problem.possibleRelaxations.text + "<br>\n");
	
	return text.toString();
    }	

    String getMinimalUnsolvableSubproblemText(MinimalUnsolvableSubproblem minimalUnsolvableSubproblem) {
	StringBuffer analysis = new StringBuffer();
	for (Problem problem : minimalUnsolvableSubproblem.problems)
	    analysis.append(getDescription(problem));

	return analysis.toString();
    }




    /***************************************************************************************************
     *  EXECUTE RELAXATION 
     ***************************************************************************************************/
    public static void executeRelaxation(String relaxationCode, PossibleRelaxations possibleRelaxations, MinimalUnsolvableSubproblem minimalUnsolvableSubproblem, ECatalogLog log) {
	assert(possibleRelaxations != null);

	StringTokenizer st = new StringTokenizer(relaxationCode);
	int minimalUnsolvableSubproblemIndex = Integer.parseInt(st.nextToken());
	int relaxationSetIndex = Integer.parseInt(st.nextToken());

	DBAnalysis.ConstraintRelaxationSet relaxationSet = (minimalUnsolvableSubproblemIndex == -1) 
	    ? possibleRelaxations.constraintRelaxationSetVector.get(relaxationSetIndex) 
	    : minimalUnsolvableSubproblem.problems.get(minimalUnsolvableSubproblemIndex).possibleRelaxations.constraintRelaxationSetVector.get(relaxationSetIndex);

	if (log != null)
	    log.relaxationSelected(minimalUnsolvableSubproblemIndex, relaxationSetIndex, relaxationSet);

	for (DBAnalysis.ConstraintRelaxation cr : relaxationSet.constraintRelaxations) {
	    cr.oldConstraint.importDetails(cr.relaxedConstraint);
	}
    }
}