package org.simantics.graph.matching;

import gnu.trove.set.hash.THashSet;

import java.util.Arrays;

import org.simantics.graph.representation.TransferableGraph1;

/**
 * Matching of two transferable graphs.
 * 
 * @author Hannu Niemistö
 */
public class GraphMatching {
	public static final boolean DEBUG = false;
	public static final boolean TIMING = false;

	int aOriginalSize;
	int bOriginalSize;
	CanonicalGraph aGraph;
	CanonicalGraph bGraph;
	protected int[] aToB;
	protected int[] bToA;
	int size;
	
	public GraphMatching(TransferableGraph1 a, TransferableGraph1 b) {
		long begin = System.nanoTime();
		this.aGraph = new CanonicalGraph(a);
		this.bGraph = new CanonicalGraph(b);
		aToB = new int[this.aGraph.resourceCount];
		Arrays.fill(aToB, -1);
		bToA = new int[this.bGraph.resourceCount];
		Arrays.fill(bToA, -1);
		this.aOriginalSize = a.resourceCount;
		this.bOriginalSize = b.resourceCount;
		if(TIMING) {
			long end = System.nanoTime();
			System.out.println("Initialization: " + (end-begin)*1e-6 + "ms");
		}
	}

	public void print() {
		System.out.println("Resources in a:  " + aGraph.resourceCount);
		System.out.println("Identities in a: " + aGraph.identities.length);
		System.out.println("Statements in a: " + aGraph.statements.length/6);
		System.out.println();
		System.out.println("Resources in b:  " + bGraph.resourceCount);
		System.out.println("Identities in b: " + bGraph.identities.length);
		System.out.println("Statements in b: " + bGraph.statements.length/6);
		System.out.println();
		System.out.println("Match size:      " + size());
	}

	public int size() {		
		return size;
	}
	
	public void recomputeSize() {
		int count = 0;
		for(int b : aToB)
			if(b >= 0)
				++count;
		size = count;
	}

	public void map(int a, int b) {
		//if(aToB[a] < 0 && bToA[b] < 0) {
			++size;
			aToB[a] = b;
			bToA[b] = a;
			/*if(aGraph.inverses.contains(a) && bGraph.inverses.contains(b) &&
					aGraph.inverses.get(a) != a) {
				int invA = aGraph.inverses.get(a);
				int invB = bGraph.inverses.get(b);
				++size;
				aToB[invA] = invB;			
				bToA[invB] = invA;			
			}*/
		/*}
		else
			System.out.println("ERR");*/
	}
	
	public void map(int[] as, int[] bs) {
		for(int i=0;i<as.length;++i)
			map(as[i], bs[i]);
	}
	
	public void unmap(int a, int b) {
		--size;
		aToB[a] = -1;
		bToA[b] = -1;
		/*if(aGraph.inverses.contains(a) && bGraph.inverses.contains(b) &&
				aGraph.inverses.get(a) != a) {
			int invA = aGraph.inverses.get(a);
			int invB = bGraph.inverses.get(b);
			--size;
			aToB[invA] = -1;
			bToA[invB] = -1;
		}*/
	}
	
	public void unmap(int[] as, int[] bs) {
		for(int i=0;i<as.length;++i)
			unmap(as[i], bs[i]);
	}

	public boolean checkMatch(int[] as, int[] bs) {
		for(int i=0;i<as.length;++i)
			if(!checkMatch(as[i], bs[i]))
				return false;
		return true;
	}

	public boolean checkMatch(int a, int b) {
		Stat[] aStats = aGraph.statements[a];
		Stat[] bStats = bGraph.statements[b];
		if(aStats.length != bStats.length)
			return false;
		THashSet<Stat> mappedStats = new THashSet<Stat>();
		int[] aToB = this.aToB;
		for(Stat stat : aStats) {
			int mp = aToB[stat.p];
			int mo = aToB[stat.o];
			if(mp < 0 || mo < 0)
				return false;
			mappedStats.add(new Stat(mp, mo));
		}
		for(Stat stat : bStats)
			if(!mappedStats.contains(stat))
				return false;
		return true;
	}
	
	public int maxSize() {
		return Math.min(aGraph.resourceCount, bGraph.resourceCount);
	}
	
	public int[] getAToB() {
		return aToB;
	}
	
	public int[] getBToA() {
		return bToA;
	}
	
	public static int[] cut(int[] map, int domainSize, int rangeSize) {
		int[] newMap = new int[domainSize];
		for(int i=0;i<domainSize;++i) {
			int temp = map[i];
			if(temp >= rangeSize)
				newMap[i] = -1;
			else
				newMap[i] = temp;
		}
		return newMap;
	}
	
	public void match() {
		apply(IdentityMatchingStrategy.INSTANCE);
		apply(CanonicalizingMatchingStrategy.INSTANCE);
		while(true) {
			if(size == maxSize())
				break;
			int curSize = size;
			apply(VotingMatchingStrategy.INSTANCE);
			if(size == curSize)
				break;
		}
		aToB = cut(aToB, aOriginalSize, bOriginalSize);
		bToA = cut(bToA, bOriginalSize, aOriginalSize);
	}
	
	private void apply(GraphMatchingStrategy strategy) {
		if(TIMING) {
			long begin = System.nanoTime();
			strategy.applyTo(this);
			long end = System.nanoTime();		
			System.out.println(strategy.getClass().getSimpleName() + ": " + 
					(end - begin)*1e-6 + "ms");
		}
		else
			strategy.applyTo(this);
	}
}