1 /*
2 * Copyright (c) 1997, 2019, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package java.util;
27
28 import jdk.internal.util.ArraysSupport;
29
30 /**
31 * This class provides a skeletal implementation of the {@code Collection}
32 * interface, to minimize the effort required to implement this interface. <p>
33 *
34 * To implement an unmodifiable collection, the programmer needs only to
35 * extend this class and provide implementations for the {@code iterator} and
36 * {@code size} methods. (The iterator returned by the {@code iterator}
37 * method must implement {@code hasNext} and {@code next}.)<p>
38 *
39 * To implement a modifiable collection, the programmer must additionally
40 * override this class's {@code add} method (which otherwise throws an
41 * {@code UnsupportedOperationException}), and the iterator returned by the
42 * {@code iterator} method must additionally implement its {@code remove}
43 * method.<p>
44 *
45 * The programmer should generally provide a void (no argument) and
46 * {@code Collection} constructor, as per the recommendation in the
47 * {@code Collection} interface specification.<p>
48 *
49 * The documentation for each non-abstract method in this class describes its
50 * implementation in detail. Each of these methods may be overridden if
51 * the collection being implemented admits a more efficient implementation.<p>
52 *
53 * This class is a member of the
54 * <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework">
55 * Java Collections Framework</a>.
56 *
57 * @author Josh Bloch
58 * @author Neal Gafter
59 * @see Collection
60 * @since 1.2
61 */
62
63 public abstract class AbstractCollection<E> implements Collection<E> {
64 /**
65 * Sole constructor. (For invocation by subclass constructors, typically
66 * implicit.)
67 */
68 protected AbstractCollection() {
69 }
70
71 // Query Operations
72
73 /**
74 * Returns an iterator over the elements contained in this collection.
75 *
76 * @return an iterator over the elements contained in this collection
77 */
78 public abstract Iterator<E> iterator();
79
80 public abstract int size();
81
82 /**
83 * {@inheritDoc}
84 *
85 * @implSpec
86 * This implementation returns {@code size() == 0}.
87 */
88 public boolean isEmpty() {
89 return size() == 0;
90 }
91
92 /**
93 * {@inheritDoc}
94 *
95 * @implSpec
96 * This implementation iterates over the elements in the collection,
97 * checking each element in turn for equality with the specified element.
98 *
99 * @throws ClassCastException {@inheritDoc}
100 * @throws NullPointerException {@inheritDoc}
101 */
102 public boolean contains(Object o) {
103 Iterator<E> it = iterator();
104 if (o==null) {
105 while (it.hasNext())
106 if (it.next()==null)
107 return true;
108 } else {
109 while (it.hasNext())
110 if (o.equals(it.next()))
111 return true;
112 }
113 return false;
114 }
115
116 /**
117 * {@inheritDoc}
118 *
119 * @implSpec
120 * This implementation returns an array containing all the elements
121 * returned by this collection's iterator, in the same order, stored in
122 * consecutive elements of the array, starting with index {@code 0}.
123 * The length of the returned array is equal to the number of elements
124 * returned by the iterator, even if the size of this collection changes
125 * during iteration, as might happen if the collection permits
126 * concurrent modification during iteration. The {@code size} method is
127 * called only as an optimization hint; the correct result is returned
128 * even if the iterator returns a different number of elements.
129 *
130 * <p>This method is equivalent to:
131 *
132 * <pre> {@code
133 * List<E> list = new ArrayList<E>(size());
134 * for (E e : this)
135 * list.add(e);
136 * return list.toArray();
137 * }</pre>
138 */
139 public Object[] toArray() {
140 // Estimate size of array; be prepared to see more or fewer elements
141 Object[] r = new Object[size()];
142 Iterator<E> it = iterator();
143 for (int i = 0; i < r.length; i++) {
144 if (! it.hasNext()) // fewer elements than expected
145 return Arrays.copyOf(r, i);
146 r[i] = it.next();
147 }
148 return it.hasNext() ? finishToArray(r, it) : r;
149 }
150
151 /**
152 * {@inheritDoc}
153 *
154 * @implSpec
155 * This implementation returns an array containing all the elements
156 * returned by this collection's iterator in the same order, stored in
157 * consecutive elements of the array, starting with index {@code 0}.
158 * If the number of elements returned by the iterator is too large to
159 * fit into the specified array, then the elements are returned in a
160 * newly allocated array with length equal to the number of elements
161 * returned by the iterator, even if the size of this collection
162 * changes during iteration, as might happen if the collection permits
163 * concurrent modification during iteration. The {@code size} method is
164 * called only as an optimization hint; the correct result is returned
165 * even if the iterator returns a different number of elements.
166 *
167 * <p>This method is equivalent to:
168 *
169 * <pre> {@code
170 * List<E> list = new ArrayList<E>(size());
171 * for (E e : this)
172 * list.add(e);
173 * return list.toArray(a);
174 * }</pre>
175 *
176 * @throws ArrayStoreException {@inheritDoc}
177 * @throws NullPointerException {@inheritDoc}
178 */
179 @SuppressWarnings("unchecked")
180 public <T> T[] toArray(T[] a) {
181 // Estimate size of array; be prepared to see more or fewer elements
182 int size = size();
183 T[] r = a.length >= size ? a :
184 (T[])java.lang.reflect.Array
185 .newInstance(a.getClass().getComponentType(), size);
186 Iterator<E> it = iterator();
187
188 for (int i = 0; i < r.length; i++) {
189 if (! it.hasNext()) { // fewer elements than expected
190 if (a == r) {
191 r[i] = null; // null-terminate
192 } else if (a.length < i) {
193 return Arrays.copyOf(r, i);
194 } else {
195 System.arraycopy(r, 0, a, 0, i);
196 if (a.length > i) {
197 a[i] = null;
198 }
199 }
200 return a;
201 }
202 r[i] = (T)it.next();
203 }
204 // more elements than expected
205 return it.hasNext() ? finishToArray(r, it) : r;
206 }
207
208 /**
209 * Reallocates the array being used within toArray when the iterator
210 * returned more elements than expected, and finishes filling it from
211 * the iterator.
212 *
213 * @param r the array, replete with previously stored elements
214 * @param it the in-progress iterator over this collection
215 * @return array containing the elements in the given array, plus any
216 * further elements returned by the iterator, trimmed to size
217 */
218 @SuppressWarnings("unchecked")
219 private static <T> T[] finishToArray(T[] r, Iterator<?> it) {
220 int len = r.length;
221 int i = len;
222 while (it.hasNext()) {
223 if (i == len) {
224 len = ArraysSupport.calcLength(len,
225 1, /* minimum growth */
226 (len >> 1) + 1 /* preferred growth */);
227 r = Arrays.copyOf(r, len);
228 }
229 r[i++] = (T)it.next();
230 }
231 // trim if overallocated
232 return (i == len) ? r : Arrays.copyOf(r, i);
233 }
234
235 // Modification Operations
236
237 /**
238 * {@inheritDoc}
239 *
240 * @implSpec
241 * This implementation always throws an
242 * {@code UnsupportedOperationException}.
243 *
244 * @throws UnsupportedOperationException {@inheritDoc}
245 * @throws ClassCastException {@inheritDoc}
246 * @throws NullPointerException {@inheritDoc}
247 * @throws IllegalArgumentException {@inheritDoc}
248 * @throws IllegalStateException {@inheritDoc}
249 */
250 public boolean add(E e) {
251 throw new UnsupportedOperationException();
252 }
253
254 /**
255 * {@inheritDoc}
256 *
257 * @implSpec
258 * This implementation iterates over the collection looking for the
259 * specified element. If it finds the element, it removes the element
260 * from the collection using the iterator's remove method.
261 *
262 * <p>Note that this implementation throws an
263 * {@code UnsupportedOperationException} if the iterator returned by this
264 * collection's iterator method does not implement the {@code remove}
265 * method and this collection contains the specified object.
266 *
267 * @throws UnsupportedOperationException {@inheritDoc}
268 * @throws ClassCastException {@inheritDoc}
269 * @throws NullPointerException {@inheritDoc}
270 */
271 public boolean remove(Object o) {
272 Iterator<E> it = iterator();
273 if (o==null) {
274 while (it.hasNext()) {
275 if (it.next()==null) {
276 it.remove();
277 return true;
278 }
279 }
280 } else {
281 while (it.hasNext()) {
282 if (o.equals(it.next())) {
283 it.remove();
284 return true;
285 }
286 }
287 }
288 return false;
289 }
290
291
292 // Bulk Operations
293
294 /**
295 * {@inheritDoc}
296 *
297 * @implSpec
298 * This implementation iterates over the specified collection,
299 * checking each element returned by the iterator in turn to see
300 * if it's contained in this collection. If all elements are so
301 * contained {@code true} is returned, otherwise {@code false}.
302 *
303 * @throws ClassCastException {@inheritDoc}
304 * @throws NullPointerException {@inheritDoc}
305 * @see #contains(Object)
306 */
307 public boolean containsAll(Collection<?> c) {
308 for (Object e : c)
309 if (!contains(e))
310 return false;
311 return true;
312 }
313
314 /**
315 * {@inheritDoc}
316 *
317 * @implSpec
318 * This implementation iterates over the specified collection, and adds
319 * each object returned by the iterator to this collection, in turn.
320 *
321 * <p>Note that this implementation will throw an
322 * {@code UnsupportedOperationException} unless {@code add} is
323 * overridden (assuming the specified collection is non-empty).
324 *
325 * @throws UnsupportedOperationException {@inheritDoc}
326 * @throws ClassCastException {@inheritDoc}
327 * @throws NullPointerException {@inheritDoc}
328 * @throws IllegalArgumentException {@inheritDoc}
329 * @throws IllegalStateException {@inheritDoc}
330 *
331 * @see #add(Object)
332 */
333 public boolean addAll(Collection<? extends E> c) {
334 boolean modified = false;
335 for (E e : c)
336 if (add(e))
337 modified = true;
338 return modified;
339 }
340
341 /**
342 * {@inheritDoc}
343 *
344 * @implSpec
345 * This implementation iterates over this collection, checking each
346 * element returned by the iterator in turn to see if it's contained
347 * in the specified collection. If it's so contained, it's removed from
348 * this collection with the iterator's {@code remove} method.
349 *
350 * <p>Note that this implementation will throw an
351 * {@code UnsupportedOperationException} if the iterator returned by the
352 * {@code iterator} method does not implement the {@code remove} method
353 * and this collection contains one or more elements in common with the
354 * specified collection.
355 *
356 * @throws UnsupportedOperationException {@inheritDoc}
357 * @throws ClassCastException {@inheritDoc}
358 * @throws NullPointerException {@inheritDoc}
359 *
360 * @see #remove(Object)
361 * @see #contains(Object)
362 */
363 public boolean removeAll(Collection<?> c) {
364 Objects.requireNonNull(c);
365 boolean modified = false;
366 Iterator<?> it = iterator();
367 while (it.hasNext()) {
368 if (c.contains(it.next())) {
369 it.remove();
370 modified = true;
371 }
372 }
373 return modified;
374 }
375
376 /**
377 * {@inheritDoc}
378 *
379 * @implSpec
380 * This implementation iterates over this collection, checking each
381 * element returned by the iterator in turn to see if it's contained
382 * in the specified collection. If it's not so contained, it's removed
383 * from this collection with the iterator's {@code remove} method.
384 *
385 * <p>Note that this implementation will throw an
386 * {@code UnsupportedOperationException} if the iterator returned by the
387 * {@code iterator} method does not implement the {@code remove} method
388 * and this collection contains one or more elements not present in the
389 * specified collection.
390 *
391 * @throws UnsupportedOperationException {@inheritDoc}
392 * @throws ClassCastException {@inheritDoc}
393 * @throws NullPointerException {@inheritDoc}
394 *
395 * @see #remove(Object)
396 * @see #contains(Object)
397 */
398 public boolean retainAll(Collection<?> c) {
399 Objects.requireNonNull(c);
400 boolean modified = false;
401 Iterator<E> it = iterator();
402 while (it.hasNext()) {
403 if (!c.contains(it.next())) {
404 it.remove();
405 modified = true;
406 }
407 }
408 return modified;
409 }
410
411 /**
412 * {@inheritDoc}
413 *
414 * @implSpec
415 * This implementation iterates over this collection, removing each
416 * element using the {@code Iterator.remove} operation. Most
417 * implementations will probably choose to override this method for
418 * efficiency.
419 *
420 * <p>Note that this implementation will throw an
421 * {@code UnsupportedOperationException} if the iterator returned by this
422 * collection's {@code iterator} method does not implement the
423 * {@code remove} method and this collection is non-empty.
424 *
425 * @throws UnsupportedOperationException {@inheritDoc}
426 */
427 public void clear() {
428 Iterator<E> it = iterator();
429 while (it.hasNext()) {
430 it.next();
431 it.remove();
432 }
433 }
434
435
436 // String conversion
437
438 /**
439 * Returns a string representation of this collection. The string
440 * representation consists of a list of the collection's elements in the
441 * order they are returned by its iterator, enclosed in square brackets
442 * ({@code "[]"}). Adjacent elements are separated by the characters
443 * {@code ", "} (comma and space). Elements are converted to strings as
444 * by {@link String#valueOf(Object)}.
445 *
446 * @return a string representation of this collection
447 */
448 public String toString() {
449 Iterator<E> it = iterator();
450 if (! it.hasNext())
451 return "[]";
452
453 StringBuilder sb = new StringBuilder();
454 sb.append('[');
455 for (;;) {
456 E e = it.next();
457 sb.append(e == this ? "(this Collection)" : e);
458 if (! it.hasNext())
459 return sb.append(']').toString();
460 sb.append(',').append(' ');
461 }
462 }
463
464 }