package org.simantics.graph.db;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.List;
import java.util.Map;

import org.simantics.db.ReadGraph;
import org.simantics.db.Resource;
import org.simantics.db.common.uri.UnescapedChildMapOfResource;
import org.simantics.db.exception.DatabaseException;
import org.simantics.db.exception.RuntimeDatabaseException;
import org.simantics.db.request.Read;
import org.simantics.graph.representation.External;
import org.simantics.graph.representation.Identity;
import org.simantics.graph.representation.IdentityDefinition;
import org.simantics.graph.representation.Internal;
import org.simantics.graph.representation.Optional;
import org.simantics.graph.representation.Root;
import org.simantics.graph.representation.TransferableGraph1;
import org.simantics.utils.datastructures.Pair;

import gnu.trove.map.hash.THashMap;
import gnu.trove.map.hash.TIntIntHashMap;
import gnu.trove.procedure.TObjectObjectProcedure;
import gnu.trove.set.hash.THashSet;

/**
 * Analyses the dependencies between transferable graphs. Usage:
 * <pre>
GraphDependencyAnalyzer<TransferableGraph1> analyzer =
    new GraphDependencyAnalyzer<TransferableGraph1>();
for(TransferableGraph1 tg : tgs)
    analyzer.addGraph(tg, tg);
if(!analyzer.analyzeDependency()) {
    <Report problems> analyzer.getConflicts()
}
else if(!analyzer.doesSatisfyExternalDependencies(graph)) {
    <Report problems> analyzer.getUnsatisfiedDependencies()
}
else
    for(TransferableGraph1 tg : analyzer.getSortedGraphs())
		<Import> tg
}
 * </pre>
 * @author Hannu Niemist�
 */
public class GraphDependencyAnalyzer<T extends Comparable<T>> {

	private ArrayList<IU> graphs = new ArrayList<IU>();
	private IdentityNode root = new IdentityNode(null, null);
	
	public static class IUList {
		IU head;
		IUList tail;
		
		public IUList(IU head, IUList tail) {
			this.head = head;
			this.tail = tail;
		} 
	}
	
	public static Collection<IU> toCollection(IUList list) {
	    ArrayList<IU> result = new ArrayList<IU>();
	    while(list != null) {
	        result.add(list.head);
	        list = list.tail;
	    }
	    return result;
	}
	
	public static class IdentityNode {
		IdentityNode parent;
		String name;
		IUList provides = null;
		IUList providesOptionally = null;
		IUList requires = null;
		THashMap<String, IdentityNode> children = null;		

		public IdentityNode(IdentityNode parent, String name) {
			this.parent = parent;
			this.name = name;
		}

		public IdentityNode get(String name) {
			if(children == null) {
				children = new THashMap<String, IdentityNode>(4);
				IdentityNode node = new IdentityNode(this, name);
				children.put(name, node);
				return node;
			}
			else {
				IdentityNode node = children.get(name);
				if(node == null) {
					node = new IdentityNode(this, name);
					children.put(name, node);	
				}
				return node;
			}
		}
		
		@Override
		public String toString() {
			if(parent == null || parent.parent == null) {
				if(name.equals(""))
					return "http:/";
				else
					return name;
			}
			return parent.toString() + "/" + name;
		}
		
		public IUList getRequires() {
            return requires;
        }
	}
	
	public static class IU implements Comparable<IU> {
		final Comparable id;
		final TransferableGraph1 tg;
		IdentityNode[] identities;
		THashMap<IUList, IUList> tgLists = new THashMap<IUList, IUList>();
		THashSet<IU> dependencies = new THashSet<IU>();

		public IU(Comparable id, TransferableGraph1 tg) {
			this.id = id;
			this.tg = tg;
		}
		
		public Object getId() {
            return id;
        }
		
		public IUList pushThis(IUList node) {
			IUList result = tgLists.get(node);
			if(result == null) {
				result = new IUList(this, node);
				tgLists.put(node, result);
			}
			return result;
		}
		
