1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.commons.collections4;
18
19 import java.util.AbstractSet;
20 import java.util.Arrays;
21 import java.util.Collection;
22 import java.util.Collections;
23 import java.util.HashSet;
24 import java.util.IdentityHashMap;
25 import java.util.Iterator;
26 import java.util.NavigableSet;
27 import java.util.Objects;
28 import java.util.Set;
29 import java.util.SortedSet;
30 import java.util.TreeSet;
31
32 import org.apache.commons.collections4.set.ListOrderedSet;
33 import org.apache.commons.collections4.set.PredicatedNavigableSet;
34 import org.apache.commons.collections4.set.PredicatedSet;
35 import org.apache.commons.collections4.set.PredicatedSortedSet;
36 import org.apache.commons.collections4.set.TransformedNavigableSet;
37 import org.apache.commons.collections4.set.TransformedSet;
38 import org.apache.commons.collections4.set.TransformedSortedSet;
39 import org.apache.commons.collections4.set.UnmodifiableNavigableSet;
40 import org.apache.commons.collections4.set.UnmodifiableSet;
41 import org.apache.commons.collections4.set.UnmodifiableSortedSet;
42
43 /**
44 * Provides utility methods and decorators for
45 * {@link Set} and {@link SortedSet} instances.
46 *
47 * @since 2.1
48 */
49 public class SetUtils {
50
51 /**
52 * An unmodifiable <strong>view</strong> of a set that may be backed by other sets.
53 * <p>
54 * If the decorated sets change, this view will change as well. The contents
55 * of this view can be transferred to another instance via the {@link #copyInto(Set)}
56 * and {@link #toSet()} methods.
57 * </p>
58 *
59 * @param <E> the element type
60 * @since 4.1
61 */
62 public abstract static class SetView<E> extends AbstractSet<E> {
63
64 /**
65 * Copies the contents of this view into the provided set.
66 *
67 * @param <S> the set type
68 * @param set the set for copying the contents
69 */
70 public <S extends Set<E>> void copyInto(final S set) {
71 CollectionUtils.addAll(set, this);
72 }
73
74 /**
75 * Return an iterator for this view; the returned iterator is
76 * not required to be unmodifiable.
77 * @return a new iterator for this view
78 */
79 protected abstract Iterator<E> createIterator();
80
81 @Override
82 public Iterator<E> iterator() {
83 return IteratorUtils.unmodifiableIterator(createIterator());
84 }
85
86 @Override
87 public int size() {
88 return IteratorUtils.size(iterator());
89 }
90
91 /**
92 * Returns a new set containing the contents of this view.
93 *
94 * @return a new set containing all elements of this view
95 */
96 public Set<E> toSet() {
97 final Set<E> set = new HashSet<>(size());
98 copyInto(set);
99 return set;
100 }
101 }
102
103 /**
104 * An empty unmodifiable sorted set.
105 * This is not provided in the JDK.
106 */
107 @SuppressWarnings("rawtypes")
108 public static final SortedSet EMPTY_SORTED_SET =
109 UnmodifiableSortedSet.unmodifiableSortedSet(new TreeSet<>());
110
111 /**
112 * Returns an unmodifiable <strong>view</strong> containing the difference of the given
113 * {@link Set}s, denoted by {@code a \ b} (or {@code a - b}).
114 * <p>
115 * The returned view contains all elements of {@code a} that are not a member
116 * of {@code b}.
117 *
118 * @param <E> the generic type that is able to represent the types contained
119 * in both input sets.
120 * @param setA the set to subtract from, must not be null
121 * @param setB the set to subtract, must not be null
122 * @return a view of the relative complement of the two sets
123 * @since 4.1
124 */
125 public static <E> SetView<E> difference(final Set<? extends E> setA, final Set<? extends E> setB) {
126 Objects.requireNonNull(setA, "setA");
127 Objects.requireNonNull(setB, "setB");
128
129 final Predicate<E> notContainedInB = object -> !setB.contains(object);
130
131 return new SetView<E>() {
132 @Override
133 public boolean contains(final Object o) {
134 return setA.contains(o) && !setB.contains(o);
135 }
136
137 @Override
138 public Iterator<E> createIterator() {
139 return IteratorUtils.filteredIterator(setA.iterator(), notContainedInB);
140 }
141 };
142 }
143
144 /**
145 * Returns an unmodifiable <strong>view</strong> of the symmetric difference of the given
146 * {@link Set}s.
147 * <p>
148 * The returned view contains all elements of {@code a} and {@code b} that are
149 * not a member of the other set.
150 * <p>
151 * This is equivalent to {@code union(difference(a, b), difference(b, a))}.
152 *
153 * @param <E> the generic type that is able to represent the types contained
154 * in both input sets.
155 * @param setA the first set, must not be null
156 * @param setB the second set, must not be null
157 * @return a view of the symmetric difference of the two sets
158 * @since 4.1
159 */
160 public static <E> SetView<E> disjunction(final Set<? extends E> setA, final Set<? extends E> setB) {
161 Objects.requireNonNull(setA, "setA");
162 Objects.requireNonNull(setB, "setB");
163
164 final SetView<E> aMinusB = difference(setA, setB);
165 final SetView<E> bMinusA = difference(setB, setA);
166
167 return new SetView<E>() {
168 @Override
169 public boolean contains(final Object o) {
170 return setA.contains(o) ^ setB.contains(o);
171 }
172
173 @Override
174 public Iterator<E> createIterator() {
175 return IteratorUtils.chainedIterator(aMinusB.iterator(), bMinusA.iterator());
176 }
177
178 @Override
179 public boolean isEmpty() {
180 return aMinusB.isEmpty() && bMinusA.isEmpty();
181 }
182
183 @Override
184 public int size() {
185 return aMinusB.size() + bMinusA.size();
186 }
187 };
188 }
189
190 /**
191 * Returns an immutable empty set if the argument is {@code null},
192 * or the argument itself otherwise.
193 *
194 * @param <T> the element type
195 * @param set the set, possibly {@code null}
196 * @return an empty set if the argument is {@code null}
197 */
198 public static <T> Set<T> emptyIfNull(final Set<T> set) {
199 return set == null ? Collections.<T>emptySet() : set;
200 }
201
202 /**
203 * Gets a typed empty unmodifiable Set.
204 * @param <E> the element type
205 * @return an empty Set
206 */
207 public static <E> Set<E> emptySet() {
208 return Collections.<E>emptySet();
209 }
210
211 /**
212 * Gets a typed empty unmodifiable sorted set.
213 * @param <E> the element type
214 * @return an empty sorted Set
215 */
216 @SuppressWarnings("unchecked") // empty set is OK for any type
217 public static <E> SortedSet<E> emptySortedSet() {
218 return EMPTY_SORTED_SET;
219 }
220
221 /**
222 * Generates a hash code using the algorithm specified in
223 * {@link java.util.Set#hashCode()}.
224 * <p>
225 * This method is useful for implementing {@code Set} when you cannot
226 * extend AbstractSet. The method takes Collection instances to enable other
227 * collection types to use the Set implementation algorithm.
228 *
229 * @param <T> the element type
230 * @see java.util.Set#hashCode()
231 * @param set the set to calculate the hash code for, may be null
232 * @return the hash code
233 */
234 public static <T> int hashCodeForSet(final Collection<T> set) {
235 if (set == null) {
236 return 0;
237 }
238
239 int hashCode = 0;
240 for (final T obj : set) {
241 if (obj != null) {
242 hashCode += obj.hashCode();
243 }
244 }
245 return hashCode;
246 }
247
248 /**
249 * Creates a set from the given items. If the passed var-args argument is {@code
250 * null}, then the method returns {@code null}.
251 * @param <E> the element type
252 * @param items the elements that make up the new set
253 * @return a set
254 * @since 4.3
255 */
256 public static <E> HashSet<E> hashSet(final E... items) {
257 if (items == null) {
258 return null;
259 }
260 return new HashSet<>(Arrays.asList(items));
261 }
262
263 /**
264 * Returns an unmodifiable <strong>view</strong> of the intersection of the given {@link Set}s.
265 * <p>
266 * The returned view contains all elements that are members of both input sets
267 * ({@code a} and {@code b}).
268 *
269 * @param <E> the generic type that is able to represent the types contained
270 * in both input sets.
271 * @param setA the first set, must not be null
272 * @param setB the second set, must not be null
273 * @return a view of the intersection of the two sets
274 * @since 4.1
275 */
276 public static <E> SetView<E> intersection(final Set<? extends E> setA, final Set<? extends E> setB) {
277 Objects.requireNonNull(setA, "setA");
278 Objects.requireNonNull(setB, "setB");
279
280 return new SetView<E>() {
281 @Override
282 public boolean contains(final Object o) {
283 return setA.contains(o) && setB.contains(o);
284 }
285
286 @Override
287 public Iterator<E> createIterator() {
288 return IteratorUtils.filteredIterator(setA.iterator(), setB::contains);
289 }
290 };
291 }
292
293 /**
294 * Tests two sets for equality as per the {@code equals()} contract
295 * in {@link java.util.Set#equals(Object)}.
296 * <p>
297 * This method is useful for implementing {@code Set} when you cannot
298 * extend AbstractSet. The method takes Collection instances to enable other
299 * collection types to use the Set implementation algorithm.
300 * <p>
301 * The relevant text (slightly paraphrased as this is a static method) is:
302 * <blockquote>
303 * <p>Two sets are considered equal if they have
304 * the same size, and every member of the first set is contained in
305 * the second. This ensures that the {@code equals} method works
306 * properly across different implementations of the {@code Set}
307 * interface.</p>
308 *
309 * <p>
310 * This implementation first checks if the two sets are the same object:
311 * if so it returns {@code true}. Then, it checks if the two sets are
312 * identical in size; if not, it returns false. If so, it returns
313 * {@code a.containsAll((Collection) b)}.</p>
314 * </blockquote>
315 *
316 * @see java.util.Set
317 * @param set1 the first set, may be null
318 * @param set2 the second set, may be null
319 * @return whether the sets are equal by value comparison
320 */
321 public static boolean isEqualSet(final Collection<?> set1, final Collection<?> set2) {
322 if (set1 == set2) {
323 return true;
324 }
325 if (set1 == null || set2 == null || set1.size() != set2.size()) {
326 return false;
327 }
328
329 return set1.containsAll(set2);
330 }
331
332 /**
333 * Returns a new hash set that matches elements based on {@code ==} not
334 * {@code equals()}.
335 * <p>
336 * <strong>This set will violate the detail of various Set contracts.</strong>
337 * As a general rule, don't compare this set to other sets. In particular, you can't
338 * use decorators like {@link ListOrderedSet} on it, which silently assume that these
339 * contracts are fulfilled.
340 * <p>
341 * <strong>Note that the returned set is not synchronized and is not thread-safe.</strong>
342 * If you wish to use this set from multiple threads concurrently, you must use
343 * appropriate synchronization. The simplest approach is to wrap this map
344 * using {@link java.util.Collections#synchronizedSet(Set)}. This class may throw
345 * exceptions when accessed by concurrent threads without synchronization.
346 *
347 * @param <E> the element type
348 * @return a new identity hash set
349 * @since 4.1
350 */
351 public static <E> Set<E> newIdentityHashSet() {
352 return Collections.newSetFromMap(new IdentityHashMap<>());
353 }
354
355 /**
356 * Returns a set that maintains the order of elements that are added
357 * backed by the given set.
358 * <p>
359 * If an element is added twice, the order is determined by the first add.
360 * The order is observed through the iterator or toArray.
361 *
362 * @param <E> the element type
363 * @param set the set to order, must not be null
364 * @return an ordered set backed by the given set
365 * @throws NullPointerException if the set is null
366 */
367 public static <E> Set<E> orderedSet(final Set<E> set) {
368 return ListOrderedSet.listOrderedSet(set);
369 }
370
371 /**
372 * Returns a predicated (validating) navigable set backed by the given navigable set.
373 * <p>
374 * Only objects that pass the test in the given predicate can be added to the set.
375 * Trying to add an invalid object results in an IllegalArgumentException.
376 * It is important not to use the original set after invoking this method,
377 * as it is a backdoor for adding invalid objects.
378 *
379 * @param <E> the element type
380 * @param set the navigable set to predicate, must not be null
381 * @param predicate the predicate for the navigable set, must not be null
382 * @return a predicated navigable set backed by the given navigable set
383 * @throws NullPointerException if the set or predicate is null
384 * @since 4.1
385 */
386 public static <E> SortedSet<E> predicatedNavigableSet(final NavigableSet<E> set,
387 final Predicate<? super E> predicate) {
388 return PredicatedNavigableSet.predicatedNavigableSet(set, predicate);
389 }
390
391 /**
392 * Returns a predicated (validating) set backed by the given set.
393 * <p>
394 * Only objects that pass the test in the given predicate can be added to the set.
395 * Trying to add an invalid object results in an IllegalArgumentException.
396 * It is important not to use the original set after invoking this method,
397 * as it is a backdoor for adding invalid objects.
398 *
399 * @param <E> the element type
400 * @param set the set to predicate, must not be null
401 * @param predicate the predicate for the set, must not be null
402 * @return a predicated set backed by the given set
403 * @throws NullPointerException if the set or predicate is null
404 */
405 public static <E> Set<E> predicatedSet(final Set<E> set, final Predicate<? super E> predicate) {
406 return PredicatedSet.predicatedSet(set, predicate);
407 }
408
409 /**
410 * Returns a predicated (validating) sorted set backed by the given sorted set.
411 * <p>
412 * Only objects that pass the test in the given predicate can be added to the set.
413 * Trying to add an invalid object results in an IllegalArgumentException.
414 * It is important not to use the original set after invoking this method,
415 * as it is a backdoor for adding invalid objects.
416 *
417 * @param <E> the element type
418 * @param set the sorted set to predicate, must not be null
419 * @param predicate the predicate for the sorted set, must not be null
420 * @return a predicated sorted set backed by the given sorted set
421 * @throws NullPointerException if the set or predicate is null
422 */
423 public static <E> SortedSet<E> predicatedSortedSet(final SortedSet<E> set,
424 final Predicate<? super E> predicate) {
425 return PredicatedSortedSet.predicatedSortedSet(set, predicate);
426 }
427
428 // Set
429 /**
430 * Returns a synchronized set backed by the given set.
431 * <p>
432 * You must manually synchronize on the returned set's iterator to
433 * avoid non-deterministic behavior:
434 *
435 * <pre>
436 * Sets s = SetUtils.synchronizedSet(mySet);
437 * synchronized (s) {
438 * Iterator i = s.iterator();
439 * while (i.hasNext()) {
440 * process (i.next());
441 * }
442 * }
443 * </pre>
444 *
445 * This method is just a wrapper for {@link Collections#synchronizedSet(Set)}.
446 *
447 * @param <E> the element type
448 * @param set the set to synchronize, must not be null
449 * @return a synchronized set backed by the given set
450 * @throws NullPointerException if the set is null
451 */
452 public static <E> Set<E> synchronizedSet(final Set<E> set) {
453 return Collections.synchronizedSet(set);
454 }
455
456 // SortedSet
457 /**
458 * Returns a synchronized sorted set backed by the given sorted set.
459 * <p>
460 * You must manually synchronize on the returned set's iterator to
461 * avoid non-deterministic behavior:
462 *
463 * <pre>
464 * Set s = SetUtils.synchronizedSortedSet(mySet);
465 * synchronized (s) {
466 * Iterator i = s.iterator();
467 * while (i.hasNext()) {
468 * process (i.next());
469 * }
470 * }
471 * </pre>
472 *
473 * This method is just a wrapper for {@link Collections#synchronizedSortedSet(SortedSet)}.
474 *
475 * @param <E> the element type
476 * @param set the sorted set to synchronize, must not be null
477 * @return a synchronized set backed by the given set
478 * @throws NullPointerException if the set is null
479 */
480 public static <E> SortedSet<E> synchronizedSortedSet(final SortedSet<E> set) {
481 return Collections.synchronizedSortedSet(set);
482 }
483
484 /**
485 * Returns a transformed navigable set backed by the given navigable set.
486 * <p>
487 * Each object is passed through the transformer as it is added to the
488 * Set. It is important not to use the original set after invoking this
489 * method, as it is a backdoor for adding untransformed objects.
490 * <p>
491 * Existing entries in the specified set will not be transformed.
492 * If you want that behavior, see {@link TransformedNavigableSet#transformedNavigableSet}.
493 *
494 * @param <E> the element type
495 * @param set the navigable set to transform, must not be null
496 * @param transformer the transformer for the set, must not be null
497 * @return a transformed set backed by the given set
498 * @throws NullPointerException if the set or transformer is null
499 * @since 4.1
500 */
501 public static <E> SortedSet<E> transformedNavigableSet(final NavigableSet<E> set,
502 final Transformer<? super E, ? extends E> transformer) {
503 return TransformedNavigableSet.transformingNavigableSet(set, transformer);
504 }
505
506 /**
507 * Returns a transformed set backed by the given set.
508 * <p>
509 * Each object is passed through the transformer as it is added to the
510 * Set. It is important not to use the original set after invoking this
511 * method, as it is a backdoor for adding untransformed objects.
512 * <p>
513 * Existing entries in the specified set will not be transformed.
514 * If you want that behavior, see {@link TransformedSet#transformedSet}.
515 *
516 * @param <E> the element type
517 * @param set the set to transform, must not be null
518 * @param transformer the transformer for the set, must not be null
519 * @return a transformed set backed by the given set
520 * @throws NullPointerException if the set or transformer is null
521 */
522 public static <E> Set<E> transformedSet(final Set<E> set,
523 final Transformer<? super E, ? extends E> transformer) {
524 return TransformedSet.transformingSet(set, transformer);
525 }
526
527 /**
528 * Returns a transformed sorted set backed by the given set.
529 * <p>
530 * Each object is passed through the transformer as it is added to the
531 * Set. It is important not to use the original set after invoking this
532 * method, as it is a backdoor for adding untransformed objects.
533 * <p>
534 * Existing entries in the specified set will not be transformed.
535 * If you want that behavior, see {@link TransformedSortedSet#transformedSortedSet}.
536 *
537 * @param <E> the element type
538 * @param set the set to transform, must not be null
539 * @param transformer the transformer for the set, must not be null
540 * @return a transformed set backed by the given set
541 * @throws NullPointerException if the set or transformer is null
542 */
543 public static <E> SortedSet<E> transformedSortedSet(final SortedSet<E> set,
544 final Transformer<? super E, ? extends E> transformer) {
545 return TransformedSortedSet.transformingSortedSet(set, transformer);
546 }
547
548 // Set operations
549
550 /**
551 * Returns an unmodifiable <strong>view</strong> of the union of the given {@link Set}s.
552 * <p>
553 * The returned view contains all elements of {@code a} and {@code b}.
554 *
555 * @param <E> the generic type that is able to represent the types contained
556 * in both input sets.
557 * @param setA the first set, must not be null
558 * @param setB the second set, must not be null
559 * @return a view of the union of the two set
560 * @throws NullPointerException if either input set is null
561 * @since 4.1
562 */
563 public static <E> SetView<E> union(final Set<? extends E> setA, final Set<? extends E> setB) {
564 Objects.requireNonNull(setA, "setA");
565 Objects.requireNonNull(setB, "setB");
566
567 final SetView<E> bMinusA = difference(setB, setA);
568
569 return new SetView<E>() {
570 @Override
571 public boolean contains(final Object o) {
572 return setA.contains(o) || setB.contains(o);
573 }
574
575 @Override
576 public Iterator<E> createIterator() {
577 return IteratorUtils.chainedIterator(setA.iterator(), bMinusA.iterator());
578 }
579
580 @Override
581 public boolean isEmpty() {
582 return setA.isEmpty() && setB.isEmpty();
583 }
584
585 @Override
586 public int size() {
587 return setA.size() + bMinusA.size();
588 }
589 };
590 }
591
592 // NavigableSet
593 /**
594 * Returns an unmodifiable navigable set backed by the given navigable set.
595 * <p>
596 * This method uses the implementation in the decorators subpackage.
597 *
598 * @param <E> the element type
599 * @param set the navigable set to make unmodifiable, must not be null
600 * @return an unmodifiable set backed by the given set
601 * @throws NullPointerException if the set is null
602 * @since 4.1
603 */
604 public static <E> SortedSet<E> unmodifiableNavigableSet(final NavigableSet<E> set) {
605 return UnmodifiableNavigableSet.unmodifiableNavigableSet(set);
606 }
607
608 /**
609 * Creates an unmodifiable set from the given items. If the passed var-args argument is {@code
610 * null}, then the method returns {@code null}.
611 * @param <E> the element type
612 * @param items the elements that make up the new set
613 * @return a set
614 * @since 4.3
615 */
616 public static <E> Set<E> unmodifiableSet(final E... items) {
617 if (items == null) {
618 return null;
619 }
620 return UnmodifiableSet.unmodifiableSet(hashSet(items));
621 }
622
623 /**
624 * Returns an unmodifiable set backed by the given set.
625 * <p>
626 * This method uses the implementation in the decorators subpackage.
627 *
628 * @param <E> the element type
629 * @param set the set to make unmodifiable, must not be null
630 * @return an unmodifiable set backed by the given set
631 * @throws NullPointerException if the set is null
632 */
633 public static <E> Set<E> unmodifiableSet(final Set<? extends E> set) {
634 return UnmodifiableSet.unmodifiableSet(set);
635 }
636
637 /**
638 * Returns an unmodifiable sorted set backed by the given sorted set.
639 * <p>
640 * This method uses the implementation in the decorators subpackage.
641 *
642 * @param <E> the element type
643 * @param set the sorted set to make unmodifiable, must not be null
644 * @return an unmodifiable set backed by the given set
645 * @throws NullPointerException if the set is null
646 */
647 public static <E> SortedSet<E> unmodifiableSortedSet(final SortedSet<E> set) {
648 return UnmodifiableSortedSet.unmodifiableSortedSet(set);
649 }
650
651 /**
652 * Don't allow instances.
653 */
654 private SetUtils() {
655 // empty
656 }
657
658 }