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;
        }
    }
}