package gr.uom.java.ast.decomposition.cfg.mapping;

import gr.uom.java.ast.MethodObject;
import gr.uom.java.ast.decomposition.AbstractExpression;
import gr.uom.java.ast.decomposition.CompositeStatementObject;
import gr.uom.java.ast.decomposition.cfg.AbstractVariable;
import gr.uom.java.ast.decomposition.cfg.CFGBranchDoLoopNode;
import gr.uom.java.ast.decomposition.cfg.CFGBranchIfNode;
import gr.uom.java.ast.decomposition.cfg.CFGBranchSwitchNode;
import gr.uom.java.ast.decomposition.cfg.GraphEdge;
import gr.uom.java.ast.decomposition.cfg.PDG;
import gr.uom.java.ast.decomposition.cfg.PDGBlockNode;
import gr.uom.java.ast.decomposition.cfg.PDGControlDependence;
import gr.uom.java.ast.decomposition.cfg.PDGControlPredicateNode;
import gr.uom.java.ast.decomposition.cfg.PDGDataDependence;
import gr.uom.java.ast.decomposition.cfg.PDGDependence;
import gr.uom.java.ast.decomposition.cfg.PDGMethodEntryNode;
import gr.uom.java.ast.decomposition.cfg.PDGNode;
import gr.uom.java.ast.decomposition.cfg.PDGStatementNode;
import gr.uom.java.ast.decomposition.cfg.PlainVariable;
import gr.uom.java.ast.decomposition.cfg.mapping.precondition.PreconditionViolation;
import gr.uom.java.ast.decomposition.matching.ASTNodeDifference;
import gr.uom.java.ast.decomposition.matching.ASTNodeMatcher;
import gr.uom.java.ast.decomposition.matching.BindingSignaturePair;
import gr.uom.java.ast.decomposition.matching.Difference;
import gr.uom.java.ast.decomposition.matching.DifferenceType;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.ListIterator;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;

import org.eclipse.core.runtime.IProgressMonitor;
import org.eclipse.jdt.core.ICompilationUnit;
import org.eclipse.jdt.core.dom.ITypeBinding;
import org.eclipse.jdt.core.dom.SwitchStatement;
import org.eclipse.jdt.core.dom.VariableDeclaration;

public abstract class DivideAndConquerMatcher {

	//if true full tree match is performed, otherwise subtree match is performed
	private boolean fullTreeMatch;
	private IProgressMonitor monitor;
	private PDG pdg1;
	private PDG pdg2;
	private ICompilationUnit iCompilationUnit1;
	private ICompilationUnit iCompilationUnit2;
	private ControlDependenceTreeNode controlDependenceTreePDG1;
	private ControlDependenceTreeNode controlDependenceTreePDG2;
	private TreeSet<PDGNode> allNodesInSubTreePDG1;
	private TreeSet<PDGNode> allNodesInSubTreePDG2;
	private CloneStructureNode root;
	private MappingState finalState;
	protected PreconditionExaminer preconditionExaminer;
	
	public DivideAndConquerMatcher(PDG pdg1, PDG pdg2,
			ICompilationUnit iCompilationUnit1, ICompilationUnit iCompilationUnit2,
			ControlDependenceTreeNode controlDependenceTreePDG1, ControlDependenceTreeNode controlDependenceTreePDG2,
			boolean fullTreeMatch, IProgressMonitor monitor) {
		this.pdg1 = pdg1;
		this.pdg2 = pdg2;
		this.iCompilationUnit1 = iCompilationUnit1;
		this.iCompilationUnit2 = iCompilationUnit2;
		this.controlDependenceTreePDG1 = controlDependenceTreePDG1;
		this.controlDependenceTreePDG2 = controlDependenceTreePDG2;
		this.fullTreeMatch = fullTreeMatch;
		this.monitor = monitor;
		this.allNodesInSubTreePDG1 = new TreeSet<PDGNode>();
		this.allNodesInSubTreePDG2 = new TreeSet<PDGNode>();
	}

	public boolean hasMappedNodes() {
		return root != null && !root.getChildren().isEmpty() && !getRemovableNodesG1().isEmpty() && !getRemovableNodesG2().isEmpty();
	}

	public PDG getPDG1() {
		return pdg1;
	}

	public PDG getPDG2() {
		return pdg2;
	}

	public String getMethodName1() {
		return pdg1.getMethod().getName();
	}

	public String getMethodName2() {
		return pdg2.getMethod().getName();
	}

	public TreeSet<PDGNode> getRemovableNodesG1() {
		return preconditionExaminer.getRemovableNodesG1();
	}

	public TreeSet<PDGNode> getRemovableNodesG2() {
		return preconditionExaminer.getRemovableNodesG2();
	}

	public TreeSet<PDGNode> getRemainingNodesG1() {
		return preconditionExaminer.getRemainingNodesG1();
	}

