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 }