/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package Transporte;

/**
 *
 * @author oarboleda
 */
/**
 *  Examples.java 
 *  This file is part of JaCoP.
 *
 *  JaCoP is a Java Constraint Programming solver. 
 *	
 *	Copyright (C) 2000-2008 Krzysztof Kuchcinski and Radoslaw Szymanek
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU Affero General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program 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 Affero General Public License for more details.
 *  
 *  Notwithstanding any other provision of this License, the copyright
 *  owners of this work supplement the terms of this License with terms
 *  prohibiting misrepresentation of the origin of this work and requiring
 *  that modified versions of this work be marked in reasonable ways as
 *  different from the original version. This supplement of the license
 *  terms is in accordance with Section 7 of GNU Affero General Public
 *  License version 3.
 *
 *  You should have received a copy of the GNU Affero General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 */

import JaCoP.constraints.Constraint;
import JaCoP.core.IntVar;
import JaCoP.core.Store;
import JaCoP.core.Var;
import JaCoP.search.CreditCalculator;
import JaCoP.search.DepthFirstSearch;
import JaCoP.search.IndomainMedian;
import JaCoP.search.IndomainMiddle;
import JaCoP.search.IndomainMin;
import JaCoP.search.IndomainSimpleRandom;
import JaCoP.search.LDS;
import JaCoP.search.MaxRegret;
import JaCoP.search.MostConstrainedStatic;
import JaCoP.search.NoGoodsCollector;
import JaCoP.search.Search;
import JaCoP.search.SelectChoicePoint;
import JaCoP.search.Shaving;
import JaCoP.search.SimpleSelect;
import JaCoP.search.SmallestDomain;
import JaCoP.search.SmallestMin;
import JaCoP.search.WeightedDegree;

import java.util.*;

/**
 * It is an abstract class to describe all necessary functions of any store.
 * 
 * @author Radoslaw Szymanek and Krzysztof Kuchcinski
 * @version 3.0
 */

public abstract class Example {

	/**
	 * It contains all variables used within a specific example.
	 */
	public ArrayList<Var> vars;
	
	/**
	 * It specifies the cost function, null if no cost function is used.
	 */
	public IntVar cost;
	
	/**
	 * It specifies the constraint store responsible for holding information 
	 * about constraints and variables.
	 */
	public Store store;
	
	/**
	 * It specifies the search procedure used by a given example.
	 */
	public Search search;	
	
	/**
	 * It specifies a standard way of modeling the problem.
	 */
	public abstract void model();
	
	/**
	 * It specifies simple search method based on input order and lexigraphical 
	 * ordering of values. 
	 * 
	 * @return true if there is a solution, false otherwise.
	 */
	public boolean search() {
		
		long T1, T2;
		T1 = System.currentTimeMillis();
		
		SelectChoicePoint select = new SimpleSelect(vars.toArray(new Var[1]), null,
				new IndomainMin());

		search = new DepthFirstSearch();

		boolean result = search.labeling(store, select);

		if (result)
			store.print();

		T2 = System.currentTimeMillis();

		System.out.println("\n\t*** Execution time = " + (T2 - T1) + " ms");
		
		System.out.println();
		System.out.print(search.getNodes() + "\t");
		System.out.print(search.getDecisions() + "\t");
		System.out.print(search.getWrongDecisions() + "\t");
		System.out.print(search.getBacktracks() + "\t");
		System.out.print(search.getMaximumDepth() + "\t");
		
		return result;
		
	}	

