1 package org.simantics.db.common.recursive;
3 import java.util.ArrayList;
4 import java.util.Collection;
6 import org.simantics.db.Resource;
7 import org.simantics.db.exception.DatabaseException;
9 import gnu.trove.impl.Constants;
10 import gnu.trove.map.hash.THashMap;
11 import gnu.trove.map.hash.TObjectIntHashMap;
14 * <p>A utility class that calculates the combination of all source values
15 * given by {@link getSourceValue}
16 * reachable from a given resource by {@link #children} function and caches the results.
18 * <p>The function {@link #combineNotNull} is assumed to be a semilattice
19 * operation, i.e., the following laws must hold:
21 * Commutativity: combineNotNull(a, b) = combineNotNull(b, a)
22 * Associativity: combineNotNull(a, combineNotNull(b, c)) = combineNotNull(combineNotNull(a, b), c)
23 * Idempotency: combineNotNull(a, a) = a
26 * <p>If the graph of the function {link children} is acyclic,
27 * the function {@link get} works equally to the following
28 * simpler implementation:
30 * public T get(Resource resource) throws DatabaseException {
31 * if(resultMap.contains(resource))
32 * return resultMap.get(resource);
34 * T result = getSourceValue(resource);
36 * for(Resource child : children(resource))
37 * result = combine(result, get(child));
38 * resultMap.put(resource, result);
43 public abstract class CachedRecursiveSearch<T> {
45 * Returns the source value associated with the given resource or {@code null},
46 * if the resource does not have a source value.
48 protected abstract T getSourceValue(Resource resource) throws DatabaseException;
51 * Returns the children of the given resource.
53 protected abstract Collection<Resource> children(Resource parent) throws DatabaseException;
56 * Combines the given source values. The function may assume that the values
57 * are not {@code null}. The function must satisfy the following laws:
59 * Commutativity: combineNotNull(a, b) = combineNotNull(b, a)
60 * Associativity: combineNotNull(a, combineNotNull(b, c)) = combineNotNull(combineNotNull(a, b), c)
61 * Idempotency: combineNotNull(a, a) = a
64 protected abstract T combineNotNull(T a, T b) throws DatabaseException;
67 * Combines the values and also checks if either of them is null or
68 * if the values are equal.
70 protected T combine(T a, T b) throws DatabaseException {
73 else if(b == null || a == b)
76 return combineNotNull(a, b);
80 * Contains the cached results
82 private final THashMap<Resource, T> resultMap = new THashMap<Resource, T>();
85 * <p>Returns the combination of all source values reachable from the given resource.
86 * Returns {@code null}, if no source value is reachable.
88 * <p>The method is not thread safe.
90 public T get(Resource resource) throws DatabaseException {
91 if(resultMap.contains(resource))
92 return resultMap.get(resource);
96 return previousResult;
100 private static final int NO_VALUE = -1;
101 private final TObjectIntHashMap<Resource> indexMap =
102 new TObjectIntHashMap<Resource>(Constants.DEFAULT_CAPACITY, Constants.DEFAULT_LOAD_FACTOR, NO_VALUE);
104 private int curIndex;
105 private final ArrayList<Resource> stack = new ArrayList<Resource>();
108 * This field is used to return the result from the {@code calc}
110 private T previousResult;
113 * <p>Calculates the result for the given resource and stores it into {@code resultMap}.
115 * <p>The function is implemented by depth-first search where each node gets increasing
116 * index number. During the calculation of the result for the resource, the index
117 * is stored into {@code indexMap}. This information is used to detect, if the recursive
118 * search has encountered a resource whose calculation has not yet been finished. In this case,
119 * the resource must be a part of a strongly connected component of the graph of
120 * {@code children}. The function returns the lowest index of unfinished calculation
123 private int calc(Resource resource) throws DatabaseException {
124 // Check first if the resource has a source value
125 T result = getSourceValue(resource);
127 resultMap.put(resource, result);
128 previousResult = result;
132 // Choose an index and put it into indexMpa
133 int index = curIndex++;
134 indexMap.put(resource, index);
137 // Variable lowindex maintains the lowest index
138 // reachable from this resource. If it is smaller than
139 // index, the resource is part of a bigger strongly connected
141 int lowindex = index;
143 for(Resource child : children(resource)) {
144 if(resultMap.contains(child)) {
145 // The result for the child has already been calculated
146 result = combine(result, resultMap.get(child));
149 int childIndex = indexMap.get(child);
150 if(childIndex == NO_VALUE) {
151 childIndex = calc(child);
152 result = combine(result, previousResult);
153 if(childIndex == NO_VALUE)
156 lowindex = Math.min(lowindex, childIndex);
160 if(lowindex == index) {
161 // Remove the resources of the strongly connected component from the stack and assign
162 // the result to all these resources.
165 r = stack.remove(stack.size()-1);
167 resultMap.put(r, result);
168 } while(r != resource);
169 previousResult = result;
173 // This resource is a part of a bigger strongly connected component.
174 // Therefore the current result is still partial and will be
175 // combined with the other results in this component.
176 previousResult = result;