	public TreeSet<PDGNode> getRemainingNodesG2() {
		return preconditionExaminer.getRemainingNodesG2();
	}

	public TreeSet<PDGNode> getNonMappedPDGNodesG1MovableBefore() {
		return preconditionExaminer.getNonMappedPDGNodesG1MovableBefore();
	}

	public TreeSet<PDGNode> getNonMappedPDGNodesG1MovableAfter() {
		return preconditionExaminer.getNonMappedPDGNodesG1MovableAfter();
	}

	public TreeSet<PDGNode> getNonMappedPDGNodesG2MovableBefore() {
		return preconditionExaminer.getNonMappedPDGNodesG2MovableBefore();
	}

	public TreeSet<PDGNode> getNonMappedPDGNodesG2MovableAfter() {
		return preconditionExaminer.getNonMappedPDGNodesG2MovableAfter();
	}

	public TreeSet<PDGNode> getAdditionallyMatchedNodesG1() {
		return preconditionExaminer.getAdditionallyMatchedNodesG1();
	}

	public TreeSet<PDGNode> getAdditionallyMatchedNodesG2() {
		return preconditionExaminer.getAdditionallyMatchedNodesG2();
	}

	public Set<AbstractVariable> getDirectlyAccessedLocalFieldsG1() {
		return preconditionExaminer.getDirectlyAccessedLocalFieldsG1();
	}

	public Set<AbstractVariable> getDirectlyAccessedLocalFieldsG2() {
		return preconditionExaminer.getDirectlyAccessedLocalFieldsG2();
	}

	public Set<AbstractVariable> getIndirectlyAccessedLocalFieldsG1() {
		return preconditionExaminer.getIndirectlyAccessedLocalFieldsG1();
	}

	public Set<AbstractVariable> getIndirectlyAccessedLocalFieldsG2() {
		return preconditionExaminer.getIndirectlyAccessedLocalFieldsG2();
	}

	public Set<AbstractVariable> getDirectlyModifiedLocalFieldsG1() {
		return preconditionExaminer.getDirectlyModifiedLocalFieldsG1();
	}

	public Set<AbstractVariable> getDirectlyModifiedLocalFieldsG2() {
		return preconditionExaminer.getDirectlyModifiedLocalFieldsG2();
	}

	public Set<AbstractVariable> getIndirectlyModifiedLocalFieldsG1() {
		return preconditionExaminer.getIndirectlyModifiedLocalFieldsG1();
	}

	public Set<AbstractVariable> getIndirectlyModifiedLocalFieldsG2() {
		return preconditionExaminer.getIndirectlyModifiedLocalFieldsG2();
	}

	public Set<MethodObject> getAccessedLocalMethodsG1() {
		return preconditionExaminer.getAccessedLocalMethodsG1();
	}

	public Set<MethodObject> getAccessedLocalMethodsG2() {
		return preconditionExaminer.getAccessedLocalMethodsG2();
	}

	public Set<MethodObject> getDirectlyAccessedLocalMethodsG1() {
		return preconditionExaminer.getDirectlyAccessedLocalMethodsG1();
	}

	public Set<MethodObject> getDirectlyAccessedLocalMethodsG2() {
		return preconditionExaminer.getDirectlyAccessedLocalMethodsG2();
	}

	public Set<MethodObject> getIndirectlyAccessedLocalMethodsG1() {
		return preconditionExaminer.getIndirectlyAccessedLocalMethodsG1();
	}

	public Set<MethodObject> getIndirectlyAccessedLocalMethodsG2() {
		return preconditionExaminer.getIndirectlyAccessedLocalMethodsG2();
	}

	public Map<VariableBindingKeyPair, ArrayList<VariableDeclaration>> getDeclaredLocalVariablesInMappedNodes() {
		return preconditionExaminer.getDeclaredLocalVariablesInMappedNodes();
	}

	public Set<VariableBindingKeyPair> getDeclaredLocalVariablesInMappedNodesWithinAnonymousClass() {
		return preconditionExaminer.getDeclaredLocalVariablesInMappedNodesWithinAnonymousClass();
	}

	public Set<VariableDeclaration> getDeclaredLocalVariablesInAdditionallyMatchedNodesG1() {
		return preconditionExaminer.getDeclaredLocalVariablesInAdditionallyMatchedNodesG1();
	}

	public Set<String> getDeclaredLocalVariableBindingKeysInAdditionallyMatchedNodesG1() {
		return preconditionExaminer.getDeclaredLocalVariableBindingKeysInAdditionallyMatchedNodesG1();
	}

	public Set<VariableDeclaration> getDeclaredLocalVariablesInAdditionallyMatchedNodesG2() {
		return preconditionExaminer.getDeclaredLocalVariablesInAdditionallyMatchedNodesG2();
	}

