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;
/**
*
A utility to finds the nearest owner of a real or imaginary resource.
*
* 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.
*
* 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.
*
* @see {@link #getNearestOwner(ReadGraph, Resource)}
* @see {@link #getNearestOwner(ReadGraph, Collection)}
*
*/
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 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 owners) throws DatabaseException {
Iterator 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 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 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 getDirectOwners(ReadGraph graph, Layer0 L0, Resource resource) throws DatabaseException {
Collection owners = graph.getObjects(resource, L0.IsOwnedBy);
if(owners.isEmpty()) {
if(resource.equals(graph.getRootLibrary()))
return Collections.emptyList();
owners = new THashSet();
// 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.
// Fix getObjects to not return duplicate entries
owners = new HashSet(owners);
}
return owners;
}
/**
* Finds the nearest owner of a resource. Nearest owner is the
* immediate dominator
* 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.
*
* 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.
*
* @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 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;
}
/**
* 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.
*
* 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.
*/
public static Resource getNearestOwnerFromDirectOwners(ReadGraph graph, Collection 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;
}
}