Robust/src/Util/MultiViewMap.java

   1 ///////////////////////////////////////////////////////////\r
   2 //\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
   6 //\r
   7 //  Ex:\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
  12 //\r
  13 ///////////////////////////////////////////////////////////\r
  14 package Util;\r
  15 \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
  22 \r
  23 \r
  24 public class MultiViewMap<T> {\r
  25 \r
  26   private Class[]        keyTypes;\r
  27   private Vector<BitSet> partialViews;\r
  28   private BitSet         fullView;\r
  29 \r
  30   private JoinOp<T> joinOp;\r
  31 \r
  32   private boolean checkTypes;\r
  33   private boolean checkConsistency;\r
  34 \r
  35   //  If the entire contents of this map are fullKey -> value:\r
  36   //    <a,b> -> 1\r
  37   //    <c,b> -> 2\r
  38   //    <d,e> -> 3\r
  39   private Map<MultiKey, T> fullKey2value;\r
  40 \r
  41   //  ...then this structure captures the partial views:\r
  42   //     view[1, 0] ->\r
  43   //       <a,*> -> {<a,b>}\r
  44   //       <c,*> -> {<c,b>}\r
  45   //       <d,*> -> {<d,e>}\r
  46   //     view[0, 1] ->\r
  47   //       <*,b> -> {<a,b>, <c,b>}\r
  48   //       <*,e> -> {<d,e>}\r
  49   private Map<BitSet, Map<MultiKey, Set<MultiKey>>>\r
  50     view2partialKey2fullKeys;\r
  51 \r
  52 \r
  53   //  NOTE!  Use MultiViewMapBuilder to get an\r
  54   //  instantiation of this class.\r
  55   protected MultiViewMap( Class[]        keyTypes,\r
  56                           JoinOp<T>      joinOp,\r
  57                           BitSet         fullView,\r
  58                           Vector<BitSet> partialViews,\r
  59                           boolean        checkTypes,\r
  60                           boolean        checkConsistency ) {\r
  61 \r
  62     this.keyTypes         = keyTypes;\r
  63     this.joinOp           = joinOp;\r
  64     this.partialViews     = partialViews;\r
  65     this.fullView         = fullView;\r
  66     this.checkTypes       = checkTypes;\r
  67     this.checkConsistency = checkConsistency;\r
  68 \r
  69     fullKey2value = new HashMap<MultiKey, T>();\r
  70 \r
  71     view2partialKey2fullKeys = \r
  72       new HashMap<BitSet, Map<MultiKey, Set<MultiKey>>>(); \r
  73   }\r
  74 \r
  75 \r
  76   public int size() {\r
  77     return fullKey2value.size();\r
  78   }\r
  79 \r
  80   public boolean equals( Object o ) {\r
  81     if( this == o ) {\r
  82       return true;\r
  83     }\r
  84     if( o == null ) {\r
  85       return false;\r
  86     }\r
  87     if( !(o instanceof MultiViewMap) ) {\r
  88       return false;\r
  89     }\r
  90     MultiViewMap that = (MultiViewMap) o;\r
  91 \r
  92     // check whether key types and views match\r
  93     if( !this.isHomogenous( that ) ) {\r
  94       return false;\r
  95     }\r
  96     \r
  97     // check contents\r
  98     return fullKey2value.equals( that.fullKey2value ) &&\r
  99       view2partialKey2fullKeys.equals( that.view2partialKey2fullKeys );\r
 100   }\r
 101 \r
 102   public int hashCode() {\r
 103     int hash = 1;\r
 104     hash = hash*31 + keyTypes.hashCode();\r
 105     hash = hash*31 + joinOp.hashCode();\r
 106     hash = hash*31 + fullView.hashCode();\r
 107     hash = hash*31 + partialViews.hashCode();\r
 108     hash = hash*31 + fullKey2value.hashCode();\r
 109     hash = hash*31 + view2partialKey2fullKeys.hashCode();\r
 110     return hash;\r
 111   }\r
 112 \r
 113 \r
 114  \r
 115   public void put( MultiKey fullKey, T value ) {\r
 116     assert( typesMatch( fullKey ) );\r
 117 \r
 118     fullKey2value.put( fullKey, value );\r
 119 \r
 120     for( BitSet view : partialViews ) {\r
 121       MultiKey partialKey = makePartialKey( view, fullKey );\r
 122       getFullKeys( view, partialKey ).add( fullKey );\r
 123     }\r
 124 \r
 125     assert( isConsistent() );\r
 126   }\r
 127 \r
 128 \r
 129   public Map<MultiKey, T> get( final BitSet view, MultiKey partialKey ) {\r
 130     checkView( view );\r
 131 \r
 132     Map<MultiKey, T> fullKey2valueBYVIEW = new HashMap<MultiKey, T>();\r
 133 \r
 134     Set<MultiKey> fullKeys = getFullKeys( view, partialKey );\r
 135     for( MultiKey fullKey : fullKeys ) {\r
 136       fullKey2valueBYVIEW.put( fullKey, \r
 137                                fullKey2value.get( fullKey ) );\r
 138     }\r
 139 \r
 140     return fullKey2valueBYVIEW;\r
 141   }\r
 142 \r
 143  \r
 144   public void remove( final BitSet viewForRemove, MultiKey fullOrPartialKey ) {    \r
 145     checkView( viewForRemove );\r
 146 \r
 147     Set<MultiKey> fullKeysToRemove = new HashSet<MultiKey>();\r
 148     \r
 149     if( viewForRemove.equals( fullView ) ) {\r
 150       fullKeysToRemove.add( fullOrPartialKey );\r
 151     } else {\r
 152       fullKeysToRemove.addAll( getFullKeys( viewForRemove, fullOrPartialKey ) );\r
 153     }\r
 154 \r
 155     for( MultiKey fullKeyToRemove : fullKeysToRemove ) {\r
 156       for( BitSet view : partialViews ) {\r
 157         MultiKey partialKey = makePartialKey( view, fullKeyToRemove );\r
 158         getFullKeys( view, partialKey ).remove( fullKeyToRemove );\r
 159       }\r
 160       fullKey2value.remove( fullKeyToRemove );\r
 161     }\r
 162 \r
 163     assert( isConsistent() );\r
 164   }\r
 165   \r
 166 \r
 167   public void merge( MultiViewMap<T> in ) {\r
 168     assert( isHomogenous( in ) );\r
 169 \r
 170     Set<MultiKey> mergedFullKeys = new HashSet<MultiKey>();\r
 171     mergedFullKeys.addAll( this.fullKey2value.keySet() );\r
 172     mergedFullKeys.addAll( in.fullKey2value.keySet() );\r
 173 \r
 174     for( MultiKey fullKey : mergedFullKeys ) { \r
 175       fullKey2value.put( fullKey, \r
 176                          joinOp.join( this.fullKey2value.get( fullKey ), \r
 177                                       in.fullKey2value.get( fullKey )\r
 178                                       ) );\r
 179     }\r
 180 \r
 181     for( MultiKey fullKey : in.fullKey2value.keySet() ) { \r
 182       for( BitSet view : partialViews ) {\r
 183         MultiKey partialKey = makePartialKey( view, fullKey );\r
 184         getFullKeys( view, partialKey ).add( fullKey );\r
 185       }\r
 186     }\r
 187 \r
 188     assert( isConsistent() );\r
 189   }\r
 190 \r
 191 \r
 192   private \r
 193     Set<MultiKey> getFullKeys( BitSet   view,\r
 194                                MultiKey partialKey ) {\r
 195 \r
 196     Map<MultiKey, Set<MultiKey>> partialKey2fullKeys =\r
 197       getPartialKey2fullKeys( view );\r
 198     return getFullKeys( partialKey2fullKeys, partialKey );\r
 199   }\r
 200 \r
 201 \r
 202   private \r
 203     Map<MultiKey, Set<MultiKey>> getPartialKey2fullKeys( BitSet view ) {\r
 204 \r
 205     Map<MultiKey, Set<MultiKey>> partialKey2fullKeys =\r
 206       view2partialKey2fullKeys.get( view );\r
 207     if( partialKey2fullKeys == null ) {\r
 208       partialKey2fullKeys = new HashMap<MultiKey, Set<MultiKey>>();\r
 209       view2partialKey2fullKeys.put( view, partialKey2fullKeys );\r
 210     }\r
 211     return partialKey2fullKeys;\r
 212   }\r
 213 \r
 214 \r
 215   private \r
 216     Set<MultiKey> getFullKeys( Map<MultiKey, Set<MultiKey>> partialKey2fullKeys,\r
 217                                MultiKey                     partialKey ) {\r
 218     \r
 219     Set<MultiKey> fullKeys = partialKey2fullKeys.get( partialKey );\r
 220     if( fullKeys == null ) {\r
 221       fullKeys = new HashSet<MultiKey>();\r
 222       partialKey2fullKeys.put( partialKey, fullKeys );\r
 223     }    \r
 224     return fullKeys;\r
 225   }\r
 226 \r
 227 \r
 228   private MultiKey makePartialKey( BitSet view, MultiKey fullKey ) {\r
 229     Object[] partialKeys = new Object[view.cardinality()];\r
 230     int j = 0;\r
 231     for( int i = 0; i < view.size(); ++i ) {\r
 232       if( view.get( i ) ) {\r
 233         partialKeys[j] = fullKey.get( i );\r
 234         ++j;\r
 235       }\r
 236     }\r
 237     assert( j == view.cardinality() );\r
 238     return new MultiKey( partialKeys );\r
 239   }\r
 240 \r
 241 \r
 242   private void checkView( BitSet view ) {\r
 243     if( view != fullView &&\r
 244         !partialViews.contains( view ) ) {\r
 245       throw new IllegalArgumentException( "This view is not supported." );\r
 246     }\r
 247   }\r
 248 \r
 249 \r
 250   private boolean typesMatch( MultiKey multiKey ) {\r
 251     if( !checkTypes ) {\r
 252       return true;\r
 253     }\r
 254 \r
 255     return multiKey.typesMatch( keyTypes );\r
 256   }\r
 257 \r
 258 \r
 259   private boolean isHomogenous( MultiViewMap in ) {\r
 260     if( this.keyTypes.length != in.keyTypes.length ) {\r
 261       return false;\r
 262     }\r
 263     for( int i = 0; i < this.keyTypes.length; ++i ) {\r
 264       if( !this.keyTypes[i].equals( in.keyTypes[i] ) ) {\r
 265         return false;\r
 266       }\r
 267     }\r
 268     return \r
 269       this.partialViews.equals( in.partialViews ) &&\r
 270       this.fullView.equals( in.fullView ) &&\r
 271       this.joinOp.equals( in.joinOp );\r
 272   }\r
 273 \r
 274 \r
 275   private boolean isConsistent() {\r
 276     if( !checkConsistency ) {\r
 277       return true;\r
 278     }\r
 279 \r
 280     // First, for every full key, make sure it is in every partial key\r
 281     // set it should be in.\r
 282     for( MultiKey fullKey : fullKey2value.keySet() ) {\r
 283       for( BitSet view : partialViews ) {\r
 284         MultiKey partialKey = makePartialKey( view, fullKey );\r
 285         if( !getFullKeys( view, partialKey ).contains( fullKey ) ) {\r
 286           System.out.println( "Expected full key="+fullKey+\r
 287                               " to be in view="+view+\r
 288                               " and partial key="+partialKey+\r
 289                               " but it is missing." );\r
 290           return false;\r
 291         }\r
 292       }\r
 293     }\r
 294 \r
 295     // Second, for each partial key set, make sure every full key is\r
 296     //   a) a match for the partial key it is filed under and\r
 297     //   b) also in the full key->value set\r
 298     for( BitSet view : partialViews ) {\r
 299       Map<MultiKey, Set<MultiKey>> partialKey2fullKeys = getPartialKey2fullKeys( view );\r
 300       for( MultiKey partialKey : partialKey2fullKeys.keySet() ) {\r
 301         Set<MultiKey> fullKeys = partialKey2fullKeys.get( partialKey );\r
 302         for( MultiKey fullKey : fullKeys ) {\r
 303           if( !partialKey.equals( makePartialKey( view, fullKey ) ) ) {\r
 304             System.out.println( "Full key="+fullKey+\r
 305                                 " was filed under view="+view+\r
 306                                 " and partial key="+partialKey+\r
 307                                 " but the (fullKey, view)->partialKey mapping is inconsistent." );\r
 308             return false;\r
 309           }\r
 310           if( !fullKey2value.containsKey( fullKey ) ) {\r
 311             System.out.println( "Full key="+fullKey+\r
 312                                 " was filed under view="+view+\r
 313                                 " and partial key="+partialKey+\r
 314                                 " but the fullKey is not in the fullKey->value map." );\r
 315             return false;\r
 316           }\r
 317         }\r
 318       }\r
 319     }\r
 320 \r
 321     return true;\r
 322   }\r
 323 }\r