package org.simantics.db.common.recursive; import java.util.ArrayList; import java.util.Collection; import org.simantics.db.Resource; import org.simantics.db.exception.DatabaseException; import gnu.trove.impl.Constants; import gnu.trove.map.hash.THashMap; import gnu.trove.map.hash.TObjectIntHashMap; /** *
A utility class that calculates the combination of all source values * given by {@link getSourceValue} * reachable from a given resource by {@link #children} function and caches the results. * *
The function {@link #combineNotNull} is assumed to be a semilattice * operation, i.e., the following laws must hold: *
* Commutativity: combineNotNull(a, b) = combineNotNull(b, a) * Associativity: combineNotNull(a, combineNotNull(b, c)) = combineNotNull(combineNotNull(a, b), c) * Idempotency: combineNotNull(a, a) = a ** *
If the graph of the function {link children} is acyclic, * the function {@link get} works equally to the following * simpler implementation: *
* public T get(Resource resource) throws DatabaseException { * if(resultMap.contains(resource)) * return resultMap.get(resource); * * T result = getSourceValue(resource); * if(result == null) * for(Resource child : children(resource)) * result = combine(result, get(child)); * resultMap.put(resource, result); * return result; * } **/ public abstract class CachedRecursiveSearch
* Commutativity: combineNotNull(a, b) = combineNotNull(b, a) * Associativity: combineNotNull(a, combineNotNull(b, c)) = combineNotNull(combineNotNull(a, b), c) * Idempotency: combineNotNull(a, a) = a **/ protected abstract T combineNotNull(T a, T b) throws DatabaseException; /** * Combines the values and also checks if either of them is null or * if the values are equal. */ protected T combine(T a, T b) throws DatabaseException { if(a == null) return b; else if(b == null || a == b) return a; else return combineNotNull(a, b); } /** * Contains the cached results */ private final THashMap
Returns the combination of all source values reachable from the given resource. * Returns {@code null}, if no source value is reachable. * *
The method is not thread safe.
*/
public T get(Resource resource) throws DatabaseException {
if(resultMap.contains(resource))
return resultMap.get(resource);
else {
curIndex = 0;
calc(resource);
return previousResult;
}
}
private static final int NO_VALUE = -1;
private final TObjectIntHashMap Calculates the result for the given resource and stores it into {@code resultMap}.
*
* The function is implemented by depth-first search where each node gets increasing
* index number. During the calculation of the result for the resource, the index
* is stored into {@code indexMap}. This information is used to detect, if the recursive
* search has encountered a resource whose calculation has not yet been finished. In this case,
* the resource must be a part of a strongly connected component of the graph of
* {@code children}. The function returns the lowest index of unfinished calculation
* it encountered.
*/
private int calc(Resource resource) throws DatabaseException {
// Check first if the resource has a source value
T result = getSourceValue(resource);
if(result != null) {
resultMap.put(resource, result);
previousResult = result;
return NO_VALUE;
}
// Choose an index and put it into indexMpa
int index = curIndex++;
indexMap.put(resource, index);
stack.add(resource);
// Variable lowindex maintains the lowest index
// reachable from this resource. If it is smaller than
// index, the resource is part of a bigger strongly connected
// component.
int lowindex = index;
for(Resource child : children(resource)) {
if(resultMap.contains(child)) {
// The result for the child has already been calculated
result = combine(result, resultMap.get(child));
}
else {
int childIndex = indexMap.get(child);
if(childIndex == NO_VALUE) {
childIndex = calc(child);
result = combine(result, previousResult);
if(childIndex == NO_VALUE)
continue;
}
lowindex = Math.min(lowindex, childIndex);
}
}
if(lowindex == index) {
// Remove the resources of the strongly connected component from the stack and assign
// the result to all these resources.
Resource r;
do {
r = stack.remove(stack.size()-1);
indexMap.remove(r);
resultMap.put(r, result);
} while(r != resource);
previousResult = result;
return NO_VALUE;
}
else {
// This resource is a part of a bigger strongly connected component.
// Therefore the current result is still partial and will be
// combined with the other results in this component.
previousResult = result;
return lowindex;
}
}
}