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