Save This Page
Home » openjdk-7 » java » util » [javadoc | source]
    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       public <T> T[] toArray(T[] a) {
  174           // Estimate size of array; be prepared to see more or fewer elements
  175           int size = size();
  176           T[] r = a.length >= size ? a :
  177                     (T[])java.lang.reflect.Array
  178                     .newInstance(a.getClass().getComponentType(), size);
  179           Iterator<E> it = iterator();
  180   
  181           for (int i = 0; i < r.length; i++) {
  182               if (! it.hasNext()) { // fewer elements than expected
  183                   if (a != r)
  184                       return Arrays.copyOf(r, i);
  185                   r[i] = null; // null-terminate
  186                   return r;
  187               }
  188               r[i] = (T)it.next();
  189           }
  190           return it.hasNext() ? finishToArray(r, it) : r;
  191       }
  192   
  193       /**
  194        * The maximum size of array to allocate.
  195        * Some VMs reserve some header words in an array.
  196        * Attempts to allocate larger arrays may result in
  197        * OutOfMemoryError: Requested array size exceeds VM limit
  198        */
  199       private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
  200   
  201       /**
  202        * Reallocates the array being used within toArray when the iterator
  203        * returned more elements than expected, and finishes filling it from
  204        * the iterator.
  205        *
  206        * @param r the array, replete with previously stored elements
  207        * @param it the in-progress iterator over this collection
  208        * @return array containing the elements in the given array, plus any
  209        *         further elements returned by the iterator, trimmed to size
  210        */
  211       private static <T> T[] finishToArray(T[] r, Iterator<?> it) {
  212           int i = r.length;
  213           while (it.hasNext()) {
  214               int cap = r.length;
  215               if (i == cap) {
  216                   int newCap = cap + (cap >> 1) + 1;
  217                   // overflow-conscious code
  218                   if (newCap - MAX_ARRAY_SIZE > 0)
  219                       newCap = hugeCapacity(cap + 1);
  220                   r = Arrays.copyOf(r, newCap);
  221               }
  222               r[i++] = (T)it.next();
  223           }
  224           // trim if overallocated
  225           return (i == r.length) ? r : Arrays.copyOf(r, i);
  226       }
  227   
  228       private static int hugeCapacity(int minCapacity) {
  229           if (minCapacity < 0) // overflow
  230               throw new OutOfMemoryError
  231                   ("Required array size too large");
  232           return (minCapacity > MAX_ARRAY_SIZE) ?
  233               Integer.MAX_VALUE :
  234               MAX_ARRAY_SIZE;
  235       }
  236   
  237       // Modification Operations
  238   
  239       /**
  240        * {@inheritDoc}
  241        *
  242        * <p>This implementation always throws an
  243        * <tt>UnsupportedOperationException</tt>.
  244        *
  245        * @throws UnsupportedOperationException {@inheritDoc}
  246        * @throws ClassCastException            {@inheritDoc}
  247        * @throws NullPointerException          {@inheritDoc}
  248        * @throws IllegalArgumentException      {@inheritDoc}
  249        * @throws IllegalStateException         {@inheritDoc}
  250        */
  251       public boolean add(E e) {
  252           throw new UnsupportedOperationException();
  253       }
  254   
  255       /**
  256        * {@inheritDoc}
  257        *
  258        * <p>This implementation iterates over the collection looking for the
  259        * specified element.  If it finds the element, it removes the element
  260        * from the collection using the iterator's remove method.
  261        *
  262        * <p>Note that this implementation throws an
  263        * <tt>UnsupportedOperationException</tt> if the iterator returned by this
  264        * collection's iterator method does not implement the <tt>remove</tt>
  265        * method and this collection contains the specified object.
  266        *
  267        * @throws UnsupportedOperationException {@inheritDoc}
  268        * @throws ClassCastException            {@inheritDoc}
  269        * @throws NullPointerException          {@inheritDoc}
  270        */
  271       public boolean remove(Object o) {
  272           Iterator<E> it = iterator();
  273           if (o==null) {
  274               while (it.hasNext()) {
  275                   if (it.next()==null) {
  276                       it.remove();
  277                       return true;
  278                   }
  279               }
  280           } else {
  281               while (it.hasNext()) {
  282                   if (o.equals(it.next())) {
  283                       it.remove();
  284                       return true;
  285                   }
  286               }
  287           }
  288           return false;
  289       }
  290   
  291   
  292       // Bulk Operations
  293   
  294       /**
  295        * {@inheritDoc}
  296        *
  297        * <p>This implementation iterates over the specified collection,
  298        * checking each element returned by the iterator in turn to see
  299        * if it's contained in this collection.  If all elements are so
  300        * contained <tt>true</tt> is returned, otherwise <tt>false</tt>.
  301        *
  302        * @throws ClassCastException            {@inheritDoc}
  303        * @throws NullPointerException          {@inheritDoc}
  304        * @see #contains(Object)
  305        */
  306       public boolean containsAll(Collection<?> c) {
  307           for (Object e : c)
  308               if (!contains(e))
  309                   return false;
  310           return true;
  311       }
  312   
  313       /**
  314        * {@inheritDoc}
  315        *
  316        * <p>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        * <tt>UnsupportedOperationException</tt> unless <tt>add</tt> 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        * <p>This implementation iterates over this collection, checking each
  343        * element returned by the iterator in turn to see if it's contained
  344        * in the specified collection.  If it's so contained, it's removed from
  345        * this collection with the iterator's <tt>remove</tt> method.
  346        *
  347        * <p>Note that this implementation will throw an
  348        * <tt>UnsupportedOperationException</tt> if the iterator returned by the
  349        * <tt>iterator</tt> method does not implement the <tt>remove</tt> method
  350        * and this collection contains one or more elements in common with the
  351        * specified collection.
  352        *
  353        * @throws UnsupportedOperationException {@inheritDoc}
  354        * @throws ClassCastException            {@inheritDoc}
  355        * @throws NullPointerException          {@inheritDoc}
  356        *
  357        * @see #remove(Object)
  358        * @see #contains(Object)
  359        */
  360       public boolean removeAll(Collection<?> c) {
  361           boolean modified = false;
  362           Iterator<?> it = iterator();
  363           while (it.hasNext()) {
  364               if (c.contains(it.next())) {
  365                   it.remove();
  366                   modified = true;
  367               }
  368           }
  369           return modified;
  370       }
  371   
  372       /**
  373        * {@inheritDoc}
  374        *
  375        * <p>This implementation iterates over this collection, checking each
  376        * element returned by the iterator in turn to see if it's contained
  377        * in the specified collection.  If it's not so contained, it's removed
  378        * from this collection with the iterator's <tt>remove</tt> method.
  379        *
  380        * <p>Note that this implementation will throw an
  381        * <tt>UnsupportedOperationException</tt> if the iterator returned by the
  382        * <tt>iterator</tt> method does not implement the <tt>remove</tt> method
  383        * and this collection contains one or more elements not present in the
  384        * specified collection.
  385        *
  386        * @throws UnsupportedOperationException {@inheritDoc}
  387        * @throws ClassCastException            {@inheritDoc}
  388        * @throws NullPointerException          {@inheritDoc}
  389        *
  390        * @see #remove(Object)
  391        * @see #contains(Object)
  392        */
  393       public boolean retainAll(Collection<?> c) {
  394           boolean modified = false;
  395           Iterator<E> it = iterator();
  396           while (it.hasNext()) {
  397               if (!c.contains(it.next())) {
  398                   it.remove();
  399                   modified = true;
  400               }
  401           }
  402           return modified;
  403       }
  404   
  405       /**
  406        * {@inheritDoc}
  407        *
  408        * <p>This implementation iterates over this collection, removing each
  409        * element using the <tt>Iterator.remove</tt> operation.  Most
  410        * implementations will probably choose to override this method for
  411        * efficiency.
  412        *
  413        * <p>Note that this implementation will throw an
  414        * <tt>UnsupportedOperationException</tt> if the iterator returned by this
  415        * collection's <tt>iterator</tt> method does not implement the
  416        * <tt>remove</tt> method and this collection is non-empty.
  417        *
  418        * @throws UnsupportedOperationException {@inheritDoc}
  419        */
  420       public void clear() {
  421           Iterator<E> it = iterator();
  422           while (it.hasNext()) {
  423               it.next();
  424               it.remove();
  425           }
  426       }
  427   
  428   
  429       //  String conversion
  430   
  431       /**
  432        * Returns a string representation of this collection.  The string
  433        * representation consists of a list of the collection's elements in the
  434        * order they are returned by its iterator, enclosed in square brackets
  435        * (<tt>"[]"</tt>).  Adjacent elements are separated by the characters
  436        * <tt>", "</tt> (comma and space).  Elements are converted to strings as
  437        * by {@link String#valueOf(Object)}.
  438        *
  439        * @return a string representation of this collection
  440        */
  441       public String toString() {
  442           Iterator<E> it = iterator();
  443           if (! it.hasNext())
  444               return "[]";
  445   
  446           StringBuilder sb = new StringBuilder();
  447           sb.append('[');
  448           for (;;) {
  449               E e = it.next();
  450               sb.append(e == this ? "(this Collection)" : e);
  451               if (! it.hasNext())
  452                   return sb.append(']').toString();
  453               sb.append(',').append(' ');
  454           }
  455       }
  456   
  457   }

Save This Page
Home » openjdk-7 » java » util » [javadoc | source]