/**
 * PDDL Graph Planner
 * Zeyn Saigol <zeyn@zeyn.net>
 * School of Computer Science
 * University of Birmingham
 *
 * $Id: GraphSolver.java 33 2007-02-23 15:45:34Z zas $
 */
package uk.ac.bham.cs.zas.plangraph;

import java.io.*;
import java.util.*;
import java.util.logging.*;
import uk.ac.bham.cs.zas.pddl.domain.*;
import uk.ac.bham.cs.zas.pddl.parser.*;

/**
 * Class to create and use a plan graph (using {@link PlanGraph}) to produce
 * a plan to solve the given problem. This requires the use of a backtracking
 * search. Currently, no heuristics are used to guide the search.
 */
public class GraphSolver
{
    private static final Logger logger = Logger.getLogger(GraphSolver.class.getName());

    private final Domain domain;
    private final Problem problem;
    private final PlanGraph graph;
    
    public GraphSolver(Domain dom, Problem prob) throws IllDefinedProblemException
    {
        if (dom == null || prob == null) {
            throw new IllegalArgumentException("null domain/problem");
        }
        this.domain = dom;
        this.problem = prob;
        
        graph = new PlanGraph(domain, problem);
    }
    
    public static void main(String[] args) 
    {
        if (args.length != 2) {
            usage();
        }
        File domainFile = new File(args[0]);
        if (!domainFile.exists()) {
            System.err.println("Unable to find PDDL domain file " + args[0]);
            usage();
        }
        File problemFile = new File(args[1]);
        if (!problemFile.exists()) {
            System.err.println("Unable to find PDDL problem file " + args[1]);
            usage();
        }
                
        try {
            ANTLRDomainBuilder domBuilder = new ANTLRDomainBuilder(domainFile);
            Domain domain = domBuilder.buildDomain();
            ANTLRProblemBuilder probBuilder = new ANTLRProblemBuilder(domain, problemFile);
            Problem problem = probBuilder.buildProblem();
            
            GraphSolver solver = new GraphSolver(domain, problem);
            List<GraphAction> plan = solver.solve();
            if (plan == null) {
                System.out.println("No plan found");
            } else {
                System.out.println("Plan found in " + solver.getNumLevels() + " levels:");
                for (GraphAction action : plan) {
                    System.out.println(action.toString());
                }
            }
        } catch (IOException e) {
            System.err.println("Error reading PDDL file(s): " + e);
            e.printStackTrace();
        } catch (PDDLSyntaxException e) {
            System.err.println("Syntax errors found in the PDDL file(s).");
        } catch (InvalidPDDLElementException e) {
            System.err.println("Invalid semantics in the PDDL file(s): " + e);
            e.printStackTrace();
        } catch (IllDefinedProblemException e) {
            System.err.println("Badly defined problem: " + e);
            e.printStackTrace();
        }
    }

    private static void usage() 
    {
        System.err.println("usage: java GraphSolver <domain-pddl-file> <problem-pddl-file>");
        System.exit(1);
    }
    
    /** 
     * @return <code>null</code> if the problem cannot be solved 
     */
    public List<GraphAction> solve()
    {
        List<GraphAction> realPlan = null;
        GoalDesc goal = problem.getGoal();
        Level currentLevel = graph.getLastLevel();
        
        while (!currentLevel.goalLiteralsArePresent(goal)) {
            currentLevel = graph.addLevel();
        }        
        
        List<Set<GraphAction>> fullPlan = generatePlan();
        
        // Continue adding levels if plan not found, AND graph not converged yet
        while (fullPlan == null && !graph.hasConverged()) {
            graph.addLevel();
            fullPlan = generatePlan();
        }
        
        // Now remove the maintenance actions, and impose an arbitrary order TODO: also return POPs
        if (fullPlan != null) {
            realPlan = new ArrayList<GraphAction>(fullPlan.size());
            for (Set<GraphAction> actionsAtLevel : fullPlan) {
                for (GraphAction action : actionsAtLevel) {
                    if (!action.isMaintenanceAction()) {
                        realPlan.add(action);
                    }
                }
            }
        }
        return realPlan;
    }

