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