X-Git-Url: https://gerrit.simantics.org/r/gitweb?a=blobdiff_plain;f=bundles%2Forg.simantics.db.common%2Fsrc%2Forg%2Fsimantics%2Fdb%2Fcommon%2Futils%2FNearestOwnerFinder.java;fp=bundles%2Forg.simantics.db.common%2Fsrc%2Forg%2Fsimantics%2Fdb%2Fcommon%2Futils%2FNearestOwnerFinder.java;h=062d1c88a6d3ffbcbeee4066d4e3dc3390721a5b;hb=68a9ec79344f44499f9a92c95ee81b8b052a22e7;hp=0000000000000000000000000000000000000000;hpb=ac990aa4625c02006f1bc56fbfd106cf7e1c8d84;p=simantics%2Fplatform.git

diff --git a/bundles/org.simantics.db.common/src/org/simantics/db/common/utils/NearestOwnerFinder.java b/bundles/org.simantics.db.common/src/org/simantics/db/common/utils/NearestOwnerFinder.java
new file mode 100644
index 000000000..062d1c88a
--- /dev/null
+++ b/bundles/org.simantics.db.common/src/org/simantics/db/common/utils/NearestOwnerFinder.java
@@ -0,0 +1,207 @@
+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;
+    }
+}