1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/rt/emul/compact/src/main/java/java/util/AbstractCollection.java Tue Feb 26 16:54:16 2013 +0100
1.3 @@ -0,0 +1,457 @@
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 provides a skeletal implementation of the <tt>Collection</tt>
1.33 + * interface, to minimize the effort required to implement this interface. <p>
1.34 + *
1.35 + * To implement an unmodifiable collection, the programmer needs only to
1.36 + * extend this class and provide implementations for the <tt>iterator</tt> and
1.37 + * <tt>size</tt> methods. (The iterator returned by the <tt>iterator</tt>
1.38 + * method must implement <tt>hasNext</tt> and <tt>next</tt>.)<p>
1.39 + *
1.40 + * To implement a modifiable collection, the programmer must additionally
1.41 + * override this class's <tt>add</tt> method (which otherwise throws an
1.42 + * <tt>UnsupportedOperationException</tt>), and the iterator returned by the
1.43 + * <tt>iterator</tt> method must additionally implement its <tt>remove</tt>
1.44 + * method.<p>
1.45 + *
1.46 + * The programmer should generally provide a void (no argument) and
1.47 + * <tt>Collection</tt> constructor, as per the recommendation in the
1.48 + * <tt>Collection</tt> interface specification.<p>
1.49 + *
1.50 + * The documentation for each non-abstract method in this class describes its
1.51 + * implementation in detail. Each of these methods may be overridden if
1.52 + * the collection being implemented admits a more efficient implementation.<p>
1.53 + *
1.54 + * This class is a member of the
1.55 + * <a href="{@docRoot}/../technotes/guides/collections/index.html">
1.56 + * Java Collections Framework</a>.
1.57 + *
1.58 + * @author Josh Bloch
1.59 + * @author Neal Gafter
1.60 + * @see Collection
1.61 + * @since 1.2
1.62 + */
1.63 +
1.64 +public abstract class AbstractCollection<E> implements Collection<E> {
1.65 + /**
1.66 + * Sole constructor. (For invocation by subclass constructors, typically
1.67 + * implicit.)
1.68 + */
1.69 + protected AbstractCollection() {
1.70 + }
1.71 +
1.72 + // Query Operations
1.73 +
1.74 + /**
1.75 + * Returns an iterator over the elements contained in this collection.
1.76 + *
1.77 + * @return an iterator over the elements contained in this collection
1.78 + */
1.79 + public abstract Iterator<E> iterator();
1.80 +
1.81 + public abstract int size();
1.82 +
1.83 + /**
1.84 + * {@inheritDoc}
1.85 + *
1.86 + * <p>This implementation returns <tt>size() == 0</tt>.
1.87 + */
1.88 + public boolean isEmpty() {
1.89 + return size() == 0;
1.90 + }
1.91 +
1.92 + /**
1.93 + * {@inheritDoc}
1.94 + *
1.95 + * <p>This implementation iterates over the elements in the collection,
1.96 + * checking each element in turn for equality with the specified element.
1.97 + *
1.98 + * @throws ClassCastException {@inheritDoc}
1.99 + * @throws NullPointerException {@inheritDoc}
1.100 + */
1.101 + public boolean contains(Object o) {
1.102 + Iterator<E> it = iterator();
1.103 + if (o==null) {
1.104 + while (it.hasNext())
1.105 + if (it.next()==null)
1.106 + return true;
1.107 + } else {
1.108 + while (it.hasNext())
1.109 + if (o.equals(it.next()))
1.110 + return true;
1.111 + }
1.112 + return false;
1.113 + }
1.114 +
1.115 + /**
1.116 + * {@inheritDoc}
1.117 + *
1.118 + * <p>This implementation returns an array containing all the elements
1.119 + * returned by this collection's iterator, in the same order, stored in
1.120 + * consecutive elements of the array, starting with index {@code 0}.
1.121 + * The length of the returned array is equal to the number of elements
1.122 + * returned by the iterator, even if the size of this collection changes
1.123 + * during iteration, as might happen if the collection permits
1.124 + * concurrent modification during iteration. The {@code size} method is
1.125 + * called only as an optimization hint; the correct result is returned
1.126 + * even if the iterator returns a different number of elements.
1.127 + *
1.128 + * <p>This method is equivalent to:
1.129 + *
1.130 + * <pre> {@code
1.131 + * List<E> list = new ArrayList<E>(size());
1.132 + * for (E e : this)
1.133 + * list.add(e);
1.134 + * return list.toArray();
1.135 + * }</pre>
1.136 + */
1.137 + public Object[] toArray() {
1.138 + // Estimate size of array; be prepared to see more or fewer elements
1.139 + Object[] r = new Object[size()];
1.140 + Iterator<E> it = iterator();
1.141 + for (int i = 0; i < r.length; i++) {
1.142 + if (! it.hasNext()) // fewer elements than expected
1.143 + return Arrays.copyOf(r, i);
1.144 + r[i] = it.next();
1.145 + }
1.146 + return it.hasNext() ? finishToArray(r, it) : r;
1.147 + }
1.148 +
1.149 + /**
1.150 + * {@inheritDoc}
1.151 + *
1.152 + * <p>This implementation returns an array containing all the elements
1.153 + * returned by this collection's iterator in the same order, stored in
1.154 + * consecutive elements of the array, starting with index {@code 0}.
1.155 + * If the number of elements returned by the iterator is too large to
1.156 + * fit into the specified array, then the elements are returned in a
1.157 + * newly allocated array with length equal to the number of elements
1.158 + * returned by the iterator, even if the size of this collection
1.159 + * changes during iteration, as might happen if the collection permits
1.160 + * concurrent modification during iteration. The {@code size} method is
1.161 + * called only as an optimization hint; the correct result is returned
1.162 + * even if the iterator returns a different number of elements.
1.163 + *
1.164 + * <p>This method is equivalent to:
1.165 + *
1.166 + * <pre> {@code
1.167 + * List<E> list = new ArrayList<E>(size());
1.168 + * for (E e : this)
1.169 + * list.add(e);
1.170 + * return list.toArray(a);
1.171 + * }</pre>
1.172 + *
1.173 + * @throws ArrayStoreException {@inheritDoc}
1.174 + * @throws NullPointerException {@inheritDoc}
1.175 + */
1.176 + public <T> T[] toArray(T[] a) {
1.177 + // Estimate size of array; be prepared to see more or fewer elements
1.178 + int size = size();
1.179 + T[] r = a.length >= size ? a :
1.180 + (T[])java.lang.reflect.Array
1.181 + .newInstance(a.getClass().getComponentType(), size);
1.182 + Iterator<E> it = iterator();
1.183 +
1.184 + for (int i = 0; i < r.length; i++) {
1.185 + if (! it.hasNext()) { // fewer elements than expected
1.186 + if (a != r)
1.187 + return Arrays.copyOf(r, i);
1.188 + r[i] = null; // null-terminate
1.189 + return r;
1.190 + }
1.191 + r[i] = (T)it.next();
1.192 + }
1.193 + return it.hasNext() ? finishToArray(r, it) : r;
1.194 + }
1.195 +
1.196 + /**
1.197 + * The maximum size of array to allocate.
1.198 + * Some VMs reserve some header words in an array.
1.199 + * Attempts to allocate larger arrays may result in
1.200 + * OutOfMemoryError: Requested array size exceeds VM limit
1.201 + */
1.202 + private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
1.203 +
1.204 + /**
1.205 + * Reallocates the array being used within toArray when the iterator
1.206 + * returned more elements than expected, and finishes filling it from
1.207 + * the iterator.
1.208 + *
1.209 + * @param r the array, replete with previously stored elements
1.210 + * @param it the in-progress iterator over this collection
1.211 + * @return array containing the elements in the given array, plus any
1.212 + * further elements returned by the iterator, trimmed to size
1.213 + */
1.214 + private static <T> T[] finishToArray(T[] r, Iterator<?> it) {
1.215 + int i = r.length;
1.216 + while (it.hasNext()) {
1.217 + int cap = r.length;
1.218 + if (i == cap) {
1.219 + int newCap = cap + (cap >> 1) + 1;
1.220 + // overflow-conscious code
1.221 + if (newCap - MAX_ARRAY_SIZE > 0)
1.222 + newCap = hugeCapacity(cap + 1);
1.223 + r = Arrays.copyOf(r, newCap);
1.224 + }
1.225 + r[i++] = (T)it.next();
1.226 + }
1.227 + // trim if overallocated
1.228 + return (i == r.length) ? r : Arrays.copyOf(r, i);
1.229 + }
1.230 +
1.231 + private static int hugeCapacity(int minCapacity) {
1.232 + if (minCapacity < 0) // overflow
1.233 + throw new OutOfMemoryError
1.234 + ("Required array size too large");
1.235 + return (minCapacity > MAX_ARRAY_SIZE) ?
1.236 + Integer.MAX_VALUE :
1.237 + MAX_ARRAY_SIZE;
1.238 + }
1.239 +
1.240 + // Modification Operations
1.241 +
1.242 + /**
1.243 + * {@inheritDoc}
1.244 + *
1.245 + * <p>This implementation always throws an
1.246 + * <tt>UnsupportedOperationException</tt>.
1.247 + *
1.248 + * @throws UnsupportedOperationException {@inheritDoc}
1.249 + * @throws ClassCastException {@inheritDoc}
1.250 + * @throws NullPointerException {@inheritDoc}
1.251 + * @throws IllegalArgumentException {@inheritDoc}
1.252 + * @throws IllegalStateException {@inheritDoc}
1.253 + */
1.254 + public boolean add(E e) {
1.255 + throw new UnsupportedOperationException();
1.256 + }
1.257 +
1.258 + /**
1.259 + * {@inheritDoc}
1.260 + *
1.261 + * <p>This implementation iterates over the collection looking for the
1.262 + * specified element. If it finds the element, it removes the element
1.263 + * from the collection using the iterator's remove method.
1.264 + *
1.265 + * <p>Note that this implementation throws an
1.266 + * <tt>UnsupportedOperationException</tt> if the iterator returned by this
1.267 + * collection's iterator method does not implement the <tt>remove</tt>
1.268 + * method and this collection contains the specified object.
1.269 + *
1.270 + * @throws UnsupportedOperationException {@inheritDoc}
1.271 + * @throws ClassCastException {@inheritDoc}
1.272 + * @throws NullPointerException {@inheritDoc}
1.273 + */
1.274 + public boolean remove(Object o) {
1.275 + Iterator<E> it = iterator();
1.276 + if (o==null) {
1.277 + while (it.hasNext()) {
1.278 + if (it.next()==null) {
1.279 + it.remove();
1.280 + return true;
1.281 + }
1.282 + }
1.283 + } else {
1.284 + while (it.hasNext()) {
1.285 + if (o.equals(it.next())) {
1.286 + it.remove();
1.287 + return true;
1.288 + }
1.289 + }
1.290 + }
1.291 + return false;
1.292 + }
1.293 +
1.294 +
1.295 + // Bulk Operations
1.296 +
1.297 + /**
1.298 + * {@inheritDoc}
1.299 + *
1.300 + * <p>This implementation iterates over the specified collection,
1.301 + * checking each element returned by the iterator in turn to see
1.302 + * if it's contained in this collection. If all elements are so
1.303 + * contained <tt>true</tt> is returned, otherwise <tt>false</tt>.
1.304 + *
1.305 + * @throws ClassCastException {@inheritDoc}
1.306 + * @throws NullPointerException {@inheritDoc}
1.307 + * @see #contains(Object)
1.308 + */
1.309 + public boolean containsAll(Collection<?> c) {
1.310 + for (Object e : c)
1.311 + if (!contains(e))
1.312 + return false;
1.313 + return true;
1.314 + }
1.315 +
1.316 + /**
1.317 + * {@inheritDoc}
1.318 + *
1.319 + * <p>This implementation iterates over the specified collection, and adds
1.320 + * each object returned by the iterator to this collection, in turn.
1.321 + *
1.322 + * <p>Note that this implementation will throw an
1.323 + * <tt>UnsupportedOperationException</tt> unless <tt>add</tt> is
1.324 + * overridden (assuming the specified collection is non-empty).
1.325 + *
1.326 + * @throws UnsupportedOperationException {@inheritDoc}
1.327 + * @throws ClassCastException {@inheritDoc}
1.328 + * @throws NullPointerException {@inheritDoc}
1.329 + * @throws IllegalArgumentException {@inheritDoc}
1.330 + * @throws IllegalStateException {@inheritDoc}
1.331 + *
1.332 + * @see #add(Object)
1.333 + */
1.334 + public boolean addAll(Collection<? extends E> c) {
1.335 + boolean modified = false;
1.336 + for (E e : c)
1.337 + if (add(e))
1.338 + modified = true;
1.339 + return modified;
1.340 + }
1.341 +
1.342 + /**
1.343 + * {@inheritDoc}
1.344 + *
1.345 + * <p>This implementation iterates over this collection, checking each
1.346 + * element returned by the iterator in turn to see if it's contained
1.347 + * in the specified collection. If it's so contained, it's removed from
1.348 + * this collection with the iterator's <tt>remove</tt> method.
1.349 + *
1.350 + * <p>Note that this implementation will throw an
1.351 + * <tt>UnsupportedOperationException</tt> if the iterator returned by the
1.352 + * <tt>iterator</tt> method does not implement the <tt>remove</tt> method
1.353 + * and this collection contains one or more elements in common with the
1.354 + * specified collection.
1.355 + *
1.356 + * @throws UnsupportedOperationException {@inheritDoc}
1.357 + * @throws ClassCastException {@inheritDoc}
1.358 + * @throws NullPointerException {@inheritDoc}
1.359 + *
1.360 + * @see #remove(Object)
1.361 + * @see #contains(Object)
1.362 + */
1.363 + public boolean removeAll(Collection<?> c) {
1.364 + boolean modified = false;
1.365 + Iterator<?> it = iterator();
1.366 + while (it.hasNext()) {
1.367 + if (c.contains(it.next())) {
1.368 + it.remove();
1.369 + modified = true;
1.370 + }
1.371 + }
1.372 + return modified;
1.373 + }
1.374 +
1.375 + /**
1.376 + * {@inheritDoc}
1.377 + *
1.378 + * <p>This implementation iterates over this collection, checking each
1.379 + * element returned by the iterator in turn to see if it's contained
1.380 + * in the specified collection. If it's not so contained, it's removed
1.381 + * from this collection with the iterator's <tt>remove</tt> method.
1.382 + *
1.383 + * <p>Note that this implementation will throw an
1.384 + * <tt>UnsupportedOperationException</tt> if the iterator returned by the
1.385 + * <tt>iterator</tt> method does not implement the <tt>remove</tt> method
1.386 + * and this collection contains one or more elements not present in the
1.387 + * specified collection.
1.388 + *
1.389 + * @throws UnsupportedOperationException {@inheritDoc}
1.390 + * @throws ClassCastException {@inheritDoc}
1.391 + * @throws NullPointerException {@inheritDoc}
1.392 + *
1.393 + * @see #remove(Object)
1.394 + * @see #contains(Object)
1.395 + */
1.396 + public boolean retainAll(Collection<?> c) {
1.397 + boolean modified = false;
1.398 + Iterator<E> it = iterator();
1.399 + while (it.hasNext()) {
1.400 + if (!c.contains(it.next())) {
1.401 + it.remove();
1.402 + modified = true;
1.403 + }
1.404 + }
1.405 + return modified;
1.406 + }
1.407 +
1.408 + /**
1.409 + * {@inheritDoc}
1.410 + *
1.411 + * <p>This implementation iterates over this collection, removing each
1.412 + * element using the <tt>Iterator.remove</tt> operation. Most
1.413 + * implementations will probably choose to override this method for
1.414 + * efficiency.
1.415 + *
1.416 + * <p>Note that this implementation will throw an
1.417 + * <tt>UnsupportedOperationException</tt> if the iterator returned by this
1.418 + * collection's <tt>iterator</tt> method does not implement the
1.419 + * <tt>remove</tt> method and this collection is non-empty.
1.420 + *
1.421 + * @throws UnsupportedOperationException {@inheritDoc}
1.422 + */
1.423 + public void clear() {
1.424 + Iterator<E> it = iterator();
1.425 + while (it.hasNext()) {
1.426 + it.next();
1.427 + it.remove();
1.428 + }
1.429 + }
1.430 +
1.431 +
1.432 + // String conversion
1.433 +
1.434 + /**
1.435 + * Returns a string representation of this collection. The string
1.436 + * representation consists of a list of the collection's elements in the
1.437 + * order they are returned by its iterator, enclosed in square brackets
1.438 + * (<tt>"[]"</tt>). Adjacent elements are separated by the characters
1.439 + * <tt>", "</tt> (comma and space). Elements are converted to strings as
1.440 + * by {@link String#valueOf(Object)}.
1.441 + *
1.442 + * @return a string representation of this collection
1.443 + */
1.444 + public String toString() {
1.445 + Iterator<E> it = iterator();
1.446 + if (! it.hasNext())
1.447 + return "[]";
1.448 +
1.449 + StringBuilder sb = new StringBuilder();
1.450 + sb.append('[');
1.451 + for (;;) {
1.452 + E e = it.next();
1.453 + sb.append(e == this ? "(this Collection)" : e);
1.454 + if (! it.hasNext())
1.455 + return sb.append(']').toString();
1.456 + sb.append(',').append(' ');
1.457 + }
1.458 + }
1.459 +
1.460 +}