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;
    }
}