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