1 ///////////////////////////////////////////////////////////
\r
3 // MultiViewMap is like a straight-forward multiple-key
\r
4 // map except that it supports retrieval and delete by
\r
5 // subset views of the multikey.
\r
8 // mvm.put(<X, Y, Z>, V);
\r
9 // mvm.put(<X, W, T>, U);
\r
10 // print( mvm.get(<*, Y, *>) ); // prints "<X, Y, Z> -> V"
\r
11 // mvm.remove(<X, *, *>); // removes both entries
\r
13 ///////////////////////////////////////////////////////////
\r
16 import java.util.Set;
\r
17 import java.util.HashSet;
\r
18 import java.util.BitSet;
\r
19 import java.util.Vector;
\r
20 import java.util.Map;
\r
21 import java.util.HashMap;
\r
24 public class MultiViewMap<T> {
\r
26 private Class[] keyTypes;
\r
27 private Vector<BitSet> partialViews;
\r
28 private BitSet fullView;
\r
30 private JoinOp<T> joinOp;
\r
32 private boolean checkTypes;
\r
33 private boolean checkConsistency;
\r
36 // for MultiViewMaps that don't need to use the value,
\r
37 // template on type Object and map every key to this dummy
\r
38 public static Object dummyValue = new Integer( -12345 );
\r
41 // If the entire contents of this map are fullKey -> value:
\r
45 private Map<MultiKey, T> fullKey2value;
\r
47 // ...then this structure captures the partial views:
\r
53 // <*,b> -> {<a,b>, <c,b>}
\r
55 private Map<BitSet, Map<MultiKey, Set<MultiKey>>>
\r
56 view2partialKey2fullKeys;
\r
59 // NOTE! Use MultiViewMapBuilder to get an
\r
60 // instantiation of this class.
\r
61 protected MultiViewMap( Class[] keyTypes,
\r
64 Vector<BitSet> partialViews,
\r
66 boolean checkConsistency ) {
\r
68 this.keyTypes = keyTypes;
\r
69 this.joinOp = joinOp;
\r
70 this.partialViews = partialViews;
\r
71 this.fullView = fullView;
\r
72 this.checkTypes = checkTypes;
\r
73 this.checkConsistency = checkConsistency;
\r
75 fullKey2value = new HashMap<MultiKey, T>();
\r
77 view2partialKey2fullKeys =
\r
78 new HashMap<BitSet, Map<MultiKey, Set<MultiKey>>>();
\r
82 public MultiViewMap<T> clone( MultiViewMapBuilder<T> builder ) {
\r
83 MultiViewMap<T> out = builder.build();
\r
84 for( Map.Entry<MultiKey, T> entry : this.get().entrySet() ) {
\r
85 out.put( entry.getKey(), entry.getValue() );
\r
91 public boolean equals( Object o ) {
\r
98 if( !(o instanceof MultiViewMap) ) {
\r
101 MultiViewMap that = (MultiViewMap) o;
\r
103 // check whether key types and views match
\r
104 if( !this.isHomogenous( that ) ) {
\r
109 return fullKey2value.equals( that.fullKey2value ) &&
\r
110 view2partialKey2fullKeys.equals( that.view2partialKey2fullKeys );
\r
113 public int hashCode() {
\r
115 hash = hash*31 + keyTypes.hashCode();
\r
116 hash = hash*31 + joinOp.hashCode();
\r
117 hash = hash*31 + fullView.hashCode();
\r
118 hash = hash*31 + partialViews.hashCode();
\r
119 hash = hash*31 + fullKey2value.hashCode();
\r
120 hash = hash*31 + view2partialKey2fullKeys.hashCode();
\r
125 public int size() {
\r
126 return fullKey2value.size();
\r
130 public void clear() {
\r
131 fullKey2value.clear();
\r
132 view2partialKey2fullKeys.clear();
\r
136 public void put( MultiKey fullKey, T value ) {
\r
137 assert( typesMatch( fullKey ) );
\r
139 fullKey2value.put( fullKey, value );
\r
141 for( BitSet view : partialViews ) {
\r
142 MultiKey partialKey = makePartialKey( view, fullKey );
\r
143 getFullKeys( view, partialKey ).add( fullKey );
\r
146 assert( isConsistent() );
\r
150 public Map<MultiKey, T> get() {
\r
151 Map<MultiKey, T> fullKey2valueALL = new HashMap<MultiKey, T>();
\r
152 fullKey2valueALL.putAll( fullKey2value );
\r
153 return fullKey2valueALL;
\r
157 public Map<MultiKey, T> get( final BitSet view, MultiKey partialKey ) {
\r
160 Map<MultiKey, T> fullKey2valueBYVIEW = new HashMap<MultiKey, T>();
\r
162 Set<MultiKey> fullKeys = getFullKeys( view, partialKey );
\r
163 for( MultiKey fullKey : fullKeys ) {
\r
164 fullKey2valueBYVIEW.put( fullKey,
\r
165 fullKey2value.get( fullKey ) );
\r
168 return fullKey2valueBYVIEW;
\r
172 public void remove( final BitSet viewForRemove, MultiKey fullOrPartialKey ) {
\r
173 checkView( viewForRemove );
\r
175 Set<MultiKey> fullKeysToRemove = new HashSet<MultiKey>();
\r
177 if( viewForRemove.equals( fullView ) ) {
\r
178 fullKeysToRemove.add( fullOrPartialKey );
\r
180 fullKeysToRemove.addAll( getFullKeys( viewForRemove, fullOrPartialKey ) );
\r
183 for( MultiKey fullKeyToRemove : fullKeysToRemove ) {
\r
184 for( BitSet view : partialViews ) {
\r
185 MultiKey partialKey = makePartialKey( view, fullKeyToRemove );
\r
186 getFullKeys( view, partialKey ).remove( fullKeyToRemove );
\r
188 fullKey2value.remove( fullKeyToRemove );
\r
191 assert( isConsistent() );
\r
195 public void merge( MultiViewMap<T> in ) {
\r
196 assert( isHomogenous( in ) );
\r
198 Set<MultiKey> mergedFullKeys = new HashSet<MultiKey>();
\r
199 mergedFullKeys.addAll( this.fullKey2value.keySet() );
\r
200 mergedFullKeys.addAll( in.fullKey2value.keySet() );
\r
202 for( MultiKey fullKey : mergedFullKeys ) {
\r
203 fullKey2value.put( fullKey,
\r
204 joinOp.join( this.fullKey2value.get( fullKey ),
\r
205 in.fullKey2value.get( fullKey )
\r
209 for( MultiKey fullKey : in.fullKey2value.keySet() ) {
\r
210 for( BitSet view : partialViews ) {
\r
211 MultiKey partialKey = makePartialKey( view, fullKey );
\r
212 getFullKeys( view, partialKey ).add( fullKey );
\r
216 assert( isConsistent() );
\r
221 Set<MultiKey> getFullKeys( BitSet view,
\r
222 MultiKey partialKey ) {
\r
224 Map<MultiKey, Set<MultiKey>> partialKey2fullKeys =
\r
225 getPartialKey2fullKeys( view );
\r
226 return getFullKeys( partialKey2fullKeys, partialKey );
\r
231 Map<MultiKey, Set<MultiKey>> getPartialKey2fullKeys( BitSet view ) {
\r
233 Map<MultiKey, Set<MultiKey>> partialKey2fullKeys =
\r
234 view2partialKey2fullKeys.get( view );
\r
235 if( partialKey2fullKeys == null ) {
\r
236 partialKey2fullKeys = new HashMap<MultiKey, Set<MultiKey>>();
\r
237 view2partialKey2fullKeys.put( view, partialKey2fullKeys );
\r
239 return partialKey2fullKeys;
\r
244 Set<MultiKey> getFullKeys( Map<MultiKey, Set<MultiKey>> partialKey2fullKeys,
\r
245 MultiKey partialKey ) {
\r
247 Set<MultiKey> fullKeys = partialKey2fullKeys.get( partialKey );
\r
248 if( fullKeys == null ) {
\r
249 fullKeys = new HashSet<MultiKey>();
\r
250 partialKey2fullKeys.put( partialKey, fullKeys );
\r
256 private MultiKey makePartialKey( BitSet view, MultiKey fullKey ) {
\r
257 Object[] partialKeys = new Object[view.cardinality()];
\r
259 for( int i = 0; i < view.size(); ++i ) {
\r
260 if( view.get( i ) ) {
\r
261 partialKeys[j] = fullKey.get( i );
\r
265 assert( j == view.cardinality() );
\r
266 return new MultiKey( partialKeys );
\r
270 private void checkView( BitSet view ) {
\r
271 if( view != fullView &&
\r
272 !partialViews.contains( view ) ) {
\r
273 throw new IllegalArgumentException( "This view is not supported." );
\r
278 private boolean typesMatch( MultiKey multiKey ) {
\r
279 if( !checkTypes ) {
\r
283 return multiKey.typesMatch( keyTypes );
\r
287 private boolean isHomogenous( MultiViewMap in ) {
\r
288 if( this.keyTypes.length != in.keyTypes.length ) {
\r
291 for( int i = 0; i < this.keyTypes.length; ++i ) {
\r
292 if( !this.keyTypes[i].equals( in.keyTypes[i] ) ) {
\r
297 this.partialViews.equals( in.partialViews ) &&
\r
298 this.fullView.equals( in.fullView ) &&
\r
299 this.joinOp.equals( in.joinOp );
\r
303 private boolean isConsistent() {
\r
304 if( !checkConsistency ) {
\r
308 // First, for every full key, make sure it is in every partial key
\r
309 // set it should be in.
\r
310 for( MultiKey fullKey : fullKey2value.keySet() ) {
\r
311 for( BitSet view : partialViews ) {
\r
312 MultiKey partialKey = makePartialKey( view, fullKey );
\r
313 if( !getFullKeys( view, partialKey ).contains( fullKey ) ) {
\r
314 System.out.println( "Expected full key="+fullKey+
\r
315 " to be in view="+view+
\r
316 " and partial key="+partialKey+
\r
317 " but it is missing." );
\r
323 // Second, for each partial key set, make sure every full key is
\r
324 // a) a match for the partial key it is filed under and
\r
325 // b) also in the full key->value set
\r
326 for( BitSet view : partialViews ) {
\r
327 Map<MultiKey, Set<MultiKey>> partialKey2fullKeys = getPartialKey2fullKeys( view );
\r
328 for( MultiKey partialKey : partialKey2fullKeys.keySet() ) {
\r
329 Set<MultiKey> fullKeys = partialKey2fullKeys.get( partialKey );
\r
330 for( MultiKey fullKey : fullKeys ) {
\r
331 if( !partialKey.equals( makePartialKey( view, fullKey ) ) ) {
\r
332 System.out.println( "Full key="+fullKey+
\r
333 " was filed under view="+view+
\r
334 " and partial key="+partialKey+
\r
335 " but the (fullKey, view)->partialKey mapping is inconsistent." );
\r
338 if( !fullKey2value.containsKey( fullKey ) ) {
\r
339 System.out.println( "Full key="+fullKey+
\r
340 " was filed under view="+view+
\r
341 " and partial key="+partialKey+
\r
342 " but the fullKey is not in the fullKey->value map." );
\r
352 public String toString() {
\r
353 return toString( 0 );
\r
356 public String toString( int indent ) {
\r
357 StringBuilder s = new StringBuilder();
\r
359 for( MultiKey key : fullKey2value.keySet() ) {
\r
360 for( int i = 0; i < indent; ++i ) {
\r
363 s.append( key+" -> "+fullKey2value.get( key )+"\n" );
\r
365 return s.toString();
\r