java/util/AbstractCollection.java

/*
 * %W% %E%
 *
 * Copyright 2006 Sun Microsystems, Inc. All rights reserved.
 * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 */

package java.util;

/**
 * This class provides a skeletal implementation of the <tt>Collection</tt>
 * interface, to minimize the effort required to implement this interface. <p>
 *
 * To implement an unmodifiable collection, the programmer needs only to
 * extend this class and provide implementations for the <tt>iterator</tt> and
 * <tt>size</tt> methods.  (The iterator returned by the <tt>iterator</tt>
 * method must implement <tt>hasNext</tt> and <tt>next</tt>.)<p>
 *
 * To implement a modifiable collection, the programmer must additionally
 * override this class's <tt>add</tt> method (which otherwise throws an
 * <tt>UnsupportedOperationException</tt>), and the iterator returned by the
 * <tt>iterator</tt> method must additionally implement its <tt>remove</tt>
 * method.<p>
 *
 * The programmer should generally provide a void (no argument) and
 * <tt>Collection</tt> constructor, as per the recommendation in the
 * <tt>Collection</tt> interface specification.<p>
 *
 * The documentation for each non-abstract method in this class describes its
 * implementation in detail.  Each of these methods may be overridden if
 * the collection being implemented admits a more efficient implementation.<p>
 *
 * This class is a member of the
 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
 * Java Collections Framework</a>.
 *
 * @author  Josh Bloch
 * @author  Neal Gafter
 * @version %I%, %G%
 * @see Collection
 * @since 1.2
 */

public abstract class AbstractCollection<E> implements Collection<E> {
    /**
     * Sole constructor.  (For invocation by subclass constructors, typically
     * implicit.)
     */
    protected AbstractCollection() {
    }

    // Query Operations

    /**
     * Returns an iterator over the elements contained in this collection.
     *
     * @return an iterator over the elements contained in this collection
     */
    public abstract Iterator<E> iterator();

    public abstract int size();

    /**
     * {@inheritDoc}
     *
     * <p>This implementation returns <tt>size() == 0</tt>.
     */
    public boolean isEmpty() {
        return size() == 0;
    }

    /**
     * {@inheritDoc}
     *
     * <p>This implementation iterates over the elements in the collection,
     * checking each element in turn for equality with the specified element.
     *
     * @throws ClassCastException   {@inheritDoc}
     * @throws NullPointerException {@inheritDoc}
     */
    public boolean contains(Object o) {
        Iterator<E> e = iterator();
        if (o==null) {
            while (e.hasNext())
                if (e.next()==null)
                    return true;
        } else {
            while (e.hasNext())
                if (o.equals(e.next()))
                    return true;
        }
        return false;
    }

    /**
     * {@inheritDoc}
     *
     * <p>This implementation returns an array containing all the elements
     * returned by this collection's iterator, in the same order, stored in
     * consecutive elements of the array, starting with index {@code 0}.
     * The length of the returned array is equal to the number of elements
     * returned by the iterator, even if the size of this collection changes
     * during iteration, as might happen if the collection permits
     * concurrent modification during iteration.  The {@code size} method is
     * called only as an optimization hint; the correct result is returned
     * even if the iterator returns a different number of elements.
     *
     * <p>This method is equivalent to:
     *
     *  <pre> {@code
     * List<E> list = new ArrayList<E>(size());
     * for (E e : this)
     *     list.add(e);
     * return list.toArray();
     * }</pre>
     */
    public Object[] toArray() {
        // Estimate size of array; be prepared to see more or fewer elements
        Object[] r = new Object[size()];
        Iterator<E> it = iterator();
        for (int i = 0; i < r.length; i++) {
            if (! it.hasNext()) // fewer elements than expected
                return Arrays.copyOf(r, i);
            r[i] = it.next();
        }
        return it.hasNext() ? finishToArray(r, it) : r;
    }