	public Set<String> getDeclaredLocalVariableBindingKeysInAdditionallyMatchedNodesG2() {
		return preconditionExaminer.getDeclaredLocalVariableBindingKeysInAdditionallyMatchedNodesG2();
	}

	public Map<VariableBindingKeyPair, ArrayList<VariableDeclaration>> getCommonPassedParameters() {
		return preconditionExaminer.getCommonPassedParameters();
	}

	public List<ASTNodeDifference> getNodeDifferences() {
		return preconditionExaminer.getNodeDifferences();
	}

	public List<ASTNodeDifference> getNonOverlappingNodeDifferences() {
		return preconditionExaminer.getNonOverlappingNodeDifferences();
	}

	public List<PreconditionViolation> getPreconditionViolations() {
		return preconditionExaminer.getPreconditionViolations();
	}

	public Set<BindingSignaturePair> getRenamedVariables() {
		return preconditionExaminer.getRenamedVariables();
	}

	public Set<VariableBindingPair> getRenamedVariableBindings() {
		return preconditionExaminer.getRenamedVariableBindings();
	}

	public Set<VariableDeclaration> getVariablesToBeReturnedG1() {
		return preconditionExaminer.getVariablesToBeReturnedG1();
	}

	public Set<VariableDeclaration> getVariablesToBeReturnedG2() {
		return preconditionExaminer.getVariablesToBeReturnedG2();
	}

	public Set<VariableDeclaration> getDeclaredVariablesInRemainingNodesDefinedByMappedNodesG1() {
		return preconditionExaminer.getDeclaredVariablesInRemainingNodesDefinedByMappedNodesG1();
	}

	public Set<VariableDeclaration> getDeclaredVariablesInRemainingNodesDefinedByMappedNodesG2() {
		return preconditionExaminer.getDeclaredVariablesInRemainingNodesDefinedByMappedNodesG2();
	}

	public boolean movableBeforeFirstMappedNode(PDGNodeMapping nodeMapping) {
		return preconditionExaminer.movableBeforeFirstMappedNode(nodeMapping);
	}

	public ITypeBinding getReturnTypeBinding() {
		return preconditionExaminer.getReturnTypeBinding();
	}

	public CloneType getCloneType() {
		return preconditionExaminer.getCloneType();
	}

	public CloneRefactoringType getCloneRefactoringType() {
		return preconditionExaminer.getCloneRefactoringType();
	}

	public boolean isTemplateMethodApplicable() {
		return preconditionExaminer.isTemplateMethodApplicable();
	}

	protected abstract Set<PDGNode> getNodesInRegion1(PDG pdg, PDGNode controlPredicate, Set<PDGNode> controlPredicateNodesInCurrentLevel,
			Set<PDGNode> controlPredicateNodesInNextLevel, ControlDependenceTreeNode controlDependenceTreeRoot);

	protected abstract Set<PDGNode> getNodesInRegion2(PDG pdg, PDGNode controlPredicate, Set<PDGNode> controlPredicateNodesInCurrentLevel,
			Set<PDGNode> controlPredicateNodesInNextLevel, ControlDependenceTreeNode controlDependenceTreeRoot);

	protected abstract Set<PDGNode> getElseNodesOfSymmetricalIfStatement1(PDG pdg, PDGNode controlPredicate, Set<PDGNode> controlPredicateNodesInCurrentLevel,
			Set<PDGNode> controlPredicateNodesInNextLevel);

	protected abstract Set<PDGNode> getElseNodesOfSymmetricalIfStatement2(PDG pdg, PDGNode controlPredicate, Set<PDGNode> controlPredicateNodesInCurrentLevel,
			Set<PDGNode> controlPredicateNodesInNextLevel);

	protected abstract List<ControlDependenceTreeNode> getIfParentChildren1(ControlDependenceTreeNode cdtNode);

	protected abstract List<ControlDependenceTreeNode> getIfParentChildren2(ControlDependenceTreeNode cdtNode);

	public CloneStructureNode getCloneStructureRoot() {
		return root;
	}
	
	public MappingState getMaximumStateWithMinimumDifferences() {
		return finalState;
	}

	public TreeSet<PDGNode> getAllNodesInSubTreePDG1() {
		return allNodesInSubTreePDG1;
	}

	public TreeSet<PDGNode> getAllNodesInSubTreePDG2() {
		return allNodesInSubTreePDG2;
	}

