1 // This was taken from org.ibex.util
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.
7 package edu.berkeley.sbp.util;
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> {
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.
19 // FIXME: this should have been static except that that makes it nonserializable
20 private Object placeholder = new java.io.Serializable() { };
22 /** the number of entries with at least one non-null key */
23 private int usedslots = 0;
25 /** the number of entries with non-null values */
26 protected int size = 0;
28 /** when num_slots < loadFactor * size, rehash into a bigger table */
29 private final int loadFactor;
32 private int[] keys1 = null;
34 /** secondary keys; null if no secondary key has ever been added */
35 private int[] keys2 = null;
37 /** the values for the table */
38 private V[] vals = null;
40 /** the number of entries with a non-null value */
41 public int size() { return size; }
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;
54 public void remove(int k1, int k2) { put_(k1, k2, null); }
55 private void rehash() {
56 int[] oldkeys1 = keys1;
57 int[] oldkeys2 = keys2;
59 keys1 = new int[oldvals.length * 2];
60 keys2 = new int[oldvals.length * 2];
61 vals = (V[])(new Object[oldvals.length * 2]);
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]);
69 public V get(int k1, int k2) {
71 int dest = Math.abs(hash) % vals.length;
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);
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();
90 int dest = Math.abs(hash) % vals.length;
95 int hk1 = keys1[dest];
96 int hk2 = keys2[dest];
97 if (vals[dest]==null || (k1==hk1 && k2==hk2 && vals[dest]!=placeholder)) {
99 if (vals[dest]==null) return;
109 dest = Math.abs((odest + (plus ? 1 : -1 ) * tries * tries) % vals.length);
116 ((Object[])vals)[dest] = v;
119 private class IntPairMapIterator implements Iterator<V> {
120 private int iterator = -1;
121 private int found = 0;
123 public void remove() { throw new Error(); }
124 public boolean hasNext() { return found < size; }
127 if (!hasNext()) return null;
129 while (o==null || o==placeholder) o = vals[++iterator];
134 public Iterator<V> iterator() { return new IntPairMapIterator(); }
136 public void put(IntegerMappable k1, IntegerMappable k2, V v) {
137 put((k1==null?0:k1.toInt()), (k2==null?0:k2.toInt()), v);
139 public V get(IntegerMappable k1, IntegerMappable k2) {
140 return get((k1==null?0:k1.toInt()), (k2==null?0:k2.toInt()));
142 public void remove(IntegerMappable k1, IntegerMappable k2) {
143 remove((k1==null?0:k1.toInt()), (k2==null?0:k2.toInt()));
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(); }