001    package ai;
002    
003    /** The LookupTable represents an efficient hash table to Variations with
004     *  two properties that make a regular HashMap unsuitable:
005     *
006     *     - The LookupTable uses bounded memory, choosing to replace old
007     *       cells rather than expand.
008     *
009     *     - The LookupTable does not check for collisions in hashCode.
010     *
011     *  As a result, LookupTable is fast, space-efficient, and
012     *  occasionally wrong.
013     *
014     *  LookupTable is thread-safe.
015     *
016     *  @specfield mapping : Map<Object, Variation> //The map represented by this table
017     */
018    public class LookupTable {
019    
020        // Each Variation can be fairly large (~40 bytes per cell) 
021        // so one million table entries and 2G memory = 50 cells/table entry
022        // which is safe.
023        
024        // Decreased it by a factor of 10 to be safe.
025        private final int SEEN_TABLE_SIZE = 100003;
026    
027        //The variation we last saw at a given table entry.
028        private Variation[] seen;
029    
030        //The whole key for a table entry
031        private int[] seenKeys;
032    
033        // AF:
034        //  mapping.get(x) = seen[x.hashCode() % SEEN_TABLE_SIZE]
035        //           if seenKeys[x.hashCode() % SEEN_TABLE_SIZE] == x.hashCode()
036        //  null     otherwise
037    
038        // RI:
039        //   seenKeys[x]%SEEN_TABLE_SIZE = x     for all x
040        //   If the Variation associated with G is in seen[x], then
041        //   seenKeys[x] = G.hashCode()
042        
043        public LookupTable() {
044            seen = new Variation[SEEN_TABLE_SIZE];
045            seenKeys = new int[SEEN_TABLE_SIZE];
046        }
047    
048        /**
049         * Get the value (probably) associated with an object, or null.
050         */
051        public Variation getTable(Object g) {
052            int key =  g.hashCode();
053            int shortKey = (SEEN_TABLE_SIZE + 
054                            key%SEEN_TABLE_SIZE)%SEEN_TABLE_SIZE;
055            synchronized(seen) {
056                if (seenKeys[shortKey] == key)
057                    return seen[shortKey];
058            }
059            return null;
060        }
061        
062        /**
063         * Set the Variation associated with an object.
064         */
065        public void update(Object g, Variation var){
066            int key =  g.hashCode();
067            int shortKey = (SEEN_TABLE_SIZE + 
068                            key%SEEN_TABLE_SIZE)%SEEN_TABLE_SIZE;
069            synchronized(seen) {
070                seen[shortKey] = var;
071                seenKeys[shortKey] = key;
072            }
073        }
074    }