001 package fj.data; 002 003 import fj.F; 004 import static fj.P.p; 005 import fj.P2; 006 import static fj.data.Option.fromNull; 007 import fj.pre.Equal; 008 import fj.pre.Hash; 009 010 import java.util.Collection; 011 import java.util.Iterator; 012 013 /** 014 * A mutable hash map providing O(1) lookup. 015 * 016 * @version %build.number%<br> 017 * <ul> 018 * <li>$LastChangedRevision: 122 $</li> 019 * <li>$LastChangedDate: 2009-04-25 08:24:38 +1000 (Sat, 25 Apr 2009) $</li> 020 * </ul> 021 * @see java.util.HashMap 022 */ 023 public final class HashMap<K, V> implements Iterable<K> { 024 private final class Key<K> { 025 private final K k; 026 private final Equal<K> e; 027 private final Hash<K> h; 028 029 Key(final K k, final Equal<K> e, final Hash<K> h) { 030 this.k = k; 031 this.e = e; 032 this.h = h; 033 } 034 035 K k() { 036 return k; 037 } 038 039 @SuppressWarnings({"unchecked"}) 040 public boolean equals(final Object o) { 041 return o instanceof Key && e.eq(k, (K) ((Key<?>) o).k()); 042 } 043 044 public int hashCode() { 045 return h.hash(k); 046 } 047 } 048 049 /** 050 * Returns an iterator for this map's keys. This method exists to permit the use in a <code>for</code>-each loop. 051 * 052 * @return A iterator for this map's keys. 053 */ 054 public Iterator<K> iterator() { 055 return keys().iterator(); 056 } 057 058 private final java.util.HashMap<Key<K>, V> m; 059 060 private final Equal<K> e; 061 private final Hash<K> h; 062 063 /** 064 * Construct a hash map with the given equality and hashing strategy. 065 * 066 * @param e The equality strategy. 067 * @param h The hashing strategy. 068 */ 069 public HashMap(final Equal<K> e, final Hash<K> h) { 070 m = new java.util.HashMap<Key<K>, V>(); 071 this.e = e; 072 this.h = h; 073 } 074 075 /** 076 * Construct a hash map with the given equality and hashing strategy. 077 * 078 * @param e The equality strategy. 079 * @param h The hashing strategy. 080 * @param initialCapacity The initial capacity. 081 */ 082 public HashMap(final Equal<K> e, final Hash<K> h, final int initialCapacity) { 083 m = new java.util.HashMap<Key<K>, V>(initialCapacity); 084 this.e = e; 085 this.h = h; 086 } 087 088 /** 089 * Construct a hash map with the given equality and hashing strategy. 090 * 091 * @param e The equality strategy. 092 * @param h The hashing strategy. 093 * @param initialCapacity The initial capacity. 094 * @param loadFactor The load factor. 095 */ 096 public HashMap(final Equal<K> e, final Hash<K> h, final int initialCapacity, final float loadFactor) { 097 m = new java.util.HashMap<Key<K>, V>(initialCapacity, loadFactor); 098 this.e = e; 099 this.h = h; 100 } 101 102 /** 103 * Construct a hash map that uses {@link Object#equals} and {@link Object#hashCode}. 104 * 105 * @return A new hash map that uses {@link Object#equals} and {@link Object#hashCode}. 106 */ 107 public static <K, V> HashMap<K, V> hashMap() { 108 final Equal<K> e = Equal.anyEqual(); 109 final Hash<K> h = Hash.anyHash(); 110 return new HashMap<K, V>(e, h); 111 } 112 113 /** 114 * Compare two key values for equality using the underlying equality strategy. 115 * 116 * @param k1 One key value to compare. 117 * @param k2 The other key value to compare. 118 * @return <code>true</code> if the two key values are equal, <code>false</code> otherwise. 119 */ 120 public boolean eq(final K k1, final K k2) { 121 return e.eq(k1, k2); 122 } 123 124 /** 125 * Compute the hash of the given key value using the underlying hashing strategy. 126 * 127 * @param k The key value to computer the hash of. 128 * @return The hash of the given key value. 129 */ 130 public int hash(final K k) { 131 return h.hash(k); 132 } 133 134 /** 135 * Returns a potential value that the given key maps to. 136 * 137 * @param k The key to look up in the hash map. 138 * @return A potential value for the given key. 139 */ 140 public Option<V> get(final K k) { 141 return fromNull(m.get(new Key<K>(k, e, h))); 142 } 143 144 /** 145 * A curried version of {@link #get(Object)}. 146 * 147 * @return A curried version of {@link #get(Object)}. 148 */ 149 public F<K, Option<V>> get() { 150 return new F<K, Option<V>>() { 151 public Option<V> f(final K k) { 152 return get(k); 153 } 154 }; 155 } 156 157 /** 158 * Clear all entries from this hash map. 159 */ 160 public void clear() { 161 m.clear(); 162 } 163 164 /** 165 * Determines if the given key value exists in this hash map. 166 * 167 * @param k The key value to look for in this hash map. 168 * @return <code>true</code> if this hash map contains the given key, <code>false</code> otherwise. 169 */ 170 public boolean contains(final K k) { 171 return m.containsKey(new Key<K>(k, e, h)); 172 } 173 174 /** 175 * Returns all key entries in this hash map. 176 * 177 * @return All key entries in this hash map. 178 */ 179 public List<K> keys() { 180 final List.Buffer<K> b = new List.Buffer<K>(); 181 182 for (final Key<K> k : m.keySet()) { 183 b.snoc(k.k()); 184 } 185 186 return b.toList(); 187 } 188 189 /** 190 * Returns all values in this hash map. 191 * 192 * @return All values in this hash map. 193 */ 194 public List<V> values() { 195 return keys().map(new F<K, V>() { 196 public V f(final K k) { 197 return m.get(new Key<K>(k, e, h)); 198 } 199 }); 200 } 201 202 /** 203 * Determines if this hash map has any entries. 204 * 205 * @return <code>true</code> if this hash map has no entries, <code>false</code> otherwise. 206 */ 207 public boolean isEmpty() { 208 return m.isEmpty(); 209 } 210 211 /** 212 * Returns the number of entries in this hash map. 213 * 214 * @return The number of entries in this hash map. 215 */ 216 public int size() { 217 return m.size(); 218 } 219 220 /** 221 * Inserts the given key and value association into the hash map. 222 * 223 * @param k The key to insert. 224 * @param v The value to insert. 225 */ 226 public void set(final K k, final V v) { 227 m.put(new Key<K>(k, e, h), v); 228 } 229 230 /** 231 * Deletes the entry in the hash map that corresponds to the given key. 232 * 233 * @param k The key to delete from this hash map. 234 */ 235 public void delete(final K k) { 236 m.remove(new Key<K>(k, e, h)); 237 } 238 239 /** 240 * Deletes the entry in the hash map that corresponds to the given key and returns any associated value. 241 * 242 * @param k The key to delete from this hash map. 243 * @return The value that was associated with the given key, if there was one. 244 */ 245 public Option<V> getDelete(final K k) { 246 return fromNull(m.remove(new Key<K>(k, e, h))); 247 } 248 249 /** 250 * Projects an immutable collection of this hash map. 251 * 252 * @return An immutable collection of this hash map. 253 */ 254 public Collection<P2<K, V>> toCollection() { 255 return keys().map(new F<K, P2<K, V>>() { 256 public P2<K, V> f(final K k) { 257 return p(k, get(k).some()); 258 } 259 }).toCollection(); 260 } 261 }