X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;ds=sidebyside;f=src%2Fedu%2Fberkeley%2Fsbp%2Futil%2FIntPairMap.java;h=b94269150fa48b0b04520a4df2ee6917f4d6c0ab;hb=HEAD;hp=c355488ec01826f06eacd1409ff2837f03767492;hpb=21b1b10a3ffb4b2021ad940f9cd722e3ed5300c4;p=sbp.git
diff --git a/src/edu/berkeley/sbp/util/IntPairMap.java b/src/edu/berkeley/sbp/util/IntPairMap.java
index c355488..b942691 100644
--- a/src/edu/berkeley/sbp/util/IntPairMap.java
+++ b/src/edu/berkeley/sbp/util/IntPairMap.java
@@ -1,18 +1,148 @@
+// This was taken from org.ibex.util
+//
+// Copyright 2000-2005 the Contributors, as shown in the revision logs.
+// Licensed under the Apache Public Source License 2.0 ("the License").
+// You may not use this file except in compliance with the License.
+
package edu.berkeley.sbp.util;
import java.util.*;
-/** a mapping from keys of type K to sets of values of type T */
-public final class IntPairMap {
+// FEATURE: make this faster (plenty of ways: quadradic probing hash table is one)
+/** a sparse mapping from pairs of int's to V's */
+public final class IntPairMap implements Iterable {
+
+ /** this object is inserted as key in a slot when the
+ * corresponding value is removed -- this ensures that the
+ * probing sequence for any given key remains the same even if
+ * other keys are removed.
+ */
+ // FIXME: this should have been static except that that makes it nonserializable
+ private Object placeholder = new java.io.Serializable() { };
+
+ /** the number of entries with at least one non-null key */
+ private int usedslots = 0;
+
+ /** the number of entries with non-null values */
+ protected int size = 0;
+
+ /** when num_slots < loadFactor * size, rehash into a bigger table */
+ private final int loadFactor;
+
+ /** primary keys */
+ private int[] keys1 = null;
+
+ /** secondary keys; null if no secondary key has ever been added */
+ private int[] keys2 = null;
+
+ /** the values for the table */
+ private V[] vals = null;
+
+ /** the number of entries with a non-null value */
+ public int size() { return size; }
+
+ public IntPairMap() { this(25, 3); }
+ public IntPairMap(int initialcapacity, int loadFactor) {
+ // using a pseudoprime in the form 4x+3 ensures full coverage
+ initialcapacity = initialcapacity / 4;
+ initialcapacity = 4 * initialcapacity + 3;
+ keys1 = new int[initialcapacity];
+ keys2 = new int[initialcapacity];
+ vals = (V[])(new Object[initialcapacity]);
+ this.loadFactor = loadFactor;
+ }
+
+ public void remove(int k1, int k2) { put_(k1, k2, null); }
+ private void rehash() {
+ int[] oldkeys1 = keys1;
+ int[] oldkeys2 = keys2;
+ V[] oldvals = vals;
+ keys1 = new int[oldvals.length * 2];
+ keys2 = new int[oldvals.length * 2];
+ vals = (V[])(new Object[oldvals.length * 2]);
+ size = 0;
+ usedslots = 0;
+ for(int i=0; i vals.length) rehash();
+ int hash = k1 ^ k2;
+ int dest = Math.abs(hash) % vals.length;
+ int odest = dest;
+ boolean plus = true;
+ int tries = 1;
+ while (true) {
+ int hk1 = keys1[dest];
+ int hk2 = keys2[dest];
+ if (vals[dest]==null || (k1==hk1 && k2==hk2 && vals[dest]!=placeholder)) {
+ if (v == null) {
+ if (vals[dest]==null) return;
+ v = placeholder;
+ size--;
+ } else {
+ size++;
+ usedslots++;
+ }
+ break;
+ }
+
+ dest = Math.abs((odest + (plus ? 1 : -1 ) * tries * tries) % vals.length);
+ if (plus) tries++;
+ plus = !plus;
+ }
- private final HashMap hm = new HashMap();
+ keys1[dest] = k1;
+ keys2[dest] = k2;
+ ((Object[])vals)[dest] = v;
+ }
+
+ private class IntPairMapIterator implements Iterator {
+ private int iterator = -1;
+ private int found = 0;
+
+ public void remove() { throw new Error(); }
+ public boolean hasNext() { return found < size; }
- private static long key(IntegerMappable k1, IntegerMappable k2) {
- return (k1==null ? 0 : (((long)k1.toInt()) << 32)) | (k2==null ? 0 : k2.toInt());
+ public V next() {
+ if (!hasNext()) return null;
+ V o = null;
+ while (o==null || o==placeholder) o = vals[++iterator];
+ found++;
+ return o;
+ }
}
+ public Iterator iterator() { return new IntPairMapIterator(); }
- public void put(IntegerMappable k1, IntegerMappable k2, V v) { hm.put(key(k1, k2), v); }
- public V get(IntegerMappable k1, IntegerMappable k2) { return hm.get(key(k1, k2)); }
- public Iterable values() { return hm.values(); }
- public int size() { return hm.size(); }
- public void toArray(V[] v) { hm.values().toArray(v); }
+ public void put(IntegerMappable k1, IntegerMappable k2, V v) {
+ put((k1==null?0:k1.toInt()), (k2==null?0:k2.toInt()), v);
+ }
+ public V get(IntegerMappable k1, IntegerMappable k2) {
+ return get((k1==null?0:k1.toInt()), (k2==null?0:k2.toInt()));
+ }
+ public void remove(IntegerMappable k1, IntegerMappable k2) {
+ remove((k1==null?0:k1.toInt()), (k2==null?0:k2.toInt()));
+ }
+ //public Iterable values() { return this; }
+ //public void toArray(V[] v) { hm.values().toArray(v); }
+ //public Iterator iterator() { return hm.values().iterator(); }
}