package org.simantics.graph.matching;

import gnu.trove.list.array.TIntArrayList;
import gnu.trove.map.hash.THashMap;
import gnu.trove.map.hash.TIntIntHashMap;
import gnu.trove.map.hash.TIntObjectHashMap;
import gnu.trove.procedure.TObjectProcedure;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

/**
 * Matches isomorphic components of the not yet matched graphs together.
 * 
 * @author Hannu Niemistö
 */
public enum ComponentMatchingStrategy implements GraphMatchingStrategy {
	INSTANCE;

	static class UnionFind {
		int[] canonical;
		
		public UnionFind(int size) {
			canonical = new int[size];
			for(int i=0;i<size;++i)
				canonical[i] = i;
		}
		
		public int canonical(int a) {
			int b = canonical[a];
			if(b != a) {
				int c = canonical[b];
				if(b != c) {
					c = canonical(c);
					canonical[b] = c;					
					canonical[a] = c;
					return c;
				}
			}
			return b;
		}
		
		public void merge(int a, int b) {
			a = canonical(a);
			b = canonical(b);
			canonical[a] = b;
		}
	}
	
	public static int[][] findComponents(int[] map, Stat[][] statements, TIntIntHashMap inverses) {
		int resourceCount = map.length;
		
		UnionFind uf = new UnionFind(resourceCount);
		for(int s=0;s<resourceCount;++s)
			if(map[s] < 0) {
				for(Stat stat : statements[s]) {
					int o = stat.o;
					if(s < o && map[o] < 0)
						uf.merge(s, o);
				}
				/*if(inverses.containsKey(s))
					uf.merge(s, inverses.get(s));
					*/
			}
		
		TIntObjectHashMap<TIntArrayList> components = new TIntObjectHashMap<TIntArrayList>();
		for(int i=0;i<resourceCount;++i)
			if(map[i] < 0) {
				int c = uf.canonical(i);
				TIntArrayList els = components.get(c);
				if(els == null) {
					els = new TIntArrayList(2);
					components.put(c, els);
				}
				els.add(i);
			}
		
		final int[][] result = new int[components.size()][];
		components.forEachValue(new TObjectProcedure<TIntArrayList>() {
			int i = 0;
			@Override
			public boolean execute(TIntArrayList els) {
				result[i++] = els.toArray();
				return true;
			}
		});
		return result;
	}	
	
	public static Stat[][] neighbors(int[] map, Stat[][] statements) {
		int resourceCount = map.length;
		Stat[][] neighbors = new Stat[resourceCount][];
		
		ArrayList<Stat> stats = new ArrayList<Stat>();
		for(int s=0;s<resourceCount;++s) {
			if(map[s] >= 0) {
				neighbors[s] = Stat.NO_STATS;
				continue;
			}
			
			for(Stat stat : statements[s]) {
				int pp = map[stat.p] >= 0 ? stat.p : -1;
				int oo = map[stat.o] >= 0 ? stat.o : -1;				
				stats.add(new Stat(pp, oo));
			}
			
			if(stats.isEmpty())
				neighbors[s] = Stat.NO_STATS;
			else {
				neighbors[s] = stats.toArray(new Stat[stats.size()]);
				stats.clear();
			}
		}
		
		return neighbors;
	}
	
	static class Component {
		int[] elements;
		Stat[][] neighbors;
		
		public Component(int[] elements, Stat[][] neighbors) {
			this.elements = elements;
			this.neighbors = new Stat[elements.length][];
			for(int i=0;i<elements.length;++i)
				this.neighbors[i] = neighbors[elements[i]];
		}
		
		public void map(int[] map) {
			for(Stat[] stats : neighbors)
				for(Stat stat : stats)
					stat.map(map);
		}
		
		static class PP {
			int element;
			Stat[] stats;
			
			public PP(int element, Stat[] stats) {
				this.element = element;
				Arrays.sort(stats, Stat.STAT_COMPARATOR);
				this.stats = stats;
			}
		}
		
		static final Comparator<PP> PP_COMPARATOR = new Comparator<PP>() {
			@Override
			public int compare(PP o1, PP o2) {
				Stat[] stats1 = o1.stats;
				Stat[] stats2 = o2.stats;
				int l1 = stats1.length;
				int l2 = stats2.length;
				if(l1 < l2)
					return -1;
				else if(l1 > l2)
					return 1;
				for(int i=0;i<l1;++i) {
					Stat s1 = stats1[i];
					Stat s2 = stats2[i];
					if(s1.p < s2.p)
						return -1;
					else if(s1.p > s2.p)
						return 1;
					else if(s1.o < s2.o)
						return -1;
					else if(s1.o > s2.o)
						return 1;
				}
				return 0;
			}			
		};
		
