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

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