	private MappingState findMaximumStateWithMinimumDifferences(List<MappingState> states) {
		int max = 0;
		List<MappingState> maximumStates = new ArrayList<MappingState>();
		for(MappingState currentState : states) {
			if(currentState.getSize() > max) {
				max = currentState.getSize();
				maximumStates.clear();
				maximumStates.add(currentState);
			}
			else if(currentState.getSize() == max) {
				maximumStates.add(currentState);
			}
		}
		
		List<MappingState> maximumStatesWithMinimumDifferences = new ArrayList<MappingState>();
		if(maximumStates.size() == 1) {
			maximumStatesWithMinimumDifferences.add(maximumStates.get(0));
		}
		else {
			int minimum = maximumStates.get(0).getDistinctDifferenceCount();
			maximumStatesWithMinimumDifferences.add(maximumStates.get(0));
			for(int i=1; i<maximumStates.size(); i++) {
				MappingState currentState = maximumStates.get(i);
				if(currentState.getDistinctDifferenceCount() < minimum) {
					minimum = currentState.getDistinctDifferenceCount();
					maximumStatesWithMinimumDifferences.clear();
					maximumStatesWithMinimumDifferences.add(currentState);
				}
				else if(currentState.getDistinctDifferenceCount() == minimum) {
					maximumStatesWithMinimumDifferences.add(currentState);
				}
			}
		}
		
		List<MappingState> maximumStatesWithMinimumNonDistinctDifferences = new ArrayList<MappingState>();
		if(maximumStatesWithMinimumDifferences.size() == 1) {
			maximumStatesWithMinimumNonDistinctDifferences.add(maximumStatesWithMinimumDifferences.get(0));
		}
		else {
			int minimum = maximumStatesWithMinimumDifferences.get(0).getNonDistinctDifferenceCount();
			maximumStatesWithMinimumNonDistinctDifferences.add(maximumStatesWithMinimumDifferences.get(0));
			for(int i=1; i<maximumStatesWithMinimumDifferences.size(); i++) {
				MappingState currentState = maximumStatesWithMinimumDifferences.get(i);
				if(currentState.getNonDistinctDifferenceCount() < minimum) {
					minimum = currentState.getNonDistinctDifferenceCount();
					maximumStatesWithMinimumNonDistinctDifferences.clear();
					maximumStatesWithMinimumNonDistinctDifferences.add(currentState);
				}
				else if(currentState.getNonDistinctDifferenceCount() == minimum) {
					maximumStatesWithMinimumNonDistinctDifferences.add(currentState);
				}
			}
		}
		
		List<MappingState> maximumStatesWithMinimumNonDistinctDifferencesIncludingTypeMismatches = new ArrayList<MappingState>();
		if(maximumStatesWithMinimumNonDistinctDifferences.size() == 1) {
			maximumStatesWithMinimumNonDistinctDifferencesIncludingTypeMismatches.add(maximumStatesWithMinimumNonDistinctDifferences.get(0));
		}
		else {
			int minimum = maximumStatesWithMinimumNonDistinctDifferences.get(0).getNonDistinctDifferenceCountIncludingTypeMismatches();
			maximumStatesWithMinimumNonDistinctDifferencesIncludingTypeMismatches.add(maximumStatesWithMinimumNonDistinctDifferences.get(0));
			for(int i=1; i<maximumStatesWithMinimumNonDistinctDifferences.size(); i++) {
				MappingState currentState = maximumStatesWithMinimumNonDistinctDifferences.get(i);
				if(currentState.getNonDistinctDifferenceCountIncludingTypeMismatches() < minimum) {
					minimum = currentState.getNonDistinctDifferenceCountIncludingTypeMismatches();
					maximumStatesWithMinimumNonDistinctDifferencesIncludingTypeMismatches.clear();
					maximumStatesWithMinimumNonDistinctDifferencesIncludingTypeMismatches.add(currentState);
				}
				else if(currentState.getNonDistinctDifferenceCountIncludingTypeMismatches() == minimum) {
					maximumStatesWithMinimumNonDistinctDifferencesIncludingTypeMismatches.add(currentState);
				}
			}
		}
		//TODO: Introduce comparison of difference "weights" in the case of multiple maximum states with minimum differences
		List<MappingState> maximumStatesWithMinimumDifferencesAndMinimumIdDiff = new ArrayList<MappingState>();
		if(maximumStatesWithMinimumNonDistinctDifferencesIncludingTypeMismatches.size() == 1) {
			maximumStatesWithMinimumDifferencesAndMinimumIdDiff.add(maximumStatesWithMinimumNonDistinctDifferencesIncludingTypeMismatches.get(0));
		}
		else {
			int minId1 = allNodesInSubTreePDG1.isEmpty() ? 0 : allNodesInSubTreePDG1.first().getId();
			int minId2 = allNodesInSubTreePDG2.isEmpty() ? 0 : allNodesInSubTreePDG2.first().getId();
			int minimum = maximumStatesWithMinimumNonDistinctDifferencesIncludingTypeMismatches.get(0).getNodeMappingRelativeIdDiff(minId1, minId2);
			maximumStatesWithMinimumDifferencesAndMinimumIdDiff.add(maximumStatesWithMinimumNonDistinctDifferencesIncludingTypeMismatches.get(0));
			for(int i=1; i<maximumStatesWithMinimumNonDistinctDifferencesIncludingTypeMismatches.size(); i++) {
				MappingState currentState = maximumStatesWithMinimumNonDistinctDifferencesIncludingTypeMismatches.get(i);
				if(currentState.getNodeMappingRelativeIdDiff(minId1, minId2) < minimum) {
					minimum = currentState.getNodeMappingRelativeIdDiff(minId1, minId2);
					maximumStatesWithMinimumDifferencesAndMinimumIdDiff.clear();
					maximumStatesWithMinimumDifferencesAndMinimumIdDiff.add(currentState);
				}
				else if(currentState.getNodeMappingRelativeIdDiff(minId1, minId2) == minimum) {
					maximumStatesWithMinimumDifferencesAndMinimumIdDiff.add(currentState);
				}
			}
		}
		
		if(maximumStatesWithMinimumDifferencesAndMinimumIdDiff.size() == 1) {
			return maximumStatesWithMinimumDifferencesAndMinimumIdDiff.get(0);
		}
		else {
			int minimum = maximumStatesWithMinimumDifferencesAndMinimumIdDiff.get(0).getEditDistanceOfDifferences();
			MappingState maximumStateWithMinimumDifferences = maximumStatesWithMinimumDifferencesAndMinimumIdDiff.get(0);
			for(int i=1; i<maximumStatesWithMinimumDifferencesAndMinimumIdDiff.size(); i++) {
				MappingState currentState = maximumStatesWithMinimumDifferencesAndMinimumIdDiff.get(i);
				if(currentState.getEditDistanceOfDifferences() < minimum) {
					minimum = currentState.getEditDistanceOfDifferences();
					maximumStateWithMinimumDifferences = currentState;
				}
			}
			return maximumStateWithMinimumDifferences;
		}
	}