    /**
     * {@inheritDoc}
     *
     * <p>This implementation returns an array containing all the elements
     * returned by this collection's iterator in the same order, stored in
     * consecutive elements of the array, starting with index {@code 0}.
     * If the number of elements returned by the iterator is too large to
     * fit into the specified array, then the elements are returned in a
     * newly allocated array with length equal to the number of elements
     * returned by the iterator, even if the size of this collection
     * changes during iteration, as might happen if the collection permits
     * concurrent modification during iteration.  The {@code size} method is
     * called only as an optimization hint; the correct result is returned
     * even if the iterator returns a different number of elements.
     *
     * <p>This method is equivalent to:
     *
     *  <pre> {@code
     * List<E> list = new ArrayList<E>(size());
     * for (E e : this)
     *     list.add(e);
     * return list.toArray(a);
     * }</pre>
     *
     * @throws ArrayStoreException  {@inheritDoc}
     * @throws NullPointerException {@inheritDoc}
     */
    public <T> T[] toArray(T[] a) {
        // Estimate size of array; be prepared to see more or fewer elements
        int size = size();
        T[] r = a.length >= size ? a :
                  (T[])java.lang.reflect.Array
                  .newInstance(a.getClass().getComponentType(), size);
        Iterator<E> it = iterator();

        for (int i = 0; i < r.length; i++) {
            if (! it.hasNext()) { // fewer elements than expected
                if (a != r)
                    return Arrays.copyOf(r, i);
                r[i] = null; // null-terminate
                return r;
            }
            r[i] = (T)it.next();
        }
        return it.hasNext() ? finishToArray(r, it) : r;
    }

    /**
     * Reallocates the array being used within toArray when the iterator
     * returned more elements than expected, and finishes filling it from
     * the iterator.
     *
     * @param r the array, replete with previously stored elements
     * @param it the in-progress iterator over this collection
     * @return array containing the elements in the given array, plus any
     *         further elements returned by the iterator, trimmed to size
     */
    private static <T> T[] finishToArray(T[] r, Iterator<?> it) {
        int i = r.length;
        while (it.hasNext()) {
            int cap = r.length;
            if (i == cap) {
                int newCap = ((cap / 2) + 1) * 3;
                if (newCap <= cap) { // integer overflow
                    if (cap == Integer.MAX_VALUE)
                        throw new OutOfMemoryError
                            ("Required array size too large");
                    newCap = Integer.MAX_VALUE;
                }
                r = Arrays.copyOf(r, newCap);
            }
            r[i++] = (T)it.next();
        }
        // trim if overallocated
        return (i == r.length) ? r : Arrays.copyOf(r, i);
    }

    // Modification Operations

    /**
     * {@inheritDoc}
     *
     * <p>This implementation always throws an
     * <tt>UnsupportedOperationException</tt>.
     *
     * @throws UnsupportedOperationException {@inheritDoc}
     * @throws ClassCastException            {@inheritDoc}
     * @throws NullPointerException          {@inheritDoc}
     * @throws IllegalArgumentException      {@inheritDoc}
     * @throws IllegalStateException         {@inheritDoc}
     */
    public boolean add(E e) {
        throw new UnsupportedOperationException();
    }

    /**
     * {@inheritDoc}
     *
     * <p>This implementation iterates over the collection looking for the
     * specified element.  If it finds the element, it removes the element
     * from the collection using the iterator's remove method.
     *
     * <p>Note that this implementation throws an
     * <tt>UnsupportedOperationException</tt> if the iterator returned by this
     * collection's iterator method does not implement the <tt>remove</tt>
     * method and this collection contains the specified object.
     *
     * @throws UnsupportedOperationException {@inheritDoc}
     * @throws ClassCastException            {@inheritDoc}
     * @throws NullPointerException          {@inheritDoc}
     */
    public boolean remove(Object o) {
        Iterator<E> e = iterator();
        if (o==null) {
            while (e.hasNext()) {
                if (e.next()==null) {
                    e.remove();
                    return true;
                }
            }
        } else {
            while (e.hasNext()) {
                if (o.equals(e.next())) {
                    e.remove();
                    return true;
                }
            }
        }
        return false;
    }


    // Bulk Operations

