/*******************************************************************************
 * Copyright (c) 2004-2008 Akos Horvath, Gergely Varro and Daniel Varro
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors:
 *    Akos Horvath, Gergely Varro - initial API and implementation
 *******************************************************************************/

 package org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.callgraph;

import org.eclipse.viatra2.core.IModelManager;
import org.eclipse.viatra2.gtasm.patternmatcher.PatternCallSignature;
import org.eclipse.viatra2.gtasm.patternmatcher.exceptions.PatternMatcherCompileTimeException;
import org.eclipse.viatra2.gtasm.patternmatcher.exceptions.PatternMatcherRuntimeException;
import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.MatchingFrame;
import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.PatternMatcherErrorStrings;
import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.SearchPlan;
import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.SearchPlanKey;
import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.VariableID;
import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.algorithms.ISearchGraph;
import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.algorithms.SearchGraphFactory;
import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.operation.DummyOperation;
import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.operation.InjectivityCheckOperation;
import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.operation.PatternCallOperation;
import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.operation.SearchPlanOperation;
import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.rgg.IQueueContentProvider;
import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.rgg.IndexedRule;
import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.rgg.LocalGoal;
import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.rgg.MagicSet;
import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.rgg.RemoteGoal;
import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.rgg.UnindexedRule;
import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.searchgraph.AbstractNode;
import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.term.ITermHandler;
import org.eclipse.viatra2.gtasmmodel.gtasm.metamodel.asm.core.AnnotatedElement;
import org.eclipse.viatra2.gtasmmodel.gtasm.metamodel.asm.core.GTASMElement;
import org.eclipse.viatra2.logger.Logger;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeMap;
import java.util.TreeSet;
import java.util.Vector;


/**
 * A FlattenedPattern corresponds to a PatternBody, in which
 * variables from all the embedded pattern invocations are aggregated.
 * 
 * FlattenedPatterns are generated during the pattern invocation analysis of
 * GTPatternBodies. If the pattern call graph is a DAG, then we have a 
 * non-recursive FlattenedPattern consisting of all the variables that appear
 * in the GTPatternBody itself or any patterns that are called by the 
 * GTPatternBody.
 * 
 * Each branch of OR patterns obviously generate a new FlattenedPattern.
 * 
 * The interpreted engine uses the following mapping:
 * VariableType => PatternVariable
 */
