001 /*
002 * Copyright 1997-2006 Sun Microsystems, Inc. All Rights Reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation. Sun designates this
008 * particular file as subject to the "Classpath" exception as provided
009 * by Sun in the LICENSE file that accompanied this code.
010 *
011 * This code is distributed in the hope that it will be useful, but WITHOUT
012 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
013 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
014 * version 2 for more details (a copy is included in the LICENSE file that
015 * accompanied this code).
016 *
017 * You should have received a copy of the GNU General Public License version
018 * 2 along with this work; if not, write to the Free Software Foundation,
019 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
020 *
021 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
022 * CA 95054 USA or visit www.sun.com if you need additional information or
023 * have any questions.
024 */
025
026 package java.util;
027
028 /**
029 * This class provides a skeletal implementation of the <tt>Collection</tt>
030 * interface, to minimize the effort required to implement this interface. <p>
031 *
032 * To implement an unmodifiable collection, the programmer needs only to
033 * extend this class and provide implementations for the <tt>iterator</tt> and
034 * <tt>size</tt> methods. (The iterator returned by the <tt>iterator</tt>
035 * method must implement <tt>hasNext</tt> and <tt>next</tt>.)<p>
036 *
037 * To implement a modifiable collection, the programmer must additionally
038 * override this class's <tt>add</tt> method (which otherwise throws an
039 * <tt>UnsupportedOperationException</tt>), and the iterator returned by the
040 * <tt>iterator</tt> method must additionally implement its <tt>remove</tt>
041 * method.<p>
042 *
043 * The programmer should generally provide a void (no argument) and
044 * <tt>Collection</tt> constructor, as per the recommendation in the
045 * <tt>Collection</tt> interface specification.<p>
046 *
047 * The documentation for each non-abstract method in this class describes its
048 * implementation in detail. Each of these methods may be overridden if
049 * the collection being implemented admits a more efficient implementation.<p>
050 *
051 * This class is a member of the
052 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
053 * Java Collections Framework</a>.
054 *
055 * @author Josh Bloch
056 * @author Neal Gafter
057 * @version 1.44, 05/05/07
058 * @see Collection
059 * @since 1.2
060 */
061
062 public abstract class AbstractCollection<E> implements Collection<E> {
063 /**
064 * Sole constructor. (For invocation by subclass constructors, typically
065 * implicit.)
066 */
067 protected AbstractCollection() {
068 }
069
070 // Query Operations
071
072 /**
073 * Returns an iterator over the elements contained in this collection.
074 *
075 * @return an iterator over the elements contained in this collection
076 */
077 public abstract Iterator<E> iterator();
078
079 public abstract int size();
080
081 /**
082 * {@inheritDoc}
083 *
084 * <p>This implementation returns <tt>size() == 0</tt>.
085 */
086 public boolean isEmpty() {
087 return size() == 0;
088 }
089
090 /**
091 * {@inheritDoc}
092 *
093 * <p>This implementation iterates over the elements in the collection,
094 * checking each element in turn for equality with the specified element.
095 *
096 * @throws ClassCastException {@inheritDoc}
097 * @throws NullPointerException {@inheritDoc}
098 */
099 public boolean contains(Object o) {
100 Iterator<E> e = iterator();
101 if (o == null) {
102 while (e.hasNext())
103 if (e.next() == null)
104 return true;
105 } else {
106 while (e.hasNext())
107 if (o.equals(e.next()))
108 return true;
109 }
110 return false;
111 }
112
113 /**
114 * {@inheritDoc}
115 *
116 * <p>This implementation returns an array containing all the elements
117 * returned by this collection's iterator, in the same order, stored in
118 * consecutive elements of the array, starting with index {@code 0}.
119 * The length of the returned array is equal to the number of elements
120 * returned by the iterator, even if the size of this collection changes
121 * during iteration, as might happen if the collection permits
122 * concurrent modification during iteration. The {@code size} method is
123 * called only as an optimization hint; the correct result is returned
124 * even if the iterator returns a different number of elements.
125 *
126 * <p>This method is equivalent to:
127 *
128 * <pre> {@code
129 * List<E> list = new ArrayList<E>(size());
130 * for (E e : this)
131 * list.add(e);
132 * return list.toArray();
133 * }</pre>
134 */
135 public Object[] toArray() {
136 // Estimate size of array; be prepared to see more or fewer elements
137 Object[] r = new Object[size()];
138 Iterator<E> it = iterator();
139 for (int i = 0; i < r.length; i++) {
140 if (!it.hasNext()) // fewer elements than expected
141 return Arrays.copyOf(r, i);
142 r[i] = it.next();
143 }
144 return it.hasNext() ? finishToArray(r, it) : r;
145 }
146
147 /**
148 * {@inheritDoc}
149 *
150 * <p>This implementation returns an array containing all the elements
151 * returned by this collection's iterator in the same order, stored in
152 * consecutive elements of the array, starting with index {@code 0}.
153 * If the number of elements returned by the iterator is too large to
154 * fit into the specified array, then the elements are returned in a
155 * newly allocated array with length equal to the number of elements
156 * returned by the iterator, even if the size of this collection
157 * changes during iteration, as might happen if the collection permits
158 * concurrent modification during iteration. The {@code size} method is
159 * called only as an optimization hint; the correct result is returned
160 * even if the iterator returns a different number of elements.
161 *
162 * <p>This method is equivalent to:
163 *
164 * <pre> {@code
165 * List<E> list = new ArrayList<E>(size());
166 * for (E e : this)
167 * list.add(e);
168 * return list.toArray(a);
169 * }</pre>
170 *
171 * @throws ArrayStoreException {@inheritDoc}
172 * @throws NullPointerException {@inheritDoc}
173 */
174 public <T> T[] toArray(T[] a) {
175 // Estimate size of array; be prepared to see more or fewer elements
176 int size = size();
177 T[] r = a.length >= size ? a : (T[]) java.lang.reflect.Array
178 .newInstance(a.getClass().getComponentType(), size);
179 Iterator<E> it = iterator();
180
181 for (int i = 0; i < r.length; i++) {
182 if (!it.hasNext()) { // fewer elements than expected
183 if (a != r)
184 return Arrays.copyOf(r, i);
185 r[i] = null; // null-terminate
186 return r;
187 }
188 r[i] = (T) it.next();
189 }
190 return it.hasNext() ? finishToArray(r, it) : r;
191 }
192
193 /**
194 * Reallocates the array being used within toArray when the iterator
195 * returned more elements than expected, and finishes filling it from
196 * the iterator.
197 *
198 * @param r the array, replete with previously stored elements
199 * @param it the in-progress iterator over this collection
200 * @return array containing the elements in the given array, plus any
201 * further elements returned by the iterator, trimmed to size
202 */
203 private static <T> T[] finishToArray(T[] r, Iterator<?> it) {
204 int i = r.length;
205 while (it.hasNext()) {
206 int cap = r.length;
207 if (i == cap) {
208 int newCap = ((cap / 2) + 1) * 3;
209 if (newCap <= cap) { // integer overflow
210 if (cap == Integer.MAX_VALUE)
211 throw new OutOfMemoryError(
212 "Required array size too large");
213 newCap = Integer.MAX_VALUE;
214 }
215 r = Arrays.copyOf(r, newCap);
216 }
217 r[i++] = (T) it.next();
218 }
219 // trim if overallocated
220 return (i == r.length) ? r : Arrays.copyOf(r, i);
221 }
222
223 // Modification Operations
224
225 /**
226 * {@inheritDoc}
227 *
228 * <p>This implementation always throws an
229 * <tt>UnsupportedOperationException</tt>.
230 *
231 * @throws UnsupportedOperationException {@inheritDoc}
232 * @throws ClassCastException {@inheritDoc}
233 * @throws NullPointerException {@inheritDoc}
234 * @throws IllegalArgumentException {@inheritDoc}
235 * @throws IllegalStateException {@inheritDoc}
236 */
237 public boolean add(E e) {
238 throw new UnsupportedOperationException();
239 }
240
241 /**
242 * {@inheritDoc}
243 *
244 * <p>This implementation iterates over the collection looking for the
245 * specified element. If it finds the element, it removes the element
246 * from the collection using the iterator's remove method.
247 *
248 * <p>Note that this implementation throws an
249 * <tt>UnsupportedOperationException</tt> if the iterator returned by this
250 * collection's iterator method does not implement the <tt>remove</tt>
251 * method and this collection contains the specified object.
252 *
253 * @throws UnsupportedOperationException {@inheritDoc}
254 * @throws ClassCastException {@inheritDoc}
255 * @throws NullPointerException {@inheritDoc}
256 */
257 public boolean remove(Object o) {
258 Iterator<E> e = iterator();
259 if (o == null) {
260 while (e.hasNext()) {
261 if (e.next() == null) {
262 e.remove();
263 return true;
264 }
265 }
266 } else {
267 while (e.hasNext()) {
268 if (o.equals(e.next())) {
269 e.remove();
270 return true;
271 }
272 }
273 }
274 return false;
275 }
276
277 // Bulk Operations
278
279 /**
280 * {@inheritDoc}
281 *
282 * <p>This implementation iterates over the specified collection,
283 * checking each element returned by the iterator in turn to see
284 * if it's contained in this collection. If all elements are so
285 * contained <tt>true</tt> is returned, otherwise <tt>false</tt>.
286 *
287 * @throws ClassCastException {@inheritDoc}
288 * @throws NullPointerException {@inheritDoc}
289 * @see #contains(Object)
290 */
291 public boolean containsAll(Collection<?> c) {
292 Iterator<?> e = c.iterator();
293 while (e.hasNext())
294 if (!contains(e.next()))
295 return false;
296 return true;
297 }
298
299 /**
300 * {@inheritDoc}
301 *
302 * <p>This implementation iterates over the specified collection, and adds
303 * each object returned by the iterator to this collection, in turn.
304 *
305 * <p>Note that this implementation will throw an
306 * <tt>UnsupportedOperationException</tt> unless <tt>add</tt> is
307 * overridden (assuming the specified collection is non-empty).
308 *
309 * @throws UnsupportedOperationException {@inheritDoc}
310 * @throws ClassCastException {@inheritDoc}
311 * @throws NullPointerException {@inheritDoc}
312 * @throws IllegalArgumentException {@inheritDoc}
313 * @throws IllegalStateException {@inheritDoc}
314 *
315 * @see #add(Object)
316 */
317 public boolean addAll(Collection<? extends E> c) {
318 boolean modified = false;
319 Iterator<? extends E> e = c.iterator();
320 while (e.hasNext()) {
321 if (add(e.next()))
322 modified = true;
323 }
324 return modified;
325 }
326
327 /**
328 * {@inheritDoc}
329 *
330 * <p>This implementation iterates over this collection, checking each
331 * element returned by the iterator in turn to see if it's contained
332 * in the specified collection. If it's so contained, it's removed from
333 * this collection with the iterator's <tt>remove</tt> method.
334 *
335 * <p>Note that this implementation will throw an
336 * <tt>UnsupportedOperationException</tt> if the iterator returned by the
337 * <tt>iterator</tt> method does not implement the <tt>remove</tt> method
338 * and this collection contains one or more elements in common with the
339 * specified collection.
340 *
341 * @throws UnsupportedOperationException {@inheritDoc}
342 * @throws ClassCastException {@inheritDoc}
343 * @throws NullPointerException {@inheritDoc}
344 *
345 * @see #remove(Object)
346 * @see #contains(Object)
347 */
348 public boolean removeAll(Collection<?> c) {
349 boolean modified = false;
350 Iterator<?> e = iterator();
351 while (e.hasNext()) {
352 if (c.contains(e.next())) {
353 e.remove();
354 modified = true;
355 }
356 }
357 return modified;
358 }
359
360 /**
361 * {@inheritDoc}
362 *
363 * <p>This implementation iterates over this collection, checking each
364 * element returned by the iterator in turn to see if it's contained
365 * in the specified collection. If it's not so contained, it's removed
366 * from this collection with the iterator's <tt>remove</tt> method.
367 *
368 * <p>Note that this implementation will throw an
369 * <tt>UnsupportedOperationException</tt> if the iterator returned by the
370 * <tt>iterator</tt> method does not implement the <tt>remove</tt> method
371 * and this collection contains one or more elements not present in the
372 * specified collection.
373 *
374 * @throws UnsupportedOperationException {@inheritDoc}
375 * @throws ClassCastException {@inheritDoc}
376 * @throws NullPointerException {@inheritDoc}
377 *
378 * @see #remove(Object)
379 * @see #contains(Object)
380 */
381 public boolean retainAll(Collection<?> c) {
382 boolean modified = false;
383 Iterator<E> e = iterator();
384 while (e.hasNext()) {
385 if (!c.contains(e.next())) {
386 e.remove();
387 modified = true;
388 }
389 }
390 return modified;
391 }
392
393 /**
394 * {@inheritDoc}
395 *
396 * <p>This implementation iterates over this collection, removing each
397 * element using the <tt>Iterator.remove</tt> operation. Most
398 * implementations will probably choose to override this method for
399 * efficiency.
400 *
401 * <p>Note that this implementation will throw an
402 * <tt>UnsupportedOperationException</tt> if the iterator returned by this
403 * collection's <tt>iterator</tt> method does not implement the
404 * <tt>remove</tt> method and this collection is non-empty.
405 *
406 * @throws UnsupportedOperationException {@inheritDoc}
407 */
408 public void clear() {
409 Iterator<E> e = iterator();
410 while (e.hasNext()) {
411 e.next();
412 e.remove();
413 }
414 }
415
416 // String conversion
417
418 /**
419 * Returns a string representation of this collection. The string
420 * representation consists of a list of the collection's elements in the
421 * order they are returned by its iterator, enclosed in square brackets
422 * (<tt>"[]"</tt>). Adjacent elements are separated by the characters
423 * <tt>", "</tt> (comma and space). Elements are converted to strings as
424 * by {@link String#valueOf(Object)}.
425 *
426 * @return a string representation of this collection
427 */
428 public String toString() {
429 Iterator<E> i = iterator();
430 if (!i.hasNext())
431 return "[]";
432
433 StringBuilder sb = new StringBuilder();
434 sb.append('[');
435 for (;;) {
436 E e = i.next();
437 sb.append(e == this ? "(this Collection)" : e);
438 if (!i.hasNext())
439 return sb.append(']').toString();
440 sb.append(", ");
441 }
442 }
443
444 }
|