    /**
     * {@inheritDoc}
     *
     * <p>This implementation iterates over the specified collection,
     * checking each element returned by the iterator in turn to see
     * if it's contained in this collection.  If all elements are so
     * contained <tt>true</tt> is returned, otherwise <tt>false</tt>.
     *
     * @throws ClassCastException            {@inheritDoc}
     * @throws NullPointerException          {@inheritDoc}
     * @see #contains(Object)
     */
    public boolean containsAll(Collection<?> c) {
        Iterator<?> e = c.iterator();
        while (e.hasNext())
            if (!contains(e.next()))
                return false;
        return true;
    }

    /**
     * {@inheritDoc}
     *
     * <p>This implementation iterates over the specified collection, and adds
     * each object returned by the iterator to this collection, in turn.
     *
     * <p>Note that this implementation will throw an
     * <tt>UnsupportedOperationException</tt> unless <tt>add</tt> is
     * overridden (assuming the specified collection is non-empty).
     *
     * @throws UnsupportedOperationException {@inheritDoc}
     * @throws ClassCastException            {@inheritDoc}
     * @throws NullPointerException          {@inheritDoc}
     * @throws IllegalArgumentException      {@inheritDoc}
     * @throws IllegalStateException         {@inheritDoc}
     *
     * @see #add(Object)
     */
    public boolean addAll(Collection<? extends E> c) {
        boolean modified = false;
        Iterator<? extends E> e = c.iterator();
        while (e.hasNext()) {
            if (add(e.next()))
                modified = true;
        }
        return modified;
    }

    /**
     * {@inheritDoc}
     *
     * <p>This implementation iterates over this collection, checking each
     * element returned by the iterator in turn to see if it's contained
     * in the specified collection.  If it's so contained, it's removed from
     * this collection with the iterator's <tt>remove</tt> method.
     *
     * <p>Note that this implementation will throw an
     * <tt>UnsupportedOperationException</tt> if the iterator returned by the
     * <tt>iterator</tt> method does not implement the <tt>remove</tt> method
     * and this collection contains one or more elements in common with the
     * specified collection.
     *
     * @throws UnsupportedOperationException {@inheritDoc}
     * @throws ClassCastException            {@inheritDoc}
     * @throws NullPointerException          {@inheritDoc}
     *
     * @see #remove(Object)
     * @see #contains(Object)
     */
    public boolean removeAll(Collection<?> c) {
        boolean modified = false;
        Iterator<?> e = iterator();
        while (e.hasNext()) {
            if (c.contains(e.next())) {
                e.remove();
                modified = true;
            }
        }
        return modified;
    }

    /**
     * {@inheritDoc}
     *
     * <p>This implementation iterates over this collection, checking each
     * element returned by the iterator in turn to see if it's contained
     * in the specified collection.  If it's not so contained, it's removed
     * from this collection with the iterator's <tt>remove</tt> method.
     *
     * <p>Note that this implementation will throw an
     * <tt>UnsupportedOperationException</tt> if the iterator returned by the
     * <tt>iterator</tt> method does not implement the <tt>remove</tt> method
     * and this collection contains one or more elements not present in the
     * specified collection.
     *
     * @throws UnsupportedOperationException {@inheritDoc}
     * @throws ClassCastException            {@inheritDoc}
     * @throws NullPointerException          {@inheritDoc}
     *
     * @see #remove(Object)
     * @see #contains(Object)
     */
    public boolean retainAll(Collection<?> c) {
        boolean modified = false;
        Iterator<E> e = iterator();
        while (e.hasNext()) {
            if (!c.contains(e.next())) {
                e.remove();
                modified = true;
            }
        }
        return modified;
    }

    /**
     * {@inheritDoc}
     *
     * <p>This implementation iterates over this collection, removing each
     * element using the <tt>Iterator.remove</tt> operation.  Most
     * implementations will probably choose to override this method for
     * efficiency.
     *
     * <p>Note that this implementation will throw an
     * <tt>UnsupportedOperationException</tt> if the iterator returned by this
     * collection's <tt>iterator</tt> method does not implement the
     * <tt>remove</tt> method and this collection is non-empty.
     *
     * @throws UnsupportedOperationException {@inheritDoc}
     */
    public void clear() {
        Iterator<E> e = iterator();
        while (e.hasNext()) {
            e.next();
            e.remove();
        }
    }


