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
10 * VTT Technical Research Centre of Finland - initial API and implementation
\r
11 *******************************************************************************/
\r
12 package org.simantics.utils.datastructures.map;
\r
14 import gnu.trove.map.hash.THashMap;
\r
15 import gnu.trove.set.hash.THashSet;
\r
17 import java.util.ArrayList;
\r
18 import java.util.Collection;
\r
19 import java.util.Collections;
\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
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
31 * Example, fully associative map for 4-tuples, use
\r
33 * AssociativeMap map = new AssociativeMap( Associativity.fullAssociativity( 4 ) );
\r
34 * map.addStatements( new Tuple( cluster, subject, predicate, object ) );
\r
36 * Example, BijectionMap
\r
38 * AssociativeMap bijectionMap =
\r
39 * new AssociativeMap( new Associativity(false, true), new Associativity(true, false) )
\r
41 * bijectionMap.addStatements( new Tuple("x", "y") );
\r
43 * Queries are described with {@link Tuple}-instances. null value describes
\r
44 * open ended value and actual object restriction.
\r
46 * Example, query for all Tuples with "x" as the first argument:
\r
48 * bijectionMap.getStatements(new Tuple("x", null), null);;
\r
50 * @see Associativity
\r
52 * @author Toni Kalajainen <toni.kalajainen@vtt.fi>
\r
54 public class AssociativeMap {
\r
56 /** Number of dimensions */
\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
66 * Create partially associative map of n-tuples.
\r
68 * @param associativenesses
\r
70 @SuppressWarnings("unchecked")
\r
71 public AssociativeMap(Associativity ... associativenesses)
\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
81 int count = (1 << level)-1;
\r
82 maps = new THashMap[count];
\r
83 for (Associativity a : associativenesses)
\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
92 tupleQueryAllTuples = new Tuple(new Object[level]);
\r
95 public void add(Collection<Tuple> stms)
\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
110 public void add(Tuple...stms)
\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
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
138 public Collection<Tuple> get(Tuple tupleQuery, Collection<Tuple> result)
\r
139 throws UnsupportedOperationException
\r
141 if (tupleQuery ==null || tupleQuery.getLevel() != level) throw new IllegalArgumentException();
\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
152 return Collections.emptySet();
\r
154 if (set.contains(tupleQuery))
\r
155 result.add(tupleQuery);
\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
170 public Associativity[] getAssociativities() {
\r
171 return associativities;
\r
174 private static Tuple createTupleQuery(Tuple tuple, int associativity)
\r
176 if (tuple.associativity == associativity) return tuple;
\r
178 int level = tuple.getLevel();
\r
179 Object fields[] = new Object[level];
\r
180 for (int i=0; i<level; i++)
\r
182 if ((associativity & mask)>0)
\r
183 fields[i] = tuple.getField(i);
\r
186 return new Tuple(fields);
\r
189 public int getLevel() {
\r