1 /* 2 * Hunt - A refined core library for D programming language. 3 * 4 * Copyright (C) 2018-2019 HuntLabs 5 * 6 * Website: https://www.huntlabs.net/ 7 * 8 * Licensed under the Apache-2.0 License. 9 * 10 */ 11 12 module hunt.collection.HashSet; 13 14 import hunt.collection.AbstractSet; 15 import hunt.collection.Collection; 16 import hunt.collection.HashMap; 17 import hunt.collection.LinkedHashMap; 18 import hunt.collection.Set; 19 20 import hunt.Object; 21 22 import std.algorithm; 23 import std.range; 24 25 /** 26 * This class implements the <tt>Set</tt> interface, backed by a hash table 27 * (actually a <tt>HashMap</tt> instance). It makes no guarantees as to the 28 * iteration order of the set; in particular, it does not guarantee that the 29 * order will remain constant over time. This class permits the <tt>null</tt> 30 * element. 31 * 32 * <p>This class offers constant time performance for the basic operations 33 * (<tt>add</tt>, <tt>remove</tt>, <tt>contains</tt> and <tt>size</tt>), 34 * assuming the hash function disperses the elements properly among the 35 * buckets. Iterating over this set requires time proportional to the sum of 36 * the <tt>HashSet</tt> instance's size (the number of elements) plus the 37 * "capacity" of the backing <tt>HashMap</tt> instance (the number of 38 * buckets). Thus, it's very important not to set the initial capacity too 39 * high (or the load factor too low) if iteration performance is important. 40 * 41 * <p><strong>Note that this implementation is not synchronized.</strong> 42 * If multiple threads access a hash set concurrently, and at least one of 43 * the threads modifies the set, it <i>must</i> be synchronized externally. 44 * This is typically accomplished by synchronizing on some object that 45 * naturally encapsulates the set. 46 * 47 * If no such object exists, the set should be "wrapped" using the 48 * {@link Collections#synchronizedSet Collections.synchronizedSet} 49 * method. This is best done at creation time, to prevent accidental 50 * unsynchronized access to the set:<pre> 51 * Set s = Collections.synchronizedSet(new HashSet(...));</pre> 52 * 53 * <p>The iterators returned by this class's <tt>iterator</tt> method are 54 * <i>fail-fast</i>: if the set is modified at any time after the iterator is 55 * created, in any way except through the iterator's own <tt>remove</tt> 56 * method, the Iterator throws a {@link ConcurrentModificationException}. 57 * Thus, in the face of concurrent modification, the iterator fails quickly 58 * and cleanly, rather than risking arbitrary, non-deterministic behavior at 59 * an undetermined time in the future. 60 * 61 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed 62 * as it is, generally speaking, impossible to make any hard guarantees in the 63 * presence of unsynchronized concurrent modification. Fail-fast iterators 64 * throw <tt>ConcurrentModificationException</tt> on a best-effort basis. 65 * Therefore, it would be wrong to write a program that depended on this 66 * exception for its correctness: <i>the fail-fast behavior of iterators 67 * should be used only to detect bugs.</i> 68 * 69 * <p>This class is a member of the 70 * <a href="{@docRoot}/../technotes/guides/collections/index.html"> 71 * Java Collections Framework</a>. 72 * 73 * @param <E> the type of elements maintained by this set 74 * 75 * @author Josh Bloch 76 * @author Neal Gafter 77 * @see Collection 78 * @see Set 79 * @see TreeSet 80 * @see HashMap 81 */ 82 class HashSet(E) : AbstractSet!E, Set!E { 83 84 protected HashMap!(E, Object) map; 85 86 // Dummy value to associate with an Object in the backing Map 87 private __gshared static Object PRESENT; // = new Object(); 88 89 shared static this() { 90 PRESENT = new Object(); 91 } 92 93 /** 94 * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has 95 * default initial capacity (16) and load factor (0.75). 96 */ 97 this() { 98 map = new HashMap!(E, Object)(); 99 } 100 101 /** 102 * Constructs a new set containing the elements in the specified 103 * collection. The <tt>HashMap</tt> is created with default load factor 104 * (0.75) and an initial capacity sufficient to contain the elements in 105 * the specified collection. 106 * 107 * @param c the collection whose elements are to be placed into this set 108 * @throws NullPointerException if the specified collection is null 109 */ 110 this(Collection!E c) { 111 map = new HashMap!(E, Object)(std.algorithm.max(cast(int)(c.size() / .75f) + 1, 16)); 112 addAll(c); 113 } 114 115 this(E[] c) { 116 map = new HashMap!(E, Object)(std.algorithm.max(cast(int)(c.length / .75f) + 1, 16)); 117 addAll(c); 118 } 119 120 /** 121 * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has 122 * the specified initial capacity and the specified load factor. 123 * 124 * @param initialCapacity the initial capacity of the hash map 125 * @param loadFactor the load factor of the hash map 126 * @throws IllegalArgumentException if the initial capacity is less 127 * than zero, or if the load factor is nonpositive 128 */ 129 this(int initialCapacity, float loadFactor) { 130 map = new HashMap!(E, Object)(initialCapacity, loadFactor); 131 } 132 133 /** 134 * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has 135 * the specified initial capacity and default load factor (0.75). 136 * 137 * @param initialCapacity the initial capacity of the hash table 138 * @throws IllegalArgumentException if the initial capacity is less 139 * than zero 140 */ 141 this(int initialCapacity) { 142 map = new HashMap!(E, Object)(initialCapacity); 143 } 144 145 /** 146 * Constructs a new, empty linked hash set. (This package private 147 * constructor is only used by LinkedHashSet.) The backing 148 * HashMap instance is a LinkedHashMap with the specified initial 149 * capacity and the specified load factor. 150 * 151 * @param initialCapacity the initial capacity of the hash map 152 * @param loadFactor the load factor of the hash map 153 * @param dummy ignored (distinguishes this 154 * constructor from other int, float constructor.) 155 * @throws IllegalArgumentException if the initial capacity is less 156 * than zero, or if the load factor is nonpositive 157 */ 158 this(int initialCapacity, float loadFactor, bool dummy) { 159 map = new LinkedHashMap!(E, Object)(initialCapacity, loadFactor); 160 } 161 162 /** 163 * Returns an iterator over the elements in this set. The elements 164 * are returned in no particular order. 165 * 166 * @return an Iterator over the elements in this set 167 * @see ConcurrentModificationException 168 */ 169 override InputRange!E iterator() { 170 return map.byKey; 171 } 172 173 /** 174 * Returns the number of elements in this set (its cardinality). 175 * 176 * @return the number of elements in this set (its cardinality) 177 */ 178 override int size() { 179 return map.size(); 180 } 181 182 /** 183 * Returns <tt>true</tt> if this set contains no elements. 184 * 185 * @return <tt>true</tt> if this set contains no elements 186 */ 187 override bool isEmpty() { 188 return map.isEmpty(); 189 } 190 191 /** 192 * Returns <tt>true</tt> if this set contains the specified element. 193 * More formally, returns <tt>true</tt> if and only if this set 194 * contains an element <tt>e</tt> such that 195 * <tt>(o is null ? e is null : o.equals(e))</tt>. 196 * 197 * @param o element whose presence in this set is to be tested 198 * @return <tt>true</tt> if this set contains the specified element 199 */ 200 override bool contains(E o) { 201 return map.containsKey(o); 202 } 203 204 /** 205 * Adds the specified element to this set if it is not already present. 206 * More formally, adds the specified element <tt>e</tt> to this set if 207 * this set contains no element <tt>e2</tt> such that 208 * <tt>(e is null ? e2 is null : e.equals(e2))</tt>. 209 * If this set already contains the element, the call leaves the set 210 * unchanged and returns <tt>false</tt>. 211 * 212 * @param e element to be added to this set 213 * @return <tt>true</tt> if this set did not already contain the specified 214 * element 215 */ 216 override bool add(E e) { 217 return map.put(e, PRESENT) is null; 218 } 219 220 /** 221 * Removes the specified element from this set if it is present. 222 * More formally, removes an element <tt>e</tt> such that 223 * <tt>(o is null ? e is null : o.equals(e))</tt>, 224 * if this set contains such an element. Returns <tt>true</tt> if 225 * this set contained the element (or equivalently, if this set 226 * changed as a result of the call). (This set will not contain the 227 * element once the call returns.) 228 * 229 * @param o object to be removed from this set, if present 230 * @return <tt>true</tt> if the set contained the specified element 231 */ 232 override bool remove(E o) { 233 return map.remove(o) == PRESENT; 234 } 235 236 /** 237 * Removes all of the elements from this set. 238 * The set will be empty after this call returns. 239 */ 240 override void clear() { 241 map.clear(); 242 } 243 244 /** 245 * Returns a shallow copy of this <tt>HashSet</tt> instance: the elements 246 * themselves are not cloned. 247 * 248 * @return a shallow copy of this set 249 */ 250 // 251 // Object clone() { 252 // try { 253 // HashSet<E> newSet = (HashSet<E>) super.clone(); 254 // newSet.map = (HashMap<E, Object>) map.clone(); 255 // return newSet; 256 // } catch (CloneNotSupportedException e) { 257 // throw new InternalError(e); 258 // } 259 // } 260 261 /** 262 * Creates a <em><a href="Spliterator.html#binding">late-binding</a></em> 263 * and <em>fail-fast</em> {@link Spliterator} over the elements in this 264 * set. 265 * 266 * <p>The {@code Spliterator} reports {@link Spliterator#SIZED} and 267 * {@link Spliterator#DISTINCT}. Overriding implementations should document 268 * the reporting of additional characteristic values. 269 * 270 * @return a {@code Spliterator} over the elements in this set 271 */ 272 // Spliterator<E> spliterator() { 273 // return new HashMap.KeySpliterator!(E, Object)(map, 0, -1, 0, 0); 274 // } 275 276 override int opApply(scope int delegate(ref E) dg) { 277 int result = 0; 278 foreach (E v; map.byKey) { 279 result = dg(v); 280 if (result != 0) 281 return result; 282 } 283 return result; 284 } 285 286 override bool opEquals(IObject o) { 287 return opEquals(cast(Object) o); 288 } 289 290 override bool opEquals(Object o) { 291 return super.opEquals(o); 292 } 293 294 override size_t toHash() @trusted nothrow { 295 return super.toHash(); 296 } 297 298 override string toString() { 299 return super.toString(); 300 } 301 }