package org.simantics.modeling.scl;

import gnu.trove.list.array.TIntArrayList;
import gnu.trove.set.hash.THashSet;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.List;

import org.simantics.db.ReadGraph;
import org.simantics.db.Resource;
import org.simantics.db.exception.DatabaseException;
import org.simantics.diagram.stubs.DiagramResource;

public class RouteGraphMatching {

    public static boolean TRACE = false;
    
    private static class Link {
        public final int a;
        public final int b;
        
        public Link(int a, int b) {
            this.a = a;
            this.b = b;
        }
    }
    
    private static class MatchingProcess {
        ReadGraph graph;
        DiagramResource DIA;
        Resource[] result;
        ArrayList<Link>[] ls;
        ArrayList<Resource>[] alternatives;
        TIntArrayList stack = new TIntArrayList();
        THashSet<Resource> knownResources = new THashSet<Resource>(); 
        
        @SuppressWarnings("unchecked")
        public MatchingProcess(ReadGraph graph, int size) {
            this.graph = graph;
            this.DIA = DiagramResource.getInstance(graph);
            this.result = new Resource[size];
            this.ls = new ArrayList[size];
            this.alternatives = new ArrayList[size];
            for(int i=0;i<size;++i)
                this.ls[i] = new ArrayList<Link>(2);
        }
        
        public void addLink(int a, int b) {
            Link link = new Link(a, b);
            ls[link.a].add(link);
            ls[link.b].add(link);
        }

        public boolean match(List<Resource> known) throws DatabaseException {
            for(int i=0;i<known.size();++i) {
                result[i] = known.get(i);
                stack.add(i);
            }
            while(!stack.isEmpty()) {
                while(!stack.isEmpty()) {
                    int pos = stack.removeAt(stack.size()-1);
                    if(!propagate(pos))
                        return false;
                }
                if(!removeKnownResourcesFromAlternatives())
                    return false;
            }
            for(int i=0;i<result.length;++i)
                if(result[i] == null) {
                    System.err.println("Didn't resolve resource " + i + ".");
                    printState();
                    return false;
                }
            return true;
        }

        private boolean removeKnownResourcesFromAlternatives() throws DatabaseException {
            for(int i=0;i<result.length;++i) {
                ArrayList<Resource> alt = alternatives[i];
                if(alt != null) {
                    alt.removeAll(knownResources);
                    if(alt.isEmpty())
                        return false;
                    if(alt.size() == 1) {
                        result[i] = alt.get(0);
                        alternatives[i] = null;
                        stack.add(i);
                    }
                }
            }
            return true;
        }

        private void printState() {
            for(int i=0;i<result.length;++i) {
                System.out.print("    {" + i + "} ");
                if(result[i] != null)
                    System.out.print(" = " + result[i].getResourceId());
                else if(alternatives[i] != null) {
                    System.out.print(" in");
                    for(Resource r : alternatives[i])
                        System.out.print(" " + r.getResourceId());
                }
                else
                    System.out.print(" unknown");
                if(!ls[i].isEmpty()) {
                    System.out.print(", links to");
                    for(Link l : ls[i])
                        System.out.print(" " + (l.a==i ? l.b : l.a));
                }
                System.out.println();
            }
        }

        private boolean propagate(int pos) throws DatabaseException {
            if(TRACE)
                System.out.println("propagate(" + pos + ")");
            Resource r = result[pos];
            knownResources.add(r);
            ArrayList<Resource> neighbors = 
                    new ArrayList<Resource>(graph.getObjects(r, DIA.AreConnected));
            neighbors.removeAll(knownResources);
            
            for(Link link : ls[pos]) {
                int other = link.a == pos ? link.b : link.a;
                ls[other].remove(link);
                if(!setAlternatives(other, neighbors))
                    return false;
            }
            ls[pos].clear();
            
            return true;
        }

        private boolean setKnown(int i, Resource value) throws DatabaseException {
            if(TRACE)
                System.out.println("setKnown(" + i + ", " + value + ")");
            if(result[i] != null) 
                return result[i].equals(value);
            if(alternatives[i] != null) {
                if(!alternatives[i].contains(value))
                    return false;
                alternatives[i] = null;
            }
            result[i] = value;
            stack.add(i);
            return true;
        }
        
        private boolean setAlternatives(int i, Collection<Resource> values) throws DatabaseException {
            if(TRACE)
                System.out.println("setAlternatives(" + i + ", " + values + ")");
            if(result[i] != null)
                return values.contains(result[i]);
            if(values.isEmpty())
                return false;
            if(values.size() == 1)
                return setKnown(i, values.iterator().next());
            ArrayList<Resource> oldAlternatives = alternatives[i];
            if(oldAlternatives == null) {
                alternatives[i] = new ArrayList<Resource>(values);
                return true;
            }
            oldAlternatives.retainAll(values);
            if(oldAlternatives.isEmpty())
                return false;
            if(oldAlternatives.size() == 1)
                return setKnown(i, oldAlternatives.get(0));
            return true;
        }
    }
    
    public static List<Resource> matchRouteGraph(ReadGraph graph, 
            List<Resource> connectors, int routeLineCount, List<Integer> links) throws DatabaseException {
        MatchingProcess process = new MatchingProcess(graph, connectors.size() +  routeLineCount);
        for(int i=0;i<links.size();i+=2)
            process.addLink(links.get(i), links.get(i+1));
        if(!process.match(connectors))
            return null;
        return Arrays.asList(process.result);
    }
    
}