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