| /* AbstractCollection.java -- Abstract implementation of most of Collection |
| Copyright (C) 1998, 2000, 2001, 2005 Free Software Foundation, Inc. |
| |
| This file is part of GNU Classpath. |
| |
| GNU Classpath is free software; you can redistribute it and/or modify |
| it under the terms of the GNU General Public License as published by |
| the Free Software Foundation; either version 2, or (at your option) |
| any later version. |
| |
| GNU Classpath is distributed in the hope that it will be useful, but |
| WITHOUT ANY WARRANTY; without even the implied warranty of |
| MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
| General Public License for more details. |
| |
| You should have received a copy of the GNU General Public License |
| along with GNU Classpath; see the file COPYING. If not, write to the |
| Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA |
| 02110-1301 USA. |
| |
| Linking this library statically or dynamically with other modules is |
| making a combined work based on this library. Thus, the terms and |
| conditions of the GNU General Public License cover the whole |
| combination. |
| |
| As a special exception, the copyright holders of this library give you |
| permission to link this library with independent modules to produce an |
| executable, regardless of the license terms of these independent |
| modules, and to copy and distribute the resulting executable under |
| terms of your choice, provided that you also meet, for each linked |
| independent module, the terms and conditions of the license of that |
| module. An independent module is a module which is not derived from |
| or based on this library. If you modify this library, you may extend |
| this exception to your version of the library, but you are not |
| obligated to do so. If you do not wish to do so, delete this |
| exception statement from your version. */ |
| |
| |
| package java.util; |
| |
| import java.lang.reflect.Array; |
| |
| /** |
| * A basic implementation of most of the methods in the Collection interface to |
| * make it easier to create a collection. To create an unmodifiable Collection, |
| * just subclass AbstractCollection and provide implementations of the |
| * iterator() and size() methods. The Iterator returned by iterator() need only |
| * provide implementations of hasNext() and next() (that is, it may throw an |
| * UnsupportedOperationException if remove() is called). To create a modifiable |
| * Collection, you must in addition provide an implementation of the |
| * add(Object) method and the Iterator returned by iterator() must provide an |
| * implementation of remove(). Other methods should be overridden if the |
| * backing data structure allows for a more efficient implementation. The |
| * precise implementation used by AbstractCollection is documented, so that |
| * subclasses can tell which methods could be implemented more efficiently. |
| * <p> |
| * |
| * The programmer should provide a no-argument constructor, and one that |
| * accepts another Collection, as recommended by the Collection interface. |
| * Unfortunately, there is no way to enforce this in Java. |
| * |
| * @author Original author unknown |
| * @author Bryce McKinlay |
| * @author Eric Blake (ebb9@email.byu.edu) |
| * @see Collection |
| * @see AbstractSet |
| * @see AbstractList |
| * @since 1.2 |
| * @status updated to 1.4 |
| */ |
| public abstract class AbstractCollection implements Collection |
| { |
| /** |
| * The main constructor, for use by subclasses. |
| */ |
| protected AbstractCollection() |
| { |
| } |
| |
| /** |
| * Return an Iterator over this collection. The iterator must provide the |
| * hasNext and next methods and should in addition provide remove if the |
| * collection is modifiable. |
| * |
| * @return an iterator |
| */ |
| public abstract Iterator iterator(); |
| |
| /** |
| * Return the number of elements in this collection. If there are more than |
| * Integer.MAX_VALUE elements, return Integer.MAX_VALUE. |
| * |
| * @return the size |
| */ |
| public abstract int size(); |
| |
| /** |
| * Add an object to the collection (optional operation). This implementation |
| * always throws an UnsupportedOperationException - it should be |
| * overridden if the collection is to be modifiable. If the collection |
| * does not accept duplicates, simply return false. Collections may specify |
| * limitations on what may be added. |
| * |
| * @param o the object to add |
| * @return true if the add operation caused the Collection to change |
| * @throws UnsupportedOperationException if the add operation is not |
| * supported on this collection |
| * @throws NullPointerException if the collection does not support null |
| * @throws ClassCastException if the object is of the wrong type |
| * @throws IllegalArgumentException if some aspect of the object prevents |
| * it from being added |
| */ |
| public boolean add(Object o) |
| { |
| throw new UnsupportedOperationException(); |
| } |
| |
| /** |
| * Add all the elements of a given collection to this collection (optional |
| * operation). This implementation obtains an Iterator over the given |
| * collection and iterates over it, adding each element with the |
| * add(Object) method (thus this method will fail with an |
| * UnsupportedOperationException if the add method does). The behavior is |
| * unspecified if the specified collection is modified during the iteration, |
| * including the special case of trying addAll(this) on a non-empty |
| * collection. |
| * |
| * @param c the collection to add the elements of to this collection |
| * @return true if the add operation caused the Collection to change |
| * @throws UnsupportedOperationException if the add operation is not |
| * supported on this collection |
| * @throws NullPointerException if the specified collection is null |
| * @throws ClassCastException if the type of any element in c is |
| * not a valid type for addition. |
| * @throws IllegalArgumentException if some aspect of any element |
| * in c prevents it being added. |
| * @throws NullPointerException if any element in c is null and this |
| * collection doesn't allow null values. |
| * @see #add(Object) |
| */ |
| public boolean addAll(Collection c) |
| { |
| Iterator itr = c.iterator(); |
| boolean modified = false; |
| int pos = c.size(); |
| while (--pos >= 0) |
| modified |= add(itr.next()); |
| return modified; |
| } |
| |
| /** |
| * Remove all elements from the collection (optional operation). This |
| * implementation obtains an iterator over the collection and calls next |
| * and remove on it repeatedly (thus this method will fail with an |
| * UnsupportedOperationException if the Iterator's remove method does) |
| * until there are no more elements to remove. |
| * Many implementations will have a faster way of doing this. |
| * |
| * @throws UnsupportedOperationException if the Iterator returned by |
| * iterator does not provide an implementation of remove |
| * @see Iterator#remove() |
| */ |
| public void clear() |
| { |
| Iterator itr = iterator(); |
| int pos = size(); |
| while (--pos >= 0) |
| { |
| itr.next(); |
| itr.remove(); |
| } |
| } |
| |
| /** |
| * Test whether this collection contains a given object. That is, if the |
| * collection has an element e such that (o == null ? e == null : |
| * o.equals(e)). This implementation obtains an iterator over the collection |
| * and iterates over it, testing each element for equality with the given |
| * object. If it is equal, true is returned. Otherwise false is returned when |
| * the end of the collection is reached. |
| * |
| * @param o the object to remove from this collection |
| * @return true if this collection contains an object equal to o |
| */ |
| public boolean contains(Object o) |
| { |
| Iterator itr = iterator(); |
| int pos = size(); |
| while (--pos >= 0) |
| if (equals(o, itr.next())) |
| return true; |
| return false; |
| } |
| |
| /** |
| * Tests whether this collection contains all the elements in a given |
| * collection. This implementation iterates over the given collection, |
| * testing whether each element is contained in this collection. If any one |
| * is not, false is returned. Otherwise true is returned. |
| * |
| * @param c the collection to test against |
| * @return true if this collection contains all the elements in the given |
| * collection |
| * @throws NullPointerException if the given collection is null |
| * @see #contains(Object) |
| */ |
| public boolean containsAll(Collection c) |
| { |
| Iterator itr = c.iterator(); |
| int pos = c.size(); |
| while (--pos >= 0) |
| if (!contains(itr.next())) |
| return false; |
| return true; |
| } |
| |
| /** |
| * Test whether this collection is empty. This implementation returns |
| * size() == 0. |
| * |
| * @return true if this collection is empty. |
| * @see #size() |
| */ |
| public boolean isEmpty() |
| { |
| return size() == 0; |
| } |
| |
| /** |
| * Remove a single instance of an object from this collection (optional |
| * operation). That is, remove one element e such that |
| * <code>(o == null ? e == null : o.equals(e))</code>, if such an element |
| * exists. This implementation obtains an iterator over the collection |
| * and iterates over it, testing each element for equality with the given |
| * object. If it is equal, it is removed by the iterator's remove method |
| * (thus this method will fail with an UnsupportedOperationException if |
| * the Iterator's remove method does). After the first element has been |
| * removed, true is returned; if the end of the collection is reached, false |
| * is returned. |
| * |
| * @param o the object to remove from this collection |
| * @return true if the remove operation caused the Collection to change, or |
| * equivalently if the collection did contain o. |
| * @throws UnsupportedOperationException if this collection's Iterator |
| * does not support the remove method |
| * @see Iterator#remove() |
| */ |
| public boolean remove(Object o) |
| { |
| Iterator itr = iterator(); |
| int pos = size(); |
| while (--pos >= 0) |
| if (equals(o, itr.next())) |
| { |
| itr.remove(); |
| return true; |
| } |
| return false; |
| } |
| |
| /** |
| * Remove from this collection all its elements that are contained in a given |
| * collection (optional operation). This implementation iterates over this |
| * collection, and for each element tests if it is contained in the given |
| * collection. If so, it is removed by the Iterator's remove method (thus |
| * this method will fail with an UnsupportedOperationException if the |
| * Iterator's remove method does). |
| * |
| * @param c the collection to remove the elements of |
| * @return true if the remove operation caused the Collection to change |
| * @throws UnsupportedOperationException if this collection's Iterator |
| * does not support the remove method |
| * @throws NullPointerException if the collection, c, is null. |
| * @see Iterator#remove() |
| */ |
| public boolean removeAll(Collection c) |
| { |
| return removeAllInternal(c); |
| } |
| |
| /** |
| * Remove from this collection all its elements that are contained in a given |
| * collection (optional operation). This implementation iterates over this |
| * collection, and for each element tests if it is contained in the given |
| * collection. If so, it is removed by the Iterator's remove method (thus |
| * this method will fail with an UnsupportedOperationException if the |
| * Iterator's remove method does). This method is necessary for ArrayList, |
| * which cannot publicly override removeAll but can optimize this call. |
| * |
| * @param c the collection to remove the elements of |
| * @return true if the remove operation caused the Collection to change |
| * @throws UnsupportedOperationException if this collection's Iterator |
| * does not support the remove method |
| * @throws NullPointerException if the collection, c, is null. |
| * @see Iterator#remove() |
| */ |
| // Package visible for use throughout java.util. |
| boolean removeAllInternal(Collection c) |
| { |
| Iterator itr = iterator(); |
| boolean modified = false; |
| int pos = size(); |
| while (--pos >= 0) |
| if (c.contains(itr.next())) |
| { |
| itr.remove(); |
| modified = true; |
| } |
| return modified; |
| } |
| |
| /** |
| * Remove from this collection all its elements that are not contained in a |
| * given collection (optional operation). This implementation iterates over |
| * this collection, and for each element tests if it is contained in the |
| * given collection. If not, it is removed by the Iterator's remove method |
| * (thus this method will fail with an UnsupportedOperationException if |
| * the Iterator's remove method does). |
| * |
| * @param c the collection to retain the elements of |
| * @return true if the remove operation caused the Collection to change |
| * @throws UnsupportedOperationException if this collection's Iterator |
| * does not support the remove method |
| * @throws NullPointerException if the collection, c, is null. |
| * @see Iterator#remove() |
| */ |
| public boolean retainAll(Collection c) |
| { |
| return retainAllInternal(c); |
| } |
| |
| /** |
| * Remove from this collection all its elements that are not contained in a |
| * given collection (optional operation). This implementation iterates over |
| * this collection, and for each element tests if it is contained in the |
| * given collection. If not, it is removed by the Iterator's remove method |
| * (thus this method will fail with an UnsupportedOperationException if |
| * the Iterator's remove method does). This method is necessary for |
| * ArrayList, which cannot publicly override retainAll but can optimize |
| * this call. |
| * |
| * @param c the collection to retain the elements of |
| * @return true if the remove operation caused the Collection to change |
| * @throws UnsupportedOperationException if this collection's Iterator |
| * does not support the remove method |
| * @throws NullPointerException if the collection, c, is null. |
| * @see Iterator#remove() |
| */ |
| // Package visible for use throughout java.util. |
| boolean retainAllInternal(Collection c) |
| { |
| Iterator itr = iterator(); |
| boolean modified = false; |
| int pos = size(); |
| while (--pos >= 0) |
| if (!c.contains(itr.next())) |
| { |
| itr.remove(); |
| modified = true; |
| } |
| return modified; |
| } |
| |
| /** |
| * Return an array containing the elements of this collection. This |
| * implementation creates an Object array of size size() and then iterates |
| * over the collection, setting each element of the array from the value |
| * returned by the iterator. The returned array is safe, and is not backed |
| * by the collection. |
| * |
| * @return an array containing the elements of this collection |
| */ |
| public Object[] toArray() |
| { |
| Iterator itr = iterator(); |
| int size = size(); |
| Object[] a = new Object[size]; |
| for (int pos = 0; pos < size; pos++) |
| a[pos] = itr.next(); |
| return a; |
| } |
| |
| /** |
| * Copy the collection into a given array if it will fit, or into a |
| * dynamically created array of the same run-time type as the given array if |
| * not. If there is space remaining in the array, the first element after the |
| * end of the collection is set to null (this is only useful if the |
| * collection is known to contain no null elements, however). This |
| * implementation first tests whether the given array is large enough to hold |
| * all the elements of the collection. If not, the reflection API is used to |
| * allocate a new array of the same run-time type. Next an iterator is |
| * obtained over the collection and the elements are placed in the array as |
| * they are returned by the iterator. Finally the first spare element, if |
| * any, of the array is set to null, and the created array is returned. |
| * The returned array is safe; it is not backed by the collection. Note that |
| * null may not mark the last element, if the collection allows null |
| * elements. |
| * |
| * @param a the array to copy into, or of the correct run-time type |
| * @return the array that was produced |
| * @throws NullPointerException if the given array is null |
| * @throws ArrayStoreException if the type of the array precludes holding |
| * one of the elements of the Collection |
| */ |
| public Object[] toArray(Object[] a) |
| { |
| int size = size(); |
| if (a.length < size) |
| a = (Object[]) Array.newInstance(a.getClass().getComponentType(), |
| size); |
| else if (a.length > size) |
| a[size] = null; |
| |
| Iterator itr = iterator(); |
| for (int pos = 0; pos < size; pos++) |
| a[pos] = itr.next(); |
| |
| return a; |
| } |
| |
| /** |
| * Creates a String representation of the Collection. The string returned is |
| * of the form "[a, b, ...]" where a and b etc are the results of calling |
| * toString on the elements of the collection. This implementation obtains an |
| * Iterator over the Collection and adds each element to a StringBuffer as it |
| * is returned by the iterator. "<this>" is inserted when the collection |
| * contains itself (only works for direct containment, not for collections |
| * inside collections). |
| * |
| * @return a String representation of the Collection |
| */ |
| public String toString() |
| { |
| Iterator itr = iterator(); |
| StringBuffer r = new StringBuffer("["); |
| boolean hasNext = itr.hasNext(); |
| while (hasNext) |
| { |
| Object o = itr.next(); |
| if (o == this) |
| r.append("<this>"); |
| else |
| r.append(o); |
| hasNext = itr.hasNext(); |
| if (hasNext) |
| r.append(", "); |
| } |
| r.append("]"); |
| return r.toString(); |
| } |
| |
| /** |
| * Compare two objects according to Collection semantics. |
| * |
| * @param o1 the first object |
| * @param o2 the second object |
| * @return o1 == null ? o2 == null : o1.equals(o2) |
| */ |
| // Package visible for use throughout java.util. |
| // It may be inlined since it is final. |
| static final boolean equals(Object o1, Object o2) |
| { |
| return o1 == null ? o2 == null : o1.equals(o2); |
| } |
| |
| /** |
| * Hash an object according to Collection semantics. |
| * |
| * @param o the object to hash |
| * @return o1 == null ? 0 : o1.hashCode() |
| */ |
| // Package visible for use throughout java.util. |
| // It may be inlined since it is final. |
| static final int hashCode(Object o) |
| { |
| return o == null ? 0 : o.hashCode(); |
| } |
| } |