	/**
	 * It specifies simple search method based on input order and lexigraphical 
	 * ordering of values. It optimizes the solution by minimizing the cost function.
	 * 
	 * @return true if there is a solution, false otherwise.
	 */
	public boolean searchOptimal() {
		
		long T1, T2;
		T1 = System.currentTimeMillis();
		
		SelectChoicePoint select = new SimpleSelect(vars.toArray(new Var[1]), null,
				new IndomainMin());

		search = new DepthFirstSearch();
		
		boolean result = search.labeling(store, select, cost);

		if (result){
			store.print();
                }

		T2 = System.currentTimeMillis();

		System.out.println("\n\t*** Execution time = " + (T2 - T1) + " ms");
		
		return result;
		
	}	
	
	
	/**
	 * It searches for all solutions with the optimal value.
	 * @return true if any optimal solution has been found.
	 */
	public boolean searchAllOptimal() {
		
		long T1, T2, T;
		T1 = System.currentTimeMillis();

		SelectChoicePoint select = new SimpleSelect(vars.toArray(new Var[1]), null,
													new IndomainMin());

		search = new DepthFirstSearch();
		search.getSolutionListener().searchAll(true);
		search.getSolutionListener().recordSolutions(true);

		boolean result = search.labeling(store, select, cost);

		T2 = System.currentTimeMillis();
		T = T2 - T1;
		System.out.println("\n\t*** Execution time = " + T + " ms");

		return result;
		
	}
	
	/**
	 * It specifies simple search method based on smallest domain variable order 
	 * and lexigraphical ordering of values. 
	 * @param optimal it specifies if the search the optimal solution takes place.
	 * 
	 * @return true if there is a solution, false otherwise.
	 */

	public boolean searchSmallestDomain(boolean optimal) {
		
		long T1, T2;
		T1 = System.currentTimeMillis();
		
		SelectChoicePoint select = new SimpleSelect(vars.toArray(new Var[1]), new SmallestDomain(),
				new IndomainMin());

		search = new DepthFirstSearch();

		boolean result = false;
		
		if (optimal) {
			search.labeling(store, select, cost);
                }
                else{
			search.labeling(store, select);
}
		System.out.println();
		System.out.print(search.getNodes() + "\t");
		System.out.print(search.getDecisions() + "\t");
		System.out.print(search.getWrongDecisions() + "\t");
		System.out.print(search.getBacktracks() + "\t");
		System.out.print(search.getMaximumDepth() + "\t");
		
		if (result)
			store.print();

		T2 = System.currentTimeMillis();

		System.out.println("\n\t*** Execution time = " + (T2 - T1) + " ms");
		
		return result;
		
	}	
	
	/**
	 * It specifies simple search method based on weighted degree variable order 
	 * and lexigraphical ordering of values. This search method is rather general
	 * any problem good fit. It can be a good first trial to see if the model is 
	 * correct.
	 * 
	 * @return true if there is a solution, false otherwise.
	 */

	public boolean searchWeightedDegree() {
		
		long T1, T2;
		T1 = System.currentTimeMillis();
		
		SelectChoicePoint select = new SimpleSelect(vars.toArray(new Var[1]), 
							    new WeightedDegree(),
							    new SmallestDomain(),
							    new IndomainMin());

		search = new DepthFirstSearch();

		boolean result = search.labeling(store, select);

		System.out.println();
		System.out.print(search.getNodes() + "\t");
		System.out.print(search.getDecisions() + "\t");
		System.out.print(search.getWrongDecisions() + "\t");
		System.out.print(search.getBacktracks() + "\t");
		System.out.print(search.getMaximumDepth() + "\t");
		
		if (result)
			store.print();

		T2 = System.currentTimeMillis();

		System.out.println("\n\t*** Execution time = " + (T2 - T1) + " ms");
		
		return result;
		
	}	

	/**
	 * It specifies simple search method based variable order which 
	 * takes into account the number of constraints attached to a variable 
	 * and lexigraphical ordering of values. 
	 * 
	 * @return true if there is a solution, false otherwise.
	 */

	public boolean searchMostConstrainedStatic() {
		
		search = new DepthFirstSearch();

		SelectChoicePoint select = new SimpleSelect(vars.toArray(new Var[1]),
				new MostConstrainedStatic(), new IndomainMin());

		boolean result = search.labeling(store, select);

		System.out.println();
		System.out.print(search.getNodes() + "\t");
		System.out.print(search.getDecisions() + "\t");
		System.out.print(search.getWrongDecisions() + "\t");
		System.out.print(search.getBacktracks() + "\t");
		System.out.print(search.getMaximumDepth() + "\t");
		
		if (!result)
			System.out.println("**** No Solution ****");

		return result;
	}
	
	/**
	 * It specifies simple search method based on most constrained static and lexigraphical 
	 * ordering of values. It searches for all solutions.
	 * 
	 * @return true if there is a solution, false otherwise.
	 */

