1 /*
2 * Copyright (c) 1997, 2013, 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 java.util.function.Predicate;
29 import java.util.stream.Stream;
30 import java.util.stream.StreamSupport;
31
32 /**
33 * The root interface in the <i>collection hierarchy</i>. A collection
34 * represents a group of objects, known as its <i>elements</i>. Some
35 * collections allow duplicate elements and others do not. Some are ordered
36 * and others unordered. The JDK does not provide any <i>direct</i>
37 * implementations of this interface: it provides implementations of more
38 * specific subinterfaces like <tt>Set</tt> and <tt>List</tt>. This interface
39 * is typically used to pass collections around and manipulate them where
40 * maximum generality is desired.
41 *
42 * <p><i>Bags</i> or <i>multisets</i> (unordered collections that may contain
43 * duplicate elements) should implement this interface directly.
44 *
45 * <p>All general-purpose <tt>Collection</tt> implementation classes (which
46 * typically implement <tt>Collection</tt> indirectly through one of its
47 * subinterfaces) should provide two "standard" constructors: a void (no
48 * arguments) constructor, which creates an empty collection, and a
49 * constructor with a single argument of type <tt>Collection</tt>, which
50 * creates a new collection with the same elements as its argument. In
51 * effect, the latter constructor allows the user to copy any collection,
52 * producing an equivalent collection of the desired implementation type.
53 * There is no way to enforce this convention (as interfaces cannot contain
54 * constructors) but all of the general-purpose <tt>Collection</tt>
55 * implementations in the Java platform libraries comply.
56 *
57 * <p>The "destructive" methods contained in this interface, that is, the
58 * methods that modify the collection on which they operate, are specified to
59 * throw <tt>UnsupportedOperationException</tt> if this collection does not
60 * support the operation. If this is the case, these methods may, but are not
61 * required to, throw an <tt>UnsupportedOperationException</tt> if the
62 * invocation would have no effect on the collection. For example, invoking
63 * the {@link #addAll(Collection)} method on an unmodifiable collection may,
64 * but is not required to, throw the exception if the collection to be added
65 * is empty.
66 *
67 * <p><a name="optional-restrictions"/>
68 * Some collection implementations have restrictions on the elements that
69 * they may contain. For example, some implementations prohibit null elements,
70 * and some have restrictions on the types of their elements. Attempting to
71 * add an ineligible element throws an unchecked exception, typically
72 * <tt>NullPointerException</tt> or <tt>ClassCastException</tt>. Attempting
73 * to query the presence of an ineligible element may throw an exception,
74 * or it may simply return false; some implementations will exhibit the former
75 * behavior and some will exhibit the latter. More generally, attempting an
76 * operation on an ineligible element whose completion would not result in
77 * the insertion of an ineligible element into the collection may throw an
78 * exception or it may succeed, at the option of the implementation.
79 * Such exceptions are marked as "optional" in the specification for this
80 * interface.
81 *
82 * <p>It is up to each collection to determine its own synchronization
83 * policy. In the absence of a stronger guarantee by the
84 * implementation, undefined behavior may result from the invocation
85 * of any method on a collection that is being mutated by another
86 * thread; this includes direct invocations, passing the collection to
87 * a method that might perform invocations, and using an existing
88 * iterator to examine the collection.
89 *
90 * <p>Many methods in Collections Framework interfaces are defined in
91 * terms of the {@link Object#equals(Object) equals} method. For example,
92 * the specification for the {@link #contains(Object) contains(Object o)}
93 * method says: "returns <tt>true</tt> if and only if this collection
94 * contains at least one element <tt>e</tt> such that
95 * <tt>(o==null ? e==null : o.equals(e))</tt>." This specification should
96 * <i>not</i> be construed to imply that invoking <tt>Collection.contains</tt>
97 * with a non-null argument <tt>o</tt> will cause <tt>o.equals(e)</tt> to be
98 * invoked for any element <tt>e</tt>. Implementations are free to implement
99 * optimizations whereby the <tt>equals</tt> invocation is avoided, for
100 * example, by first comparing the hash codes of the two elements. (The
101 * {@link Object#hashCode()} specification guarantees that two objects with
102 * unequal hash codes cannot be equal.) More generally, implementations of
103 * the various Collections Framework interfaces are free to take advantage of
104 * the specified behavior of underlying {@link Object} methods wherever the
105 * implementor deems it appropriate.
106 *
107 * <p>This interface is a member of the
108 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
109 * Java Collections Framework</a>.
110 *
111 * @implSpec
112 * The default method implementations (inherited or otherwise) do not apply any
113 * synchronization protocol. If a {@code Collection} implementation has a
114 * specific synchronization protocol, then it must override default
115 * implementations to apply that protocol.
116 *
117 * @param <E> the type of elements in this collection
118 *
119 * @author Josh Bloch
120 * @author Neal Gafter
121 * @see Set
122 * @see List
123 * @see Map
124 * @see SortedSet
125 * @see SortedMap
126 * @see HashSet
127 * @see TreeSet
128 * @see ArrayList
129 * @see LinkedList
130 * @see Vector
131 * @see Collections
132 * @see Arrays
133 * @see AbstractCollection
134 * @since 1.2
135 */
136
137 public interface Collection<E> extends Iterable<E> {
138 // Query Operations
139
140 /**
141 * Returns the number of elements in this collection. If this collection
142 * contains more than <tt>Integer.MAX_VALUE</tt> elements, returns
143 * <tt>Integer.MAX_VALUE</tt>.
144 *
145 * @return the number of elements in this collection
146 */
147 int size();
148
149 /**
150 * Returns <tt>true</tt> if this collection contains no elements.
151 *
152 * @return <tt>true</tt> if this collection contains no elements
153 */
154 boolean isEmpty();
155
156 /**
157 * Returns <tt>true</tt> if this collection contains the specified element.
158 * More formally, returns <tt>true</tt> if and only if this collection
159 * contains at least one element <tt>e</tt> such that
160 * <tt>(o==null ? e==null : o.equals(e))</tt>.
161 *
162 * @param o element whose presence in this collection is to be tested
163 * @return <tt>true</tt> if this collection contains the specified
164 * element
165 * @throws ClassCastException if the type of the specified element
166 * is incompatible with this collection
167 * (<a href="#optional-restrictions">optional</a>)
168 * @throws NullPointerException if the specified element is null and this
169 * collection does not permit null elements
170 * (<a href="#optional-restrictions">optional</a>)
171 */
172 boolean contains(Object o);
173
174 /**
175 * Returns an iterator over the elements in this collection. There are no
176 * guarantees concerning the order in which the elements are returned
177 * (unless this collection is an instance of some class that provides a
178 * guarantee).
179 *
180 * @return an <tt>Iterator</tt> over the elements in this collection
181 */
182 Iterator<E> iterator();
183
184 /**
185 * Returns an array containing all of the elements in this collection.
186 * If this collection makes any guarantees as to what order its elements
187 * are returned by its iterator, this method must return the elements in
188 * the same order.
189 *
190 * <p>The returned array will be "safe" in that no references to it are
191 * maintained by this collection. (In other words, this method must
192 * allocate a new array even if this collection is backed by an array).
193 * The caller is thus free to modify the returned array.
194 *
195 * <p>This method acts as bridge between array-based and collection-based
196 * APIs.
197 *
198 * @return an array containing all of the elements in this collection
199 */
200 Object[] toArray();
201
202 /**
203 * Returns an array containing all of the elements in this collection;
204 * the runtime type of the returned array is that of the specified array.
205 * If the collection fits in the specified array, it is returned therein.
206 * Otherwise, a new array is allocated with the runtime type of the
207 * specified array and the size of this collection.
208 *
209 * <p>If this collection fits in the specified array with room to spare
210 * (i.e., the array has more elements than this collection), the element
211 * in the array immediately following the end of the collection is set to
212 * <tt>null</tt>. (This is useful in determining the length of this
213 * collection <i>only</i> if the caller knows that this collection does
214 * not contain any <tt>null</tt> elements.)
215 *
216 * <p>If this collection makes any guarantees as to what order its elements
217 * are returned by its iterator, this method must return the elements in
218 * the same order.
219 *
220 * <p>Like the {@link #toArray()} method, this method acts as bridge between
221 * array-based and collection-based APIs. Further, this method allows
222 * precise control over the runtime type of the output array, and may,
223 * under certain circumstances, be used to save allocation costs.
224 *
225 * <p>Suppose <tt>x</tt> is a collection known to contain only strings.
226 * The following code can be used to dump the collection into a newly
227 * allocated array of <tt>String</tt>:
228 *
229 * <pre>
230 * String[] y = x.toArray(new String[0]);</pre>
231 *
232 * Note that <tt>toArray(new Object[0])</tt> is identical in function to
233 * <tt>toArray()</tt>.
234 *
235 * @param a the array into which the elements of this collection are to be
236 * stored, if it is big enough; otherwise, a new array of the same
237 * runtime type is allocated for this purpose.
238 * @return an array containing all of the elements in this collection
239 * @throws ArrayStoreException if the runtime type of the specified array
240 * is not a supertype of the runtime type of every element in
241 * this collection
242 * @throws NullPointerException if the specified array is null
243 */
244 <T> T[] toArray(T[] a);
245
246 // Modification Operations
247
248 /**
249 * Ensures that this collection contains the specified element (optional
250 * operation). Returns <tt>true</tt> if this collection changed as a
251 * result of the call. (Returns <tt>false</tt> if this collection does
252 * not permit duplicates and already contains the specified element.)<p>
253 *
254 * Collections that support this operation may place limitations on what
255 * elements may be added to this collection. In particular, some
256 * collections will refuse to add <tt>null</tt> elements, and others will
257 * impose restrictions on the type of elements that may be added.
258 * Collection classes should clearly specify in their documentation any
259 * restrictions on what elements may be added.<p>
260 *
261 * If a collection refuses to add a particular element for any reason
262 * other than that it already contains the element, it <i>must</i> throw
263 * an exception (rather than returning <tt>false</tt>). This preserves
264 * the invariant that a collection always contains the specified element
265 * after this call returns.
266 *
267 * @param e element whose presence in this collection is to be ensured
268 * @return <tt>true</tt> if this collection changed as a result of the
269 * call
270 * @throws UnsupportedOperationException if the <tt>add</tt> operation
271 * is not supported by this collection
272 * @throws ClassCastException if the class of the specified element
273 * prevents it from being added to this collection
274 * @throws NullPointerException if the specified element is null and this
275 * collection does not permit null elements
276 * @throws IllegalArgumentException if some property of the element
277 * prevents it from being added to this collection
278 * @throws IllegalStateException if the element cannot be added at this
279 * time due to insertion restrictions
280 */
281 boolean add(E e);
282
283 /**
284 * Removes a single instance of the specified element from this
285 * collection, if it is present (optional operation). More formally,
286 * removes an element <tt>e</tt> such that
287 * <tt>(o==null ? e==null : o.equals(e))</tt>, if
288 * this collection contains one or more such elements. Returns
289 * <tt>true</tt> if this collection contained the specified element (or
290 * equivalently, if this collection changed as a result of the call).
291 *
292 * @param o element to be removed from this collection, if present
293 * @return <tt>true</tt> if an element was removed as a result of this call
294 * @throws ClassCastException if the type of the specified element
295 * is incompatible with this collection
296 * (<a href="#optional-restrictions">optional</a>)
297 * @throws NullPointerException if the specified element is null and this
298 * collection does not permit null elements
299 * (<a href="#optional-restrictions">optional</a>)
300 * @throws UnsupportedOperationException if the <tt>remove</tt> operation
301 * is not supported by this collection
302 */
303 boolean remove(Object o);
304
305
306 // Bulk Operations
307
308 /**
309 * Returns <tt>true</tt> if this collection contains all of the elements
310 * in the specified collection.
311 *
312 * @param c collection to be checked for containment in this collection
313 * @return <tt>true</tt> if this collection contains all of the elements
314 * in the specified collection
315 * @throws ClassCastException if the types of one or more elements
316 * in the specified collection are incompatible with this
317 * collection
318 * (<a href="#optional-restrictions">optional</a>)
319 * @throws NullPointerException if the specified collection contains one
320 * or more null elements and this collection does not permit null
321 * elements
322 * (<a href="#optional-restrictions">optional</a>),
323 * or if the specified collection is null.
324 * @see #contains(Object)
325 */
326 boolean containsAll(Collection<?> c);
327
328 /**
329 * Adds all of the elements in the specified collection to this collection
330 * (optional operation). The behavior of this operation is undefined if
331 * the specified collection is modified while the operation is in progress.
332 * (This implies that the behavior of this call is undefined if the
333 * specified collection is this collection, and this collection is
334 * nonempty.)
335 *
336 * @param c collection containing elements to be added to this collection
337 * @return <tt>true</tt> if this collection changed as a result of the call
338 * @throws UnsupportedOperationException if the <tt>addAll</tt> operation
339 * is not supported by this collection
340 * @throws ClassCastException if the class of an element of the specified
341 * collection prevents it from being added to this collection
342 * @throws NullPointerException if the specified collection contains a
343 * null element and this collection does not permit null elements,
344 * or if the specified collection is null
345 * @throws IllegalArgumentException if some property of an element of the
346 * specified collection prevents it from being added to this
347 * collection
348 * @throws IllegalStateException if not all the elements can be added at
349 * this time due to insertion restrictions
350 * @see #add(Object)
351 */
352 boolean addAll(Collection<? extends E> c);
353
354 /**
355 * Removes all of this collection's elements that are also contained in the
356 * specified collection (optional operation). After this call returns,
357 * this collection will contain no elements in common with the specified
358 * collection.
359 *
360 * @param c collection containing elements to be removed from this collection
361 * @return <tt>true</tt> if this collection changed as a result of the
362 * call
363 * @throws UnsupportedOperationException if the <tt>removeAll</tt> method
364 * is not supported by this collection
365 * @throws ClassCastException if the types of one or more elements
366 * in this collection are incompatible with the specified
367 * collection
368 * (<a href="#optional-restrictions">optional</a>)
369 * @throws NullPointerException if this collection contains one or more
370 * null elements and the specified collection does not support
371 * null elements
372 * (<a href="#optional-restrictions">optional</a>),
373 * or if the specified collection is null
374 * @see #remove(Object)
375 * @see #contains(Object)
376 */
377 boolean removeAll(Collection<?> c);
378
379 /**
380 * Removes all of the elements of this collection which match the provided
381 * predicate. Exceptions thrown by the predicate are relayed to the caller.
382 *
383 * @implSpec
384 * The default implementation traverses all elements of the collection using
385 * its {@link #iterator}. Each matching element is removed using
386 * {@link Iterator#remove()}. If the collection's iterator does not
387 * support removal then an {@code UnsupportedOperationException} will be
388 * thrown on the first matching element.
389 *
390 * @param filter a predicate which returns {@code true} for elements to be
391 * removed
392 * @return {@code true} if any elements were removed
393 * @throws NullPointerException if the specified filter is null
394 * @throws UnsupportedOperationException if the {@code removeIf}
395 * method is not supported by this collection
396 * @since 1.8
397 */
398 default boolean removeIf(Predicate<? super E> filter) {
399 Objects.requireNonNull(filter);
400 boolean removed = false;
401 final Iterator<E> each = iterator();
402 while (each.hasNext()) {
403 if (filter.test(each.next())) {
404 each.remove();
405 removed = true;
406 }
407 }
408 return removed;
409 }
410
411 /**
412 * Retains only the elements in this collection that are contained in the
413 * specified collection (optional operation). In other words, removes from
414 * this collection all of its elements that are not contained in the
415 * specified collection.
416 *
417 * @param c collection containing elements to be retained in this collection
418 * @return <tt>true</tt> if this collection changed as a result of the call
419 * @throws UnsupportedOperationException if the <tt>retainAll</tt> operation
420 * is not supported by this collection
421 * @throws ClassCastException if the types of one or more elements
422 * in this collection are incompatible with the specified
423 * collection
424 * (<a href="#optional-restrictions">optional</a>)
425 * @throws NullPointerException if this collection contains one or more
426 * null elements and the specified collection does not permit null
427 * elements
428 * (<a href="#optional-restrictions">optional</a>),
429 * or if the specified collection is null
430 * @see #remove(Object)
431 * @see #contains(Object)
432 */
433 boolean retainAll(Collection<?> c);
434
435 /**
436 * Removes all of the elements from this collection (optional operation).
437 * The collection will be empty after this method returns.
438 *
439 * @throws UnsupportedOperationException if the <tt>clear</tt> operation
440 * is not supported by this collection
441 */
442 void clear();
443
444
445 // Comparison and hashing
446
447 /**
448 * Compares the specified object with this collection for equality. <p>
449 *
450 * While the <tt>Collection</tt> interface adds no stipulations to the
451 * general contract for the <tt>Object.equals</tt>, programmers who
452 * implement the <tt>Collection</tt> interface "directly" (in other words,
453 * create a class that is a <tt>Collection</tt> but is not a <tt>Set</tt>
454 * or a <tt>List</tt>) must exercise care if they choose to override the
455 * <tt>Object.equals</tt>. It is not necessary to do so, and the simplest
456 * course of action is to rely on <tt>Object</tt>'s implementation, but
457 * the implementor may wish to implement a "value comparison" in place of
458 * the default "reference comparison." (The <tt>List</tt> and
459 * <tt>Set</tt> interfaces mandate such value comparisons.)<p>
460 *
461 * The general contract for the <tt>Object.equals</tt> method states that
462 * equals must be symmetric (in other words, <tt>a.equals(b)</tt> if and
463 * only if <tt>b.equals(a)</tt>). The contracts for <tt>List.equals</tt>
464 * and <tt>Set.equals</tt> state that lists are only equal to other lists,
465 * and sets to other sets. Thus, a custom <tt>equals</tt> method for a
466 * collection class that implements neither the <tt>List</tt> nor
467 * <tt>Set</tt> interface must return <tt>false</tt> when this collection
468 * is compared to any list or set. (By the same logic, it is not possible
469 * to write a class that correctly implements both the <tt>Set</tt> and
470 * <tt>List</tt> interfaces.)
471 *
472 * @param o object to be compared for equality with this collection
473 * @return <tt>true</tt> if the specified object is equal to this
474 * collection
475 *
476 * @see Object#equals(Object)
477 * @see Set#equals(Object)
478 * @see List#equals(Object)
479 */
480 boolean equals(Object o);
481
482 /**
483 * Returns the hash code value for this collection. While the
484 * <tt>Collection</tt> interface adds no stipulations to the general
485 * contract for the <tt>Object.hashCode</tt> method, programmers should
486 * take note that any class that overrides the <tt>Object.equals</tt>
487 * method must also override the <tt>Object.hashCode</tt> method in order
488 * to satisfy the general contract for the <tt>Object.hashCode</tt> method.
489 * In particular, <tt>c1.equals(c2)</tt> implies that
490 * <tt>c1.hashCode()==c2.hashCode()</tt>.
491 *
492 * @return the hash code value for this collection
493 *
494 * @see Object#hashCode()
495 * @see Object#equals(Object)
496 */
497 int hashCode();
498
499 /**
500 * Creates a {@link Spliterator} over the elements in this collection.
501 *
502 * <p>The returned {@code Spliterator} must report the characteristic
503 * {@link Spliterator#SIZED}; implementations should document any additional
504 * characteristic values reported by the returned Spliterator.
505 *
506 * <p>The default implementation should be overridden by subclasses that
507 * can return a more efficient spliterator. In order to
508 * preserve expected laziness behavior for the {@link #stream()} and
509 * {@link #parallelStream()}} methods, spliterators should either have the
510 * characteristic of {@code IMMUTABLE} or {@code CONCURRENT}, or be
511 * <em><a href="Spliterator.html#binding">late-binding</a></em>.
512 * If none of these is practical, the overriding class should describe the
513 * spliterator's documented policy of binding and structural interference,
514 * and should override the {@link #stream()} and {@link #parallelStream()}
515 * methods to create streams using a {@code Supplier} of the spliterator,
516 * as in:
517 * <pre>{@code
518 * Stream<E> s = Streams.stream(() -> spliterator(), spliteratorCharacteristics)
519 * }</pre>
520 * These requirements ensure that streams produced by the {@link #stream()}
521 * and {@link #parallelStream()} methods will reflect the contents of the
522 * collection as of initiation of the terminal stream operation.
523 *
524 * @implSpec
525 * The default implementation creates a
526 * <em><a href="Spliterator.html#binding">late-binding</a></em> spliterator
527 * from the collections's {@code Iterator}. The spliterator inherits the
528 * <em>fail-fast</em> properties of the collection's iterator.
529 *
530 * @implNote
531 * The returned {@code Spliterator} additionally reports
532 * {@link Spliterator#SUBSIZED}.
533 *
534 * @return a {@code Spliterator} over the elements in this collection
535 * @since 1.8
536 */
537 default Spliterator<E> spliterator() {
538 return Spliterators.spliterator(this, 0);
539 }
540
541 /**
542 * Creates a sequential {@code Stream} with this collection as its source.
543 *
544 * <p>This method should be overridden when the {@link #spliterator()}
545 * method cannot return a spliterator that is {@code IMMUTABLE},
546 * {@code CONCURRENT}, or <em>late-binding</em>. (See {@link #spliterator()}
547 * for details.)
548 *
549 * @implSpec
550 * The default implementation creates a sequential {@code Stream} from the
551 * collection's {@code Spliterator}.
552 *
553 * @return a sequential {@code Stream} over the elements in this collection
554 * @since 1.8
555 */
556 default Stream<E> stream() {
557 return StreamSupport.stream(spliterator());
558 }
559
560 /**
561 * Creates a parallel {@code Stream} with this collection as its source.
562 * It is allowable for this method to return a sequential stream.
563 *
564 * <p>This method should be overridden when the {@link #spliterator()}
565 * method cannot return a spliterator that is {@code IMMUTABLE},
566 * {@code CONCURRENT}, or <em>late-binding</em>. (See {@link #spliterator()}
567 * for details.)
568 *
569 * @implSpec
570 * The default implementation creates a parallel {@code Stream} from the
571 * collection's {@code Spliterator}.
572 *
573 * @return a parallel {@code Stream} over the elements in this collection
574 * @since 1.8
575 */
576 default Stream<E> parallelStream() {
577 return StreamSupport.parallelStream(spliterator());
578 }
579 }
580