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