	public boolean searchAllAtOnce() {
		
		long T1, T2;
		T1 = System.currentTimeMillis();		
		
		SelectChoicePoint select = new SimpleSelect(vars.toArray(new Var[1]),
				new MostConstrainedStatic(), new IndomainMin());

		search = new DepthFirstSearch();
		
		search.getSolutionListener().searchAll(true);
		search.getSolutionListener().recordSolutions(true);
		search.setAssignSolution(true);
		
		boolean result = search.labeling(store, select);

		T2 = System.currentTimeMillis();

		if (result) {
			System.out.println("Number of solutions " + search.getSolutionListener().solutionsNo());
			search.printAllSolutions();
		} 
		else
			System.out.println("Failed to find any solution");

		System.out.println("\n\t*** Execution time = " + (T2 - T1) + " ms");

		return result;
	}	
	
	
	/**
	 * It searches using an input order search with indomain based on middle value.
	 * @return true if there is a solution, false otherwise.
	 */
	public boolean searchMiddle() {

		long begin = System.currentTimeMillis();

		search = new DepthFirstSearch();

		SelectChoicePoint select = new SimpleSelect(vars.toArray(new Var[1]), 
													null, new IndomainMiddle());

		boolean result = search.labeling(store, select);

		long end = System.currentTimeMillis();

		System.out.println("Number of milliseconds " + (end - begin));

		return result;
	}

	/**
	 * It searches with shaving which is guided by supplied constraints.
	 * @param guidingShaving the array of constraints proposing shaving candidates.
	 * @param printInfo it specifies if that function should print any info.
	 * @return true if the solution was found, false otherwise.
	 */
	public boolean shavingSearch(ArrayList<Constraint> guidingShaving, boolean printInfo) {

		Shaving shaving = new Shaving();
		shaving.setStore(store);
		shaving.quickShave = true;

		for (Constraint c : guidingShaving)
			shaving.addShavingConstraint(c);

		long begin = System.currentTimeMillis();

		search = new DepthFirstSearch();
		search.setPrintInfo(printInfo);
		
		SelectChoicePoint select = new SimpleSelect(vars.toArray(new Var[1]), null, new IndomainMiddle());

		search.setConsistencyListener(shaving);
		search.setExitChildListener(shaving);

		boolean result = search.labeling(store, select);

		long end = System.currentTimeMillis();

		if (printInfo) {
			System.out.println("Number of milliseconds " + (end - begin));
			System.out.println("Ratio "	+ (shaving.successes * 100 / (shaving.successes + shaving.failures)));

			if (result)
				store.print();
		}
		
		return result;

	}
	
	/**
	 * It conducts the search with restarts from which the no-goods are derived. 
	 * Every search contributes with new no-goods which are kept so eventually
	 * the search is complete (although can be very expensive to maintain explicitly
	 * all no-goods found during search). 
	 * @return true if there is a solution, false otherwise.
	 */
	public boolean searchWithRestarts() {
		
		// Input Order tie breaking
		boolean result = false;
		boolean timeout = true;
		
		int nodes = 0;
		int decisions = 0;
		int backtracks = 0;
		int wrongDecisions = 0;

		search = new DepthFirstSearch();

		NoGoodsCollector collector = new NoGoodsCollector();
		search.setExitChildListener(collector);
		search.setTimeOutListener(collector);
		search.setExitListener(collector);

		SelectChoicePoint select = new SimpleSelect(vars.toArray(new Var[1]), new SmallestDomain(),
				new IndomainSimpleRandom());
		
		while (timeout) {

			// search.setPrintInfo(false);
			search.setNodesOut(1000);

			result = search.labeling(store, select);
			timeout &= collector.timeOut;
			
			nodes += search.getNodes();
			decisions += search.getDecisions();
			wrongDecisions += search.getWrongDecisions();
			backtracks += search.getBacktracks();

			search = new DepthFirstSearch();
			collector = new NoGoodsCollector();
			search.setExitChildListener(collector);
			search.setTimeOutListener(collector);
			search.setExitListener(collector);

		}

		// System.out.println(search.noGoodsVariables);
		// System.out.println(search.noGoodsValues);
		// System.out.println(store.watchedConstraints);

		// store.toXCSP2_0();
		// store.finalizeXCSP2_0(-1, "./", "restarts.xml");

		System.out.println();
		System.out.print(nodes + "\t");
		System.out.print(decisions + "\t");
		System.out.print(wrongDecisions + "\t");
		System.out.print(backtracks + "\t");

		if (result)
			System.out.println(1);
		else
			System.out.println(0);

		return result;
	}
	
