bundles/org.simantics.utils.datastructures/src/org/simantics/utils/datastructures/map/AssociativeMap.java

   1 /*******************************************************************************
   2  * Copyright (c) 2007, 2010 Association for Decentralized Information Management
   3  * in Industry THTH ry.
   4  * All rights reserved. This program and the accompanying materials
   5  * are made available under the terms of the Eclipse Public License v1.0
   6  * which accompanies this distribution, and is available at
   7  * http://www.eclipse.org/legal/epl-v10.html
   8  *
   9  * Contributors:
  10  *     VTT Technical Research Centre of Finland - initial API and implementation
  11  *******************************************************************************/
  12 package org.simantics.utils.datastructures.map;
  13
  14 import gnu.trove.map.hash.THashMap;
  15 import gnu.trove.set.hash.THashSet;
  16
  17 import java.util.ArrayList;
  18 import java.util.Collection;
  19 import java.util.Collections;
  20
  21 /**
  22  * Associative map of n-tuples. Tuple is the primitive of this data structure.
  23  * It describes an association between objects.
  24  * The number of fields in each tuple must match the level of associativity.
  25  * <P>
  26  * Associative map allows quick queries of tuples by pre-indexing its content.
  27  * Indexing requires that the object is told ahead which combinations of fields
  28  * to cache. Each combination is described with {@link Associativity} object
  29  * at construction, and for each description a new hashmap is created.
  30  *
  31  * Example, fully associative map for 4-tuples, use
  32  *
  33  *   AssociativeMap map = new AssociativeMap( Associativity.fullAssociativity( 4 ) );
  34  *   map.addStatements( new Tuple( cluster, subject, predicate, object ) );
  35  *
  36  * Example, BijectionMap
  37  *
  38  *   AssociativeMap bijectionMap =
  39  *       new AssociativeMap( new Associativity(false, true), new Associativity(true, false) )
  40  *
  41  *   bijectionMap.addStatements( new Tuple("x", "y") );
  42  * <P>
  43  * Queries are described with {@link Tuple}-instances. null value describes
  44  * open ended value and actual object restriction.
  45  *
  46  * Example, query for all Tuples with "x" as the first argument:
  47  *
  48  *   bijectionMap.getStatements(new Tuple("x", null), null);;
  49  *
  50  * @see Associativity
  51  * @see Tuple
  52  * @author Toni Kalajainen <toni.kalajainen@vtt.fi>
  53  */
  54 public class AssociativeMap {
  55
  56     /** Number of dimensions */
  57     int level;
  58     /** Maps sorted by TupleQueryAssociativity, TupleQuery, Tuples */
  59     THashMap<Tuple, THashSet<Tuple>> [] maps;
  60     /** Tuple query for all statements */
  61     Tuple tupleQueryAllTuples;
  62     /** Associativities */
  63     Associativity[] associativities;
  64
  65     /**
  66      * Create partially associative map of n-tuples.
  67      *
  68      * @param associativenesses
  69      */
  70     @SuppressWarnings("unchecked")
  71     public AssociativeMap(Associativity ... associativenesses)
  72     {
  73         if (associativenesses==null) throw new NullPointerException();
  74         if (associativenesses.length==0) throw new IllegalArgumentException();
  75         this.associativities = associativenesses;
  76         level = associativenesses[0].getLevel();
  77         for (int i=1; i<associativenesses.length; i++)
  78             if (associativenesses[i].getLevel()!=level)
  79                 throw new IllegalArgumentException("Levels are different");
  80
  81         int count = (1 << level)-1;
  82         maps = new THashMap[count];
  83         for (Associativity a : associativenesses)
  84         {
  85             int associativity = a.dimensionAssociativity;
  86             // omit last and replaces with the first
  87             if (associativity == count) associativity = 0;
  88             if (maps[associativity]!=null) continue;
  89             THashMap<Tuple, THashSet<Tuple>> map = new THashMap<Tuple, THashSet<Tuple>>();
  90             maps[associativity] = map;
  91         }
  92         tupleQueryAllTuples = new Tuple(new Object[level]);
  93     }
  94
  95     public void add(Collection<Tuple> stms)
  96     {
  97         for (int associativity=0; associativity<maps.length; associativity++) {
  98             THashMap<Tuple, THashSet<Tuple>> map = maps[associativity];
  99             if (map==null) continue;
 100             for (Tuple stm : stms) {
 101                 if (!stm.isFull()) throw new IllegalArgumentException("Tuple Query cannot be added.");
 102                 Tuple tupleQuery = createTupleQuery(stm, associativity);
 103                 THashSet<Tuple> set = map.get(tupleQuery);
 104                 if (set==null) map.put(tupleQuery, set = new THashSet<Tuple>());
 105                 set.add(stm);
 106             }
 107         }
 108     }
 109
 110     public void add(Tuple...stms)
 111     {
 112         for (int associativity=0; associativity<maps.length; associativity++) {
 113             THashMap<Tuple, THashSet<Tuple>> map = maps[associativity];
 114             if (map==null) continue;
 115             for (Tuple stm : stms) {
 116                 if (!stm.isFull()) throw new IllegalArgumentException("Tuple Query cannot be added.");
 117                 Tuple tupleQuery = createTupleQuery(stm, associativity);
 118                 THashSet<Tuple> set = map.get(tupleQuery);
 119                 if (set==null) map.put(tupleQuery, set = new THashSet<Tuple>());
 120                 set.add(stm);
 121             }
 122         }
 123     }
 124
 125     public void remove(Collection<Tuple> stms) {
 126         for (int associativity=0; associativity<maps.length; associativity++) {
 127             THashMap<Tuple, THashSet<Tuple>> map = maps[associativity];
 128             if (map==null) continue;
 129             for (Tuple stm : stms) {
 130                 Tuple tupleQuery = createTupleQuery(stm, associativity);
 131                 THashSet<Tuple> set = map.get(tupleQuery);
 132                 if (set==null) continue;
 133                 set.remove(stm);
 134             }
 135         }
 136     }
 137
 138     public Collection<Tuple> get(Tuple tupleQuery, Collection<Tuple> result)
 139     throws UnsupportedOperationException
 140     {
 141         if (tupleQuery ==null || tupleQuery.getLevel() != level) throw new IllegalArgumentException();
 142
 143         /** Special case, query for existance of a specific tuple */
 144         if (tupleQuery.associativity == maps.length) {
 145             THashMap<Tuple, THashSet<Tuple>> map = maps[0];
 146             if (map==null) throw new UnsupportedOperationException();
 147             THashSet<Tuple> set = map.get(tupleQueryAllTuples);
 148             if (result == null) {
 149                 if (set!=null && set.contains(tupleQuery))
 150                     return Collections.singleton(tupleQuery);
 151                 else
 152                     return Collections.emptySet();
 153             } else {
 154                 if (set.contains(tupleQuery))
 155                     result.add(tupleQuery);
 156                 return result;
 157             }
 158         }
 159
 160         THashMap<Tuple, THashSet<Tuple>> map = maps[tupleQuery.associativity];
 161         if (map==null) throw new UnsupportedOperationException();
 162         THashSet<Tuple> set = map.get(tupleQuery);
 163         if (set==null) return Collections.emptySet();
 164         if (result == null) result = new ArrayList<Tuple>(set.size());
 165         for (Tuple t : set)
 166             result.add(t);
 167         return result;
 168     }
 169
 170     public Associativity[] getAssociativities() {
 171         return associativities;
 172     }
 173
 174     private static Tuple createTupleQuery(Tuple tuple, int associativity)
 175     {
 176         if (tuple.associativity == associativity) return tuple;
 177         int mask = 1;
 178         int level = tuple.getLevel();
 179         Object fields[] = new Object[level];
 180         for (int i=0; i<level; i++)
 181         {
 182             if ((associativity & mask)>0)
 183                 fields[i] = tuple.getField(i);
 184             mask <<= 1;
 185         }
 186         return new Tuple(fields);
 187     }
 188
 189     public int getLevel() {
 190         return level;
 191     }
 192
 193 }
 194