001package stdlib;
002
003/**
004 * An implementation of a hash table where each value has a composite key
005 * generated from 3 objects.  Acts like the Java HashMap except that:
006 * <ul>
007 * <li>None of the keys or values are allowed to be null.</li>
008 * <li>None of the values are allowed to be arrays.</li>
009 * <li>It uses == rather than .equals to compare objects for equality.</li>
010 * </ul>
011 * Hack hack hack for space efficiency...
012 */
013public class HashMap3 {
014
015        Object[] values = new Object[128];
016        Object[] keys1 = new Object[128];
017        Object[] keys2 = new Object[128];
018        Object[] keys3 = new Object[128];
019        int size=0;
020
021        public void put (Object key1, Object key2, Object key3, Object value) {
022                if (size > values.length) {
023                        grow ();
024                }
025                putNoGrow (key1, key2, key3, value);
026        }
027
028        public void grow () {
029                Object[] oldValues = this.values;
030                Object[] oldKeys1 = this.keys1;
031                Object[] oldKeys2 = this.keys2;
032                Object[] oldKeys3 = this.keys3;
033                this.values = new Object[oldValues.length * 2];
034                this.keys1 = new Object[oldValues.length * 2];
035                this.keys2 = new Object[oldValues.length * 2];
036                this.keys3 = new Object[oldValues.length * 2];
037                for (int i=0; i<oldValues.length; i++) {
038                        if (oldValues[i] == null) {
039                                continue;
040                        } else if (oldValues[i] instanceof Object[]) {
041                                Object[] valuesBucket = (Object[])(oldValues[i]);
042                                Object[] keys1Bucket = (Object[])(oldKeys1[i]);
043                                Object[] keys2Bucket = (Object[])(oldKeys2[i]);
044                                Object[] keys3Bucket = (Object[])(oldKeys3[i]);
045                                for (int j=0; j<valuesBucket.length; j++) {
046                                        if (valuesBucket[j] == null) {
047                                                break;
048                                        }
049                                        putNoGrow (keys1Bucket[j], keys2Bucket[j], keys3Bucket[j], valuesBucket[j]);
050                                }
051                        } else {
052                                putNoGrow (oldKeys1[i], oldKeys2[i], oldKeys3[i], oldValues[i]);
053                        }
054                }
055        }
056
057        public void putNoGrow (Object key1, Object key2, Object key3, Object value) {
058                size++;
059                int hash = hash3 (key1, key2, key3) % values.length;
060                if (values[hash] == null) {
061                        keys1[hash] = key1;
062                        keys2[hash] = key2;
063                        keys3[hash] = key3;
064                        values[hash] = value;
065                        return;
066                } else if (values[hash] instanceof Object[]) {
067                        Object[] valuesBucket = (Object[])(values[hash]);
068                        Object[] keys1Bucket = (Object[])(keys1[hash]);
069                        Object[] keys2Bucket = (Object[])(keys2[hash]);
070                        Object[] keys3Bucket = (Object[])(keys3[hash]);
071                        for (int i=0; i<valuesBucket.length; i++) {
072                                if (valuesBucket[i] == null) {
073                                        keys1Bucket[i] = key1;
074                                        keys2Bucket[i] = key2;
075                                        keys3Bucket[i] = key3;
076                                        valuesBucket[i] = value;
077                                        return;
078                                }
079                        }
080                        Object[] newValuesBucket = new Object[valuesBucket.length * 2];
081                        Object[] newKeys1Bucket = new Object[valuesBucket.length * 2];
082                        Object[] newKeys2Bucket = new Object[valuesBucket.length * 2];
083                        Object[] newKeys3Bucket = new Object[valuesBucket.length * 2];
084                        for (int i=0; i<valuesBucket.length; i++) {
085                                newValuesBucket[i] = valuesBucket[i];
086                                newKeys1Bucket[i] = keys1Bucket[i];
087                                newKeys2Bucket[i] = keys2Bucket[i];
088                                newKeys3Bucket[i] = keys3Bucket[i];
089                        }
090                        newValuesBucket[valuesBucket.length] = value;
091                        newKeys1Bucket[valuesBucket.length] = key1;
092                        newKeys2Bucket[valuesBucket.length] = key2;
093                        newKeys3Bucket[valuesBucket.length] = key3;
094                        values[hash] = newValuesBucket;
095                        keys1[hash] = newKeys1Bucket;
096                        keys2[hash] = newKeys2Bucket;
097                        keys3[hash] = newKeys3Bucket;
098                        return;
099                } else {
100                        values[hash] = new Object[]{ values[hash], value };
101                        keys1[hash] = new Object[]{ keys1[hash], key1 };
102                        keys2[hash] = new Object[]{ keys2[hash], key2 };
103                        keys3[hash] = new Object[]{ keys3[hash], key3 };
104                        return;
105                }
106        }
107
108        public Object get (Object key1, Object key2, Object key3) {
109                int hash = hash3 (key1, key2, key3) % values.length;
110                if (values[hash] == null) {
111                        return null;
112                } else if (values[hash] instanceof Object[]) {
113                        Object[] valuesBucket = (Object[])(values[hash]);
114                        Object[] keys1Bucket = (Object[])(keys1[hash]);
115                        Object[] keys2Bucket = (Object[])(keys2[hash]);
116                        Object[] keys3Bucket = (Object[])(keys3[hash]);
117                        for (int i=0; i<valuesBucket.length; i++) {
118                                if (keys1Bucket[i] == key1
119                                                && keys2Bucket[i] == key2
120                                                && keys3Bucket[i] == key3) {
121                                        return valuesBucket[i];
122                                }
123                        }
124                        return null;
125                } else if (keys1[hash] == key1
126                                && keys2[hash] == key2
127                                && keys3[hash] == key3) {
128                        return values[hash];
129                } else {
130                        return null;
131                }
132        }
133
134        public static int hash3 (Object key1, Object key2, Object key3) {
135                return key1.hashCode () + 5 * key2.hashCode () + 13 * key3.hashCode ();
136        }
137
138}