	/**
	 * It uses credit search to solve a problem.
	 * @param credits the number of credits available.
	 * @param backtracks the maximum number of backtracks used when a path exhausts its credits.
	 * @param maxDepth the maximum depth to which the credit distribution takes place.
	 * @return true if a solution was found, false otherwise.
	 */
	public boolean creditSearch(int credits, int backtracks, int maxDepth) {

		SelectChoicePoint select = new SimpleSelect(vars
				.toArray(new Var[1]), new SmallestDomain(),
				new IndomainMin());

		CreditCalculator credit = new CreditCalculator(credits, backtracks, maxDepth);

		search = new DepthFirstSearch();

		if (search.getConsistencyListener() == null)
			search.setConsistencyListener(credit);
		else
			search.getConsistencyListener().setChildrenListeners(credit);

		search.setExitChildListener(credit);
		search.setTimeOutListener(credit);

		boolean result = search.labeling(store, select);

		store.print();

		System.out.print(search.getNodes() + "\t");
		System.out.print(search.getDecisions() + "\t");
		System.out.print(search.getWrongDecisions() + "\t");
		System.out.print(search.getBacktracks() + "\t");
		System.out.print(search.getMaximumDepth() + "\t");

		if (result)
			System.out.println(1);
		else
			System.out.println(0);

		return result;
	}

	
    /**
    *
    * It uses MaxRegret variable ordering heuristic to search for a solution.
    * @return true if there is a solution, false otherwise.
    *
    */
   public boolean searchWithMaxRegret() {

       SelectChoicePoint select = new SimpleSelect (vars.toArray(new Var[0]),
                                                   	new MaxRegret(),
                                                   	new SmallestDomain(),
                                                    new IndomainMiddle());
       
       search = new DepthFirstSearch();
       search.getSolutionListener().searchAll(true);
       search.getSolutionListener().recordSolutions(true);
       
       boolean result = search.labeling(store, select);
       
	   return result;

   }
	
   /**
    * It searches for solution using Limited Discrepancy Search.
    * @param noDiscrepancy maximal number of discrepancies
    * @return true if the solution was found, false otherwise.
    */
   public boolean searchLDS(int noDiscrepancy) {
		
		search = new DepthFirstSearch();

		boolean result = false;

		SelectChoicePoint select = new SimpleSelect(vars.toArray(new Var[1]),
				new SmallestDomain(), new IndomainMiddle());

		LDS lds = new LDS(noDiscrepancy);

		if (search.getExitChildListener() == null)
			search.setExitChildListener(lds);
		else
			search.getExitChildListener().setChildrenListeners(lds);

		// Execution time measurement
		long begin = System.currentTimeMillis();

		result = search.labeling(store, select);

		// Execution time measurement
		long end = System.currentTimeMillis();

		System.out.println("Number of milliseconds " + (end - begin));

		return result;
		
	}
   
   
 /**
  * It searches for optimal solution using max regret variable ordering
  * and indomain min for value ordering.
 * @return true if there is a solution, false otherwise.
 */
   public boolean searchMaxRegretOptimal() {
		
		long T1, T2, T;
		T1 = System.currentTimeMillis();

		search = new DepthFirstSearch();

		SelectChoicePoint select = new SimpleSelect(vars.toArray(new Var[1]), new MaxRegret(),
				new IndomainMin());

		boolean result = search.labeling(store, select, cost);

		T2 = System.currentTimeMillis();
		T = T2 - T1;

		if (result)
			System.out.println("Variables : " + vars);
		else
			System.out.println("Failed to find any solution");

		System.out.println("\n\t*** Execution time = " + T + " ms");

		return result;
	}
   
