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
1 package org.simantics.db.common.recursive;
2
3 import java.util.Collections;
4 import java.util.Set;
5
6 import org.simantics.db.Resource;
7 import org.simantics.db.exception.DatabaseException;
8
9 import gnu.trove.set.hash.THashSet;
10
11 /**
12  * Finds all roots reachable by {@code children} function
13  */
14 public abstract class FindRoots extends CachedRecursiveSearch<Set<Resource>> {
15     protected abstract boolean isRoot(Resource resource) throws DatabaseException;
16     
17     protected Set<Resource> getSourceValue(Resource resource) throws org.simantics.db.exception.DatabaseException {
18         if(isRoot(resource))
19             return Collections.singleton(resource);
20         else
21             return null;
22     }
23     
24     private static int sharedElements(Set<Resource> a, Set<Resource> b) {
25         int count = 0;
26         for(Resource r : a)
27             if(b.contains(r))
28                 ++count;
29         return count;
30     }
31     
32     @Override
33     protected Set<Resource> combineNotNull(Set<Resource> a, Set<Resource> b) throws DatabaseException {
34         int aSize = a.size();
35         int bSize = b.size();
36         
37         int shared;
38         if(aSize <= bSize) {
39             shared = sharedElements(a, b);
40             if(aSize == shared)
41                 return b;
42         }
43         else {
44             shared = sharedElements(b, a);
45             if(bSize == shared)
46                 return a;
47         }
48         
49         // Both set contain elements not in the other set
50         THashSet<Resource> combined = new THashSet<Resource>(aSize + bSize - shared);
51         combined.addAll(a);
52         combined.addAll(b);
53         return combined;
54     }
55 }