bundles/org.simantics.db.common/src/org/simantics/db/common/recursive/CachedRecursiveSearch.java

   1 package org.simantics.db.common.recursive;
   2
   3 import java.util.ArrayList;
   4 import java.util.Collection;
   5
   6 import org.simantics.db.Resource;
   7 import org.simantics.db.exception.DatabaseException;
   8
   9 import gnu.trove.impl.Constants;
  10 import gnu.trove.map.hash.THashMap;
  11 import gnu.trove.map.hash.TObjectIntHashMap;
  12
  13 /**
  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.
  17  *
  18  * <p>The function {@link #combineNotNull} is assumed to be a semilattice
  19  * operation, i.e., the following laws must hold:
  20  * <pre>
  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
  24  * </pre>
  25  *
  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:
  29  * <pre>
  30  *  public T get(Resource resource) throws DatabaseException {
  31  *      if(resultMap.contains(resource))
  32  *          return resultMap.get(resource);
  33  *
  34  *      T result = getSourceValue(resource);
  35  *      if(result == null)
  36  *          for(Resource child : children(resource))
  37  *              result = combine(result, get(child));
  38  *      resultMap.put(resource, result);
  39  *      return result;
  40  *  }
  41  * </pre>
  42  */
  43 public abstract class CachedRecursiveSearch<T> {
  44     /**
  45      * Returns the source value associated with the given resource or {@code null},
  46      * if the resource does not have a source value.
  47      */
  48     protected abstract T getSourceValue(Resource resource) throws DatabaseException;
  49
  50     /**
  51      * Returns the children of the given resource.
  52      */
  53     protected abstract Collection<Resource> children(Resource parent) throws DatabaseException;
  54
  55     /**
  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:
  58      * <pre>
  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
  62      * </pre>
  63      */
  64     protected abstract T combineNotNull(T a, T b) throws DatabaseException;
  65
  66     /**
  67      * Combines the values and also checks if either of them is null or
  68      * if the values are equal.
  69      */
  70     protected T combine(T a, T b) throws DatabaseException {
  71         if(a == null)
  72             return b;
  73         else if(b == null || a == b)
  74             return a;
  75         else
  76             return combineNotNull(a, b);
  77     }
  78
  79     /**
  80      * Contains the cached results
  81      */
  82     private final THashMap<Resource, T> resultMap = new THashMap<Resource, T>();
  83
  84     /**
  85      * <p>Returns the combination of all source values reachable from the given resource.
  86      * Returns {@code null}, if no source value is reachable.
  87      *
  88      * <p>The method is not thread safe.
  89      */
  90     public T get(Resource resource) throws DatabaseException {
  91         if(resultMap.contains(resource))
  92             return resultMap.get(resource);
  93         else {
  94             curIndex = 0;
  95             calc(resource);
  96             return previousResult;
  97         }
  98     }
  99
 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);
 103
 104     private int curIndex;
 105     private final ArrayList<Resource> stack = new ArrayList<Resource>();
 106
 107     /**
 108      * This field is used to return the result from the {@code calc}
 109      */
 110     private T previousResult;
 111
 112     /**
 113      * <p>Calculates the result for the given resource and stores it into {@code resultMap}.
 114      *
 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
 121      * it encountered.
 122      */
 123     private int calc(Resource resource) throws DatabaseException {
 124         // Check first if the resource has a source value
 125         T result = getSourceValue(resource);
 126         if(result != null) {
 127             resultMap.put(resource, result);
 128             previousResult = result;
 129             return NO_VALUE;
 130         }
 131
 132         // Choose an index and put it into indexMpa
 133         int index = curIndex++;
 134         indexMap.put(resource, index);
 135         stack.add(resource);
 136
 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
 140         // component.
 141         int lowindex = index;
 142
 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));
 147             }
 148             else {
 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)
 154                         continue;
 155                 }
 156                 lowindex = Math.min(lowindex, childIndex);
 157             }
 158         }
 159
 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.
 163             Resource r;
 164             do {
 165                 r = stack.remove(stack.size()-1);
 166                 indexMap.remove(r);
 167                 resultMap.put(r, result);
 168             } while(r != resource);
 169             previousResult = result;
 170             return NO_VALUE;
 171         }
 172         else {
 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;
 177             return lowindex;
 178         }
 179     }
 180 }