| AbstractCollection.java |
1 /*
2 * %W% %E%
3 *
4 * Copyright (c) 2006, Oracle and/or its affiliates. All rights reserved.
5 * ORACLE 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 * The documentation for each non-abstract method in this class describes its
30 * 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 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
35 * Java Collections Framework</a>.
36 *
37 * @author Josh Bloch
38 * @author Neal Gafter
39 * @version %I%, %G%
40 * @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 * <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 */
117 public Object[] toArray() {
118 // Estimate size of array; be prepared to see more or fewer elements
119 Object[] r = new Object[size()];
120 Iterator<E> it = iterator();
121 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 }
128
129 /**
130 * {@inheritDoc}
131 *
132 * <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 *
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 T[] r = a.length >= size ? a :
160 (T[])java.lang.reflect.Array
161 .newInstance(a.getClass().getComponentType(), size);
162 Iterator<E> it = iterator();
163
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 }
175
176 /**
177 * 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 * @return array containing the elements in the given array, plus any
184 * further elements returned by the iterator, trimmed to size
185 */
186 private static <T> T[] finishToArray(T[] r, Iterator<?> it) {
187 int i = r.length;
188 while (it.hasNext()) {
189 int cap = r.length;
190 if (i == cap) {
191 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 newCap = Integer.MAX_VALUE;
197 }
198 r = Arrays.copyOf(r, newCap);
199 }
200 r[i++] = (T)it.next();
201 }
202 // trim if overallocated
203 return (i == r.length) ? r : Arrays.copyOf(r, i);
204 }
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 }
430