--- /dev/null
+///////////////////////////////////////////////////////////\r
+//\r
+// MultiViewMap is like a straight-forward multiple-key\r
+// map except that it supports retrieval and delete by\r
+// subset views of the multikey.\r
+//\r
+// Ex:\r
+// mvm.put(<X, Y, Z>, V);\r
+// mvm.put(<X, W, T>, U);\r
+// print( mvm.get(<*, Y, *>) ); // prints "<X, Y, Z> -> V"\r
+// mvm.remove(<X, *, *>); // removes both entries\r
+//\r
+///////////////////////////////////////////////////////////\r
+package Util;\r
+\r
+import java.util.Set;\r
+import java.util.HashSet;\r
+import java.util.BitSet;\r
+import java.util.Vector;\r
+import java.util.Map;\r
+import java.util.HashMap;\r
+\r
+\r
+public class MultiViewMap<T> {\r
+\r
+ private Class[] keyTypes;\r
+ private Vector<BitSet> partialViews;\r
+ private BitSet fullView;\r
+\r
+ private JoinOp<T> joinOp;\r
+\r
+ private boolean checkTypes;\r
+ private boolean checkConsistency;\r
+\r
+ // If the entire contents of this map are fullKey -> value:\r
+ // <a,b> -> 1\r
+ // <c,b> -> 2\r
+ // <d,e> -> 3\r
+ private Map<MultiKey, T> fullKey2value;\r
+\r
+ // ...then this structure captures the partial views:\r
+ // view[1, 0] ->\r
+ // <a,*> -> {<a,b>}\r
+ // <c,*> -> {<c,b>}\r
+ // <d,*> -> {<d,e>}\r
+ // view[0, 1] ->\r
+ // <*,b> -> {<a,b>, <c,b>}\r
+ // <*,e> -> {<d,e>}\r
+ private Map<BitSet, Map<MultiKey, Set<MultiKey>>>\r
+ view2partialKey2fullKeys;\r
+\r
+\r
+ // NOTE! Use MultiViewMapBuilder to get an\r
+ // instantiation of this class.\r
+ protected MultiViewMap( Class[] keyTypes,\r
+ JoinOp<T> joinOp,\r
+ BitSet fullView,\r
+ Vector<BitSet> partialViews,\r
+ boolean checkTypes,\r
+ boolean checkConsistency ) {\r
+\r
+ this.keyTypes = keyTypes;\r
+ this.joinOp = joinOp;\r
+ this.partialViews = partialViews;\r
+ this.fullView = fullView;\r
+ this.checkTypes = checkTypes;\r
+ this.checkConsistency = checkConsistency;\r
+\r
+ fullKey2value = new HashMap<MultiKey, T>();\r
+\r
+ view2partialKey2fullKeys = \r
+ new HashMap<BitSet, Map<MultiKey, Set<MultiKey>>>(); \r
+ }\r
+\r
+\r
+ public int size() {\r
+ return fullKey2value.size();\r
+ }\r
+\r
+ \r
+ public void put( MultiKey fullKey, T value ) {\r
+ assert( typesMatch( fullKey ) );\r
+\r
+ fullKey2value.put( fullKey, value );\r
+\r
+ for( BitSet view : partialViews ) {\r
+ MultiKey partialKey = makePartialKey( view, fullKey );\r
+ getFullKeys( view, partialKey ).add( fullKey );\r
+ }\r
+\r
+ assert( isConsistent() );\r
+ }\r
+\r
+\r
+ public Map<MultiKey, T> get( final BitSet view, MultiKey partialKey ) {\r
+ checkView( view );\r
+\r
+ Map<MultiKey, T> fullKey2valueBYVIEW = new HashMap<MultiKey, T>();\r
+\r
+ Set<MultiKey> fullKeys = getFullKeys( view, partialKey );\r
+ for( MultiKey fullKey : fullKeys ) {\r
+ fullKey2valueBYVIEW.put( fullKey, \r
+ fullKey2value.get( fullKey ) );\r
+ }\r
+\r
+ return fullKey2valueBYVIEW;\r
+ }\r
+\r
+ \r
+ public void remove( final BitSet viewForRemove, MultiKey fullOrPartialKey ) { \r
+ checkView( viewForRemove );\r
+\r
+ Set<MultiKey> fullKeysToRemove = new HashSet<MultiKey>();\r
+ \r
+ if( viewForRemove.equals( fullView ) ) {\r
+ fullKeysToRemove.add( fullOrPartialKey );\r
+ } else {\r
+ fullKeysToRemove.addAll( getFullKeys( viewForRemove, fullOrPartialKey ) );\r
+ }\r
+\r
+ for( MultiKey fullKeyToRemove : fullKeysToRemove ) {\r
+ for( BitSet view : partialViews ) {\r
+ MultiKey partialKey = makePartialKey( view, fullKeyToRemove );\r
+ getFullKeys( view, partialKey ).remove( fullKeyToRemove );\r
+ }\r
+ fullKey2value.remove( fullKeyToRemove );\r
+ }\r
+\r
+ assert( isConsistent() );\r
+ }\r
+ \r
+\r
+ public void merge( MultiViewMap<T> in ) {\r
+ assert( isHomogenous( in ) );\r
+\r
+ Set<MultiKey> mergedFullKeys = new HashSet<MultiKey>();\r
+ mergedFullKeys.addAll( this.fullKey2value.keySet() );\r
+ mergedFullKeys.addAll( in.fullKey2value.keySet() );\r
+\r
+ for( MultiKey fullKey : mergedFullKeys ) { \r
+ fullKey2value.put( fullKey, \r
+ joinOp.join( this.fullKey2value.get( fullKey ), \r
+ in.fullKey2value.get( fullKey )\r
+ ) );\r
+ }\r
+\r
+ for( MultiKey fullKey : in.fullKey2value.keySet() ) { \r
+ for( BitSet view : partialViews ) {\r
+ MultiKey partialKey = makePartialKey( view, fullKey );\r
+ getFullKeys( view, partialKey ).add( fullKey );\r
+ }\r
+ }\r
+\r
+ assert( isConsistent() );\r
+ }\r
+\r
+\r
+ private \r
+ Set<MultiKey> getFullKeys( BitSet view,\r
+ MultiKey partialKey ) {\r
+\r
+ Map<MultiKey, Set<MultiKey>> partialKey2fullKeys =\r
+ getPartialKey2fullKeys( view );\r
+ return getFullKeys( partialKey2fullKeys, partialKey );\r
+ }\r
+\r
+\r
+ private \r
+ Map<MultiKey, Set<MultiKey>> getPartialKey2fullKeys( BitSet view ) {\r
+\r
+ Map<MultiKey, Set<MultiKey>> partialKey2fullKeys =\r
+ view2partialKey2fullKeys.get( view );\r
+ if( partialKey2fullKeys == null ) {\r
+ partialKey2fullKeys = new HashMap<MultiKey, Set<MultiKey>>();\r
+ view2partialKey2fullKeys.put( view, partialKey2fullKeys );\r
+ }\r
+ return partialKey2fullKeys;\r
+ }\r
+\r
+\r
+ private \r
+ Set<MultiKey> getFullKeys( Map<MultiKey, Set<MultiKey>> partialKey2fullKeys,\r
+ MultiKey partialKey ) {\r
+ \r
+ Set<MultiKey> fullKeys = partialKey2fullKeys.get( partialKey );\r
+ if( fullKeys == null ) {\r
+ fullKeys = new HashSet<MultiKey>();\r
+ partialKey2fullKeys.put( partialKey, fullKeys );\r
+ } \r
+ return fullKeys;\r
+ }\r
+\r
+\r
+ private MultiKey makePartialKey( BitSet view, MultiKey fullKey ) {\r
+ Object[] partialKeys = new Object[view.cardinality()];\r
+ int j = 0;\r
+ for( int i = 0; i < view.size(); ++i ) {\r
+ if( view.get( i ) ) {\r
+ partialKeys[j] = fullKey.get( i );\r
+ ++j;\r
+ }\r
+ }\r
+ assert( j == view.cardinality() );\r
+ return new MultiKey( partialKeys );\r
+ }\r
+\r
+\r
+ private void checkView( BitSet view ) {\r
+ if( view != fullView &&\r
+ !partialViews.contains( view ) ) {\r
+ throw new IllegalArgumentException( "This view is not supported." );\r
+ }\r
+ }\r
+\r
+\r
+ private boolean typesMatch( MultiKey multiKey ) {\r
+ if( !checkTypes ) {\r
+ return true;\r
+ }\r
+\r
+ return multiKey.typesMatch( keyTypes );\r
+ }\r
+\r
+\r
+ private boolean isHomogenous( MultiViewMap in ) {\r
+ if( this.keyTypes.length != in.keyTypes.length ) {\r
+ return false;\r
+ }\r
+ for( int i = 0; i < this.keyTypes.length; ++i ) {\r
+ if( !this.keyTypes[i].equals( in.keyTypes[i] ) ) {\r
+ return false;\r
+ }\r
+ }\r
+ return \r
+ this.partialViews.equals( in.partialViews ) &&\r
+ this.fullView.equals( in.fullView );\r
+ }\r
+\r
+\r
+ private boolean isConsistent() {\r
+ if( !checkConsistency ) {\r
+ return true;\r
+ }\r
+\r
+ // First, for every full key, make sure it is in every partial key\r
+ // set it should be in.\r
+ for( MultiKey fullKey : fullKey2value.keySet() ) {\r
+ for( BitSet view : partialViews ) {\r
+ MultiKey partialKey = makePartialKey( view, fullKey );\r
+ if( !getFullKeys( view, partialKey ).contains( fullKey ) ) {\r
+ System.out.println( "Expected full key="+fullKey+\r
+ " to be in view="+view+\r
+ " and partial key="+partialKey+\r
+ " but it is missing." );\r
+ return false;\r
+ }\r
+ }\r
+ }\r
+\r
+ // Second, for each partial key set, make sure every full key is\r
+ // a) a match for the partial key it is filed under and\r
+ // b) also in the full key->value set\r
+ for( BitSet view : partialViews ) {\r
+ Map<MultiKey, Set<MultiKey>> partialKey2fullKeys = getPartialKey2fullKeys( view );\r
+ for( MultiKey partialKey : partialKey2fullKeys.keySet() ) {\r
+ Set<MultiKey> fullKeys = partialKey2fullKeys.get( partialKey );\r
+ for( MultiKey fullKey : fullKeys ) {\r
+ if( !partialKey.equals( makePartialKey( view, fullKey ) ) ) {\r
+ System.out.println( "Full key="+fullKey+\r
+ " was filed under view="+view+\r
+ " and partial key="+partialKey+\r
+ " but the (fullKey, view)->partialKey mapping is inconsistent." );\r
+ return false;\r
+ }\r
+ if( !fullKey2value.containsKey( fullKey ) ) {\r
+ System.out.println( "Full key="+fullKey+\r
+ " was filed under view="+view+\r
+ " and partial key="+partialKey+\r
+ " but the fullKey is not in the fullKey->value map." );\r
+ return false;\r
+ }\r
+ }\r
+ }\r
+ }\r
+\r
+ return true;\r
+ }\r
+}\r
projects / IRC.git / blobdiff