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&nbsp;?&nbsp;e is null&nbsp;:&nbsp;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&nbsp;?&nbsp;e2 is null&nbsp;:&nbsp;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&nbsp;?&nbsp;e is null&nbsp;:&nbsp;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 }