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