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     Map<MultiKey, Set<MultiKey>> partialKey2fullKeys =\r
 225       getPartialKey2fullKeys( view );\r
 226     return getFullKeys( partialKey2fullKeys, partialKey );\r
 227   }\r
 228 \r
 229 \r
 230   private \r
 231     Map<MultiKey, Set<MultiKey>> getPartialKey2fullKeys( BitSet view ) {\r
 232 \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
 238     }\r
 239     return partialKey2fullKeys;\r
 240   }\r
 241 \r
 242 \r
 243   private \r
 244     Set<MultiKey> getFullKeys( Map<MultiKey, Set<MultiKey>> partialKey2fullKeys,\r
 245                                MultiKey                     partialKey ) {\r
 246     \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
 251     }    \r
 252     return fullKeys;\r
 253   }\r
 254 \r
 255 \r
 256   private MultiKey makePartialKey( BitSet view, MultiKey fullKey ) {\r
 257     Object[] partialKeys = new Object[view.cardinality()];\r
 258     int j = 0;\r
 259     for( int i = 0; i < view.size(); ++i ) {\r
 260       if( view.get( i ) ) {\r
 261         partialKeys[j] = fullKey.get( i );\r
 262         ++j;\r
 263       }\r
 264     }\r
 265     assert( j == view.cardinality() );\r
 266     return new MultiKey( partialKeys );\r
 267   }\r
 268 \r
 269 \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
 274     }\r
 275   }\r
 276 \r
 277 \r
 278   private boolean typesMatch( MultiKey multiKey ) {\r
 279     if( !checkTypes ) {\r
 280       return true;\r
 281     }\r
 282 \r
 283     return multiKey.typesMatch( keyTypes );\r
 284   }\r
 285 \r
 286 \r
 287   private boolean isHomogenous( MultiViewMap in ) {\r
 288     if( this.keyTypes.length != in.keyTypes.length ) {\r
 289       return false;\r
 290     }\r
 291     for( int i = 0; i < this.keyTypes.length; ++i ) {\r
 292       if( !this.keyTypes[i].equals( in.keyTypes[i] ) ) {\r
 293         return false;\r
 294       }\r
 295     }\r
 296     return \r
 297       this.partialViews.equals( in.partialViews ) &&\r
 298       this.fullView.equals( in.fullView ) &&\r
 299       this.joinOp.equals( in.joinOp );\r
 300   }\r
 301 \r
 302 \r
 303   private boolean isConsistent() {\r
 304     if( !checkConsistency ) {\r
 305       return true;\r
 306     }\r
 307 \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
 318           return false;\r
 319         }\r
 320       }\r
 321     }\r
 322 \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
 336             return false;\r
 337           }\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
 343             return false;\r
 344           }\r
 345         }\r
 346       }\r
 347     }\r
 348 \r
 349     return true;\r
 350   }\r
 351 \r
 352   public String toString() {\r
 353     return toString( 0 );\r
 354   }\r
 355 \r
 356   public String toString( int indent ) {\r
 357     StringBuilder s = new StringBuilder();\r
 358     \r
 359     for( MultiKey key : fullKey2value.keySet() ) {\r
 360       for( int i = 0; i < indent; ++i ) {\r
 361         s.append( ' ' );\r
 362       }\r
 363       s.append( key+" -> "+fullKey2value.get( key )+"\n" );\r
 364     }\r
 365     return s.toString();\r
 366   }\r
 367 }\r