1/*
2 *  Licensed to the Apache Software Foundation (ASF) under one or more
3 *  contributor license agreements.  See the NOTICE file distributed with
4 *  this work for additional information regarding copyright ownership.
5 *  The ASF licenses this file to You under the Apache License, Version 2.0
6 *  (the "License"); you may not use this file except in compliance with
7 *  the License.  You may obtain a copy of the License at
8 *
9 *     http://www.apache.org/licenses/LICENSE-2.0
10 *
11 *  Unless required by applicable law or agreed to in writing, software
12 *  distributed under the License is distributed on an "AS IS" BASIS,
13 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 *  See the License for the specific language governing permissions and
15 *  limitations under the License.
16 */
17
18package java.util;
19
20import java.io.IOException;
21import java.io.ObjectInputStream;
22import java.io.ObjectOutputStream;
23import java.io.Serializable;
24
25/**
26 * HashSet is an implementation of a Set. All optional operations (adding and
27 * removing) are supported. The elements can be any objects.
28 */
29public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable,
30        Serializable {
31
32    private static final long serialVersionUID = -5024744406713321676L;
33
34    transient HashMap<E, HashSet<E>> backingMap;
35
36    /**
37     * Constructs a new empty instance of {@code HashSet}.
38     */
39    public HashSet() {
40        this(new HashMap<E, HashSet<E>>());
41    }
42
43    /**
44     * Constructs a new instance of {@code HashSet} with the specified capacity.
45     *
46     * @param capacity
47     *            the initial capacity of this {@code HashSet}.
48     */
49    public HashSet(int capacity) {
50        this(new HashMap<E, HashSet<E>>(capacity));
51    }
52
53    /**
54     * Constructs a new instance of {@code HashSet} with the specified capacity
55     * and load factor.
56     *
57     * @param capacity
58     *            the initial capacity.
59     * @param loadFactor
60     *            the initial load factor.
61     */
62    public HashSet(int capacity, float loadFactor) {
63        this(new HashMap<E, HashSet<E>>(capacity, loadFactor));
64    }
65
66    /**
67     * Constructs a new instance of {@code HashSet} containing the unique
68     * elements in the specified collection.
69     *
70     * @param collection
71     *            the collection of elements to add.
72     */
73    public HashSet(Collection<? extends E> collection) {
74        this(new HashMap<E, HashSet<E>>(collection.size() < 6 ? 11 : collection
75                .size() * 2));
76        for (E e : collection) {
77            add(e);
78        }
79    }
80
81    HashSet(HashMap<E, HashSet<E>> backingMap) {
82        this.backingMap = backingMap;
83    }
84
85    /**
86     * Adds the specified object to this {@code HashSet} if not already present.
87     *
88     * @param object
89     *            the object to add.
90     * @return {@code true} when this {@code HashSet} did not already contain
91     *         the object, {@code false} otherwise
92     */
93    @Override
94    public boolean add(E object) {
95        return backingMap.put(object, this) == null;
96    }
97
98    /**
99     * Removes all elements from this {@code HashSet}, leaving it empty.
100     *
101     * @see #isEmpty
102     * @see #size
103     */
104    @Override
105    public void clear() {
106        backingMap.clear();
107    }
108
109    /**
110     * Returns a new {@code HashSet} with the same elements and size as this
111     * {@code HashSet}.
112     *
113     * @return a shallow copy of this {@code HashSet}.
114     * @see java.lang.Cloneable
115     */
116    @Override
117    @SuppressWarnings("unchecked")
118    public Object clone() {
119        try {
120            HashSet<E> clone = (HashSet<E>) super.clone();
121            clone.backingMap = (HashMap<E, HashSet<E>>) backingMap.clone();
122            return clone;
123        } catch (CloneNotSupportedException e) {
124            throw new AssertionError(e);
125        }
126    }
127
128    /**
129     * Searches this {@code HashSet} for the specified object.
130     *
131     * @param object
132     *            the object to search for.
133     * @return {@code true} if {@code object} is an element of this
134     *         {@code HashSet}, {@code false} otherwise.
135     */
136    @Override
137    public boolean contains(Object object) {
138        return backingMap.containsKey(object);
139    }
140
141    /**
142     * Returns true if this {@code HashSet} has no elements, false otherwise.
143     *
144     * @return {@code true} if this {@code HashSet} has no elements,
145     *         {@code false} otherwise.
146     * @see #size
147     */
148    @Override
149    public boolean isEmpty() {
150        return backingMap.isEmpty();
151    }
152
153    /**
154     * Returns an Iterator on the elements of this {@code HashSet}.
155     *
156     * @return an Iterator on the elements of this {@code HashSet}.
157     * @see Iterator
158     */
159    @Override
160    public Iterator<E> iterator() {
161        return backingMap.keySet().iterator();
162    }
163
164    /**
165     * Removes the specified object from this {@code HashSet}.
166     *
167     * @param object
168     *            the object to remove.
169     * @return {@code true} if the object was removed, {@code false} otherwise.
170     */
171    @Override
172    public boolean remove(Object object) {
173        return backingMap.remove(object) != null;
174    }
175
176    /**
177     * Returns the number of elements in this {@code HashSet}.
178     *
179     * @return the number of elements in this {@code HashSet}.
180     */
181    @Override
182    public int size() {
183        return backingMap.size();
184    }
185
186    private void writeObject(ObjectOutputStream stream) throws IOException {
187        stream.defaultWriteObject();
188        stream.writeInt(backingMap.table.length);
189        stream.writeFloat(HashMap.DEFAULT_LOAD_FACTOR);
190        stream.writeInt(size());
191        for (E e : this) {
192            stream.writeObject(e);
193        }
194    }
195
196    @SuppressWarnings("unchecked")
197    private void readObject(ObjectInputStream stream) throws IOException,
198            ClassNotFoundException {
199        stream.defaultReadObject();
200        int length = stream.readInt();
201        float loadFactor = stream.readFloat();
202        backingMap = createBackingMap(length, loadFactor);
203        int elementCount = stream.readInt();
204        for (int i = elementCount; --i >= 0;) {
205            E key = (E) stream.readObject();
206            backingMap.put(key, this);
207        }
208    }
209
210    HashMap<E, HashSet<E>> createBackingMap(int capacity, float loadFactor) {
211        return new HashMap<E, HashSet<E>>(capacity, loadFactor);
212    }
213}
214