public class FlattenedPattern extends EvenLevelNode 
	implements Comparable<FlattenedPattern> {
    
    private boolean isRecursionBased;

    private ISearchGraph searchGraph;
	/**
     * The mapping of pattern variables to their location in
     * the PatternFrames.
	 */
    private Map<VariableID,Integer> variableMapping;
    private Map<Integer, Set<VariableID>> inverseVariableMapping;

    private Set<Pair> injectivityExclusionSet, injectivityInclusionSet;
    
	/**
     * The mapping of PatternSignatures to the SearchPlans
     * that are available for a given PatternSignature.
	 */
	private Map<SearchPlanKey,Collection<SearchPlan>> searchPlanMapping;

	private Vector<SearchPlanOperation> preSearchPlanOperations;
    private Vector<SearchPlanOperation> postSearchPlanOperations;
    
    /**
     * The size of the binding arrays inside the corresponding 
     * MatchingFrames.
	 */
	private int frameSize;
    private int injectivityFrameSize;
    
    public FlattenedPattern(PatternNode parent, List<IFlattenedPatternElement> specification) 
        throws PatternMatcherCompileTimeException {
    	super(parent);
    	//this.SearchGraph = new VPMBasedSearchGraph(parent.getModelManager());
    	this.searchGraph = SearchGraphFactory.getSearchGraph(parent.getModelManager());
    	this.variableMapping = new HashMap<VariableID, Integer>();
        this.inverseVariableMapping = new TreeMap<Integer, Set<VariableID>>();
    	this.searchPlanMapping = new HashMap<SearchPlanKey, Collection<SearchPlan>>();
      	this.preSearchPlanOperations = new Vector<SearchPlanOperation>();
        this.postSearchPlanOperations = new Vector<SearchPlanOperation>();
        this.isRecursionBased = false;
        this.frameSize = 0;
        this.injectivityFrameSize = 0;
        this.injectivityExclusionSet = new HashSet<Pair>();
        injectivityInclusionSet = new HashSet<Pair>();

        Logger logger = parent.getLogger();
        // Main loop for processing all the variables of a pattern variant
        for (int i = 0; i < specification.size(); i++) {
            IFlattenedPatternElement element = specification.get(i);
            element.setCurrentLocation(i);
            element.addFormalParameters(this);
            element.addLocalVariables(this);
        }
        injectivityFrameSize = frameSize;
        for (int i = 0; i < specification.size(); i++) {
            IFlattenedPatternElement element = specification.get(i);
            element.processNegativeApplicationConditions(this, logger, parent.getModelManager());
            element.processCheckExpressions(this, logger);
            element.buildSearchGraph(this);
            element.generateElementInjectivityConstraints(this, 
            		element.processVariableAssignments(this),
            		element.processInjectivityAssignments(this));
            
            // element.processFormalParameterScopes(this);
            //Scope of the input parameter is not added to the search graph
            // element.processPatternCallScopes(this);
        }
        this.searchGraph.connectDanglingRelations(this);
        addPostSearchPlanOperation(new InjectivityCheckOperation());

        //TODO: in case of adaptive pattern matching the searchNodeOrder is not fix have to go back to the iSearchGraph itself
        // the order of the nodes are calculated, it would be better to have it contained

        //For debugging purpose
//      result.searchNodeOrder= result.alg.evaulateSearchPlan(result);
//      result.debug(); 
//      //result.debugPL(a);
//      result.alg.evaulateOperationPlan(result.searchNodeOrder);

        printVariableMapping(logger);
    }
    
    /**
     * Adds SearchPlan plan to the set of search plans with
     * PatternSignature signature.
     * @param signature The key that identifies the set of search plans 
     * to which plan has to be added. 
     * @param plan The search plan to be added.
     * @return true if plan has been successfully added to the
     * search plan mapping dictionary.
     */
    boolean addSearchPlan(PatternCallSignature signature, SearchPlan plan) {
        return false;
    }
    
    MatchingFrame getInstance() {
        return null;
    }
    
    Collection<SearchPlan> getSearchPlansFor(SearchPlanKey key) {
        return searchPlanMapping.get(key);
    }

    /**
     * 
     * @return the frameSize
     */
    public int getFrameSize() {
        return frameSize;
    }

    /**
     * @param frameSize the frameSize to set
     */
    public void setFrameSize(int frameSize) {
        this.frameSize = frameSize;
    }
    
    public ISearchGraph getSearchGraph() {
    	return searchGraph;
    }
    
    public void addPreSearchPlanOperation(SearchPlanOperation operation) {
        preSearchPlanOperations.add(operation);
    }
    
    public void addPostSearchPlanOperation(SearchPlanOperation operation) {
        postSearchPlanOperations.add(operation);
    }
    
    public Integer getIndex(VariableID variable) {
        return variableMapping.get(variable);
    }
    
    public Set<VariableID> getVariableIDs(Integer index) {
        return inverseVariableMapping.get(index);
    }
    
    private void addToInverseMapping(VariableID variable, Integer index) {
        Set<VariableID> idSet = inverseVariableMapping.get(index);
        if (idSet == null) {
            idSet = new HashSet<VariableID>();
            inverseVariableMapping.put(index, idSet);
        }
        idSet.add(variable);
    }
    
    public void setIndex(VariableID variable, Integer index) {
        variableMapping.put(variable, index);
        addToInverseMapping(variable, index);
    }
    
    public int addVariable(VariableID variable) {
        if (variable != null) {
            variableMapping.put(variable, frameSize);
            addToInverseMapping(variable, frameSize);
        }
        return frameSize++;
    }
    
    private void printVariableMapping(Logger logger) {
        for (VariableID id : variableMapping.keySet()) {
            logger.debug(id.toString() + " : " + variableMapping.get(id));
        }
        for (Integer key : inverseVariableMapping.keySet()) {
            for (VariableID id : inverseVariableMapping.get(key)) {
                logger.debug(key + " : " + id.toString());
            }
        }
        logger.debug("Injective frame size: \t" + injectivityFrameSize);
        logger.debug("Frame size: \t" + frameSize);
    }
    
    public boolean containsIndex(VariableID variable){
    	return variableMapping.containsKey(variable);
    }

	// Moves non-recursion based patterns ahead of recursion based patterns
    public int compareTo(FlattenedPattern o) {
        /*
         * this = o : !isRecursionBased AND !o.isRecursionBased
         * this = o : isRecursionBased AND o.isRecursionBased
         * this > o : isRecursionBased AND !o.isRecursionBased
         * this < o : !isRecursionBased AND o.isRecursionBased
         */
        if (isRecursionBased == o.isRecursionBased) {
            return 0;
        } else {
            return (isRecursionBased ? 1 : -1);
        }
    }

    /**
     * @return the injectivityFrameSize
     */
    public int getInjectivityFrameSize() {
        return injectivityFrameSize;
    }

    public ITermHandler getTermHandler() {
        return parent.getTermHandler();
    }
    
    public Collection<SearchPlanOperation> generateCoreSearchPlan(Boolean[] adornment, IModelManager manager) throws PatternMatcherRuntimeException{
    	return searchGraph.generateSearchPlan(this, adornment, manager);
    }
    
    public List<SearchPlanOperation> generateSearchPlan(Boolean[] adornment, IModelManager manager) throws PatternMatcherRuntimeException{
    	Collection<SearchPlanOperation> vec = searchGraph.generateSearchPlan(this, adornment,manager);

    	// Copies pre and post operations
    	ArrayList<SearchPlanOperation> finalSearchPlan = new ArrayList<SearchPlanOperation>();
    	finalSearchPlan.addAll(preSearchPlanOperations);
    	finalSearchPlan.addAll(vec);
    	finalSearchPlan.addAll(postSearchPlanOperations);
    	SearchPlanOperation[] operations = new SearchPlanOperation[finalSearchPlan.size()];
    	operations = finalSearchPlan.toArray(operations);
    	SearchPlan splan = new SearchPlan(operations);
    	splan.printDebugInformation(parent.getLogger());
    	// sets the iSearchGraph back to starting state
    	searchGraph.initSearchGraph();
    	
        return finalSearchPlan;
    }

    IQueueContentProvider buildSubtree(Map<String, RemoteGoal> rggRoots,
    		MagicSet ms,
    		List<SearchPlanOperation> searchPlan, 
    		int upperBound, 
    		SortedSet<Integer> preCallInterfaceVariables) throws PatternMatcherRuntimeException {
    	//gervarro: put to the constructor of the Rule?
        SortedSet<Integer> localVariables = new TreeSet<Integer>();
        int i = upperBound;
    	for (; i >= 0 && !(searchPlan.get(i) instanceof PatternCallOperation); i--) {
			searchPlan.get(i).calculateSidewaysPassedVariables(preCallInterfaceVariables);
			searchPlan.get(i).calculateLocalVariables(localVariables);
    	}

    	if (upperBound < 0) {
    		// sup_i.0 :- ms_i
    		return ms; // look up the appropriate magic set
    	} else if (i < upperBound) {
    		// sup_i.j :- sup_i.(j-1), local_j
    		IQueueContentProvider left = 
    			buildSubtree(rggRoots, ms, searchPlan, i, preCallInterfaceVariables);
    		List<SearchPlanOperation> operations = 
    			new Vector<SearchPlanOperation>(searchPlan.subList(i+1, upperBound+1));
    		operations.add(new DummyOperation());
    		SearchPlanOperation[] array = new SearchPlanOperation[operations.size()];
    		array = operations.toArray(array);
    		LocalGoal right = new LocalGoal(array);

    		/*
			int size = localVariables.size();
			Integer[] localVariableMapping = new Integer[size];
			Boolean[] adornment = new Boolean[size];
			int counter = 0;
			for (Integer position: localVariables) {
				adornment[counter] = preCallInterfaceVariables.contains(position);
				counter++;
			}
			localVariables.toArray(localVariableMapping);
			*/

    		return new UnindexedRule(this, left, right);
    	} else if (i == upperBound) {
    		// sup_i.j :- sup_i.(j-1), remote_j
    		PatternCallOperation pco = (PatternCallOperation) searchPlan.get(i);
    		pco.calculateSidewaysPassedVariables(preCallInterfaceVariables);
			pco.calculateLocalVariables(localVariables);
			
    		IQueueContentProvider left = 
    			buildSubtree(rggRoots, ms, searchPlan, i-1, preCallInterfaceVariables);

    		String id = RemoteGoal.generateID(pco.getPatternNode(), pco.getAdornment());
    		// If right goal exists in runtimes
     		if (rggRoots.containsKey(id)) {
        		// then get the runtime from runtimes
    			RemoteGoal right = rggRoots.get(id);
    			return new IndexedRule(this, left, right, pco.getParameterMapping(), pco.getAdornment());
    		} else {
        		// else generate a new runtime
    			RemoteGoal right = pco.getPatternNode().buildRuleGoalGraph(pco.getAdornment(),rggRoots);
    			return new IndexedRule(this, left, right, pco.getParameterMapping(), pco.getAdornment());
    		}
    		// ms_call :- sup_i.(j-1)
     		// Explicitly handled by RemoteGoal 
    	} else {
    		String[] context = {getParent().getPattern().getName()};
    		throw new PatternMatcherRuntimeException(
    				PatternMatcherErrorStrings.INTERNAL_FLATTENED_PATTERN_BUILD
    				,context
    				,getParent().getPattern());
    	}
    }
    
    public AnnotatedElement getGTASMRepresentation(AbstractNode node){
    	return searchGraph.getGTASMRepresentation(node);
    }
    
    
    
    
    public Pair addInjectivityExclusionPair(int left, int right) {
    	Pair p = (left < right ? new Pair(left,right) : new Pair(right,left));
    	injectivityExclusionSet.add(p);
    	return p;
    }
    
    public void removeInjectivityExclusionPair(int left, int right) {
    	Pair p = (left < right ? new Pair(left,right) : new Pair(right,left));
    	injectivityExclusionSet.remove(p);
    }
    
    public Pair addInjectivityInclusionPair(int left, int right) {
     	Pair p = (left < right ? new Pair(left,right) : new Pair(right,left));
    	injectivityInclusionSet.add(p);
    	return p;
 	}
    
    public void removeInjectivityInclusionPair(int left, int right) {
     	Pair p = (left < right ? new Pair(left,right) : new Pair(right,left));
    	injectivityInclusionSet.remove(p);
 		
	}
    
    public boolean isIncludedInInjectivityCheck(int i, int j) {
    	Pair p = (i < j ? new Pair(i,j) : new Pair(j,i));
    	return injectivityInclusionSet.contains(p); // if it is in the Inclusion set then it has to be checked for injectivity (|| !injectivityExclusionSet.contains(p)) 
    }
    
	public static class Pair {
		public Integer getLeft() {
			return left;
		}

		public Integer getRight() {
			return right;
		}

		private Integer left;
		private Integer right;
		
		Pair(int left, int right) {
			this.left = left;
			this.right = right;
		}
		
		public boolean equals(Object other) {
			if (other != null && other instanceof Pair) {
				Pair o = (Pair) other;
				return (left == o.left && right == o.right);
			} else {
				return false;
			}
		}
		
		public int hashCode() {
			return left.hashCode() + right.hashCode();
		}
	}

	

	
}