		public void canonicalize(String[] elNames, String[] statNames) {
			PP[] pps = new PP[elements.length];
			for(int i=0;i<elements.length;++i)
				pps[i] = new PP(elements[i], neighbors[i]);
			Arrays.sort(pps, PP_COMPARATOR);
			for(int i=0;i<pps.length-1;++i)
				if(PP_COMPARATOR.compare(pps[i], pps[i+1]) == 0) {
					System.out.println("AMB " + pps.length + " " + (elNames==statNames));
					for(i=0;i<pps.length-1;++i) {
						if(PP_COMPARATOR.compare(pps[i], pps[i+1]) == 0)
							System.out.print(">   ");
						else
							System.out.print("    ");
						System.out.println(elNames[pps[i].element]);
						for(Stat stat : pps[i].stats)
							System.out.println("        " + stat.toString(statNames));
					}
					break;
				}
			for(int i=0;i<elements.length;++i) {
				PP pp = pps[i];
				elements[i] = pp.element;
				neighbors[i] = pp.stats;
			}
		}

		public boolean isIsolated() {
			for(Stat[] stats : neighbors)
				if(stats.length > 0)
					return false;
			return true;
		}
	}
	
	static class TNeighbourObjectHashMap<T> extends THashMap<Stat[][], T> {
		@Override
		protected boolean equals(Object one, Object two) {
			Stat[][] o1 = (Stat[][])one;
			Stat[][] o2 = (Stat[][])two;
			if(o1.length != o2.length)
				return false;
			for(int i=0;i<o1.length;++i) {
				Stat[] ss1 = o1[i];
				Stat[] ss2 = o2[i];
				if(ss1.length != ss2.length)
					return false;
				for(int j=0;j<ss1.length;++j) {
					Stat s1 = ss1[j];
					Stat s2 = ss2[j];
					if(s1.p != s2.p || s1.o != s2.o)
						return false;
				}
			}
			return true;
		}
		
		@Override
		protected int hash(Object obj) {
			int result = 152433;
			for(Stat[] stats : (Stat[][])obj)
				for(Stat stat : stats)
					result = (result*31 + stat.p)*31 + stat.o;
			return result;
		}
	}
	
	@Override
	public void applyTo(GraphMatching matching) {
		System.out.println("ComponentMatchingStrategy");
		TNeighbourObjectHashMap<ArrayList<int[]>> aComponents = new TNeighbourObjectHashMap<ArrayList<int[]>>(); 
		{			
			Stat[][] neighbors = neighbors(matching.aToB, matching.aGraph.statements);
			//TIntIntHashMap componentSizes = new TIntIntHashMap();
			for(int[] els : findComponents(matching.aToB, matching.aGraph.statements, matching.aGraph.inverses)) {
				/*for(int el : els)
					System.out.print(matching.aGraph.names[el] + " ");
				System.out.println();
				componentSizes.adjustOrPutValue(els.length, 1, 1);*/
				Component component = new Component(els, neighbors);
				if(component.isIsolated())
					continue;
				component.map(matching.aToB);
				component.canonicalize(matching.aGraph.names, matching.bGraph.names);
				ArrayList<int[]> values = aComponents.get(component.neighbors);
				if(values == null) {
					values = new ArrayList<int[]>(1);
					aComponents.put(component.neighbors, values);
				}
				values.add(component.elements);
			}
			/*componentSizes.forEachEntry(new TIntIntProcedure() {				
				@Override
				public boolean execute(int a, int b) {
					System.out.println("Components of size " + a + ": " + b);
					return true;
				}
			});*/
		}
		
		ArrayList<Component> bComponents = new ArrayList<Component>(); 
		{
			Stat[][] neighbors = neighbors(matching.bToA, matching.bGraph.statements);
			for(int[] els : findComponents(matching.bToA, matching.bGraph.statements, matching.bGraph.inverses)) {
				Component component = new Component(els, neighbors);
				if(component.isIsolated())
					continue;
				component.canonicalize(matching.bGraph.names, matching.bGraph.names);
				bComponents.add(component);
			}
		}
		
		for(Component c : bComponents) {
			ArrayList<int[]> candidates = aComponents.get(c.neighbors);
			if(candidates != null)
				for(int i=0;i<candidates.size();++i) {
					int[] els = candidates.get(i);
					if(els != null) {
						matching.map(els, c.elements);
						if(matching.checkMatch(els, c.elements)) {
							if(candidates.size() == 1)
								aComponents.remove(c.neighbors);
							else {
								int last = candidates.size()-1;
								int[] temp = candidates.remove(last);
								if(i < last)
									candidates.set(i, temp);
							}
						    break;
						}
						else
							matching.unmap(els, c.elements);
					}	
				}			
		}
	}
}