   /**
    * It searches using smallest domain variable ordering and 
    * indomain middle value ordering. 
    * @return true if there is a solution, false otherwise.
    */
   public boolean searchSmallestMiddle() {
		
		long begin = System.currentTimeMillis();

		boolean result = false;

		search = new DepthFirstSearch();

		SelectChoicePoint select = new SimpleSelect(vars.toArray(new Var[1]), new SmallestDomain(),
				new IndomainMiddle());

		result = search.labeling(store, select);

		long end = System.currentTimeMillis();


		System.out.println("Number of milliseconds " + (end - begin));
		
		return result;
		
	}

   
   /**
    * It searches using smallest domain variable ordering and 
    * indomain middle value ordering. 
    * @return true if there is a solution, false otherwise.
    */
   public boolean searchSmallestMedian() {
		
		long begin = System.currentTimeMillis();

		boolean result = false;

		search = new DepthFirstSearch();

		SelectChoicePoint select = new SimpleSelect(vars.toArray(new Var[1]), new SmallestDomain(),
				new IndomainMedian());

		result = search.labeling(store, select);

		long end = System.currentTimeMillis();


		System.out.println("Number of milliseconds " + (end - begin));
		
		return result;
		
	}
   
   
	/**
	 * It searches using Smallest Min variable ordering heuristic and indomainMin value
	 * ordering heuristic.
	 * 
	 * @return true if there is a solution, false otherwise.
	 */
	public boolean searchSmallestMin() { 

		long begin = System.currentTimeMillis();
		
		SelectChoicePoint select = new SimpleSelect(vars.toArray(new Var[1]), new SmallestMin(),
				new IndomainMin());

		search = new DepthFirstSearch();
		
		boolean solution = search.labeling(store, select, cost);

		long end = System.currentTimeMillis();

		if (solution)
			store.print();
		else
			System.out.println("Failed to find any solution");

		System.out.println("Number of milliseconds " + (end - begin));

		return solution;
	
	}

	
	/**
	 * It conducts master-slave search. Both of them use input order variable ordering. 
	 * 
	 * @param masterVars it specifies the search variables used in master search.
	 * @param slaveVars it specifies the search variables used in slave search.
	 * 
	 * @return true if the solution exists, false otherwise.
	 */
	public boolean searchMasterSlave(ArrayList<Var> masterVars, 
									 ArrayList<Var> slaveVars) {

		long T1 = System.currentTimeMillis();

		boolean result = false;

		Search labelSlave = new DepthFirstSearch();
		SelectChoicePoint selectSlave = new SimpleSelect(slaveVars.toArray(new Var[0]), null,
				new IndomainMin());
		labelSlave.setSelectChoicePoint(selectSlave);

		Search labelMaster = new DepthFirstSearch();
		SelectChoicePoint selectMaster = new SimpleSelect(masterVars.toArray(new Var[0]), null,
				new IndomainMin());
		
		labelMaster.addChildSearch(labelSlave);

		search = labelMaster;
		
		result = labelMaster.labeling(store, selectMaster);

		if (result)
			System.out.println("Solution found");

		if (result)
			store.print();

		long T2 = System.currentTimeMillis();
		
		System.out.println("\n\t*** Execution time = " + (T2 - T1) + " ms");

		return result;
	}

	
	/**
	 * It returns the search used within an example.
	 * @return the search used within an example.
	 */
	public Search getSearch() {
		return search;
	}

	/**
	 * It specifies the constraint store used within an example.
	 * @return constraint store used within an example.
	 */
	public Store getStore() {
		return store;
	}

	/**
	 * It returns an array list of variables used to model the example.
	 * @return the array list of variables used to model the example.
	 */
	public ArrayList<Var> getSearchVariables() {
		return vars;
	}	
		
    /**
     * It prints a matrix of variables. All variables must be grounded.
     * @param matrix matrix containing the grounded variables.
     * @param rows number of elements in the first dimension.
     * @param cols number of elements in the second dimension.
     */
    public static void printMatrix(IntVar[][] matrix, int rows, int cols) {

        for(int i = 0; i < rows; i++) {
            for(int j = 0; j < cols; j++) {
                System.out.print(matrix[i][j].value() + " ");
            }
            System.out.println();
        }

    }

}