A utility class for recursive search in cyclic graph
[simantics/platform.git] / 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 }