/*******************************************************************************
 * Copyright (c) 2007, 2010 Association for Decentralized Information Management
 * in Industry THTH ry.
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors:
 *     VTT Technical Research Centre of Finland - initial API and implementation
 *******************************************************************************/
package org.simantics.utils.datastructures.map;

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

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

/**
 * Associative map of n-tuples. Tuple is the primitive of this data structure.
 * It describes an association between objects.
 * The number of fields in each tuple must match the level of associativity.
 * <P>
 * Associative map allows quick queries of tuples by pre-indexing its content.
 * Indexing requires that the object is told ahead which combinations of fields
 * to cache. Each combination is described with {@link Associativity} object
 * at construction, and for each description a new hashmap is created.
 * 
 * Example, fully associative map for 4-tuples, use
 * 
 *   AssociativeMap map = new AssociativeMap( Associativity.fullAssociativity( 4 ) );
 *   map.addStatements( new Tuple( cluster, subject, predicate, object ) );
 * 
 * Example, BijectionMap
 * 
 *   AssociativeMap bijectionMap =
 *       new AssociativeMap( new Associativity(false, true), new Associativity(true, false) )
 * 
 *   bijectionMap.addStatements( new Tuple("x", "y") );
 * <P>
 * Queries are described with {@link Tuple}-instances. null value describes
 * open ended value and actual object restriction.
 * 
 * Example, query for all Tuples with "x" as the first argument:
 * 
 *   bijectionMap.getStatements(new Tuple("x", null), null);;
 * 
 * @see Associativity
 * @see Tuple
 * @author Toni Kalajainen <toni.kalajainen@vtt.fi>
 */
public class AssociativeMap {

    /** Number of dimensions */
    int level;
    /** Maps sorted by TupleQueryAssociativity, TupleQuery, Tuples */
    THashMap<Tuple, THashSet<Tuple>> [] maps;
    /** Tuple query for all statements */
    Tuple tupleQueryAllTuples;
    /** Associativities */
    Associativity[] associativities;

    /**
     * Create partially associative map of n-tuples.
     * 
     * @param associativenesses
     */
    @SuppressWarnings("unchecked")
    public AssociativeMap(Associativity ... associativenesses)
    {
        if (associativenesses==null) throw new NullPointerException();
        if (associativenesses.length==0) throw new IllegalArgumentException();
        this.associativities = associativenesses;
        level = associativenesses[0].getLevel();
        for (int i=1; i<associativenesses.length; i++)
            if (associativenesses[i].getLevel()!=level)
                throw new IllegalArgumentException("Levels are different");

        int count = (1 << level)-1;
        maps = new THashMap[count];
        for (Associativity a : associativenesses)
        {
            int associativity = a.dimensionAssociativity;
            // omit last and replaces with the first
            if (associativity == count) associativity = 0;
            if (maps[associativity]!=null) continue;
            THashMap<Tuple, THashSet<Tuple>> map = new THashMap<Tuple, THashSet<Tuple>>();
            maps[associativity] = map;
        }
        tupleQueryAllTuples = new Tuple(new Object[level]);
    }

    public void add(Collection<Tuple> stms)
    {
        for (int associativity=0; associativity<maps.length; associativity++) {
            THashMap<Tuple, THashSet<Tuple>> map = maps[associativity];
            if (map==null) continue;
            for (Tuple stm : stms) {
                if (!stm.isFull()) throw new IllegalArgumentException("Tuple Query cannot be added.");
                Tuple tupleQuery = createTupleQuery(stm, associativity);
                THashSet<Tuple> set = map.get(tupleQuery);
                if (set==null) map.put(tupleQuery, set = new THashSet<Tuple>());
                set.add(stm);
            }
        }
    }

    public void add(Tuple...stms)
    {
        for (int associativity=0; associativity<maps.length; associativity++) {
            THashMap<Tuple, THashSet<Tuple>> map = maps[associativity];
            if (map==null) continue;
            for (Tuple stm : stms) {
                if (!stm.isFull()) throw new IllegalArgumentException("Tuple Query cannot be added.");
                Tuple tupleQuery = createTupleQuery(stm, associativity);
                THashSet<Tuple> set = map.get(tupleQuery);
                if (set==null) map.put(tupleQuery, set = new THashSet<Tuple>());
                set.add(stm);
            }
        }
    }

    public void remove(Collection<Tuple> stms) {
        for (int associativity=0; associativity<maps.length; associativity++) {
            THashMap<Tuple, THashSet<Tuple>> map = maps[associativity];
            if (map==null) continue;
            for (Tuple stm : stms) {
                Tuple tupleQuery = createTupleQuery(stm, associativity);
                THashSet<Tuple> set = map.get(tupleQuery);
                if (set==null) continue;
                set.remove(stm);
            }
        }
    }

    public Collection<Tuple> get(Tuple tupleQuery, Collection<Tuple> result)
    throws UnsupportedOperationException
    {
        if (tupleQuery ==null || tupleQuery.getLevel() != level) throw new IllegalArgumentException();

        /** Special case, query for existance of a specific tuple */
        if (tupleQuery.associativity == maps.length) {
            THashMap<Tuple, THashSet<Tuple>> map = maps[0];
            if (map==null) throw new UnsupportedOperationException();
            THashSet<Tuple> set = map.get(tupleQueryAllTuples);
            if (result == null) {
                if (set!=null && set.contains(tupleQuery))
                    return Collections.singleton(tupleQuery);
                else
                    return Collections.emptySet();
            } else {
                if (set.contains(tupleQuery))
                    result.add(tupleQuery);
                return result;
            }
        }

        THashMap<Tuple, THashSet<Tuple>> map = maps[tupleQuery.associativity];
        if (map==null) throw new UnsupportedOperationException();
        THashSet<Tuple> set = map.get(tupleQuery);
        if (set==null) return Collections.emptySet();
        if (result == null) result = new ArrayList<Tuple>(set.size());
        for (Tuple t : set)
            result.add(t);
        return result;
    }

    public Associativity[] getAssociativities() {
        return associativities;
    }

    private static Tuple createTupleQuery(Tuple tuple, int associativity)
    {
        if (tuple.associativity == associativity) return tuple;
        int mask = 1;
        int level = tuple.getLevel();
        Object fields[] = new Object[level];
        for (int i=0; i<level; i++)
        {
            if ((associativity & mask)>0)
                fields[i] = tuple.getField(i);
            mask <<= 1;
        }
        return new Tuple(fields);
    }

    public int getLevel() {
        return level;
    }

}