1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/rt/emul/compact/src/main/java/java/util/HashSet.java Tue Feb 26 16:54:16 2013 +0100
1.3 @@ -0,0 +1,260 @@
1.4 +/*
1.5 + * Copyright (c) 1997, 2010, Oracle and/or its affiliates. All rights reserved.
1.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
1.7 + *
1.8 + * This code is free software; you can redistribute it and/or modify it
1.9 + * under the terms of the GNU General Public License version 2 only, as
1.10 + * published by the Free Software Foundation. Oracle designates this
1.11 + * particular file as subject to the "Classpath" exception as provided
1.12 + * by Oracle in the LICENSE file that accompanied this code.
1.13 + *
1.14 + * This code is distributed in the hope that it will be useful, but WITHOUT
1.15 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
1.16 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1.17 + * version 2 for more details (a copy is included in the LICENSE file that
1.18 + * accompanied this code).
1.19 + *
1.20 + * You should have received a copy of the GNU General Public License version
1.21 + * 2 along with this work; if not, write to the Free Software Foundation,
1.22 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
1.23 + *
1.24 + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
1.25 + * or visit www.oracle.com if you need additional information or have any
1.26 + * questions.
1.27 + */
1.28 +
1.29 +package java.util;
1.30 +
1.31 +/**
1.32 + * This class implements the <tt>Set</tt> interface, backed by a hash table
1.33 + * (actually a <tt>HashMap</tt> instance). It makes no guarantees as to the
1.34 + * iteration order of the set; in particular, it does not guarantee that the
1.35 + * order will remain constant over time. This class permits the <tt>null</tt>
1.36 + * element.
1.37 + *
1.38 + * <p>This class offers constant time performance for the basic operations
1.39 + * (<tt>add</tt>, <tt>remove</tt>, <tt>contains</tt> and <tt>size</tt>),
1.40 + * assuming the hash function disperses the elements properly among the
1.41 + * buckets. Iterating over this set requires time proportional to the sum of
1.42 + * the <tt>HashSet</tt> instance's size (the number of elements) plus the
1.43 + * "capacity" of the backing <tt>HashMap</tt> instance (the number of
1.44 + * buckets). Thus, it's very important not to set the initial capacity too
1.45 + * high (or the load factor too low) if iteration performance is important.
1.46 + *
1.47 + * <p><strong>Note that this implementation is not synchronized.</strong>
1.48 + * If multiple threads access a hash set concurrently, and at least one of
1.49 + * the threads modifies the set, it <i>must</i> be synchronized externally.
1.50 + * This is typically accomplished by synchronizing on some object that
1.51 + * naturally encapsulates the set.
1.52 + *
1.53 + * If no such object exists, the set should be "wrapped" using the
1.54 + * {@link Collections#synchronizedSet Collections.synchronizedSet}
1.55 + * method. This is best done at creation time, to prevent accidental
1.56 + * unsynchronized access to the set:<pre>
1.57 + * Set s = Collections.synchronizedSet(new HashSet(...));</pre>
1.58 + *
1.59 + * <p>The iterators returned by this class's <tt>iterator</tt> method are
1.60 + * <i>fail-fast</i>: if the set is modified at any time after the iterator is
1.61 + * created, in any way except through the iterator's own <tt>remove</tt>
1.62 + * method, the Iterator throws a {@link ConcurrentModificationException}.
1.63 + * Thus, in the face of concurrent modification, the iterator fails quickly
1.64 + * and cleanly, rather than risking arbitrary, non-deterministic behavior at
1.65 + * an undetermined time in the future.
1.66 + *
1.67 + * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
1.68 + * as it is, generally speaking, impossible to make any hard guarantees in the
1.69 + * presence of unsynchronized concurrent modification. Fail-fast iterators
1.70 + * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
1.71 + * Therefore, it would be wrong to write a program that depended on this
1.72 + * exception for its correctness: <i>the fail-fast behavior of iterators
1.73 + * should be used only to detect bugs.</i>
1.74 + *
1.75 + * <p>This class is a member of the
1.76 + * <a href="{@docRoot}/../technotes/guides/collections/index.html">
1.77 + * Java Collections Framework</a>.
1.78 + *
1.79 + * @param <E> the type of elements maintained by this set
1.80 + *
1.81 + * @author Josh Bloch
1.82 + * @author Neal Gafter
1.83 + * @see Collection
1.84 + * @see Set
1.85 + * @see TreeSet
1.86 + * @see HashMap
1.87 + * @since 1.2
1.88 + */
1.89 +
1.90 +public class HashSet<E>
1.91 + extends AbstractSet<E>
1.92 + implements Set<E>, Cloneable, java.io.Serializable
1.93 +{
1.94 + static final long serialVersionUID = -5024744406713321676L;
1.95 +
1.96 + private transient HashMap<E,Object> map;
1.97 +
1.98 + // Dummy value to associate with an Object in the backing Map
1.99 + private static final Object PRESENT = new Object();
1.100 +
1.101 + /**
1.102 + * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
1.103 + * default initial capacity (16) and load factor (0.75).
1.104 + */
1.105 + public HashSet() {
1.106 + map = new HashMap<>();
1.107 + }
1.108 +
1.109 + /**
1.110 + * Constructs a new set containing the elements in the specified
1.111 + * collection. The <tt>HashMap</tt> is created with default load factor
1.112 + * (0.75) and an initial capacity sufficient to contain the elements in
1.113 + * the specified collection.
1.114 + *
1.115 + * @param c the collection whose elements are to be placed into this set
1.116 + * @throws NullPointerException if the specified collection is null
1.117 + */
1.118 + public HashSet(Collection<? extends E> c) {
1.119 + map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
1.120 + addAll(c);
1.121 + }
1.122 +
1.123 + /**
1.124 + * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
1.125 + * the specified initial capacity and the specified load factor.
1.126 + *
1.127 + * @param initialCapacity the initial capacity of the hash map
1.128 + * @param loadFactor the load factor of the hash map
1.129 + * @throws IllegalArgumentException if the initial capacity is less
1.130 + * than zero, or if the load factor is nonpositive
1.131 + */
1.132 + public HashSet(int initialCapacity, float loadFactor) {
1.133 + map = new HashMap<>(initialCapacity, loadFactor);
1.134 + }
1.135 +
1.136 + /**
1.137 + * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
1.138 + * the specified initial capacity and default load factor (0.75).
1.139 + *
1.140 + * @param initialCapacity the initial capacity of the hash table
1.141 + * @throws IllegalArgumentException if the initial capacity is less
1.142 + * than zero
1.143 + */
1.144 + public HashSet(int initialCapacity) {
1.145 + map = new HashMap<>(initialCapacity);
1.146 + }
1.147 +
1.148 + /**
1.149 + * Constructs a new, empty linked hash set. (This package private
1.150 + * constructor is only used by LinkedHashSet.) The backing
1.151 + * HashMap instance is a LinkedHashMap with the specified initial
1.152 + * capacity and the specified load factor.
1.153 + *
1.154 + * @param initialCapacity the initial capacity of the hash map
1.155 + * @param loadFactor the load factor of the hash map
1.156 + * @param dummy ignored (distinguishes this
1.157 + * constructor from other int, float constructor.)
1.158 + * @throws IllegalArgumentException if the initial capacity is less
1.159 + * than zero, or if the load factor is nonpositive
1.160 + */
1.161 + HashSet(int initialCapacity, float loadFactor, boolean dummy) {
1.162 + map = new LinkedHashMap<>(initialCapacity, loadFactor);
1.163 + }
1.164 +
1.165 + /**
1.166 + * Returns an iterator over the elements in this set. The elements
1.167 + * are returned in no particular order.
1.168 + *
1.169 + * @return an Iterator over the elements in this set
1.170 + * @see ConcurrentModificationException
1.171 + */
1.172 + public Iterator<E> iterator() {
1.173 + return map.keySet().iterator();
1.174 + }
1.175 +
1.176 + /**
1.177 + * Returns the number of elements in this set (its cardinality).
1.178 + *
1.179 + * @return the number of elements in this set (its cardinality)
1.180 + */
1.181 + public int size() {
1.182 + return map.size();
1.183 + }
1.184 +
1.185 + /**
1.186 + * Returns <tt>true</tt> if this set contains no elements.
1.187 + *
1.188 + * @return <tt>true</tt> if this set contains no elements
1.189 + */
1.190 + public boolean isEmpty() {
1.191 + return map.isEmpty();
1.192 + }
1.193 +
1.194 + /**
1.195 + * Returns <tt>true</tt> if this set contains the specified element.
1.196 + * More formally, returns <tt>true</tt> if and only if this set
1.197 + * contains an element <tt>e</tt> such that
1.198 + * <tt>(o==null ? e==null : o.equals(e))</tt>.
1.199 + *
1.200 + * @param o element whose presence in this set is to be tested
1.201 + * @return <tt>true</tt> if this set contains the specified element
1.202 + */
1.203 + public boolean contains(Object o) {
1.204 + return map.containsKey(o);
1.205 + }
1.206 +
1.207 + /**
1.208 + * Adds the specified element to this set if it is not already present.
1.209 + * More formally, adds the specified element <tt>e</tt> to this set if
1.210 + * this set contains no element <tt>e2</tt> such that
1.211 + * <tt>(e==null ? e2==null : e.equals(e2))</tt>.
1.212 + * If this set already contains the element, the call leaves the set
1.213 + * unchanged and returns <tt>false</tt>.
1.214 + *
1.215 + * @param e element to be added to this set
1.216 + * @return <tt>true</tt> if this set did not already contain the specified
1.217 + * element
1.218 + */
1.219 + public boolean add(E e) {
1.220 + return map.put(e, PRESENT)==null;
1.221 + }
1.222 +
1.223 + /**
1.224 + * Removes the specified element from this set if it is present.
1.225 + * More formally, removes an element <tt>e</tt> such that
1.226 + * <tt>(o==null ? e==null : o.equals(e))</tt>,
1.227 + * if this set contains such an element. Returns <tt>true</tt> if
1.228 + * this set contained the element (or equivalently, if this set
1.229 + * changed as a result of the call). (This set will not contain the
1.230 + * element once the call returns.)
1.231 + *
1.232 + * @param o object to be removed from this set, if present
1.233 + * @return <tt>true</tt> if the set contained the specified element
1.234 + */
1.235 + public boolean remove(Object o) {
1.236 + return map.remove(o)==PRESENT;
1.237 + }
1.238 +
1.239 + /**
1.240 + * Removes all of the elements from this set.
1.241 + * The set will be empty after this call returns.
1.242 + */
1.243 + public void clear() {
1.244 + map.clear();
1.245 + }
1.246 +
1.247 + /**
1.248 + * Returns a shallow copy of this <tt>HashSet</tt> instance: the elements
1.249 + * themselves are not cloned.
1.250 + *
1.251 + * @return a shallow copy of this set
1.252 + */
1.253 + public Object clone() {
1.254 + try {
1.255 + HashSet<E> newSet = (HashSet<E>) super.clone();
1.256 + newSet.map = (HashMap<E, Object>) map.clone();
1.257 + return newSet;
1.258 + } catch (CloneNotSupportedException e) {
1.259 + throw new InternalError();
1.260 + }
1.261 + }
1.262 +
1.263 +}