src/edu/berkeley/sbp/util/IntPairMap.java

   1 // This was taken from org.ibex.util
   2 //
   3 // Copyright 2000-2005 the Contributors, as shown in the revision logs.
   4 // Licensed under the Apache Public Source License 2.0 ("the License").
   5 // You may not use this file except in compliance with the License.
   6
   7 package edu.berkeley.sbp.util;
   8 import java.util.*;
   9
  10 // FEATURE: make this faster (plenty of ways: quadradic probing hash table is one)
  11 /** a sparse mapping from pairs of <tt>int</tt>'s to <tt>V</tt>'s */
  12 public final class IntPairMap<V> implements Iterable<V> {
  13
  14     /** this object is inserted as key in a slot when the
  15      *  corresponding value is removed -- this ensures that the
  16      *  probing sequence for any given key remains the same even if
  17      *  other keys are removed.
  18      */
  19     // FIXME: this should have been static except that that makes it nonserializable
  20     private Object placeholder = new java.io.Serializable() { };
  21
  22     /** the number of entries with at least one non-null key */
  23     private int usedslots = 0;
  24
  25     /** the number of entries with non-null values */
  26     protected int size = 0;
  27
  28     /** when num_slots < loadFactor * size, rehash into a bigger table */
  29     private final int loadFactor;
  30
  31     /** primary keys */
  32     private int[] keys1 = null;
  33
  34     /** secondary keys; null if no secondary key has ever been added */
  35     private int[] keys2 = null;
  36
  37     /** the values for the table */
  38     private V[] vals = null;
  39
  40     /** the number of entries with a non-null value */
  41     public int size() { return size; }
  42
  43     public IntPairMap() { this(25, 3); }
  44     public IntPairMap(int initialcapacity, int loadFactor) {
  45         // using a pseudoprime in the form 4x+3 ensures full coverage
  46         initialcapacity = initialcapacity / 4;
  47         initialcapacity = 4 * initialcapacity + 3;
  48         keys1 = new int[initialcapacity];
  49         keys2 = new int[initialcapacity];
  50         vals = (V[])(new Object[initialcapacity]);
  51         this.loadFactor = loadFactor;
  52     }
  53
  54     public void remove(int k1, int k2) { put_(k1, k2, null); }
  55     private void rehash() {
  56         int[] oldkeys1 = keys1;
  57         int[] oldkeys2 = keys2;
  58         V[] oldvals = vals;
  59         keys1 = new int[oldvals.length * 2];
  60         keys2 = new int[oldvals.length * 2];
  61         vals = (V[])(new Object[oldvals.length * 2]);
  62         size = 0;
  63         usedslots = 0;
  64         for(int i=0; i<oldvals.length; i++)
  65             if (oldvals[i] != null && oldvals[i] != placeholder)
  66                 put_(oldkeys1[i], oldkeys2[i], oldvals[i]);
  67     }
  68
  69     public V get(int k1, int k2) {
  70         int hash = k1 ^ k2;
  71         int dest = Math.abs(hash) % vals.length;
  72         int odest = dest;
  73         int tries = 1;
  74         boolean plus = true;
  75         while (vals[dest]!=null) {
  76             int hk1 = keys1[dest];
  77             int hk2 = keys2[dest];
  78             if (k1 == hk1 && k2 == hk2 && vals[dest]!=placeholder) return vals[dest];
  79             dest = Math.abs((odest + (plus ? 1 : -1 ) * tries * tries) % vals.length);
  80             if (plus) tries++;
  81             plus = !plus;
  82         }
  83         return null;
  84     }
  85
  86     public void put(int k1, int k2, Object v) { put_(k1, k2, v); }
  87     private void put_(int k1, int k2, Object v) {
  88         if (usedslots * loadFactor > vals.length) rehash();
  89         int hash = k1 ^ k2;
  90         int dest = Math.abs(hash) % vals.length;
  91         int odest = dest;
  92         boolean plus = true;
  93         int tries = 1;
  94         while (true) {
  95             int hk1 = keys1[dest];
  96             int hk2 = keys2[dest];
  97             if (vals[dest]==null || (k1==hk1 && k2==hk2 && vals[dest]!=placeholder)) {
  98                 if (v == null) {
  99                     if (vals[dest]==null) return;
 100                     v = placeholder;
 101                     size--;
 102                 } else {
 103                     size++;
 104                     usedslots++;
 105                 }
 106                 break;
 107             }
 108
 109             dest = Math.abs((odest + (plus ? 1 : -1 ) * tries * tries) % vals.length);
 110             if (plus) tries++;
 111             plus = !plus;
 112         }
 113
 114         keys1[dest] = k1;
 115         keys2[dest] = k2;
 116         ((Object[])vals)[dest] = v;
 117     }
 118
 119     private class IntPairMapIterator implements Iterator<V> {
 120         private int iterator = -1;
 121         private int found = 0;
 122
 123         public void remove() { throw new Error(); }
 124         public boolean hasNext() { return found < size; }
 125
 126         public V next() {
 127             if (!hasNext()) return null;
 128             V o = null;
 129             while (o==null || o==placeholder) o = vals[++iterator];
 130             found++;
 131             return o;
 132         }
 133     }
 134     public Iterator<V> iterator() { return new IntPairMapIterator(); }
 135
 136     public void put(IntegerMappable k1, IntegerMappable k2, V v) {
 137         put((k1==null?0:k1.toInt()), (k2==null?0:k2.toInt()), v);
 138     }
 139     public V get(IntegerMappable k1, IntegerMappable k2) {
 140         return get((k1==null?0:k1.toInt()), (k2==null?0:k2.toInt()));
 141     }
 142     public void remove(IntegerMappable k1, IntegerMappable k2) {
 143         remove((k1==null?0:k1.toInt()), (k2==null?0:k2.toInt()));
 144     }
 145     //public Iterable<V> values() { return this; }
 146     //public void toArray(V[] v) { hm.values().toArray(v); }
 147     //public Iterator<V> iterator() { return hm.values().iterator(); }
 148 }