00001: package simplebdd.util;
00002:
00003: // An implementation of a hash table where each value has a composite key
00004: // generated from 3 objects. Acts like the Java HashMap except that:
00005: //
00006: // a) None of the keys or values are allowed to be null
00007: // b) None of the values are allowed to be arrays.
00008: // c) It usees == rather than .equals to compare objects for equality.
00009: //
00010: // Hack hack hack for space efficiency...
00011:
00012: import java.util.HashMap;
00013:
00014: public class HashMap3 {
00015:
00016: Object[] values = new Object[128];
00017: Object[] keys1 = new Object[128];
00018: Object[] keys2 = new Object[128];
00019: Object[] keys3 = new Object[128];
00020: int size=0;
00021:
00022: public void put (Object key1, Object key2, Object key3, Object value) {
00023: if (size > values.length) {
00024: grow ();
00025: }
00026: putNoGrow (key1, key2, key3, value);
00027: }
00028:
00029: public void grow () {
00030: Object[] oldValues = this.values;
00031: Object[] oldKeys1 = this.keys1;
00032: Object[] oldKeys2 = this.keys2;
00033: Object[] oldKeys3 = this.keys3;
00034: this.values = new Object[oldValues.length * 2];
00035: this.keys1 = new Object[oldValues.length * 2];
00036: this.keys2 = new Object[oldValues.length * 2];
00037: this.keys3 = new Object[oldValues.length * 2];
00038: for (int i=0; i<oldValues.length; i++) {
00039: if (oldValues[i] == null) {
00040: continue;
00041: } else if (oldValues[i] instanceof Object[]) {
00042: Object[] valuesBucket = (Object[])(oldValues[i]);
00043: Object[] keys1Bucket = (Object[])(oldKeys1[i]);
00044: Object[] keys2Bucket = (Object[])(oldKeys2[i]);
00045: Object[] keys3Bucket = (Object[])(oldKeys3[i]);
00046: for (int j=0; j<valuesBucket.length; j++) {
00047: if (valuesBucket[j] == null) {
00048: break;
00049: }
00050: putNoGrow (keys1Bucket[j], keys2Bucket[j], keys3Bucket[j], valuesBucket[j]);
00051: }
00052: } else {
00053: putNoGrow (oldKeys1[i], oldKeys2[i], oldKeys3[i], oldValues[i]);
00054: }
00055: }
00056: }
00057:
00058: public void putNoGrow (Object key1, Object key2, Object key3, Object value) {
00059: size++;
00060: int hash = hash3 (key1, key2, key3) % values.length;
00061: if (values[hash] == null) {
00062: keys1[hash] = key1;
00063: keys2[hash] = key2;
00064: keys3[hash] = key3;
00065: values[hash] = value;
00066: return;
00067: } else if (values[hash] instanceof Object[]) {
00068: Object[] valuesBucket = (Object[])(values[hash]);
00069: Object[] keys1Bucket = (Object[])(keys1[hash]);
00070: Object[] keys2Bucket = (Object[])(keys2[hash]);
00071: Object[] keys3Bucket = (Object[])(keys3[hash]);
00072: for (int i=0; i<valuesBucket.length; i++) {
00073: if (valuesBucket[i] == null) {
00074: keys1Bucket[i] = key1;
00075: keys2Bucket[i] = key2;
00076: keys3Bucket[i] = key3;
00077: valuesBucket[i] = value;
00078: return;
00079: }
00080: }
00081: Object[] newValuesBucket = new Object[valuesBucket.length * 2];
00082: Object[] newKeys1Bucket = new Object[valuesBucket.length * 2];
00083: Object[] newKeys2Bucket = new Object[valuesBucket.length * 2];
00084: Object[] newKeys3Bucket = new Object[valuesBucket.length * 2];
00085: for (int i=0; i<valuesBucket.length; i++) {
00086: newValuesBucket[i] = valuesBucket[i];
00087: newKeys1Bucket[i] = keys1Bucket[i];
00088: newKeys2Bucket[i] = keys2Bucket[i];
00089: newKeys3Bucket[i] = keys3Bucket[i];
00090: }
00091: newValuesBucket[valuesBucket.length] = value;
00092: newKeys1Bucket[valuesBucket.length] = key1;
00093: newKeys2Bucket[valuesBucket.length] = key2;
00094: newKeys3Bucket[valuesBucket.length] = key3;
00095: values[hash] = newValuesBucket;
00096: keys1[hash] = newKeys1Bucket;
00097: keys2[hash] = newKeys2Bucket;
00098: keys3[hash] = newKeys3Bucket;
00099: return;
00100: } else {
00101: values[hash] = new Object[]{ values[hash], value };
00102: keys1[hash] = new Object[]{ keys1[hash], key1 };
00103: keys2[hash] = new Object[]{ keys2[hash], key2 };
00104: keys3[hash] = new Object[]{ keys3[hash], key3 };
00105: return;
00106: }
00107: }
00108:
00109: public Object get (Object key1, Object key2, Object key3) {
00110: int hash = hash3 (key1, key2, key3) % values.length;
00111: if (values[hash] == null) {
00112: return null;
00113: } else if (values[hash] instanceof Object[]) {
00114: Object[] valuesBucket = (Object[])(values[hash]);
00115: Object[] keys1Bucket = (Object[])(keys1[hash]);
00116: Object[] keys2Bucket = (Object[])(keys2[hash]);
00117: Object[] keys3Bucket = (Object[])(keys3[hash]);
00118: for (int i=0; i<valuesBucket.length; i++) {
00119: if (keys1Bucket[i] == key1
00120: && keys2Bucket[i] == key2
00121: && keys3Bucket[i] == key3) {
00122: return valuesBucket[i];
00123: }
00124: }
00125: return null;
00126: } else if (keys1[hash] == key1
00127: && keys2[hash] == key2
00128: && keys3[hash] == key3) {
00129: return values[hash];
00130: } else {
00131: return null;
00132: }
00133: }
00134:
00135: public int hash3 (Object key1, Object key2, Object key3) {
00136: return key1.hashCode () + 5 * key2.hashCode () + 13 * key3.hashCode ();
00137: }
00138:
00139: }
00140:
|
