001 package fj.data; 002 003 import fj.Unit; 004 import static fj.Unit.unit; 005 import fj.pre.Equal; 006 import fj.pre.Hash; 007 008 import java.util.Collection; 009 import java.util.Iterator; 010 011 /** 012 * A mutable hash set that guarantees uniqueness of its elements providing O(1) lookup. 013 * 014 * @version %build.number%<br> 015 * <ul> 016 * <li>$LastChangedRevision: 122 $</li> 017 * <li>$LastChangedDate: 2009-04-25 08:24:38 +1000 (Sat, 25 Apr 2009) $</li> 018 * </ul> 019 * @see HashMap 020 */ 021 public final class HashSet<A> implements Iterable<A> { 022 /** 023 * Returns an iterator for this hash set. This method exists to permit the use in a <code>for</code>-each loop. 024 * 025 * @return A iterator for this hash set. 026 */ 027 public Iterator<A> iterator() { 028 return toCollection().iterator(); 029 } 030 031 private final HashMap<A, Unit> m; 032 033 /** 034 * Construct a hash set with the given equality and hashing strategy. 035 * 036 * @param e The equality strategy. 037 * @param h The hashing strategy. 038 */ 039 public HashSet(final Equal<A> e, final Hash<A> h) { 040 m = new HashMap<A, Unit>(e, h); 041 } 042 043 /** 044 * Construct a hash set with the given equality and hashing strategy. 045 * 046 * @param e The equality strategy. 047 * @param h The hashing strategy. 048 * @param initialCapacity The initial capacity. 049 */ 050 public HashSet(final Equal<A> e, final Hash<A> h, final int initialCapacity) { 051 m = new HashMap<A, Unit>(e, h, initialCapacity); 052 } 053 054 /** 055 * Construct a hash set with the given equality and hashing strategy. 056 * 057 * @param e The equality strategy. 058 * @param h The hashing strategy. 059 * @param initialCapacity The initial capacity. 060 * @param loadFactor The load factor. 061 */ 062 public HashSet(final Equal<A> e, final Hash<A> h, final int initialCapacity, final float loadFactor) { 063 m = new HashMap<A, Unit>(e, h, initialCapacity, loadFactor); 064 } 065 066 /** 067 * Compare two values for equality using the underlying equality strategy. 068 * 069 * @param a1 One value to compare. 070 * @param a2 The other value to compare. 071 * @return <code>true</code> if the two values are equal, <code>false</code> otherwise. 072 */ 073 public boolean eq(final A a1, final A a2) { 074 return m.eq(a1, a2); 075 } 076 077 /** 078 * Compute the hash of the given value using the underlying hashing strategy. 079 * 080 * @param a The value to computer the hash of. 081 * @return The hash of the given value. 082 */ 083 public int hash(final A a) { 084 return m.hash(a); 085 } 086 087 /** 088 * Determines if this hash set contains the given element. 089 * 090 * @param a The element to look for in this hash set. 091 * @return <code>true</code> if this hash set contains the given element, <code>false</code> otherwise. 092 */ 093 public boolean contains(final A a) { 094 return m.contains(a); 095 } 096 097 /** 098 * Insert the given element into this hash set. 099 * 100 * @param a The element to insert. 101 */ 102 public void set(final A a) { 103 m.set(a, unit()); 104 } 105 106 /** 107 * Clear all elements from this hash set. 108 */ 109 public void clear() { 110 m.clear(); 111 } 112 113 /** 114 * Determines if this hash set contains any elements. 115 * 116 * @return <code>true</code> if this hash set contains no elements, <code>false</code> otherwise. 117 */ 118 public boolean isEmpty() { 119 return m.isEmpty(); 120 } 121 122 /** 123 * Returns the number of entries in this hash set. 124 * 125 * @return The number of entries in this hash set. 126 */ 127 public int size() { 128 return m.size(); 129 } 130 131 /** 132 * Deletes the given element from this hash set. 133 * 134 * @param a The element to delete from this hash set. 135 * @return <code>true</code> if this hash set contained the given element prior to deletion, <code>false</code> 136 * otherwise. 137 */ 138 public boolean delete(final A a) { 139 return m.getDelete(a).isSome(); 140 } 141 142 /** 143 * Returns a list projection of this hash set. 144 * 145 * @return A list projection of this hash set. 146 */ 147 public List<A> toList() { 148 return m.keys(); 149 } 150 151 /** 152 * Projects an immutable collection of this hash set. 153 * 154 * @return An immutable collection of this hash set. 155 */ 156 public Collection<A> toCollection() { 157 return toList().toCollection(); 158 } 159 }