		public IdentityNode defineIdentity(IdentityNode root, TIntIntHashMap identityIdToIdentityIndex, Identity identity) {
			IdentityDefinition definition = identity.definition;
			if(identities[identity.resource] != null) return identities[identity.resource]; 
			if(definition instanceof External) {
				External def = (External)definition;
				IdentityNode in = identities[def.parent];
				if(in == null)
					in = defineIdentity(root, identityIdToIdentityIndex, tg.identities[identityIdToIdentityIndex.get(def.parent)]);
				IdentityNode node = in.get(def.name);		
				node.requires = pushThis(node.requires);
				identities[identity.resource] = node;
				return node;
			}
			else if(definition instanceof Internal) {
				Internal def = (Internal)definition;
				IdentityNode in = identities[def.parent];
				if(in == null)
					in = defineIdentity(root, identityIdToIdentityIndex, tg.identities[identityIdToIdentityIndex.get(def.parent)]);
				IdentityNode node = in.get(def.name);		
				node.provides = pushThis(node.provides);
				identities[identity.resource] = node;
				return node;
			}
			else if(definition instanceof Root) {
				Root def = (Root)definition;
				IdentityNode node = root.get(def.name);
				identities[identity.resource] = node;
				return node;
			}
			else if(definition instanceof Optional) {
				Optional def = (Optional)definition;
				IdentityNode node = identities[def.parent].get(def.name);
				node.providesOptionally = pushThis(node.providesOptionally);
				identities[identity.resource] = node;
				return node;
			}
			throw new IllegalStateException("definition: " + definition);
		}
		
		public void findIdentities(IdentityNode root) {
			identities = new IdentityNode[tg.resourceCount];
			TIntIntHashMap identityIdToIdentityIndex = new TIntIntHashMap();
			for(int i=0;i<tg.identities.length;i++) {
				Identity id = tg.identities[i];
				identityIdToIdentityIndex.put(id.resource, i);
			}
			for(Identity identity : tg.identities) {
				defineIdentity(root, identityIdToIdentityIndex, identity);
			}
		}

        @Override
        public int compareTo(IU o) {
            return id.compareTo(o.id);
        }
	}
	
	private static class IUPair {
		public final IU a, b;
		public IUPair(IU a, IU b) {		
			this.a = a;
			this.b = b;
		}
		@Override
		public int hashCode() {
			return a.hashCode() + 31 * b.hashCode();
		}
		@Override
		public boolean equals(Object obj) {
			if(this == obj)
				return true;
			IUPair other = (IUPair)obj;
			return a==other.a && b == other.b;
		}
	}
	
	private static class IUListPair {
		public final IUList a;
		public final IU b;
		public IUListPair(IUList a, IU b) {		
			this.a = a;
			this.b = b;
		}
		@Override
		public int hashCode() {
			return a.hashCode() + 31 * b.hashCode();
		}
		@Override
		public boolean equals(Object obj) {
			if(this == obj)
				return true;
			IUListPair other = (IUListPair)obj;
			return a==other.a && b == other.b;
		}
	}
	
	private THashSet<IUPair> conflicts = new THashSet<IUPair>();
	private THashSet<IUListPair> handled = new THashSet<IUListPair>();
	
	private void addConflicts(IUList a) {
		while(a != null) {
			IUList b = a.tail;
			while(b != null) {
				conflicts.add(new IUPair(a.head, b.head));
				b=b.tail;
			}
			a = a.tail;
		}
	}
	
	private void addDependencies(IUList ius, IU dependency) {	
		while(ius != null) {
			ius.head.dependencies.add(dependency);			
			ius = ius.tail;
		}
	}
	
	private void analyzeDependency(IdentityNode node) {
		if(node.provides != null) {
			if(node.provides.tail != null) {
				addConflicts(node.provides);
			}
			else {
				if(node.requires != null && handled.add(new IUListPair(node.requires, node.provides.head)))
					addDependencies(node.requires, node.provides.head);
			}
		} 
		else if(node.providesOptionally != null) {
			if(handled.add(new IUListPair(node.requires, node.providesOptionally.head)))
				addDependencies(node.requires, node.providesOptionally.head);
		}
		if(node.children != null)
			for(IdentityNode child : node.children.values())
				analyzeDependency(child);
	}	

	/**
	 * Adds a graph to the analyzer
	 * @param id An identifier that is used when reporting the results.
	 * @param tg A tranferable graph.
	 */
	public void addGraph(T id, TransferableGraph1 tg) {
		assert(id != null);
		IU iu = new IU(id, tg);
		graphs.add(iu);
		iu.findIdentities(root);
	}
	
