package org.simantics.db.common.utils;

import java.util.Collection;
import java.util.Collections;
import java.util.HashSet;
import java.util.Iterator;

import org.simantics.db.ReadGraph;
import org.simantics.db.Resource;
import org.simantics.db.Statement;
import org.simantics.db.exception.DatabaseException;
import org.simantics.layer0.Layer0;

import gnu.trove.map.hash.TObjectIntHashMap;
import gnu.trove.set.hash.THashSet;

/**
 * <p>A utility to finds the nearest owner of a real or imaginary resource.</p>
 * 
 * <p>The nearest owner
 * is found by first finding a path (pilot path) from the input to a root resource and then
 * trying to find other paths to the resources in the pilot path such that the other
 * paths don't visit other resources of the pilot path. The farthest resource so found
 * is then the nearest common owner. See the methods for the exact specification.</p>
 * 
 * <p>The time and space complexity of the algorithm is O(m),
 * where m is the number of resources reachable by direct-owners relation from the input.</p>
 * 
 * @see {@link #getNearestOwner(ReadGraph, Resource)}
 * @see {@link #getNearestOwner(ReadGraph, Collection)}</p>
 * 
 */
public class NearestOwnerFinder {
    private static final int FIRST_DISTANCE = 1;
    private static final int UNVISITED = 0;
    private static final int NOT_INTERESTING_ANYMORE = -1;

    private final ReadGraph graph;
    private final Layer0 L0;

    private final TObjectIntHashMap<Resource> resourceStatus = new TObjectIntHashMap<>();

    private int nearestOwnerDistance; // = 0
    private Resource nearestOwner; // = null

    private NearestOwnerFinder(ReadGraph graph, Layer0 L0) {
        this.graph = graph;
        this.L0 = L0;
    }

    /**
     * Iterates the owners of the input resource. It first
     * tries to find the pilot path and when it has been found,
     * it browses other owners with {@link #browseNonpilot}.
     */
    private void browseOwnersOfInput(Collection<Resource> owners) throws DatabaseException {
        Iterator<Resource> it = owners.iterator();
        while(it.hasNext()) {
            Resource owner = it.next();
            if(browsePilot(owner, FIRST_DISTANCE)) {
                // Because we found a path to root, {@code owner}
                // becomes our first candidate for nearestOwner.
                nearestOwner = owner;
                nearestOwnerDistance = FIRST_DISTANCE;
                
                // Tries to find other paths to the resource in the pilot path.
                while(it.hasNext())
                    browseNonpilot(it.next());
                return;
            }
        }
    }

    /**
     * Tries to find a first path (=pilot path) to a root with DFS.
     */
    private boolean browsePilot(Resource resource, int distance) throws DatabaseException {
        if(resourceStatus.putIfAbsent(resource, distance) != UNVISITED)
            // We recursed back to the current path or encountered previously failed path.
            return false;

        Collection<Resource> owners = getDirectOwners(graph, L0, resource);
        if(owners.isEmpty())
            // We found a root
            return true;

        for(Resource owner : owners)
            if(browsePilot(owner, distance+1)) {
                // We found a path to a root
                return true;
            }

        // Failed to find a path to a root
        resourceStatus.put(resource, NOT_INTERESTING_ANYMORE);
        return false;
    }

    /**
     * Tries to find some path to a resource on a pilot path using DFS.
     * Marks all visited resource by {@code NOT_INTERESTING_ANYMORE}
     * to prevent visiting the same resources more than once.
     */
    private void browseNonpilot(Resource resource) throws DatabaseException {
        // In the next statement, we may overwrite also information about resource being on pilot path,
        // but that is ok, because we don't care resources that are nearer than nearestOwnerDistance.
        int status = resourceStatus.put(resource, NOT_INTERESTING_ANYMORE);
        if(status == UNVISITED) {
            Collection<Resource> owners = getDirectOwners(graph, L0, resource);
            if(owners.isEmpty()) {
                // This is a root that differs from the root at the end of the pilot path.
                // Therefore there cannot be a nearest owner.
                nearestOwnerDistance = Integer.MAX_VALUE;
                nearestOwner = null;
                return;
            }
            for(Resource owner : owners)
                browseNonpilot(owner);
        }
        else if(status > nearestOwnerDistance) {
            nearestOwnerDistance = status;
            nearestOwner = resource;
        }
    }

