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