package org.simantics.db.layer0.util;

import gnu.trove.map.hash.THashMap;
import gnu.trove.set.hash.THashSet;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.List;

import org.simantics.db.ReadGraph;
import org.simantics.db.exception.DatabaseException;

/**
 * <p>HierarchyMultiMap is a multi map whose keys are 
 * partially ordered. When values are asked for a key 
 * all values associated with that key and all its
 * superkeys are returned. The order of the returned values
 * is such that values associated with subelements are 
 * in the list before their superelements.</p>
 *
 * @author Hannu Niemist&ouml;
 */
public abstract class HierarchyMultiMap<A,B> {
    THashMap<A, List<B>> map = new THashMap<A, List<B>>();
    THashMap<A, List<B>> cache;

    /**
     * Associates the value {@code b} with the key {@code a}.
     */
    public synchronized void put(A a, B b) {
        List<B> bs = map.get(a);
        if(bs == null) {
            bs = new ArrayList<B>(2);
            map.put(a, bs);
        }
        bs.add(b);
        cache = null;
    }
    
    /**
     * Gets the values stored into the map for the key {@code a} or
     * its superelements.
     */
    public synchronized List<B> get(ReadGraph g, A a) throws DatabaseException {
        if(cache == null)
            cache = new THashMap<A, List<B>>();
            
        List<B> bs = cache.get(a);
        if(bs == null) {
            List<B> base = map.get(a);
            Collection<A> supers = getImmediateSuperelements(g, a);
            
            if(base == null) {
                if(supers.isEmpty())
                    bs = Collections.emptyList();
                else if(supers.size() == 1)
                    bs = get(g, supers.iterator().next());
                else {
                    THashSet<B> temp = new THashSet<B>();
                    for(A s : supers)
                        temp.addAll(get(g, s));
                    bs = new ArrayList<B>(temp);
                    sort(bs);
                }
            }
            else {
                if(supers.isEmpty()) {
                    bs = base;
                    sort(bs);
                }
                else {
                    bs = new ArrayList<B>(base);
                    // Filter is used to remove duplicates from the result
                    THashSet<B> filter = new THashSet<B>(base);
                    for(A s : supers) 
                        for(B b : get(g, s))
                            if(filter.add(b))
                                bs.add(b);                    
                    
                    // Do not store duplicate of the base unnecessarily
                    if(bs.size() == base.size())
                        bs = base;
                    sort(bs);
                }
            }
            cache.put(a, bs);
        }
        return bs;
    }
    
    /**
     * Returns the immediate superelements of {@code a}.
     * @throws DatabaseException 
     */
    protected abstract Collection<A> getImmediateSuperelements(ReadGraph g, A a) throws DatabaseException;
    
    protected void sort(List<B> values) {
    }
}