1 /* 2 * Copyright (c) 1997, 2019, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 26 package java.util; 27 28 /** 29 * This class provides a skeletal implementation of the {@code Collection} 30 * interface, to minimize the effort required to implement this interface. <p> 31 * 32 * To implement an unmodifiable collection, the programmer needs only to 33 * extend this class and provide implementations for the {@code iterator} and 34 * {@code size} methods. (The iterator returned by the {@code iterator} 35 * method must implement {@code hasNext} and {@code next}.)<p> 36 * 37 * To implement a modifiable collection, the programmer must additionally 38 * override this class's {@code add} method (which otherwise throws an 39 * {@code UnsupportedOperationException}), and the iterator returned by the 40 * {@code iterator} method must additionally implement its {@code remove} 41 * method.<p> 42 * 43 * The programmer should generally provide a void (no argument) and 44 * {@code Collection} constructor, as per the recommendation in the 45 * {@code Collection} interface specification.<p> 46 * 47 * The documentation for each non-abstract method in this class describes its 48 * implementation in detail. Each of these methods may be overridden if 49 * the collection being implemented admits a more efficient implementation.<p> 50 * 51 * This class is a member of the 52 * <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework"> 53 * Java Collections Framework</a>. 54 * 55 * @author Josh Bloch 56 * @author Neal Gafter 57 * @see Collection 58 * @since 1.2 59 */ 60 61 public abstract class AbstractCollection<E> implements Collection<E> { 62 /** 63 * Sole constructor. (For invocation by subclass constructors, typically 64 * implicit.) 65 */ 66 protected AbstractCollection() { 67 } 68 69 // Query Operations 70 71 /** 72 * Returns an iterator over the elements contained in this collection. 73 * 74 * @return an iterator over the elements contained in this collection 75 */ 76 public abstract Iterator<E> iterator(); 77 78 public abstract int size(); 79 80 /** 81 * {@inheritDoc} 82 * 83 * @implSpec 84 * This implementation returns {@code size() == 0}. 85 */ 86 public boolean isEmpty() { 87 return size() == 0; 88 } 89 90 /** 91 * {@inheritDoc} 92 * 93 * @implSpec 94 * This implementation iterates over the elements in the collection, 95 * checking each element in turn for equality with the specified element. 96 * 97 * @throws ClassCastException {@inheritDoc} 98 * @throws NullPointerException {@inheritDoc} 99 */ 100 public boolean contains(Object o) { 101 Iterator<E> it = iterator(); 102 if (o==null) { 103 while (it.hasNext()) 104 if (it.next()==null) 105 return true; 106 } else { 107 while (it.hasNext()) 108 if (o.equals(it.next())) 109 return true; 110 } 111 return false; 112 } 113 114 /** 115 * {@inheritDoc} 116 * 117 * @implSpec 118 * This implementation returns an array containing all the elements 119 * returned by this collection's iterator, in the same order, stored in 120 * consecutive elements of the array, starting with index {@code 0}. 121 * The length of the returned array is equal to the number of elements 122 * returned by the iterator, even if the size of this collection changes 123 * during iteration, as might happen if the collection permits 124 * concurrent modification during iteration. The {@code size} method is 125 * called only as an optimization hint; the correct result is returned 126 * even if the iterator returns a different number of elements. 127 * 128 * <p>This method is equivalent to: 129 * 130 * <pre> {@code 131 * List<E> list = new ArrayList<E>(size()); 132 * for (E e : this) 133 * list.add(e); 134 * return list.toArray(); 135 * }</pre> 136 */ 137 public Object[] toArray() { 138 // Estimate size of array; be prepared to see more or fewer elements 139 Object[] r = new Object[size()]; 140 Iterator<E> it = iterator(); 141 for (int i = 0; i < r.length; i++) { 142 if (! it.hasNext()) // fewer elements than expected 143 return Arrays.copyOf(r, i); 144 r[i] = it.next(); 145 } 146 return it.hasNext() ? finishToArray(r, it) : r; 147 } 148 149 /** 150 * {@inheritDoc} 151 * 152 * @implSpec 153 * This implementation returns an array containing all the elements 154 * returned by this collection's iterator in the same order, stored in 155 * consecutive elements of the array, starting with index {@code 0}. 156 * If the number of elements returned by the iterator is too large to 157 * fit into the specified array, then the elements are returned in a 158 * newly allocated array with length equal to the number of elements 159 * returned by the iterator, even if the size of this collection 160 * changes during iteration, as might happen if the collection permits 161 * concurrent modification during iteration. The {@code size} method is 162 * called only as an optimization hint; the correct result is returned 163 * even if the iterator returns a different number of elements. 164 * 165 * <p>This method is equivalent to: 166 * 167 * <pre> {@code 168 * List<E> list = new ArrayList<E>(size()); 169 * for (E e : this) 170 * list.add(e); 171 * return list.toArray(a); 172 * }</pre> 173 * 174 * @throws ArrayStoreException {@inheritDoc} 175 * @throws NullPointerException {@inheritDoc} 176 */ 177 @SuppressWarnings("unchecked") 178 public <T> T[] toArray(T[] a) { 179 // Estimate size of array; be prepared to see more or fewer elements 180 int size = size(); 181 T[] r = a.length >= size ? a : 182 (T[])java.lang.reflect.Array 183 .newInstance(a.getClass().getComponentType(), size); 184 Iterator<E> it = iterator(); 185 186 for (int i = 0; i < r.length; i++) { 187 if (! it.hasNext()) { // fewer elements than expected 188 if (a == r) { 189 r[i] = null; // null-terminate 190 } else if (a.length < i) { 191 return Arrays.copyOf(r, i); 192 } else { 193 System.arraycopy(r, 0, a, 0, i); 194 if (a.length > i) { 195 a[i] = null; 196 } 197 } 198 return a; 199 } 200 r[i] = (T)it.next(); 201 } 202 // more elements than expected 203 return it.hasNext() ? finishToArray(r, it) : r; 204 } 205 206 /** 207 * The maximum size of array to allocate. 208 * Some VMs reserve some header words in an array. 209 * Attempts to allocate larger arrays may result in 210 * OutOfMemoryError: Requested array size exceeds VM limit 211 */ 212 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; 213 214 /** 215 * Reallocates the array being used within toArray when the iterator 216 * returned more elements than expected, and finishes filling it from 217 * the iterator. 218 * 219 * @param r the array, replete with previously stored elements 220 * @param it the in-progress iterator over this collection 221 * @return array containing the elements in the given array, plus any 222 * further elements returned by the iterator, trimmed to size 223 */ 224 @SuppressWarnings("unchecked") 225 private static <T> T[] finishToArray(T[] r, Iterator<?> it) { 226 int i = r.length; 227 while (it.hasNext()) { 228 int cap = r.length; 229 if (i == cap) { 230 int newCap = cap + (cap >> 1) + 1; 231 // overflow-conscious code 232 if (newCap - MAX_ARRAY_SIZE > 0) 233 newCap = hugeCapacity(cap + 1); 234 r = Arrays.copyOf(r, newCap); 235 } 236 r[i++] = (T)it.next(); 237 } 238 // trim if overallocated 239 return (i == r.length) ? r : Arrays.copyOf(r, i); 240 } 241 242 private static int hugeCapacity(int minCapacity) { 243 if (minCapacity < 0) // overflow 244 throw new OutOfMemoryError 245 ("Required array size too large"); 246 return (minCapacity > MAX_ARRAY_SIZE) ? 247 Integer.MAX_VALUE : 248 MAX_ARRAY_SIZE; 249 } 250 251 // Modification Operations 252 253 /** 254 * {@inheritDoc} 255 * 256 * @implSpec 257 * This implementation always throws an 258 * {@code UnsupportedOperationException}. 259 * 260 * @throws UnsupportedOperationException {@inheritDoc} 261 * @throws ClassCastException {@inheritDoc} 262 * @throws NullPointerException {@inheritDoc} 263 * @throws IllegalArgumentException {@inheritDoc} 264 * @throws IllegalStateException {@inheritDoc} 265 */ 266 public boolean add(E e) { 267 throw new UnsupportedOperationException(); 268 } 269 270 /** 271 * {@inheritDoc} 272 * 273 * @implSpec 274 * This implementation iterates over the collection looking for the 275 * specified element. If it finds the element, it removes the element 276 * from the collection using the iterator's remove method. 277 * 278 * <p>Note that this implementation throws an 279 * {@code UnsupportedOperationException} if the iterator returned by this 280 * collection's iterator method does not implement the {@code remove} 281 * method and this collection contains the specified object. 282 * 283 * @throws UnsupportedOperationException {@inheritDoc} 284 * @throws ClassCastException {@inheritDoc} 285 * @throws NullPointerException {@inheritDoc} 286 */ 287 public boolean remove(Object o) { 288 Iterator<E> it = iterator(); 289 if (o==null) { 290 while (it.hasNext()) { 291 if (it.next()==null) { 292 it.remove(); 293 return true; 294 } 295 } 296 } else { 297 while (it.hasNext()) { 298 if (o.equals(it.next())) { 299 it.remove(); 300 return true; 301 } 302 } 303 } 304 return false; 305 } 306 307 308 // Bulk Operations 309 310 /** 311 * {@inheritDoc} 312 * 313 * @implSpec 314 * This implementation iterates over the specified collection, 315 * checking each element returned by the iterator in turn to see 316 * if it's contained in this collection. If all elements are so 317 * contained {@code true} is returned, otherwise {@code false}. 318 * 319 * @implNote 320 * {@inheritDoc} 321 * 322 * @throws ClassCastException {@inheritDoc} 323 * @throws NullPointerException {@inheritDoc} 324 * @see #contains(Object) 325 */ 326 public boolean containsAll(Collection<?> c) { 327 for (Object e : c) 328 if (!contains(e)) 329 return false; 330 return true; 331 } 332 333 /** 334 * {@inheritDoc} 335 * 336 * @implSpec 337 * This implementation iterates over the specified collection, and adds 338 * each object returned by the iterator to this collection, in turn. 339 * 340 * <p>Note that this implementation will throw an 341 * {@code UnsupportedOperationException} unless {@code add} is 342 * overridden (assuming the specified collection is non-empty). 343 * 344 * @throws UnsupportedOperationException {@inheritDoc} 345 * @throws ClassCastException {@inheritDoc} 346 * @throws NullPointerException {@inheritDoc} 347 * @throws IllegalArgumentException {@inheritDoc} 348 * @throws IllegalStateException {@inheritDoc} 349 * 350 * @see #add(Object) 351 */ 352 public boolean addAll(Collection<? extends E> c) { 353 boolean modified = false; 354 for (E e : c) 355 if (add(e)) 356 modified = true; 357 return modified; 358 } 359 360 /** 361 * {@inheritDoc} 362 * 363 * @implSpec 364 * This implementation iterates over each element of this collection by 365 * obtaining an iterator from the {@code iterator} method. Each element 366 * is passed to the {@code contains} method of the specified collection. 367 * If {@code contains} returns {@code true}, the element is removed from this 368 * collection with the iterator's {@code remove} method. 369 * 370 * <p>Note that this implementation will throw an 371 * {@code UnsupportedOperationException} if the iterator returned by the 372 * {@code iterator} method does not implement the {@code remove} method 373 * and this collection contains one or more elements in common with the 374 * specified collection. 375 * 376 * @implNote 377 * {@inheritDoc} 378 * 379 * @throws UnsupportedOperationException {@inheritDoc} 380 * @throws ClassCastException {@inheritDoc} 381 * @throws NullPointerException {@inheritDoc} 382 * 383 * @see #remove(Object) 384 * @see #contains(Object) 385 */ 386 public boolean removeAll(Collection<?> c) { 387 Objects.requireNonNull(c); 388 boolean modified = false; 389 Iterator<?> it = iterator(); 390 while (it.hasNext()) { 391 if (c.contains(it.next())) { 392 it.remove(); 393 modified = true; 394 } 395 } 396 return modified; 397 } 398 399 /** 400 * {@inheritDoc} 401 * 402 * @implSpec 403 * This implementation iterates over each element of this collection by 404 * obtaining an iterator from the {@code iterator} method. Each element 405 * is passed to the {@code contains} method of the specified collection. 406 * If {@code contains} returns {@code false}, the element is removed from 407 * this collection with the iterator's {@code remove} method. 408 * 409 * <p>Note that this implementation will throw an 410 * {@code UnsupportedOperationException} if the iterator returned by the 411 * {@code iterator} method does not implement the {@code remove} method 412 * and this collection contains one or more elements not present in the 413 * specified collection. 414 * 415 * @implNote 416 * {@inheritDoc} 417 * 418 * @throws UnsupportedOperationException {@inheritDoc} 419 * @throws ClassCastException {@inheritDoc} 420 * @throws NullPointerException {@inheritDoc} 421 * 422 * @see #remove(Object) 423 * @see #contains(Object) 424 */ 425 public boolean retainAll(Collection<?> c) { 426 Objects.requireNonNull(c); 427 boolean modified = false; 428 Iterator<E> it = iterator(); 429 while (it.hasNext()) { 430 if (!c.contains(it.next())) { 431 it.remove(); 432 modified = true; 433 } 434 } 435 return modified; 436 } 437 438 /** 439 * {@inheritDoc} 440 * 441 * @implSpec 442 * This implementation iterates over this collection, removing each 443 * element using the {@code Iterator.remove} operation. Most 444 * implementations will probably choose to override this method for 445 * efficiency. 446 * 447 * <p>Note that this implementation will throw an 448 * {@code UnsupportedOperationException} if the iterator returned by this 449 * collection's {@code iterator} method does not implement the 450 * {@code remove} method and this collection is non-empty. 451 * 452 * @throws UnsupportedOperationException {@inheritDoc} 453 */ 454 public void clear() { 455 Iterator<E> it = iterator(); 456 while (it.hasNext()) { 457 it.next(); 458 it.remove(); 459 } 460 } 461 462 463 // String conversion 464 465 /** 466 * Returns a string representation of this collection. The string 467 * representation consists of a list of the collection's elements in the 468 * order they are returned by its iterator, enclosed in square brackets 469 * ({@code "[]"}). Adjacent elements are separated by the characters 470 * {@code ", "} (comma and space). Elements are converted to strings as 471 * by {@link String#valueOf(Object)}. 472 * 473 * @return a string representation of this collection 474 */ 475 public String toString() { 476 Iterator<E> it = iterator(); 477 if (! it.hasNext()) 478 return "[]"; 479 480 StringBuilder sb = new StringBuilder(); 481 sb.append('['); 482 for (;;) { 483 E e = it.next(); 484 sb.append(e == this ? "(this Collection)" : e); 485 if (! it.hasNext()) 486 return sb.append(']').toString(); 487 sb.append(',').append(' '); 488 } 489 } 490 491 }