    private static Collection<Resource> getDirectOwners(ReadGraph graph, Layer0 L0, Resource resource) throws DatabaseException {
        Collection<Resource> owners = graph.getObjects(resource, L0.IsOwnedBy);
        if(owners.isEmpty()) {
            if(resource.equals(graph.getRootLibrary()))
                return Collections.emptyList();

            owners = new THashSet<Resource>();

            // If there are no owners, collect resources referring to this resource by IsRelatedTo
            for(Statement statement : graph.getStatements(resource, L0.IsWeaklyRelatedTo)) {
                Resource inverse = graph.getPossibleInverse(statement.getPredicate());
                if(inverse != null) {
                    if(graph.isSubrelationOf(inverse, L0.IsRelatedTo)) {
                        // Filter away tags
                        if(resource.equals(statement.getObject()))
                            continue;
                        owners.add(statement.getObject());
                    }
                }
            }
        }
        else if(owners.size() > 1) {
            // TODO: getObjects returns duplicate entries (https://www.simantics.org/redmine/issues/4885) and therefore direct is Set<Resource>.
            // Fix getObjects to not return duplicate entries
            owners = new HashSet<Resource>(owners);
        }

        return owners;
    }

    /**
     * <p>Finds the nearest owner of a resource. Nearest owner is the
     * <a href="https://en.wikipedia.org/wiki/Dominator_(graph_theory)">immediate dominator</a>
     * of the resource in a graph defined in the following way:
     * Each IsComposedOf statement is an edge of the graph.
     * Additionally an IsRelatedTo statement in an edge of graph if
     * no IsComposedOf statement points to its object.</p>
     * 
     * <p>The root of the graph is any resource without owners or the root resource
     * of the database. If the search encounters two distinct roots, there
     * cannot be a nearest owner.</p>
     * 
     * @return The nearest owner or {@code null} if no roots or more than one roots are found.
     */
    public static Resource getNearestOwner(ReadGraph graph, Resource resource) throws DatabaseException {
        // Handle cases of one or zero direct owners
        Layer0 L0 = Layer0.getInstance(graph);
        Collection<Resource> owners = getDirectOwners(graph, L0, resource);
        if(owners.size() == 1)
            return owners.iterator().next();
        if(owners.isEmpty())
            return null;

        // There are two or more direct owners
        NearestOwnerFinder finder = new NearestOwnerFinder(graph, L0);
        finder.resourceStatus.put(resource, NOT_INTERESTING_ANYMORE);
        finder.browseOwnersOfInput(owners);
        return finder.nearestOwner;
    }
    
    /**
     * <p>Finds the nearest owner of a real or imaginary resource whose direct owners are known. This works in the same
     * way as the method for one resource {@link #getNearestOwner(ReadGraph, Resource)}
     * but we add one extra node to the graph that has the input resources as direct owners and
     * find the immediate dominator of that extra node.</p>
     * 
     * <p>Note that this method may return one of the input resources if it is dominator of all other
     * resources in the collection. Returns {@code null} if the input collection is empty.</p>
     */
    public static Resource getNearestOwnerFromDirectOwners(ReadGraph graph, Collection<Resource> owners) throws DatabaseException {
        // Handle the cases of one or zero direct owners
        if(owners.size() == 1)
            return owners.iterator().next();
        if(owners.isEmpty())
            return null;

        // There are two or more direct owners
        Layer0 L0 = Layer0.getInstance(graph);
        NearestOwnerFinder finder = new NearestOwnerFinder(graph, L0);
        finder.browseOwnersOfInput(owners);
        return finder.nearestOwner;
    }
}