--- /dev/null
+/*******************************************************************************\r
+ * Copyright (c) 2007, 2010 Association for Decentralized Information Management\r
+ * in Industry THTH ry.\r
+ * All rights reserved. This program and the accompanying materials\r
+ * are made available under the terms of the Eclipse Public License v1.0\r
+ * which accompanies this distribution, and is available at\r
+ * http://www.eclipse.org/legal/epl-v10.html\r
+ *\r
+ * Contributors:\r
+ * VTT Technical Research Centre of Finland - initial API and implementation\r
+ *******************************************************************************/\r
+package org.simantics.utils.datastructures.map;\r
+\r
+import gnu.trove.map.hash.THashMap;\r
+import gnu.trove.set.hash.THashSet;\r
+\r
+import java.util.ArrayList;\r
+import java.util.Collection;\r
+import java.util.Collections;\r
+\r
+/**\r
+ * Associative map of n-tuples. Tuple is the primitive of this data structure.\r
+ * It describes an association between objects.\r
+ * The number of fields in each tuple must match the level of associativity.\r
+ * <P>\r
+ * Associative map allows quick queries of tuples by pre-indexing its content.\r
+ * Indexing requires that the object is told ahead which combinations of fields\r
+ * to cache. Each combination is described with {@link Associativity} object\r
+ * at construction, and for each description a new hashmap is created.\r
+ * \r
+ * Example, fully associative map for 4-tuples, use\r
+ * \r
+ * AssociativeMap map = new AssociativeMap( Associativity.fullAssociativity( 4 ) );\r
+ * map.addStatements( new Tuple( cluster, subject, predicate, object ) );\r
+ * \r
+ * Example, BijectionMap\r
+ * \r
+ * AssociativeMap bijectionMap =\r
+ * new AssociativeMap( new Associativity(false, true), new Associativity(true, false) )\r
+ * \r
+ * bijectionMap.addStatements( new Tuple("x", "y") );\r
+ * <P>\r
+ * Queries are described with {@link Tuple}-instances. null value describes\r
+ * open ended value and actual object restriction.\r
+ * \r
+ * Example, query for all Tuples with "x" as the first argument:\r
+ * \r
+ * bijectionMap.getStatements(new Tuple("x", null), null);;\r
+ * \r
+ * @see Associativity\r
+ * @see Tuple\r
+ * @author Toni Kalajainen <toni.kalajainen@vtt.fi>\r
+ */\r
+public class AssociativeMap {\r
+\r
+ /** Number of dimensions */\r
+ int level;\r
+ /** Maps sorted by TupleQueryAssociativity, TupleQuery, Tuples */\r
+ THashMap<Tuple, THashSet<Tuple>> [] maps;\r
+ /** Tuple query for all statements */\r
+ Tuple tupleQueryAllTuples;\r
+ /** Associativities */\r
+ Associativity[] associativities;\r
+\r
+ /**\r
+ * Create partially associative map of n-tuples.\r
+ * \r
+ * @param associativenesses\r
+ */\r
+ @SuppressWarnings("unchecked")\r
+ public AssociativeMap(Associativity ... associativenesses)\r
+ {\r
+ if (associativenesses==null) throw new NullPointerException();\r
+ if (associativenesses.length==0) throw new IllegalArgumentException();\r
+ this.associativities = associativenesses;\r
+ level = associativenesses[0].getLevel();\r
+ for (int i=1; i<associativenesses.length; i++)\r
+ if (associativenesses[i].getLevel()!=level)\r
+ throw new IllegalArgumentException("Levels are different");\r
+\r
+ int count = (1 << level)-1;\r
+ maps = new THashMap[count];\r
+ for (Associativity a : associativenesses)\r
+ {\r
+ int associativity = a.dimensionAssociativity;\r
+ // omit last and replaces with the first\r
+ if (associativity == count) associativity = 0;\r
+ if (maps[associativity]!=null) continue;\r
+ THashMap<Tuple, THashSet<Tuple>> map = new THashMap<Tuple, THashSet<Tuple>>();\r
+ maps[associativity] = map;\r
+ }\r
+ tupleQueryAllTuples = new Tuple(new Object[level]);\r
+ }\r
+\r
+ public void add(Collection<Tuple> stms)\r
+ {\r
+ for (int associativity=0; associativity<maps.length; associativity++) {\r
+ THashMap<Tuple, THashSet<Tuple>> map = maps[associativity];\r
+ if (map==null) continue;\r
+ for (Tuple stm : stms) {\r
+ if (!stm.isFull()) throw new IllegalArgumentException("Tuple Query cannot be added.");\r
+ Tuple tupleQuery = createTupleQuery(stm, associativity);\r
+ THashSet<Tuple> set = map.get(tupleQuery);\r
+ if (set==null) map.put(tupleQuery, set = new THashSet<Tuple>());\r
+ set.add(stm);\r
+ }\r
+ }\r
+ }\r
+\r
+ public void add(Tuple...stms)\r
+ {\r
+ for (int associativity=0; associativity<maps.length; associativity++) {\r
+ THashMap<Tuple, THashSet<Tuple>> map = maps[associativity];\r
+ if (map==null) continue;\r
+ for (Tuple stm : stms) {\r
+ if (!stm.isFull()) throw new IllegalArgumentException("Tuple Query cannot be added.");\r
+ Tuple tupleQuery = createTupleQuery(stm, associativity);\r
+ THashSet<Tuple> set = map.get(tupleQuery);\r
+ if (set==null) map.put(tupleQuery, set = new THashSet<Tuple>());\r
+ set.add(stm);\r
+ }\r
+ }\r
+ }\r
+\r
+ public void remove(Collection<Tuple> stms) {\r
+ for (int associativity=0; associativity<maps.length; associativity++) {\r
+ THashMap<Tuple, THashSet<Tuple>> map = maps[associativity];\r
+ if (map==null) continue;\r
+ for (Tuple stm : stms) {\r
+ Tuple tupleQuery = createTupleQuery(stm, associativity);\r
+ THashSet<Tuple> set = map.get(tupleQuery);\r
+ if (set==null) continue;\r
+ set.remove(stm);\r
+ }\r
+ }\r
+ }\r
+\r
+ public Collection<Tuple> get(Tuple tupleQuery, Collection<Tuple> result)\r
+ throws UnsupportedOperationException\r
+ {\r
+ if (tupleQuery ==null || tupleQuery.getLevel() != level) throw new IllegalArgumentException();\r
+\r
+ /** Special case, query for existance of a specific tuple */\r
+ if (tupleQuery.associativity == maps.length) {\r
+ THashMap<Tuple, THashSet<Tuple>> map = maps[0];\r
+ if (map==null) throw new UnsupportedOperationException();\r
+ THashSet<Tuple> set = map.get(tupleQueryAllTuples);\r
+ if (result == null) {\r
+ if (set!=null && set.contains(tupleQuery))\r
+ return Collections.singleton(tupleQuery);\r
+ else\r
+ return Collections.emptySet();\r
+ } else {\r
+ if (set.contains(tupleQuery))\r
+ result.add(tupleQuery);\r
+ return result;\r
+ }\r
+ }\r
+\r
+ THashMap<Tuple, THashSet<Tuple>> map = maps[tupleQuery.associativity];\r
+ if (map==null) throw new UnsupportedOperationException();\r
+ THashSet<Tuple> set = map.get(tupleQuery);\r
+ if (set==null) return Collections.emptySet();\r
+ if (result == null) result = new ArrayList<Tuple>(set.size());\r
+ for (Tuple t : set)\r
+ result.add(t);\r
+ return result;\r
+ }\r
+\r
+ public Associativity[] getAssociativities() {\r
+ return associativities;\r
+ }\r
+\r
+ private static Tuple createTupleQuery(Tuple tuple, int associativity)\r
+ {\r
+ if (tuple.associativity == associativity) return tuple;\r
+ int mask = 1;\r
+ int level = tuple.getLevel();\r
+ Object fields[] = new Object[level];\r
+ for (int i=0; i<level; i++)\r
+ {\r
+ if ((associativity & mask)>0)\r
+ fields[i] = tuple.getField(i);\r
+ mask <<= 1;\r
+ }\r
+ return new Tuple(fields);\r
+ }\r
+\r
+ public int getLevel() {\r
+ return level;\r
+ }\r
+\r
+}\r
+\r
Code Review / simantics / platform.git / blobdiff