    private List<Set<GraphAction>> generatePlan()
    {
        try {
            Level finalLevel = graph.getLastLevel();
            List<Set<GraphAction>> plan = new ArrayList<Set<GraphAction>>();
            
            GoalDesc goal = problem.getGoal();
            Set<LiteralInstance> litInstances = new HashSet<LiteralInstance>();
            goal.getLiteralsUsed(litInstances);
            List<Set<Literal>> possibleLitCombinations = finalLevel.getConsistentLitCombinations(litInstances);           
            
            // Now check if the goal is satisfied in any of the combinations
            for (Set<Literal> inputLiterals : possibleLitCombinations) {
                ConsistentLiteralSet literals = new ConsistentLiteralSet(inputLiterals);
                if (goal.evaluate(literals)) {
                    // This set of literals is a possible
                    logger.info("Trying to find solution with end literal set:\n" + inputLiterals);
                    
                    plan.clear();
                    if (recursiveSolve(finalLevel, inputLiterals, plan)) {
                        Collections.reverse(plan);
                        return plan; /***/
                    }
                }
            }
            // No solution possible
            return null; /***/
            
            // TODO: how to make non-maintenance actions preferred...
        } catch (InconsistentLiteralException e) {
            throw new RuntimeException(e);
        }
    }

    private boolean recursiveSolve(Level level, Set<Literal> goals, List<Set<GraphAction>> plan)
    {
        if (level.getLevelNum() == 0) {
            return solveStartState(level, goals, plan);
        } else {
            return solveLevel(level, goals, plan);
        }
    }
    
    /**
     * In this case, just need all the goals to be present in the start state of the 
     * problem.
     */
    private boolean solveStartState(Level level, Set<Literal> goals, List<Set<GraphAction>> plan)
    {
        Set<Literal> startState = level.getEndLiterals();
        for (Literal goal : goals) {
            if (!startState.contains(goal)) {
                logger.fine("Failing search at start state for plan with first action " 
                            + plan.get(0).iterator().next());
                return false; /***/
            }
        }
        return true;
    }

    /*
     * This builds the plan BACKWARDS, so actions that should be executed first are added
     * at the end of the list.
     * @plan the list that will contain a plan on successful completion. May not be null.
     */
    private boolean solveLevel(Level level, Set<Literal> goals, List<Set<GraphAction>> plan)
    {        
        // TODO: should we check if any of the goal literals are themselves mutex??        
        Map<Literal, List<GraphAction>> creatorMap = level.getLiteralCreatorMap();        
        // Get list of possible action combinations
        List<Set<GraphAction>> possibleCombinations = new ArrayList<Set<GraphAction>>();
        // Start with a single empty set
        possibleCombinations.add(new HashSet<GraphAction>());

        // Iterate over literals
        for (Literal goal : goals) {
            List<Set<GraphAction>> newCombinations = new ArrayList<Set<GraphAction>>();
            List<GraphAction> possibleActions = creatorMap.get(goal);
            
            for (Set<GraphAction> partialSoln : possibleCombinations) {
                for (GraphAction action : possibleActions) {
                    // Create a new set for each existing set, if action is allowed
                    if (noneMutex(level, action, partialSoln)) {
                        Set<GraphAction> newSoln = new HashSet<GraphAction>(partialSoln);
                        newSoln.add(action);
                        newCombinations.add(newSoln);
                    }
                }
            }
            possibleCombinations = newCombinations;
        }
        
        // Now iterate over each candidate set of actions to take at this level
        final int levelNum = plan.size();
        plan.add(null); // Add an extra entry for this level
        Set<Literal> newGoals = new HashSet<Literal>();
        
        for (Set<GraphAction> trialSolution : possibleCombinations) {
            newGoals.clear();
            for (GraphAction action : trialSolution) {
                newGoals.addAll(action.getPreconditions().getLiterals());
            }
            plan.set(levelNum, trialSolution);
            
            // Try to build the rest of the plan from this partial solution
            if (recursiveSolve(level.getPreviousLevel(), newGoals, plan)) {
                return true; /***/
            }
        }
        
        plan.remove(levelNum);
        return false;
    }

    private boolean noneMutex(Level level, GraphAction action, Set<GraphAction> partialSoln)
    {
        for (GraphAction testAction : partialSoln) {
            if (level.actionsAreMutex(testAction, action)) {
                return false;
            }
        }
        return true;
    }

    public int getNumLevels()
    {
        return graph.getLastLevel().getLevelNum();
    }
}
