package org.simantics.graph.matching;

import gnu.trove.map.hash.TIntIntHashMap;
import gnu.trove.map.hash.TIntObjectHashMap;
import gnu.trove.map.hash.TObjectIntHashMap;

import java.util.ArrayList;

import org.simantics.graph.representation.External;
import org.simantics.graph.representation.Identity;
import org.simantics.graph.representation.Internal;
import org.simantics.graph.representation.Optional;
import org.simantics.graph.representation.Root;

/**
 * A strategy matching resources with equal URIs.
 * 
 * @author Hannu Niemistö
 */
public enum IdentityMatchingStrategy implements GraphMatchingStrategy {

	INSTANCE;
	
	static class NamedResource {
		String name;
		int resource;
		
		public NamedResource(String name, int resource) {
			this.name = name;
			this.resource = resource;
		}
	}
	
	static class IdentityTree {
		TIntObjectHashMap<ArrayList<NamedResource>> childMap = new TIntObjectHashMap<ArrayList<NamedResource>>();
		ArrayList<NamedResource> roots = new ArrayList<NamedResource>(); 
		
		public IdentityTree(Identity[] indentities) {
			for(Identity id : indentities) {
				if(id.definition instanceof External) {
					External def = (External)id.definition;
					addChild(id.resource, def.parent, def.name);
				}
				else if(id.definition instanceof Internal) {
					Internal def = (Internal)id.definition;
					addChild(id.resource, def.parent, def.name);
				}
				else if(id.definition instanceof Optional) {
					Optional def = (Optional)id.definition;
					addChild(id.resource, def.parent, def.name);
				}
				else if(id.definition instanceof Root) {
					addRoot(id.resource, ((Root)id.definition).name);
				}
			}
		}

		private void addRoot(int root, String name) {
			roots.add(new NamedResource(name, root));
		}
		
		private void addChild(int child, int parent, String name) {
			ArrayList<NamedResource> children = childMap.get(parent);
			if(children == null) {
				children = new ArrayList<NamedResource>();
				childMap.put(parent, children);
			}
			children.add(new NamedResource(name, child));
		}
	}
	
	static class MatchingProcess {
		int[] aToB; 
		int[] bToA; 
		TIntIntHashMap aInv;
		TIntIntHashMap bInv;
		IdentityTree aTree; 
		IdentityTree bTree;
		
		public MatchingProcess(int[] aToB, int[] bToA,
				TIntIntHashMap aInv, TIntIntHashMap bInv,
				IdentityTree aTree, IdentityTree bTree) {
			this.aToB = aToB;
			this.bToA = bToA;
			this.aInv = aInv;
			this.bInv = bInv;
			this.aTree = aTree;
			this.bTree = bTree;
		}

		public void execute() {
			match(aTree.roots, bTree.roots);
		}

		private void match(ArrayList<NamedResource> as, ArrayList<NamedResource> bs) {
			TObjectIntHashMap<String> map = new TObjectIntHashMap<String>();
			for(NamedResource b : bs)
				map.put(b.name, b.resource);
			for(NamedResource a : as)
				if(map.contains(a.name))
					match(a.resource, map.get(a.name));
		}

		private void match(int a, int b) {
			if(aToB[a] < 0 && bToA[b] < 0) {
				aToB[a] = b;
				bToA[b] = a;
				
				if(aInv.contains(a) && bInv.contains(b))
					match(aInv.get(a), bInv.get(b));
				
				ArrayList<NamedResource> as = aTree.childMap.get(a);
				if(as == null)
					return;
				ArrayList<NamedResource> bs = bTree.childMap.get(b);
				if(bs == null)
					return;
				match(as, bs);
			}
		}
	}
	
	public void mapUnmapped(int[] map, TIntIntHashMap inverses, Identity[] identities, int rangeCount) {
		for(Identity id : identities) {
			int r = id.resource;
			if(map[r] < 0) {
				map[r] = rangeCount++;
				if(inverses.containsKey(r))
					map[inverses.get(r)] = rangeCount++;
			}
		}
	}
	
	@Override
	public void applyTo(GraphMatching matching) {
		new MatchingProcess(
				matching.aToB, matching.bToA, 
				matching.aGraph.inverses, matching.bGraph.inverses,
				new IdentityTree(matching.aGraph.identities), new IdentityTree(matching.bGraph.identities)
		).execute();	
		mapUnmapped(matching.aToB, matching.aGraph.inverses, 
				matching.aGraph.identities, matching.bGraph.resourceCount);
		mapUnmapped(matching.bToA, matching.bGraph.inverses, 
				matching.bGraph.identities, matching.aGraph.resourceCount);
		matching.recomputeSize();
	}
}