SE547: BDDs: Util Code [22/22] Previous pageContents

file:simplebdd/util/HashMap3.java [source] [doc-public] [doc-private]
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: 

Previous pageContents