1.1 --- a/emul/compact/src/main/java/java/util/HashSet.java Tue Feb 26 14:55:55 2013 +0100
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,260 +0,0 @@
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 -}