A utility class for recursive search in cyclic graph

[simantics/platform.git] / bundles / org.simantics.db.common / src / org / simantics / db / common / recursive / FindRoots.java

diff --git a/bundles/org.simantics.db.common/src/org/simantics/db/common/recursive/FindRoots.java b/bundles/org.simantics.db.common/src/org/simantics/db/common/recursive/FindRoots.java
new file mode 100644 (file)
index 0000000..1f6b657
--- /dev/null
+++ b/bundles/org.simantics.db.common/src/org/simantics/db/common/recursive/FindRoots.java
@@ -0,0 +1,55 @@
+package org.simantics.db.common.recursive;
+
+import java.util.Collections;
+import java.util.Set;
+
+import org.simantics.db.Resource;
+import org.simantics.db.exception.DatabaseException;
+
+import gnu.trove.set.hash.THashSet;
+
+/**
+ * Finds all roots reachable by {@code children} function
+ */
+public abstract class FindRoots extends CachedRecursiveSearch<Set<Resource>> {
+    protected abstract boolean isRoot(Resource resource) throws DatabaseException;
+    
+    protected Set<Resource> getSourceValue(Resource resource) throws org.simantics.db.exception.DatabaseException {
+        if(isRoot(resource))
+            return Collections.singleton(resource);
+        else
+            return null;
+    }
+    
+    private static int sharedElements(Set<Resource> a, Set<Resource> b) {
+        int count = 0;
+        for(Resource r : a)
+            if(b.contains(r))
+                ++count;
+        return count;
+    }
+    
+    @Override
+    protected Set<Resource> combineNotNull(Set<Resource> a, Set<Resource> b) throws DatabaseException {
+        int aSize = a.size();
+        int bSize = b.size();
+        
+        int shared;
+        if(aSize <= bSize) {
+            shared = sharedElements(a, b);
+            if(aSize == shared)
+                return b;
+        }
+        else {
+            shared = sharedElements(b, a);
+            if(bSize == shared)
+                return a;
+        }
+        
+        // Both set contain elements not in the other set
+        THashSet<Resource> combined = new THashSet<Resource>(aSize + bSize - shared);
+        combined.addAll(a);
+        combined.addAll(b);
+        return combined;
+    }
+}