-/*******************************************************************************\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
+/*******************************************************************************
+ * 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;
+ }
+
+}
+