+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;
+
+/**
+ * <p>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.
+ *
+ * <p>The function {@link #combineNotNull} is assumed to be a semilattice
+ * operation, i.e., the following laws must hold:
+ * <pre>
+ * Commutativity: combineNotNull(a, b) = combineNotNull(b, a)
+ * Associativity: combineNotNull(a, combineNotNull(b, c)) = combineNotNull(combineNotNull(a, b), c)
+ * Idempotency: combineNotNull(a, a) = a
+ * </pre>
+ *
+ * <p>If the graph of the function {link children} is acyclic,
+ * the function {@link get} works equally to the following
+ * simpler implementation:
+ * <pre>
+ * 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;
+ * }
+ * </pre>
+ */
+public abstract class CachedRecursiveSearch<T> {
+ /**
+ * Returns the source value associated with the given resource or {@code null},
+ * if the resource does not have a source value.
+ */
+ protected abstract T getSourceValue(Resource resource) throws DatabaseException;
+
+ /**
+ * Returns the children of the given resource.
+ */
+ protected abstract Collection<Resource> children(Resource parent) throws DatabaseException;
+
+ /**
+ * Combines the given source values. The function may assume that the values
+ * are not {@code null}. The function must satisfy the following laws:
+ * <pre>
+ * Commutativity: combineNotNull(a, b) = combineNotNull(b, a)
+ * Associativity: combineNotNull(a, combineNotNull(b, c)) = combineNotNull(combineNotNull(a, b), c)
+ * Idempotency: combineNotNull(a, a) = a
+ * </pre>
+ */
+ 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<Resource, T> resultMap = new THashMap<Resource, T>();
+
+ /**
+ * <p>Returns the combination of all source values reachable from the given resource.
+ * Returns {@code null}, if no source value is reachable.
+ *
+ * <p>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<Resource> indexMap =
+ new TObjectIntHashMap<Resource>(Constants.DEFAULT_CAPACITY, Constants.DEFAULT_LOAD_FACTOR, NO_VALUE);
+
+ private int curIndex;
+ private final ArrayList<Resource> stack = new ArrayList<Resource>();
+
+ /**
+ * This field is used to return the result from the {@code calc}
+ */
+ private T previousResult;
+
+ /**
+ * <p>Calculates the result for the given resource and stores it into {@code resultMap}.
+ *
+ * <p>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;
+ }
+ }
+}
Code Review / simantics / platform.git / commitdiff