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 }
--- EOF ---