package org.simantics.scl.compiler.elaboration.query.compilation;

import java.util.ArrayList;
import java.util.Collections;

import gnu.trove.map.hash.TLongObjectHashMap;
import gnu.trove.procedure.TLongObjectProcedure;

public class DynamicProgrammingOrdering {
    final ConstraintCollectionContext collectionContext;
    int variableCount;
    final QueryConstraint[] constraints;
    TLongObjectHashMap<Entry> entries = new TLongObjectHashMap<Entry>(); 
    
    private static class Path {
        public final QueryConstraint constraint;
        public final Path prev;
        
        public Path(QueryConstraint constraint, Path prev) {
            this.constraint = constraint;
            this.prev = prev;
        }

        public void updateOrder(QueryConstraint[] constraints) {
            Path path = this;
            for(int i=constraints.length-1;i>=0;--i,path=path.prev)
                constraints[i] = path.constraint;
        }
    }
    
    private static class Entry {
        double branching;
        double cost;
        Path path;
        long variables;
        
        public Entry(double branching, double cost, Path path, long variables) {
            this.branching = branching;
            this.cost = cost;
            this.path = path;
            this.variables = variables;
        }
    }
    
    private DynamicProgrammingOrdering(ConstraintCollectionContext collectionContext,
            QueryConstraint[] constraints) {
        this.collectionContext = collectionContext;
        this.constraints = constraints;
        
        //for(QueryConstraint constraint : constraints)
        //    System.out.println(constraint);
        
        int maxVariable = -1;
        for(QueryConstraint constraint : constraints)
            for(int v : constraint.variables)
                maxVariable = Math.max(maxVariable, v);
        this.variableCount = maxVariable + 1;
    }
    
    private void run(long initialVariableBindings) throws UnsolvableQueryException {
        entries.put(0L, new Entry(1.0, 0.0, null, initialVariableBindings));
        for(int i=0;i<constraints.length;++i)
            nextEntries();
        
        Entry entry = entries.valueCollection().iterator().next();
        if(entry.path != null)
            entry.path.updateOrder(constraints);
        updateFinalBoundVariables(initialVariableBindings);
        //System.out.println("cost = " + entry.cost);
        //System.out.println("branching = " + entry.branching);
    }
    
    private void updateFinalBoundVariables(long boundVariables) {
        for(QueryConstraint constraint : constraints) {
            constraint.finalBoundVariables = boundVariables;
            boundVariables |= constraint.getVariableMask();
        }
    }

    private void nextEntries() throws UnsolvableQueryException {
        TLongObjectHashMap<Entry> oldEntries = entries;
        entries = new TLongObjectHashMap<Entry>();
        oldEntries.forEachEntry(new TLongObjectProcedure<Entry>() {
            @Override
            public boolean execute(long constraintPattern, Entry entry) {
                double branching = entry.branching;
                double cost = entry.cost;
                Path path = entry.path;
                long variables = entry.variables;
                {
                    // Try to find a nonbranching constraint
                    double bestBranching = Double.POSITIVE_INFINITY;
                    int bestConstraint = -1;
                    for(int i=0;i<constraints.length;++i) {
                        if( ((constraintPattern>>i)&1) == 0 ) {
                            QueryConstraint constraint = constraints[i];
                            double newBranching = constraint.getSolutionBranching(variables);
                            if(newBranching < bestBranching) {
                                bestConstraint = i;
                                bestBranching = newBranching;
                            }
                        }
                    }
                    if(bestBranching <= 1.0) {
                        QueryConstraint constraint = constraints[bestConstraint];
                        long newConstraintPattern = constraintPattern | (1L << bestConstraint);
                        double newBranching = constraint.getSolutionBranching(variables)*branching;
                        double newCost = constraint.getSolutionCost(variables)*branching + cost;
                        
                        Entry newEntry = entries.get(newConstraintPattern);
                        if(newEntry == null) {
                            entries.put(newConstraintPattern,
                                    new Entry(newBranching, newCost, new Path(constraint, path),
                                            variables | constraint.getVariableMask()));
                        }
                        else {
                            if(newBranching < newEntry.branching)
                                newEntry.branching = newBranching;
                            if(newCost < newEntry.cost) {
                                newEntry.cost = newCost;
                                newEntry.path = new Path(constraint, path);
                            }
                        }
                        return true;
                    }
                }
                
                for(int i=0;i<constraints.length;++i) {
                    if( ((constraintPattern>>i)&1) == 0 ) {
                        QueryConstraint constraint = constraints[i];
                        if(constraint.canBeSolvedFrom(variables)) {
                            long newConstraintPattern = constraintPattern | (1L << i);
                            double newBranching = constraint.getSolutionBranching(variables)*branching;
                            double newCost = constraint.getSolutionCost(variables)*branching + cost;
                            
                            Entry newEntry = entries.get(newConstraintPattern);
                            if(newEntry == null) {
                                entries.put(newConstraintPattern,
                                        new Entry(newBranching, newCost, new Path(constraint, path),
                                                variables | constraint.getVariableMask()));
                            }
                            else {
                                if(newBranching < newEntry.branching)
                                    newEntry.branching = newBranching;
                                if(newCost < newEntry.cost) {
                                    newEntry.cost = newCost;
                                    newEntry.path = new Path(constraint, path);
                                }
                            }
                        }
                    }
                }
                return true;
            }
        });
        if(entries.isEmpty()) {
            Entry entry = oldEntries.valueCollection().iterator().next();
            long variables = entry.variables;

            ArrayList<String> variableNames = new ArrayList<String>(); 
            for(int i=0;i<variableCount;++i)
                if( ((variables >> i)&1) == 0 )
                    variableNames.add(collectionContext.variables.get(i).getName());
            Collections.sort(variableNames);

            StringBuilder b = new StringBuilder();
            b.append("Unsolved variables: ");
            for(int i=0;i<variableNames.size();++i) {
                if(i > 0)
                    b.append(", ");
                b.append(variableNames.get(i));
            }
            
            /*b.append("\nUnsolved constraints:");
            for(QueryConstraint constraint : constraints)
                if(!constraint.canBeSolvedFrom(entry.variables))
                    b.append("\n    ").append(constraint);
            */
            throw new UnsolvableQueryException(b.toString());
        }
    }

    public static void order(ConstraintCollectionContext collectionContext,
            QueryConstraint[] constraints, long initialVariableBindings) throws UnsolvableQueryException {
        DynamicProgrammingOrdering algorithm = new DynamicProgrammingOrdering(collectionContext, constraints);
        algorithm.run(initialVariableBindings);
    }
}