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