001    /* AbstractCollection.java -- Abstract implementation of most of Collection
002       Copyright (C) 1998, 2000, 2001, 2004, 2005 Free Software Foundation, Inc.
003    
004    This file is part of GNU Classpath.
005    
006    GNU Classpath is free software; you can redistribute it and/or modify
007    it under the terms of the GNU General Public License as published by
008    the Free Software Foundation; either version 2, or (at your option)
009    any later version.
010    
011    GNU Classpath is distributed in the hope that it will be useful, but
012    WITHOUT ANY WARRANTY; without even the implied warranty of
013    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
014    General Public License for more details.
015    
016    You should have received a copy of the GNU General Public License
017    along with GNU Classpath; see the file COPYING.  If not, write to the
018    Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
019    02110-1301 USA.
020    
021    Linking this library statically or dynamically with other modules is
022    making a combined work based on this library.  Thus, the terms and
023    conditions of the GNU General Public License cover the whole
024    combination.
025    
026    As a special exception, the copyright holders of this library give you
027    permission to link this library with independent modules to produce an
028    executable, regardless of the license terms of these independent
029    modules, and to copy and distribute the resulting executable under
030    terms of your choice, provided that you also meet, for each linked
031    independent module, the terms and conditions of the license of that
032    module.  An independent module is a module which is not derived from
033    or based on this library.  If you modify this library, you may extend
034    this exception to your version of the library, but you are not
035    obligated to do so.  If you do not wish to do so, delete this
036    exception statement from your version. */
037    
038    
039    package java.util;
040    
041    import java.lang.reflect.Array;
042    
043    /**
044     * A basic implementation of most of the methods in the Collection interface to
045     * make it easier to create a collection. To create an unmodifiable Collection,
046     * just subclass AbstractCollection and provide implementations of the
047     * iterator() and size() methods. The Iterator returned by iterator() need only
048     * provide implementations of hasNext() and next() (that is, it may throw an
049     * UnsupportedOperationException if remove() is called). To create a modifiable
050     * Collection, you must in addition provide an implementation of the
051     * add(Object) method and the Iterator returned by iterator() must provide an
052     * implementation of remove(). Other methods should be overridden if the
053     * backing data structure allows for a more efficient implementation. The
054     * precise implementation used by AbstractCollection is documented, so that
055     * subclasses can tell which methods could be implemented more efficiently.
056     * <p>
057     *
058     * The programmer should provide a no-argument constructor, and one that
059     * accepts another Collection, as recommended by the Collection interface.
060     * Unfortunately, there is no way to enforce this in Java.
061     *
062     * @author Original author unknown
063     * @author Bryce McKinlay
064     * @author Eric Blake (ebb9@email.byu.edu)
065     * @author Tom Tromey (tromey@redhat.com)
066     * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
067     * @see Collection
068     * @see AbstractSet
069     * @see AbstractList
070     * @since 1.2
071     * @status updated to 1.4
072     */
073    public abstract class AbstractCollection<E>
074      implements Collection<E>, Iterable<E>
075    {
076      /**
077       * The main constructor, for use by subclasses.
078       */
079      protected AbstractCollection()
080      {
081      }
082    
083      /**
084       * Return an Iterator over this collection. The iterator must provide the
085       * hasNext and next methods and should in addition provide remove if the
086       * collection is modifiable.
087       *
088       * @return an iterator
089       */
090      public abstract Iterator<E> iterator();
091    
092      /**
093       * Return the number of elements in this collection. If there are more than
094       * Integer.MAX_VALUE elements, return Integer.MAX_VALUE.
095       *
096       * @return the size
097       */
098      public abstract int size();
099    
100      /**
101       * Add an object to the collection (optional operation). This implementation
102       * always throws an UnsupportedOperationException - it should be
103       * overridden if the collection is to be modifiable. If the collection
104       * does not accept duplicates, simply return false. Collections may specify
105       * limitations on what may be added.
106       *
107       * @param o the object to add
108       * @return true if the add operation caused the Collection to change
109       * @throws UnsupportedOperationException if the add operation is not
110       *         supported on this collection
111       * @throws NullPointerException if the collection does not support null
112       * @throws ClassCastException if the object is of the wrong type
113       * @throws IllegalArgumentException if some aspect of the object prevents
114       *         it from being added
115       */
116      public boolean add(E o)
117      {
118        throw new UnsupportedOperationException();
119      }
120    
121      /**
122       * Add all the elements of a given collection to this collection (optional
123       * operation). This implementation obtains an Iterator over the given
124       * collection and iterates over it, adding each element with the
125       * add(Object) method (thus this method will fail with an
126       * UnsupportedOperationException if the add method does). The behavior is
127       * unspecified if the specified collection is modified during the iteration,
128       * including the special case of trying addAll(this) on a non-empty
129       * collection.
130       *
131       * @param c the collection to add the elements of to this collection
132       * @return true if the add operation caused the Collection to change
133       * @throws UnsupportedOperationException if the add operation is not
134       *         supported on this collection
135       * @throws NullPointerException if the specified collection is null
136       * @throws ClassCastException if the type of any element in c is
137       *         not a valid type for addition.
138       * @throws IllegalArgumentException if some aspect of any element
139       *         in c prevents it being added.
140       * @throws NullPointerException if any element in c is null and this
141       *         collection doesn't allow null values.
142       * @see #add(Object)
143       */
144      public boolean addAll(Collection<? extends E> c)
145      {
146        Iterator<? extends E> itr = c.iterator();
147        boolean modified = false;
148        int pos = c.size();
149        while (--pos >= 0)
150          modified |= add(itr.next());
151        return modified;
152      }
153    
154      /**
155       * Remove all elements from the collection (optional operation). This
156       * implementation obtains an iterator over the collection and calls next
157       * and remove on it repeatedly (thus this method will fail with an
158       * UnsupportedOperationException if the Iterator's remove method does)
159       * until there are no more elements to remove.
160       * Many implementations will have a faster way of doing this.
161       *
162       * @throws UnsupportedOperationException if the Iterator returned by
163       *         iterator does not provide an implementation of remove
164       * @see Iterator#remove()
165       */
166      public void clear()
167      {
168        Iterator<E> itr = iterator();
169        int pos = size();
170        while (--pos >= 0)
171          {
172            itr.next();
173            itr.remove();
174          }
175      }
176    
177      /**
178       * Test whether this collection contains a given object. That is, if the
179       * collection has an element e such that (o == null ? e == null :
180       * o.equals(e)). This implementation obtains an iterator over the collection
181       * and iterates over it, testing each element for equality with the given
182       * object. If it is equal, true is returned. Otherwise false is returned when
183       * the end of the collection is reached.
184       *
185       * @param o the object to remove from this collection
186       * @return true if this collection contains an object equal to o
187       */
188      public boolean contains(Object o)
189      {
190        Iterator<E> itr = iterator();
191        int pos = size();
192        while (--pos >= 0)
193          if (equals(o, itr.next()))
194            return true;
195        return false;
196      }
197    
198      /**
199       * Tests whether this collection contains all the elements in a given
200       * collection. This implementation iterates over the given collection,
201       * testing whether each element is contained in this collection. If any one
202       * is not, false is returned. Otherwise true is returned.
203       *
204       * @param c the collection to test against
205       * @return true if this collection contains all the elements in the given
206       *         collection
207       * @throws NullPointerException if the given collection is null
208       * @see #contains(Object)
209       */
210      public boolean containsAll(Collection<?> c)
211      {
212        Iterator<?> itr = c.iterator();
213        int pos = c.size();
214        while (--pos >= 0)
215          if (!contains(itr.next()))
216            return false;
217        return true;
218      }
219    
220      /**
221       * Test whether this collection is empty. This implementation returns
222       * size() == 0.
223       *
224       * @return true if this collection is empty.
225       * @see #size()
226       */
227      public boolean isEmpty()
228      {
229        return size() == 0;
230      }
231    
232      /**
233       * Remove a single instance of an object from this collection (optional
234       * operation). That is, remove one element e such that
235       * <code>(o == null ? e == null : o.equals(e))</code>, if such an element
236       * exists. This implementation obtains an iterator over the collection
237       * and iterates over it, testing each element for equality with the given
238       * object. If it is equal, it is removed by the iterator's remove method
239       * (thus this method will fail with an UnsupportedOperationException if
240       * the Iterator's remove method does). After the first element has been
241       * removed, true is returned; if the end of the collection is reached, false
242       * is returned.
243       *
244       * @param o the object to remove from this collection
245       * @return true if the remove operation caused the Collection to change, or
246       *         equivalently if the collection did contain o.
247       * @throws UnsupportedOperationException if this collection's Iterator
248       *         does not support the remove method
249       * @see Iterator#remove()
250       */
251      public boolean remove(Object o)
252      {
253        Iterator<E> itr = iterator();
254        int pos = size();
255        while (--pos >= 0)
256          if (equals(o, itr.next()))
257            {
258              itr.remove();
259              return true;
260            }
261        return false;
262      }
263    
264      /**
265       * Remove from this collection all its elements that are contained in a given
266       * collection (optional operation). This implementation iterates over this
267       * collection, and for each element tests if it is contained in the given
268       * collection. If so, it is removed by the Iterator's remove method (thus
269       * this method will fail with an UnsupportedOperationException if the
270       * Iterator's remove method does).
271       *
272       * @param c the collection to remove the elements of
273       * @return true if the remove operation caused the Collection to change
274       * @throws UnsupportedOperationException if this collection's Iterator
275       *         does not support the remove method
276       * @throws NullPointerException if the collection, c, is null.
277       * @see Iterator#remove()
278       */
279      public boolean removeAll(Collection<?> c)
280      {
281        return removeAllInternal(c);
282      }
283    
284      /**
285       * Remove from this collection all its elements that are contained in a given
286       * collection (optional operation). This implementation iterates over this
287       * collection, and for each element tests if it is contained in the given
288       * collection. If so, it is removed by the Iterator's remove method (thus
289       * this method will fail with an UnsupportedOperationException if the
290       * Iterator's remove method does). This method is necessary for ArrayList,
291       * which cannot publicly override removeAll but can optimize this call.
292       *
293       * @param c the collection to remove the elements of
294       * @return true if the remove operation caused the Collection to change
295       * @throws UnsupportedOperationException if this collection's Iterator
296       *         does not support the remove method
297       * @throws NullPointerException if the collection, c, is null.
298       * @see Iterator#remove()
299       */
300      // Package visible for use throughout java.util.
301      boolean removeAllInternal(Collection<?> c)
302      {
303        Iterator<E> itr = iterator();
304        boolean modified = false;
305        int pos = size();
306        while (--pos >= 0)
307          if (c.contains(itr.next()))
308            {
309              itr.remove();
310              modified = true;
311            }
312        return modified;
313      }
314    
315      /**
316       * Remove from this collection all its elements that are not contained in a
317       * given collection (optional operation). This implementation iterates over
318       * this collection, and for each element tests if it is contained in the
319       * given collection. If not, it is removed by the Iterator's remove method
320       * (thus this method will fail with an UnsupportedOperationException if
321       * the Iterator's remove method does).
322       *
323       * @param c the collection to retain the elements of
324       * @return true if the remove operation caused the Collection to change
325       * @throws UnsupportedOperationException if this collection's Iterator
326       *         does not support the remove method
327       * @throws NullPointerException if the collection, c, is null.
328       * @see Iterator#remove()
329       */
330      public boolean retainAll(Collection<?> c)
331      {
332        return retainAllInternal(c);
333      }
334    
335      /**
336       * Remove from this collection all its elements that are not contained in a
337       * given collection (optional operation). This implementation iterates over
338       * this collection, and for each element tests if it is contained in the
339       * given collection. If not, it is removed by the Iterator's remove method
340       * (thus this method will fail with an UnsupportedOperationException if
341       * the Iterator's remove method does). This method is necessary for
342       * ArrayList, which cannot publicly override retainAll but can optimize
343       * this call.
344       *
345       * @param c the collection to retain the elements of
346       * @return true if the remove operation caused the Collection to change
347       * @throws UnsupportedOperationException if this collection's Iterator
348       *         does not support the remove method
349       * @throws NullPointerException if the collection, c, is null.
350       * @see Iterator#remove()
351       */
352      // Package visible for use throughout java.util.
353      boolean retainAllInternal(Collection<?> c)
354      {
355        Iterator<E> itr = iterator();
356        boolean modified = false;
357        int pos = size();
358        while (--pos >= 0)
359          if (!c.contains(itr.next()))
360            {
361              itr.remove();
362              modified = true;
363            }
364        return modified;
365      }
366    
367      /**
368       * Return an array containing the elements of this collection. This
369       * implementation creates an Object array of size size() and then iterates
370       * over the collection, setting each element of the array from the value
371       * returned by the iterator. The returned array is safe, and is not backed
372       * by the collection.
373       *
374       * @return an array containing the elements of this collection
375       */
376      public Object[] toArray()
377      {
378        Iterator<E> itr = iterator();
379        int size = size();
380        Object[] a = new Object[size];
381        for (int pos = 0; pos < size; pos++)
382          a[pos] = itr.next();
383        return a;
384      }
385    
386      /**
387       * Copy the collection into a given array if it will fit, or into a
388       * dynamically created array of the same run-time type as the given array if
389       * not. If there is space remaining in the array, the first element after the
390       * end of the collection is set to null (this is only useful if the
391       * collection is known to contain no null elements, however). This
392       * implementation first tests whether the given array is large enough to hold
393       * all the elements of the collection. If not, the reflection API is used to
394       * allocate a new array of the same run-time type. Next an iterator is
395       * obtained over the collection and the elements are placed in the array as
396       * they are returned by the iterator. Finally the first spare element, if
397       * any, of the array is set to null, and the created array is returned.
398       * The returned array is safe; it is not backed by the collection. Note that
399       * null may not mark the last element, if the collection allows null
400       * elements.
401       *
402       * @param a the array to copy into, or of the correct run-time type
403       * @return the array that was produced
404       * @throws NullPointerException if the given array is null
405       * @throws ArrayStoreException if the type of the array precludes holding
406       *         one of the elements of the Collection
407       */
408      public <T> T[] toArray(T[] a)
409      {
410        int size = size();
411        if (a.length < size)
412          a = (T[]) Array.newInstance(a.getClass().getComponentType(),
413                                           size);
414        else if (a.length > size)
415          a[size] = null;
416    
417        Iterator<E> itr = iterator();
418        for (int pos = 0; pos < size; pos++)
419          a[pos] = (T) (itr.next());
420        return a;
421      }
422    
423      /**
424       * Creates a String representation of the Collection. The string returned is
425       * of the form "[a, b, ...]" where a and b etc are the results of calling
426       * toString on the elements of the collection. This implementation obtains an
427       * Iterator over the Collection and adds each element to a StringBuffer as it
428       * is returned by the iterator. "<this>" is inserted when the collection
429       * contains itself (only works for direct containment, not for collections
430       * inside collections).
431       *
432       * @return a String representation of the Collection
433       */
434      public String toString()
435      {
436        Iterator itr = iterator();
437        StringBuffer r = new StringBuffer("[");
438        boolean hasNext = itr.hasNext();
439        while (hasNext)
440          {
441            Object o = itr.next();
442            if (o == this)
443              r.append("<this>");
444            else
445              r.append(o);
446            hasNext = itr.hasNext();
447            if (hasNext)
448              r.append(", ");
449          }
450        r.append("]");
451        return r.toString();
452      }
453    
454      /**
455       * Compare two objects according to Collection semantics.
456       *
457       * @param o1 the first object
458       * @param o2 the second object
459       * @return o1 == null ? o2 == null : o1.equals(o2)
460       */
461      // Package visible for use throughout java.util.
462      // It may be inlined since it is final.
463      static final boolean equals(Object o1, Object o2)
464      {
465        return o1 == null ? o2 == null : o1.equals(o2);
466      }
467    
468      /**
469       * Hash an object according to Collection semantics.
470       *
471       * @param o the object to hash
472       * @return o1 == null ? 0 : o1.hashCode()
473       */
474      // Package visible for use throughout java.util.
475      // It may be inlined since it is final.
476      static final int hashCode(Object o)
477      {
478        return o == null ? 0 : o.hashCode();
479      }
480    }