	ArrayList<T> sortedGraphs = new ArrayList<T>();
	
	class Sorter {
		THashSet<IU> alreadyInList = new THashSet<IU>();
		@SuppressWarnings("unchecked")
        public void add(IU iu) {
			if(alreadyInList.add(iu)) {
				/*System.out.println(iu.id);
				for(IU dep : iu.dependencies)
					System.out.println("    " + dep.id);
				*/
			    ArrayList<IU> list = new ArrayList<IU>(iu.dependencies);
			    Collections.sort(list);
				for(IU dep : list)
					add(dep);
				sortedGraphs.add((T)iu.id);
			}
		}
	}
	
	private void sortByDependency() {
		//System.out.println("SortByDependency");
		sortedGraphs.clear();
		Sorter sorter = new Sorter();
		Collections.sort(graphs);
		for(IU iu : graphs)
			sorter.add(iu);
	}

	/**
	 * Analyzes the dependency between transferable graphs
	 * @return true, if there are no conflicts or cyclic dependencies
	 */
	public boolean analyzeDependency() {
		analyzeDependency(root);
		sortByDependency();
		return conflicts.isEmpty();
	}

	private ArrayList<IdentityNode> unsatisfiedRequirements = new ArrayList<IdentityNode>();
	
	private void doesSatisfyExternalDependencies(final ReadGraph g, IdentityNode node, Resource resource) {		
		try {
			final Map<String, Resource> childMap = g.syncRequest(new UnescapedChildMapOfResource(resource));
			if(node.children != null)
				node.children.forEachEntry(new TObjectObjectProcedure<String, GraphDependencyAnalyzer.IdentityNode>() {
					@Override
					public boolean execute(String name, IdentityNode child) {
						Resource childResource = childMap.get(name);
						if(childResource == null) {
							if(child.provides == null && child.requires != null)
								unsatisfiedRequirements.add(child);
						}
						else
							doesSatisfyExternalDependencies(g, child, childResource);
						return true;
					}
				});
		} catch(DatabaseException e) {
			throw new RuntimeDatabaseException(e);
		}
	}
	
	/**
	 * Returns true if previously analyzed graphs are importable,
	 * i.e. all external dependencies are satisfied. This method can be called
	 * after {@code analyzeDependency} method.
	 */
	public boolean doesSatisfyExternalDependencies(ReadGraph g) throws DatabaseException {
		unsatisfiedRequirements.clear();
		IdentityNode rootLibrary = root.get("");
		if(rootLibrary != null)
			try {
				doesSatisfyExternalDependencies(g, root.get(""), g.getRootLibrary());
			} catch(RuntimeDatabaseException e) {
				Throwable cause = e.getCause();
				if(cause instanceof DatabaseException)
					throw (DatabaseException)cause;
				else
					throw e;
			}
		return unsatisfiedRequirements.isEmpty();
	}
	
	public Read<Boolean> queryExternalDependenciesSatisfied = new Read<Boolean>() {
		@Override
		public Boolean perform(ReadGraph graph) throws DatabaseException {
			return doesSatisfyExternalDependencies(graph);
		}
	};	
	
	/**
	 * Returns a collection URIs of all resources not found in the database.
	 * This method can be called after {@code doesSatisfyExternalDependencies} method.
	 * @return
	 */
	public ArrayList<IdentityNode> getUnsatisfiedDependencies() {
		return unsatisfiedRequirements;
	}
	
	/**
	 * Returns all conflicting pairs of graphs. This method can be called after 
	 * {@code analyzeDependency} method. 
	 */
	@SuppressWarnings("unchecked")
    public Collection<Pair<T, T>> getConflicts() {
		ArrayList<Pair<T,T>> result = new ArrayList<Pair<T,T>>();
		for(IUPair pair : conflicts)
			result.add(Pair.make((T)pair.a.id, (T)pair.b.id));
		return result;
	}
	
	/**
	 * Returns a list sorted by dependency so that if A depends on B
	 * then A is in the list later than B.
	 * @return
	 */
	public List<T> getSortedGraphs() {
		return sortedGraphs;
	}
		
}