	protected void matchBasedOnControlDependenceTreeStructure() {
		int maxLevel1 = controlDependenceTreePDG1.getMaxLevel();
		int level1 = maxLevel1;
		int maxLevel2 = controlDependenceTreePDG2.getMaxLevel();
		int level2 = maxLevel2;
		if(monitor != null)
			monitor.beginTask("Mapping Program Dependence Graphs", Math.min(maxLevel1, maxLevel2));
		
		List<CloneStructureNode> parents = new ArrayList<CloneStructureNode>();
		while(level1 >= 0 && level2 >= 0) {
			Set<PDGNode> controlPredicateNodesG1 = controlDependenceTreePDG1.getControlPredicateNodesInLevel(level1);
			Set<PDGNode> controlPredicateNodesG2 = controlDependenceTreePDG2.getControlPredicateNodesInLevel(level2);
			Set<PDGNode> controlPredicateNodesInNextLevelG1 = new LinkedHashSet<PDGNode>();
			Set<PDGNode> controlPredicateNodesInNextLevelG2 = new LinkedHashSet<PDGNode>();
			if(level1 < maxLevel1) {
				Set<PDGNode> nodesInNextLevel = controlDependenceTreePDG1.getControlPredicateNodesInLevel(level1+1);
				controlPredicateNodesInNextLevelG1.addAll(nodesInNextLevel);
				for(PDGNode node : nodesInNextLevel) {
					if(node instanceof PDGBlockNode) {
						controlPredicateNodesInNextLevelG1.addAll(pdg1.getNestedNodesWithinBlockNode((PDGBlockNode)node));
					}
				}
			}
			if(level2 < maxLevel2) {
				Set<PDGNode> nodesInNextLevel = controlDependenceTreePDG2.getControlPredicateNodesInLevel(level2+1);
				controlPredicateNodesInNextLevelG2.addAll(nodesInNextLevel);
				for(PDGNode node : nodesInNextLevel) {
					if(node instanceof PDGBlockNode) {
						controlPredicateNodesInNextLevelG2.addAll(pdg2.getNestedNodesWithinBlockNode((PDGBlockNode)node));
					}
				}
			}
			for(PDGNode predicate1 : controlPredicateNodesG1) {
				Set<PDGNode> nodesG1 = getNodesInRegion1(pdg1, predicate1, controlPredicateNodesG1, controlPredicateNodesInNextLevelG1, controlDependenceTreePDG1);
				//special handling in level 0 for sub tree match
				if(level1 == 0 && !fullTreeMatch) {
					//int minId = allNodesInSubTreePDG1.first().getId();
					int maxId = allNodesInSubTreePDG1.last().getId();
					Set<PDGNode> nodesG1ToBeRemoved = new LinkedHashSet<PDGNode>();
					for(PDGNode nodeG1 : nodesG1) {
						if(nodeG1.getId() > maxId/* || nodeG1.getId() < minId*/) {
							nodesG1ToBeRemoved.add(nodeG1);
						}
						if(controlDependenceTreePDG1.isElseNode()) {
							double elseNodeId = controlDependenceTreePDG1.getId();
							if(nodeG1.getId() < elseNodeId) {
								nodesG1ToBeRemoved.add(nodeG1);
							}
						}
					}
					nodesG1.removeAll(nodesG1ToBeRemoved);
				}
				this.allNodesInSubTreePDG1.addAll(nodesG1);
				List<MappingState> currentStates = new ArrayList<MappingState>();
				for(PDGNode predicate2 : controlPredicateNodesG2) {
					Set<PDGNode> nodesG2 = getNodesInRegion2(pdg2, predicate2, controlPredicateNodesG2, controlPredicateNodesInNextLevelG2, controlDependenceTreePDG2);
					//special handling to add the nodes inside the final else of a symmetrical if/else if
					for(CloneStructureNode parentCloneStructure : parents) {
						if(parentCloneStructure.getMapping() instanceof PDGNodeMapping) {
							PDGNodeMapping pdgNodeMapping = (PDGNodeMapping)parentCloneStructure.getMapping();
							PDGNodeMapping symmetricalPDGNodeMapping = pdgNodeMapping.getSymmetricalIfNodePair();
							if(symmetricalPDGNodeMapping != null) {
								if(symmetricalPDGNodeMapping.getNodeG1().equals(predicate1) && symmetricalPDGNodeMapping.getNodeG2().equals(predicate2)) {
									Set<PDGNode> elseNodes = getElseNodesOfSymmetricalIfStatement2(pdg2, pdgNodeMapping.getNodeG2(), controlPredicateNodesG2, controlPredicateNodesInNextLevelG2);
									nodesG2.addAll(elseNodes);
								}
							}
						}
					}
					if(level2 == 0 && !fullTreeMatch) {
						//int minId = allNodesInSubTreePDG2.first().getId();
						int maxId = allNodesInSubTreePDG2.last().getId();
						Set<PDGNode> nodesG2ToBeRemoved = new LinkedHashSet<PDGNode>();
						for(PDGNode nodeG2 : nodesG2) {
							if(nodeG2.getId() > maxId/* || nodeG2.getId() < minId*/) {
								nodesG2ToBeRemoved.add(nodeG2);
							}
							if(controlDependenceTreePDG2.isElseNode()) {
								double elseNodeId = controlDependenceTreePDG2.getId();
								if(nodeG2.getId() < elseNodeId) {
									nodesG2ToBeRemoved.add(nodeG2);
								}
							}
						}
						nodesG2.removeAll(nodesG2ToBeRemoved);
					}
					this.allNodesInSubTreePDG2.addAll(nodesG2);
					List<MappingState> maxStates = null;
					if(level1 == 0 || level2 == 0) {
						if(predicate1.getCFGNode() instanceof CFGBranchSwitchNode && predicate2.getCFGNode() instanceof CFGBranchSwitchNode) {
							maxStates = matchBasedOnSwitchCases(finalState, nodesG1, nodesG2);
						}
						else {
							maxStates = matchBasedOnCodeFragments(finalState, nodesG1, nodesG2);
						}
					}
					else {
						ControlDependenceTreeNode cdtNode1 = controlDependenceTreePDG1.getNode(predicate1);
						ControlDependenceTreeNode cdtNode2 = controlDependenceTreePDG2.getNode(predicate2);
						//check parent-child relationship preservation (parent in the current level, children in the previously examined level)
						if(level1 < maxLevel1 && level2 < maxLevel2 && cdtNode1 != null && cdtNode2 != null) {
							List<ControlDependenceTreeNode> children1 = cdtNode1.getChildren();
							List<ControlDependenceTreeNode> children2 = cdtNode2.getChildren();
							if(finalState != null && !children1.isEmpty() && !children2.isEmpty()) {
								Set<PDGNodeMapping> nodeMappings = finalState.getNodeMappings();
								boolean childPairFoundInFinalState = false;
								for(PDGNodeMapping nodeMapping : nodeMappings) {
									ControlDependenceTreeNode cdtChildNode1 = controlDependenceTreePDG1.getNode(nodeMapping.getNodeG1());
									ControlDependenceTreeNode cdtChildNode2 = controlDependenceTreePDG2.getNode(nodeMapping.getNodeG2());
									if(cdtChildNode1 != null && cdtChildNode2 != null) {
										if(children1.contains(cdtChildNode1) && children2.contains(cdtChildNode2)) {
											childPairFoundInFinalState = true;
											break;
										}
									}
								}
								if(!childPairFoundInFinalState) {
									Set<ControlDependenceTreeNode> elseNodes1 = controlDependenceTreePDG1.getElseNodesInLevel(level1);
									Set<ControlDependenceTreeNode> elseNodes2 = controlDependenceTreePDG2.getElseNodesInLevel(level2);
									ControlDependenceTreeNode elseNode1 = controlDependenceTreePDG1.getElseNode(predicate1);
									ControlDependenceTreeNode elseNode2 = controlDependenceTreePDG2.getElseNode(predicate2);
									if(elseNode1 != null && elseNode2 != null && elseNodes1.contains(elseNode1) && elseNodes2.contains(elseNode2)) {
										List<ControlDependenceTreeNode> elseChildren1 = elseNode1.getChildren();
										List<ControlDependenceTreeNode> elseChildren2 = elseNode2.getChildren();
										boolean ifElseChildPairFoundInFinalState = false;
										boolean elseIfChildPairFoundInFinalState = false;
										for(PDGNodeMapping nodeMapping : nodeMappings) {
											ControlDependenceTreeNode cdtChildNode1 = controlDependenceTreePDG1.getNode(nodeMapping.getNodeG1());
											ControlDependenceTreeNode cdtChildNode2 = controlDependenceTreePDG2.getNode(nodeMapping.getNodeG2());
											if(cdtChildNode1 != null && cdtChildNode2 != null) {
												if(children1.contains(cdtChildNode1) && elseChildren2.contains(cdtChildNode2)) {
													ifElseChildPairFoundInFinalState = true;
												}
												if(elseChildren1.contains(cdtChildNode1) && children2.contains(cdtChildNode2)) {
													elseIfChildPairFoundInFinalState = true;
												}
											}
										}
										if(ifElseChildPairFoundInFinalState && elseIfChildPairFoundInFinalState) {
											//symmetrical if-else match
											Set<PDGNode> nodesNestedUnderIf1 = new LinkedHashSet<PDGNode>();
											Set<PDGNode> nodesNestedUnderIf2 = new LinkedHashSet<PDGNode>();
											Set<PDGNode> nodesNestedUnderElse1 = new LinkedHashSet<PDGNode>();
											Set<PDGNode> nodesNestedUnderElse2 = new LinkedHashSet<PDGNode>();
											findNodesNestedUnderIfAndElse(predicate1, nodesG1, nodesNestedUnderIf1, nodesNestedUnderElse1);
											findNodesNestedUnderIfAndElse(predicate2, nodesG2, nodesNestedUnderIf2, nodesNestedUnderElse2);
											ASTNodeMatcher astNodeMatcher = new ASTNodeMatcher(iCompilationUnit1, iCompilationUnit2);
											boolean match = astNodeMatcher.match(predicate1, predicate2);
											if(match && astNodeMatcher.isParameterizable()) {
												CompositeStatementObject composite1 = (CompositeStatementObject)predicate1.getStatement();
												List<AbstractExpression> expressions1 = composite1.getExpressions();
												CompositeStatementObject composite2 = (CompositeStatementObject)predicate2.getStatement();
												List<AbstractExpression> expressions2 = composite2.getExpressions();
												AbstractExpression conditional1 = expressions1.get(0);
												AbstractExpression conditional2 = expressions2.get(0);
												//check if there is already a difference covering the entire conditional expressions
												boolean found = false;
												for(ASTNodeDifference nodeDifference : astNodeMatcher.getDifferences()) {
													if(nodeDifference.getExpression1().toString().equals(conditional1.toString()) &&
															nodeDifference.getExpression2().toString().equals(conditional2.toString())) {
														found = true;
														Difference diff = new Difference(conditional1.toString(),conditional2.toString(),
																DifferenceType.IF_ELSE_SYMMETRICAL_MATCH);
														nodeDifference.addDifference(diff);
														break;
													}
												}
												if(!found) {
													ASTNodeDifference nodeDifference = new ASTNodeDifference(conditional1, conditional2);
													Difference diff = new Difference(conditional1.toString(),conditional2.toString(),
															DifferenceType.IF_ELSE_SYMMETRICAL_MATCH);
													nodeDifference.addDifference(diff);
													astNodeMatcher.getDifferences().add(nodeDifference);
												}
												PDGNodeMapping mapping = new PDGNodeMapping(predicate1, predicate2, astNodeMatcher);
												mapping.setSymmetricalIfElse(true);
												MappingState state = new MappingState(finalState, mapping);
												if(finalState != null)
													finalState.addChild(state);
												//match nested nodes symmetrically
												maxStates = matchBasedOnIfElseSymmetry(state, nodesNestedUnderIf1, nodesNestedUnderIf2,
														nodesNestedUnderElse1, nodesNestedUnderElse2);
												for(MappingState temp : maxStates) {
													if(!currentStates.contains(temp)) {
														currentStates.add(temp);
													}
												}
											}
										}
									}
								}
								if(!childPairFoundInFinalState) {
									continue;
								}
							}
							//handle the case where only one of the cdtNodes has mapped children
							if(finalState != null && !children1.isEmpty() && children2.isEmpty()) {
								//cdtNode2 has no children
								Set<PDGNodeMapping> nodeMappings = finalState.getNodeMappings();
								boolean cdtNode1MappedChild = false;
								for(PDGNodeMapping nodeMapping : nodeMappings) {
									ControlDependenceTreeNode cdtChildNode1 = controlDependenceTreePDG1.getNode(nodeMapping.getNodeG1());
									if(cdtChildNode1 != null && children1.contains(cdtChildNode1)) {
										cdtNode1MappedChild = true;
										break;
									}
								}
								if(cdtNode1MappedChild) {
									continue;
								}
							}
							if(finalState != null && children1.isEmpty() && !children2.isEmpty()) {
								//cdtNode1 has no children
								Set<PDGNodeMapping> nodeMappings = finalState.getNodeMappings();
								boolean cdtNode2MappedChild = false;
								for(PDGNodeMapping nodeMapping : nodeMappings) {
									ControlDependenceTreeNode cdtChildNode2 = controlDependenceTreePDG2.getNode(nodeMapping.getNodeG2());
									if(cdtChildNode2 != null && children2.contains(cdtChildNode2)) {
										cdtNode2MappedChild = true;
										break;
									}
								}
								if(cdtNode2MappedChild) {
									continue;
								}
							}
						}
						//check sibling relationship preservation (all siblings in the current level)
						ControlDependenceTreeNode cdtNode1Parent = null;
						ControlDependenceTreeNode cdtNode2Parent = null;
						if(cdtNode1 != null && cdtNode2 != null) {
							cdtNode1Parent = cdtNode1.getParent();
							cdtNode2Parent = cdtNode2.getParent();
							if(finalState != null) {
								Set<PDGNodeMapping> nodeMappings = finalState.getNodeMappings();
								List<ControlDependenceTreeNode> parentChildren1 = cdtNode1Parent.getChildren();
								//set true only if cdtNode is the first node in the list of children
								boolean siblingPairFoundInFinalState = !parentChildren1.isEmpty() && parentChildren1.get(0).equals(cdtNode1);
								boolean ifParentChildFoundInFinalState = false;
								List<ControlDependenceTreeNode> ifParentChildren1 = getIfParentChildren1(cdtNode1Parent);
								List<ControlDependenceTreeNode> ifParentChildren2 = getIfParentChildren2(cdtNode2Parent);
								List<ControlDependenceTreeNode> siblings1 = cdtNode1.getSiblings();
								List<ControlDependenceTreeNode> siblings2 = cdtNode2.getSiblings();
								for(PDGNodeMapping nodeMapping : nodeMappings) {
									ControlDependenceTreeNode cdtSiblingNode1 = controlDependenceTreePDG1.getNode(nodeMapping.getNodeG1());
									ControlDependenceTreeNode cdtSiblingNode2 = controlDependenceTreePDG2.getNode(nodeMapping.getNodeG2());
									if(cdtSiblingNode1 != null && cdtSiblingNode2 != null) {
										if(cdtNode1Parent.isElseNode() && cdtNode2Parent.isElseNode()) {
											if(ifParentChildren1.contains(cdtSiblingNode1) && ifParentChildren2.contains(cdtSiblingNode2)) {
												ifParentChildFoundInFinalState = true;
											}
										}
										if(siblings1.contains(cdtSiblingNode1) && siblings2.contains(cdtSiblingNode2)) {
											siblingPairFoundInFinalState = true;
											break;
										}
									}
								}
								if(cdtNode1Parent.isElseNode() && cdtNode2Parent.isElseNode() &&
										!ifParentChildren1.isEmpty() && !ifParentChildren2.isEmpty()) {
									if(!ifParentChildFoundInFinalState) {
										continue;
									}
								}
								else if(!siblingPairFoundInFinalState) {
									continue;
								}
							}
						}
						if(predicate1.getASTStatement() instanceof SwitchStatement && predicate2.getASTStatement() instanceof SwitchStatement) {
							ASTNodeMatcher astNodeMatcher = new ASTNodeMatcher(iCompilationUnit1, iCompilationUnit2);
							boolean match = astNodeMatcher.match(predicate1, predicate2);
							if(match && astNodeMatcher.isParameterizable()) {
								PDGNodeMapping mapping = new PDGNodeMapping(predicate1, predicate2, astNodeMatcher);
								MappingState state = new MappingState(finalState, mapping);
								if(finalState != null)
									finalState.addChild(state);
								//remove switch nodes from the nodes to be processed
								Set<PDGNode> switchBodyNodes1 = new LinkedHashSet<PDGNode>(nodesG1);
								switchBodyNodes1.remove(predicate1);
