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    }