    //  String conversion

    /**
     * Returns a string representation of this collection.  The string
     * representation consists of a list of the collection's elements in the
     * order they are returned by its iterator, enclosed in square brackets
     * (<tt>"[]"</tt>).  Adjacent elements are separated by the characters
     * <tt>", "</tt> (comma and space).  Elements are converted to strings as
     * by {@link String#valueOf(Object)}.
     *
     * @return a string representation of this collection
     */
    public String toString() {
        Iterator<E> i = iterator();
        if (! i.hasNext())
            return "[]";

        StringBuilder sb = new StringBuilder();
        sb.append('[');
        for (;;) {
            E e = i.next();
            sb.append(e == this ? "(this Collection)" : e);
            if (! i.hasNext())
                return sb.append(']').toString();
            sb.append(", ");
        }
    }

}
Revision:	1.9
Committed:	Sun Jun 25 19:07:16 2006 UTC (17 years, 10 months ago) by jsr166
Branch:	MAIN
Changes since 1.8:	+70 -42 lines
Log Message:	6377302: AbstractCollection.toArray is not safe for concurrent collections
#	User	Rev	Content
1	dl	1.1	/*
2	jsr166	1.3	* %W% %E%
3	dl	1.1	*
4	jsr166	1.5	* Copyright 2006 Sun Microsystems, Inc. All rights reserved.
5	dl	1.1	* SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6			*/
7
8			package java.util;
9
10			/**
11			* This class provides a skeletal implementation of the <tt>Collection</tt>
12			* interface, to minimize the effort required to implement this interface. <p>
13			*
14			* To implement an unmodifiable collection, the programmer needs only to
15			* extend this class and provide implementations for the <tt>iterator</tt> and
16			* <tt>size</tt> methods. (The iterator returned by the <tt>iterator</tt>
17			* method must implement <tt>hasNext</tt> and <tt>next</tt>.)<p>
18			*
19			* To implement a modifiable collection, the programmer must additionally
20			* override this class's <tt>add</tt> method (which otherwise throws an
21			* <tt>UnsupportedOperationException</tt>), and the iterator returned by the
22			* <tt>iterator</tt> method must additionally implement its <tt>remove</tt>
23			* method.<p>
24			*
25			* The programmer should generally provide a void (no argument) and
26			* <tt>Collection</tt> constructor, as per the recommendation in the
27			* <tt>Collection</tt> interface specification.<p>
28			*
29	jsr166	1.9	* The documentation for each non-abstract method in this class describes its
30	dl	1.1	* implementation in detail. Each of these methods may be overridden if
31			* the collection being implemented admits a more efficient implementation.<p>
32			*
33			* This class is a member of the
34	jsr166	1.8	* <a href="{@docRoot}/../technotes/guides/collections/index.html">
35	dl	1.1	* Java Collections Framework</a>.
36			*
37			* @author Josh Bloch
38			* @author Neal Gafter
39	jsr166	1.6	* @version %I%, %G%
40	dl	1.1	* @see Collection
41			* @since 1.2
42			*/
43
44			public abstract class AbstractCollection<E> implements Collection<E> {
45			/**
46			* Sole constructor. (For invocation by subclass constructors, typically
47			* implicit.)
48			*/
49			protected AbstractCollection() {
50			}
51
52			// Query Operations
53
54			/**
55			* Returns an iterator over the elements contained in this collection.
56			*
57			* @return an iterator over the elements contained in this collection
58			*/
59			public abstract Iterator<E> iterator();
60
61			public abstract int size();
62
63			/**
64			* {@inheritDoc}
65			*
66			* <p>This implementation returns <tt>size() == 0</tt>.
67			*/
68			public boolean isEmpty() {
69			return size() == 0;
70			}
71
72			/**
73			* {@inheritDoc}
74			*
75			* <p>This implementation iterates over the elements in the collection,
76			* checking each element in turn for equality with the specified element.
77			*
78			* @throws ClassCastException {@inheritDoc}
79			* @throws NullPointerException {@inheritDoc}
80			*/
81			public boolean contains(Object o) {
82			Iterator<E> e = iterator();
83			if (o==null) {
84			while (e.hasNext())
85			if (e.next()==null)
86			return true;
87			} else {
88			while (e.hasNext())
89			if (o.equals(e.next()))
90			return true;
91			}
92			return false;
93			}
94
95			/**
96			* {@inheritDoc}
97			*
98	jsr166	1.9	* <p>This implementation returns an array containing all the elements
99			* returned by this collection's iterator, in the same order, stored in
100			* consecutive elements of the array, starting with index {@code 0}.
101			* The length of the returned array is equal to the number of elements
102			* returned by the iterator, even if the size of this collection changes
103			* during iteration, as might happen if the collection permits
104			* concurrent modification during iteration. The {@code size} method is
105			* called only as an optimization hint; the correct result is returned
106			* even if the iterator returns a different number of elements.
107			*
108			* <p>This method is equivalent to:
109			*
110			* <pre> {@code
111			* List<E> list = new ArrayList<E>(size());
112			* for (E e : this)
113			* list.add(e);
114			* return list.toArray();
115			* }</pre>
116	dl	1.1	*/
117			public Object[] toArray() {
118			// Estimate size of array; be prepared to see more or fewer elements
119			Object[] r = new Object[size()];
120	jsr166	1.3	Iterator<E> it = iterator();
121	jsr166	1.9	for (int i = 0; i < r.length; i++) {
122			if (! it.hasNext()) // fewer elements than expected
123			return Arrays.copyOf(r, i);
124			r[i] = it.next();
125			}
126			return it.hasNext() ? finishToArray(r, it) : r;
127	dl	1.1	}
128
129			/**
130			* {@inheritDoc}
131			*
132	jsr166	1.9	* <p>This implementation returns an array containing all the elements
133			* returned by this collection's iterator in the same order, stored in
134			* consecutive elements of the array, starting with index {@code 0}.
135			* If the number of elements returned by the iterator is too large to
136			* fit into the specified array, then the elements are returned in a
137			* newly allocated array with length equal to the number of elements
138			* returned by the iterator, even if the size of this collection
139			* changes during iteration, as might happen if the collection permits
140			* concurrent modification during iteration. The {@code size} method is
141			* called only as an optimization hint; the correct result is returned
142			* even if the iterator returns a different number of elements.
143			*
144			* <p>This method is equivalent to:
145			*
146			* <pre> {@code
147			* List<E> list = new ArrayList<E>(size());
148			* for (E e : this)
149			* list.add(e);
150			* return list.toArray(a);
151			* }</pre>
152	dl	1.1	*
153			* @throws ArrayStoreException {@inheritDoc}
154			* @throws NullPointerException {@inheritDoc}
155			*/
156			public <T> T[] toArray(T[] a) {
157			// Estimate size of array; be prepared to see more or fewer elements
158			int size = size();
159	jsr166	1.3	T[] r = a.length >= size ? a :
160	dl	1.1	(T[])java.lang.reflect.Array
161			.newInstance(a.getClass().getComponentType(), size);
162	jsr166	1.3	Iterator<E> it = iterator();
163	jsr166	1.9
164			for (int i = 0; i < r.length; i++) {
165			if (! it.hasNext()) { // fewer elements than expected
166			if (a != r)
167			return Arrays.copyOf(r, i);
168			r[i] = null; // null-terminate
169			return r;
170			}
171			r[i] = (T)it.next();
172			}
173			return it.hasNext() ? finishToArray(r, it) : r;
174	dl	1.1	}
175
176			/**
177	jsr166	1.9	* Reallocates the array being used within toArray when the iterator
178			* returned more elements than expected, and finishes filling it from
179			* the iterator.
180			*
181			* @param r the array, replete with previously stored elements
182			* @param it the in-progress iterator over this collection
183	jsr166	1.3	* @return array containing the elements in the given array, plus any
184			* further elements returned by the iterator, trimmed to size
185	dl	1.1	*/
186	jsr166	1.9	private static <T> T[] finishToArray(T[] r, Iterator<?> it) {
187			int i = r.length;
188	jsr166	1.2	while (it.hasNext()) {
189	dl	1.1	int cap = r.length;
190	jsr166	1.9	if (i == cap) {
191	dl	1.4	int newCap = ((cap / 2) + 1) * 3;
192			if (newCap <= cap) { // integer overflow
193			if (cap == Integer.MAX_VALUE)
194			throw new OutOfMemoryError
195			("Required array size too large");
196	jsr166	1.9	newCap = Integer.MAX_VALUE;
197	dl	1.4	}
198	jsr166	1.9	r = Arrays.copyOf(r, newCap);
199			}
200			r[i++] = (T)it.next();
201	jsr166	1.7	}
202	dl	1.1	// trim if overallocated
203	jsr166	1.9	return (i == r.length) ? r : Arrays.copyOf(r, i);
204	dl	1.1	}
205
206			// Modification Operations
207
208			/**
209			* {@inheritDoc}
210			*
211			* <p>This implementation always throws an
212			* <tt>UnsupportedOperationException</tt>.
213			*
214			* @throws UnsupportedOperationException {@inheritDoc}
215			* @throws ClassCastException {@inheritDoc}
216			* @throws NullPointerException {@inheritDoc}
217			* @throws IllegalArgumentException {@inheritDoc}
218			* @throws IllegalStateException {@inheritDoc}
219			*/
220			public boolean add(E e) {
221			throw new UnsupportedOperationException();
222			}
223
224			/**
225			* {@inheritDoc}
226			*
227			* <p>This implementation iterates over the collection looking for the
228			* specified element. If it finds the element, it removes the element
229			* from the collection using the iterator's remove method.
230			*
231			* <p>Note that this implementation throws an
232			* <tt>UnsupportedOperationException</tt> if the iterator returned by this
233			* collection's iterator method does not implement the <tt>remove</tt>
234			* method and this collection contains the specified object.
235			*
236			* @throws UnsupportedOperationException {@inheritDoc}
237			* @throws ClassCastException {@inheritDoc}
238			* @throws NullPointerException {@inheritDoc}
239			*/
240			public boolean remove(Object o) {
241			Iterator<E> e = iterator();
242			if (o==null) {
243			while (e.hasNext()) {
244			if (e.next()==null) {
245			e.remove();
246			return true;
247			}
248			}
249			} else {
250			while (e.hasNext()) {
251			if (o.equals(e.next())) {
252			e.remove();
253			return true;
254			}
255			}
256			}
257			return false;
258			}
259
260
261			// Bulk Operations
262
263			/**
264			* {@inheritDoc}
265			*
266			* <p>This implementation iterates over the specified collection,
267			* checking each element returned by the iterator in turn to see
268			* if it's contained in this collection. If all elements are so
269			* contained <tt>true</tt> is returned, otherwise <tt>false</tt>.
270			*
271			* @throws ClassCastException {@inheritDoc}
272			* @throws NullPointerException {@inheritDoc}
273			* @see #contains(Object)
274			*/
275			public boolean containsAll(Collection<?> c) {
276			Iterator<?> e = c.iterator();
277			while (e.hasNext())
278			if (!contains(e.next()))
279			return false;
280			return true;
281			}
282
283			/**
284			* {@inheritDoc}
285			*
286			* <p>This implementation iterates over the specified collection, and adds
287			* each object returned by the iterator to this collection, in turn.
288			*
289			* <p>Note that this implementation will throw an
290			* <tt>UnsupportedOperationException</tt> unless <tt>add</tt> is
291			* overridden (assuming the specified collection is non-empty).
292			*
293			* @throws UnsupportedOperationException {@inheritDoc}
294			* @throws ClassCastException {@inheritDoc}
295			* @throws NullPointerException {@inheritDoc}
296			* @throws IllegalArgumentException {@inheritDoc}
297			* @throws IllegalStateException {@inheritDoc}
298			*
299			* @see #add(Object)
300			*/
301			public boolean addAll(Collection<? extends E> c) {
302			boolean modified = false;
303			Iterator<? extends E> e = c.iterator();
304			while (e.hasNext()) {
305			if (add(e.next()))
306			modified = true;
307			}
308			return modified;
309			}
310
311			/**
312			* {@inheritDoc}
313			*
314			* <p>This implementation iterates over this collection, checking each
315			* element returned by the iterator in turn to see if it's contained
316			* in the specified collection. If it's so contained, it's removed from
317			* this collection with the iterator's <tt>remove</tt> method.
318			*
319			* <p>Note that this implementation will throw an
320			* <tt>UnsupportedOperationException</tt> if the iterator returned by the
321			* <tt>iterator</tt> method does not implement the <tt>remove</tt> method
322			* and this collection contains one or more elements in common with the
323			* specified collection.
324			*
325			* @throws UnsupportedOperationException {@inheritDoc}
326			* @throws ClassCastException {@inheritDoc}
327			* @throws NullPointerException {@inheritDoc}
328			*
329			* @see #remove(Object)
330			* @see #contains(Object)
331			*/
332			public boolean removeAll(Collection<?> c) {
333			boolean modified = false;
334			Iterator<?> e = iterator();
335			while (e.hasNext()) {
336			if (c.contains(e.next())) {
337			e.remove();
338			modified = true;
339			}
340			}
341			return modified;
342			}
343
344			/**
345			* {@inheritDoc}
346			*
347			* <p>This implementation iterates over this collection, checking each
348			* element returned by the iterator in turn to see if it's contained
349			* in the specified collection. If it's not so contained, it's removed
350			* from this collection with the iterator's <tt>remove</tt> method.
351			*
352			* <p>Note that this implementation will throw an
353			* <tt>UnsupportedOperationException</tt> if the iterator returned by the
354			* <tt>iterator</tt> method does not implement the <tt>remove</tt> method
355			* and this collection contains one or more elements not present in the
356			* specified collection.
357			*
358			* @throws UnsupportedOperationException {@inheritDoc}
359			* @throws ClassCastException {@inheritDoc}
360			* @throws NullPointerException {@inheritDoc}
361			*
362			* @see #remove(Object)
363			* @see #contains(Object)
364			*/
365			public boolean retainAll(Collection<?> c) {
366			boolean modified = false;
367			Iterator<E> e = iterator();
368			while (e.hasNext()) {
369			if (!c.contains(e.next())) {
370			e.remove();
371			modified = true;
372			}
373			}
374			return modified;
375			}
376
377			/**
378			* {@inheritDoc}
379			*
380			* <p>This implementation iterates over this collection, removing each
381			* element using the <tt>Iterator.remove</tt> operation. Most
382			* implementations will probably choose to override this method for
383			* efficiency.
384			*
385			* <p>Note that this implementation will throw an
386			* <tt>UnsupportedOperationException</tt> if the iterator returned by this
387			* collection's <tt>iterator</tt> method does not implement the
388			* <tt>remove</tt> method and this collection is non-empty.
389			*
390			* @throws UnsupportedOperationException {@inheritDoc}
391			*/
392			public void clear() {
393			Iterator<E> e = iterator();
394			while (e.hasNext()) {
395			e.next();
396			e.remove();
397			}
398			}
399
400
401			// String conversion
402
403			/**
404			* Returns a string representation of this collection. The string
405			* representation consists of a list of the collection's elements in the
406			* order they are returned by its iterator, enclosed in square brackets
407			* (<tt>"[]"</tt>). Adjacent elements are separated by the characters
408			* <tt>", "</tt> (comma and space). Elements are converted to strings as
409			* by {@link String#valueOf(Object)}.
410			*
411			* @return a string representation of this collection
412			*/
413			public String toString() {
414			Iterator<E> i = iterator();
415			if (! i.hasNext())
416			return "[]";
417
418			StringBuilder sb = new StringBuilder();
419			sb.append('[');
420			for (;;) {
421			E e = i.next();
422			sb.append(e == this ? "(this Collection)" : e);
423			if (! i.hasNext())
424			return sb.append(']').toString();
425			sb.append(", ");
426			}
427			}
428
429			}