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 dummyValue = 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 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
  86     }\r
  87     return out;\r
  88   }\r
  89 \r
  90 \r
  91   public boolean equals( Object o ) {\r
  92     if( this == o ) {\r
  93       return true;\r
  94     }\r
  95     if( o == null ) {\r
  96       return false;\r
  97     }\r
  98     if( !(o instanceof MultiViewMap) ) {\r
  99       return false;\r
 100     }\r
 101     MultiViewMap that = (MultiViewMap) o;\r
 102 \r
 103     // check whether key types and views match\r
 104     if( !this.isHomogenous( that ) ) {\r
 105       return false;\r
 106     }\r
 107     \r
 108     // check contents\r
 109     return fullKey2value.equals( that.fullKey2value ) &&\r
 110       view2partialKey2fullKeys.equals( that.view2partialKey2fullKeys );\r
 111   }\r
 112 \r
 113   public int hashCode() {\r
 114     int hash = 1;\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
 121     return hash;\r
 122   }\r
 123 \r
 124 \r
 125   public int size() {\r
 126     return fullKey2value.size();\r
 127   }\r
 128 \r
 129 \r
 130   public void clear() {\r
 131     fullKey2value.clear();\r
 132     view2partialKey2fullKeys.clear();\r
 133   }\r
 134 \r
 135  \r
 136   public void put( MultiKey fullKey, T value ) {\r
 137     assert( typesMatch( fullKey ) );\r
 138 \r
 139     fullKey2value.put( fullKey, value );\r
 140 \r
 141     for( BitSet view : partialViews ) {\r
 142       MultiKey partialKey = makePartialKey( view, fullKey );\r
 143       getFullKeys( view, partialKey ).add( fullKey );\r
 144     }\r
 145 \r
 146     assert( isConsistent() );\r
 147   }\r
 148 \r
 149 \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
 154   }\r
 155 \r
 156 \r
 157   public Map<MultiKey, T> get( final BitSet view, MultiKey partialKey ) {\r
 158     checkView( view );\r
 159 \r
 160     Map<MultiKey, T> fullKey2valueBYVIEW = new HashMap<MultiKey, T>();\r
 161 \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
 166     }\r
 167 \r
 168     return fullKey2valueBYVIEW;\r
 169   }\r
 170 \r
 171  \r
 172   public void remove( final BitSet viewForRemove, MultiKey fullOrPartialKey ) {    \r
 173     checkView( viewForRemove );\r
 174 \r
 175     Set<MultiKey> fullKeysToRemove = new HashSet<MultiKey>();\r
 176     \r
 177     if( viewForRemove.equals( fullView ) ) {\r
 178       fullKeysToRemove.add( fullOrPartialKey );\r
 179     } else {\r
 180       fullKeysToRemove.addAll( getFullKeys( viewForRemove, fullOrPartialKey ) );\r
 181     }\r
 182 \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
 187       }\r
 188       fullKey2value.remove( fullKeyToRemove );\r
 189     }\r
 190 \r
 191     assert( isConsistent() );\r
 192   }\r
 193   \r
 194 \r
 195   public void merge( MultiViewMap<T> in ) {\r
 196     assert( isHomogenous( in ) );\r
 197 \r
 198     Set<MultiKey> mergedFullKeys = new HashSet<MultiKey>();\r
 199     mergedFullKeys.addAll( this.fullKey2value.keySet() );\r
 200     mergedFullKeys.addAll( in.fullKey2value.keySet() );\r
 201 \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
 206                                       ) );\r
 207     }\r
 208 \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
 213       }\r
 214     }\r
 215 \r
 216     assert( isConsistent() );\r
 217   }\r
 218 \r
 219 \r
 220   private \r
 221     Set<MultiKey> getFullKeys( BitSet   view,\r
 222                                MultiKey partialKey ) {\r
 223 \r
 224     if( view.equals( fullView ) ) {\r
 225       Set<MultiKey> fullKeys = new HashSet<MultiKey>();\r
 226       if( fullKey2value.containsKey( partialKey ) ) {\r
 227         fullKeys.add( partialKey );\r
 228       }\r
 229       return fullKeys;\r
 230     }\r
 231 \r
 232     Map<MultiKey, Set<MultiKey>> partialKey2fullKeys =\r
 233       getPartialKey2fullKeys( view );\r
 234     return getFullKeys( partialKey2fullKeys, partialKey );\r
 235   }\r
 236 \r
 237 \r
 238   private \r
 239     Map<MultiKey, Set<MultiKey>> getPartialKey2fullKeys( BitSet view ) {\r
 240 \r
 241     Map<MultiKey, Set<MultiKey>> partialKey2fullKeys =\r
 242       view2partialKey2fullKeys.get( view );\r
 243     if( partialKey2fullKeys == null ) {\r
 244       partialKey2fullKeys = new HashMap<MultiKey, Set<MultiKey>>();\r
 245       view2partialKey2fullKeys.put( view, partialKey2fullKeys );\r
 246     }\r
 247     return partialKey2fullKeys;\r
 248   }\r
 249 \r
 250 \r
 251   private \r
 252     Set<MultiKey> getFullKeys( Map<MultiKey, Set<MultiKey>> partialKey2fullKeys,\r
 253                                MultiKey                     partialKey ) {\r
 254     \r
 255     Set<MultiKey> fullKeys = partialKey2fullKeys.get( partialKey );\r
 256     if( fullKeys == null ) {\r
 257       fullKeys = new HashSet<MultiKey>();\r
 258       partialKey2fullKeys.put( partialKey, fullKeys );\r
 259     }    \r
 260     return fullKeys;\r
 261   }\r
 262 \r
 263 \r
 264   private MultiKey makePartialKey( BitSet view, MultiKey fullKey ) {\r
 265     Object[] partialKeys = new Object[view.cardinality()];\r
 266     int j = 0;\r
 267     for( int i = 0; i < view.size(); ++i ) {\r
 268       if( view.get( i ) ) {\r
 269         partialKeys[j] = fullKey.get( i );\r
 270         ++j;\r
 271       }\r
 272     }\r
 273     assert( j == view.cardinality() );\r
 274     return new MultiKey( partialKeys );\r
 275   }\r
 276 \r
 277 \r
 278   private void checkView( BitSet view ) {\r
 279     if( view != fullView &&\r
 280         !partialViews.contains( view ) ) {\r
 281       throw new IllegalArgumentException( "This view is not supported." );\r
 282     }\r
 283   }\r
 284 \r
 285 \r
 286   private boolean typesMatch( MultiKey multiKey ) {\r
 287     if( !checkTypes ) {\r
 288       return true;\r
 289     }\r
 290 \r
 291     return multiKey.typesMatch( keyTypes );\r
 292   }\r
 293 \r
 294 \r
 295   private boolean isHomogenous( MultiViewMap in ) {\r
 296     if( this.keyTypes.length != in.keyTypes.length ) {\r
 297       return false;\r
 298     }\r
 299     for( int i = 0; i < this.keyTypes.length; ++i ) {\r
 300       if( !this.keyTypes[i].equals( in.keyTypes[i] ) ) {\r
 301         return false;\r
 302       }\r
 303     }\r
 304     return \r
 305       this.partialViews.equals( in.partialViews ) &&\r
 306       this.fullView.equals( in.fullView ) &&\r
 307       this.joinOp.equals( in.joinOp );\r
 308   }\r
 309 \r
 310 \r
 311   private boolean isConsistent() {\r
 312     if( !checkConsistency ) {\r
 313       return true;\r
 314     }\r
 315 \r
 316     // First, for every full key, make sure it is in every partial key\r
 317     // set it should be in.\r
 318     for( MultiKey fullKey : fullKey2value.keySet() ) {\r
 319       for( BitSet view : partialViews ) {\r
 320         MultiKey partialKey = makePartialKey( view, fullKey );\r
 321         if( !getFullKeys( view, partialKey ).contains( fullKey ) ) {\r
 322           System.out.println( "Expected full key="+fullKey+\r
 323                               " to be in view="+view+\r
 324                               " and partial key="+partialKey+\r
 325                               " but it is missing." );\r
 326           return false;\r
 327         }\r
 328       }\r
 329     }\r
 330 \r
 331     // Second, for each partial key set, make sure every full key is\r
 332     //   a) a match for the partial key it is filed under and\r
 333     //   b) also in the full key->value set\r
 334     for( BitSet view : partialViews ) {\r
 335       Map<MultiKey, Set<MultiKey>> partialKey2fullKeys = getPartialKey2fullKeys( view );\r
 336       for( MultiKey partialKey : partialKey2fullKeys.keySet() ) {\r
 337         Set<MultiKey> fullKeys = partialKey2fullKeys.get( partialKey );\r
 338         for( MultiKey fullKey : fullKeys ) {\r
 339           if( !partialKey.equals( makePartialKey( view, fullKey ) ) ) {\r
 340             System.out.println( "Full key="+fullKey+\r
 341                                 " was filed under view="+view+\r
 342                                 " and partial key="+partialKey+\r
 343                                 " but the (fullKey, view)->partialKey mapping is inconsistent." );\r
 344             return false;\r
 345           }\r
 346           if( !fullKey2value.containsKey( fullKey ) ) {\r
 347             System.out.println( "Full key="+fullKey+\r
 348                                 " was filed under view="+view+\r
 349                                 " and partial key="+partialKey+\r
 350                                 " but the fullKey is not in the fullKey->value map." );\r
 351             return false;\r
 352           }\r
 353         }\r
 354       }\r
 355     }\r
 356 \r
 357     return true;\r
 358   }\r
 359 \r
 360   public String toString() {\r
 361     return toString( 0 );\r
 362   }\r
 363 \r
 364   public String toString( int indent ) {\r
 365     StringBuilder s = new StringBuilder();\r
 366     \r
 367     for( MultiKey key : fullKey2value.keySet() ) {\r
 368       for( int i = 0; i < indent; ++i ) {\r
 369         s.append( ' ' );\r
 370       }\r
 371       s.append( key+" -> "+fullKey2value.get( key )+"\n" );\r
 372     }\r
 373     return s.toString();\r
 374   }\r
 375 }\r