Package org.plumelib.util

Class CollectionsPlume

java.lang.Object
org.plumelib.util.CollectionsPlume
public final class CollectionsPlume extends Object
Utility functions for Collections, ArrayList, Iterator, and Map.

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    static final class 
    CollectionsPlume.EnumerationIterator<T>
    Converts an Enumeration into an Iterator.
    static final class 
    CollectionsPlume.FilteredIterator<T extends @Nullable Object>
    An iterator that only returns elements that match the given predicate.
    static final class 
    CollectionsPlume.IteratorEnumeration<T>
    Converts an Iterator into an Enumeration.
    static final class 
    CollectionsPlume.MergedIterator<T>
    An Iterator that returns the elements in each of its argument Iterators, in turn.
    static final class 
    CollectionsPlume.MergedIterator2<T>
    An Iterator that returns first the elements returned by its first argument, then the elements returned by its second argument.
    static final class 
    CollectionsPlume.RemoveFirstAndLastIterator<T>
    Returns an iterator just like its argument, except that the first and last elements are removed.
    static class 
    CollectionsPlume.Replacement<T>
    Represents a replacement of one range of a collection by another collection.

  • Method Summary

    Modifier and Type
    Method
    Description
    static <T> boolean
    adjoin(Collection<T> c, T e)
    Adds an element to the given collection, but only if it is not already present.
    static <T> boolean
    adjoinAll(Collection<T> c, Collection<? extends T> toAdd)
    Adds elements to the given collection, but only ones that are not already present.
    static <T> boolean
    allMatch(Iterable<T> coll, Predicate<? super T> predicate)
    Returns true if all elements of the collection match the predicate.
    static <T> boolean
    anyMatch(Iterable<T> coll, Predicate<? super T> predicate)
    Returns true if any element of the collection matches the predicate.
    static <T> List<T>
    append(Collection<T> list, T lastElt)
    Concatenates a list and an element into a new list.
    static <T extends @Nullable Object, C extends @Nullable Collection<T>>
    @PolyNull C
    cloneElements(@PolyNull C orig)
    Returns a copy of orig, where each element of the result is a clone of the corresponding element of orig.
    static <K, V, M extends @Nullable Map<K, V>>
    @PolyNull M
    cloneElements(@PolyNull M orig)
    Returns a copy of orig, where each key and value in the result is a clone of the corresponding element of orig.
    static <K, V, M extends @Nullable Map<K, V>>
    @PolyNull M
    cloneValues(@PolyNull M orig)
    Returns a copy of orig, where each value of the result is a clone of the corresponding value of orig, but the keys are the same objects.
    static <T> List<T>
    concatenate(Collection<T> list1, Collection<T> list2)
    Concatenates two lists into a new list.
    static <T> List<List<T>>
    createCombinations(@org.checkerframework.checker.index.qual.Positive int dims, @org.checkerframework.checker.index.qual.NonNegative int start, List<T> objs)
    Returns a list of lists of each combination (with repetition, but not permutations) of the specified objects starting at index start over dims dimensions, for dims > 0.
    static ArrayList<ArrayList<Integer>>
    createCombinations(int arity, @org.checkerframework.checker.index.qual.NonNegative int start, int cnt)
    Returns a list of lists of each combination (with repetition, but not permutations) of integers from start to cnt (inclusive) over arity dimensions.
    static <K, V> Map<K,V>
    createLruCache(@org.checkerframework.checker.index.qual.Positive int size)
    Creates a LRU cache.
    static <T extends @Nullable DeepCopyable<T>, C extends @Nullable Collection<T>>
    @PolyNull C
    deepCopy(@PolyNull C orig)
    Returns a copy of orig, where each element of the result is a deep copy (according to the DeepCopyable interface) of the corresponding element of orig.
    static <K extends @Nullable DeepCopyable<K>, V extends @Nullable DeepCopyable<V>, M extends @Nullable Map<K, V>>
    @PolyNull M
    deepCopy(@PolyNull M orig)
    Returns a copy of orig, where each key and value in the result is a deep copy (according to the DeepCopyable interface) of the corresponding element of orig.
    static <K, V extends @Nullable DeepCopyable<V>, M extends @Nullable Map<K, V>>
    @PolyNull M
    deepCopyValues(@PolyNull M orig)
    Returns a copy of orig, where each value of the result is a deep copy (according to the DeepCopyable interface) of the corresponding value of orig, but the keys are the same objects.
    static boolean
    deepEquals(@Nullable Object o1, @Nullable Object o2)
    Determines deep equality for the elements.
    static <T> Collection<T>
    duplicates(Collection<T> c)
    Returns the elements (once each) that appear more than once in the given collection.
    static <T> List<T>
    filter(Iterable<T> coll, Predicate<? super T> filter)
    Returns a new list containing only the elements for which the filter returns true.
    static @Nullable Object
    getFromSet(Set<? extends @Nullable Object> set, Object key)
    Returns the object in the given set that is equal to key.
    static <T> boolean
    hasDuplicates(List<T> a)
    Returns true iff the list does not contain duplicate elements, according to equals().
    static <T> boolean
    hasNoDuplicates(List<T> a)
    Returns true iff the list does not contain duplicate elements, according to equals().
    static <K extends @NonNull Object>
    @Nullable Integer
    incrementMap(Map<K,Integer> m, K key)
    Increment the Integer which is indexed by key in the Map.
    static <K extends @NonNull Object>
    @Nullable Integer
    incrementMap(Map<K,Integer> m, K key, int count)
    Increment the Integer which is indexed by key in the Map.
    static int
    indexOf(List<?> list, Object value, int start)
    Returns the first index of the given value in the list, starting at the given index.
    static int
    intersectionCardinality(BitSet a, BitSet b)
    Returns the cardinality of the intersection of the two BitSets.
    static int
    intersectionCardinality(BitSet a, BitSet b, BitSet c)
    Returns the cardinality of the intersection of the three BitSets.
    static boolean
    intersectionCardinalityAtLeast(BitSet a, BitSet b, @org.checkerframework.checker.index.qual.NonNegative int i)
    Returns true if the cardinality of the intersection of the two BitSets is at least the given value.
    static boolean
    intersectionCardinalityAtLeast(BitSet a, BitSet b, BitSet c, @org.checkerframework.checker.index.qual.NonNegative int i)
    Returns true if the cardinality of the intersection of the three BitSets is at least the given value.
    static <T extends Comparable<T>>
    boolean
    isSorted(List<T> values)
    Returns true if the given list is sorted.
    static <T extends Comparable<T>>
    boolean
    isSortedNoDuplicates(List<T> values)
    Returns true if the given list is sorted and has no duplicates
    static <T> boolean
    isSubsequenceMaybeNonContiguous(Iterable<T> longer, Iterable<T> shorter)
    Returns true if the second list is a subsequence (not necessarily contiguous) of the first.
    static <T> Iterable<T>
    iteratorToIterable(Iterator<T> source)
    Converts an Iterator to an Iterable.
    static <T> List<T>
    listFilter(Iterable<T> coll, Predicate<? super T> filter)
    Deprecated.
    use filter(java.lang.Iterable<T>, java.util.function.Predicate<? super T>) instead
    static <T> List<T>
    listIntersection(Collection<T> c1, Collection<T> c2)
    Returns a new list that is the intersection of the given collections.
    static <E> List<E>
    listOf(E e1, E e2)
    Creates an immutable list containing two elements.
    static <T> List<T>
    listUnion(Collection<T> c1, Collection<T> c2)
    Returns a new list that is the union of the given collections.
    static <T> ArrayList<T>
    makeArrayList(Enumeration<T> e)
    Returns a vector containing the elements of the enumeration.
    static int
    mapCapacity(int numElements)
    Given an expected number of elements, returns the capacity that should be passed to a HashMap or HashSet constructor, so that the set or map will not resize.
    static int
    mapCapacity(Collection<?> c)
    Given a collection, returns the capacity that should be passed to a HashMap or HashSet constructor, so that the set or map will not resize.
    static int
    mapCapacity(Map<?,?> m)
    Given a map, returns the capacity that should be passed to a HashMap or HashSet constructor, so that the set or map will not resize.
    static <T> int
    mapCapacity(T[] a)
    Given an array, returns the capacity that should be passed to a HashMap or HashSet constructor, so that the set or map will not resize.
    static <@KeyForBottom FROM extends @Nullable @UnknownKeyFor Object, @KeyForBottom TO extends @Nullable @UnknownKeyFor Object>
    List<TO>
    mapList(Function<? super @KeyForBottom FROM,? extends @KeyForBottom TO> f, @KeyForBottom FROM[] a)
    Applies the function to each element of the given array, producing a list of the results.
    static <@KeyForBottom FROM extends @Nullable @UnknownKeyFor Object, @KeyForBottom TO extends @Nullable @UnknownKeyFor Object>
    List<TO>
    mapList(Function<? super @KeyForBottom FROM,? extends @KeyForBottom TO> f, Iterable<@KeyForBottom FROM> iterable)
    Applies the function to each element of the given iterable, producing a new list of the results.
    static <K extends @Signed @Nullable Object, V extends @Signed @Nullable Object>
    void
    mapToString(Appendable sb, Map<K,V> m, String linePrefix)
    Write a multi-line representation of the map into the given Appendable (e.g., a StringBuilder).
    static <K extends @Signed @Nullable Object, V extends @Signed @Nullable Object>
    String
    mapToString(Map<K,V> m)
    Returns a multi-line string representation of a map.
    static <T> boolean
    noDuplicates(List<T> a)
    Deprecated.
    use hasNoDuplicates(List)
    static <T> boolean
    noneMatch(Iterable<T> coll, Predicate<? super T> predicate)
    Returns true if no element of the collection matches the predicate.
    static <T> List<T>
    randomElements(Iterator<T> itor, int numElts)
    Returns a List containing numElts randomly chosen elements from the iterator, or all the elements of the iterator if there are fewer.
    static <T> List<T>
    randomElements(Iterator<T> itor, int numElts, Random random)
    Returns a List containing numElts randomly chosen elements from the iterator, or all the elements of the iterator if there are fewer.
    static <T> List<T>
    removeDuplicates(List<T> l)
    Deprecated.
    use <T>withoutDuplicates(java.util.List<T>) or <T>withoutDuplicatesComparable(java.util.List<T>)
    static <T> List<T>
    replace(Iterable<T> c, Iterable<CollectionsPlume.Replacement<T>> replacements)
    Performs a set of replacements on the given collection, returning the transformed result (as a list).
    static <T> List<T>
    replace(T[] c, Collection<CollectionsPlume.Replacement<T>> replacements)
    Performs a set of replacements on the given array, returning the transformed result (as a list).
    static <K extends Comparable<? super K>, V>
    Collection<@KeyFor("#1") K>
    sortedKeySet(Map<K,V> m)
    Returns a sorted version of m.keySet().
    static <K, V> Collection<@KeyFor("#1") K>
    sortedKeySet(Map<K,V> m, Comparator<K> comparator)
    Returns a sorted version of m.keySet().
    static <T> boolean
    sortedSetContainsAll(SortedSet<T> set1, SortedSet<T> set2)
    Returns true if the two sets contain the same elements in the same order.
    static <T> boolean
    sortedSetEquals(SortedSet<T> set1, SortedSet<T> set2)
    Returns true if the two sets contain the same elements in the same order.
    static <T> List<T>
    sortList(List<T> l, Comparator<? super T> c)
    Returns the sorted version of the list.
    static <@KeyForBottom FROM extends @Nullable @UnknownKeyFor Object, @KeyForBottom TO extends @Nullable @UnknownKeyFor Object>
    List<TO>
    transform(Iterable<@KeyForBottom FROM> iterable, Function<? super @KeyForBottom FROM,? extends @KeyForBottom TO> f)
    Applies the function to each element of the given iterable, producing a new list of the results.
    static <T> List<T>
    withoutDuplicates(List<T> values)
    Returns a copy of the list with duplicates (according to equals()) removed, but retaining the original order.
    static <T extends Comparable<T>>
    List<T>
    withoutDuplicatesComparable(List<T> values)
    Returns a list with the same contents as its argument, but without duplicates.
    static <T extends Comparable<T>>
    List<T>
    withoutDuplicatesSorted(List<T> values)
    Returns a list with the same contents as its argument, but sorted and without duplicates (according to equals()).

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Method Details

    • hasDuplicates

      @Pure public static <T> boolean hasDuplicates(List<T> a)
      Returns true iff the list does not contain duplicate elements, according to equals().

      The implementation uses O(n) time and O(n) space.

      Type Parameters:
      T - the type of the elements
      Parameters:
      a - a list
      Returns:
      true iff a does not contain duplicate elements

    • hasNoDuplicates

      @Pure public static <T> boolean hasNoDuplicates(List<T> a)
      Returns true iff the list does not contain duplicate elements, according to equals().

      The implementation uses O(n) time and O(n) space.

      Type Parameters:
      T - the type of the elements
      Parameters:
      a - a list
      Returns:
      true iff a does not contain duplicate elements

    • noDuplicates

      @Deprecated @Pure public static <T> boolean noDuplicates(List<T> a)
      Deprecated.
      use hasNoDuplicates(List)
      Returns true iff the list does not contain duplicate elements, according to equals().

      The implementation uses O(n) time and O(n) space.

      Type Parameters:
      T - the type of the elements
      Parameters:
      a - a list
      Returns:
      true iff a does not contain duplicate elements

    • removeDuplicates

      @Deprecated public static <T> List<T> removeDuplicates(List<T> l)
      Deprecated.
      use <T>withoutDuplicates(java.util.List<T>) or <T>withoutDuplicatesComparable(java.util.List<T>)
      Returns a copy of the list (never the original list) with duplicates (according to equals()) removed, but retaining the original order. The argument is not modified.
      Type Parameters:
      T - type of elements of the list
      Parameters:
      l - a list to remove duplicates from
      Returns:
      a copy of the list with duplicates removed

    • withoutDuplicates

      public static <T> List<T> withoutDuplicates(List<T> values)
      Returns a copy of the list with duplicates (according to equals()) removed, but retaining the original order. May return its argument if its argument has no duplicates, but is not guaranteed to do so. The argument is not modified.

      If the element type implements Comparable, use withoutDuplicatesSorted(java.util.List<T>) or withoutDuplicatesComparable(java.util.List<T>).

      Type Parameters:
      T - the type of elements in values
      Parameters:
      values - a list of values
      Returns:
      the values, with duplicates removed

    • withoutDuplicatesSorted

      public static <T extends Comparable<T>> List<T> withoutDuplicatesSorted(List<T> values)
      Returns a list with the same contents as its argument, but sorted and without duplicates (according to equals()). May return its argument if its argument is sorted and has no duplicates, but is not guaranteed to do so. The argument is not modified.

      This is like withoutDuplicates(java.util.List<T>), but requires the list elements to implement Comparable, and thus can be more efficient.

      Type Parameters:
      T - the type of elements in values
      Parameters:
      values - a list of values
      Returns:
      the values, with duplicates removed
      See Also:

    • withoutDuplicatesComparable

      public static <T extends Comparable<T>> List<T> withoutDuplicatesComparable(List<T> values)
      Returns a list with the same contents as its argument, but without duplicates. May return its argument if its argument has no duplicates, but is not guaranteed to do so. The argument is not modified.

      This is like withoutDuplicatesSorted(java.util.List<T>), but it is not guaranteed to return a sorted list. Thus, it is occasionally more efficient.

      This is like withoutDuplicates(java.util.List<T>), but requires the list elements to implement Comparable, and thus can be more efficient. If a new list is returned, this does not retain the original order; the result is sorted.

      Type Parameters:
      T - the type of elements in values
      Parameters:
      values - a list of values
      Returns:
      the values, with duplicates removed
      See Also:

    • sortList

      public static <T> List<T> sortList(List<T> l, Comparator<? super T> c)
      Returns the sorted version of the list. Does not alter the list. Simply calls Collections.sort(List<T>, Comparator<? super T>) on a copy.
      Type Parameters:
      T - type of elements of the list
      Parameters:
      l - a list to sort
      c - a sorted version of the list
      Returns:
      a sorted version of the list

    • isSorted

      public static <T extends Comparable<T>> boolean isSorted(List<T> values)
      Returns true if the given list is sorted.
      Type Parameters:
      T - the component type of the list
      Parameters:
      values - a list
      Returns:
      true if the list is sorted

    • isSortedNoDuplicates

      public static <T extends Comparable<T>> boolean isSortedNoDuplicates(List<T> values)
      Returns true if the given list is sorted and has no duplicates
      Type Parameters:
      T - the component type of the list
      Parameters:
      values - a list
      Returns:
      true if the list is sorted and has no duplicates

    • duplicates

      public static <T> Collection<T> duplicates(Collection<T> c)
      Returns the elements (once each) that appear more than once in the given collection.
      Type Parameters:
      T - the type of elements
      Parameters:
      c - a collection
      Returns:
      the elements (once each) that appear more than once in the given collection

    • deepEquals

      @Pure public static boolean deepEquals(@Nullable Object o1, @Nullable Object o2)
      Determines deep equality for the elements.
      • If both are primitive arrays, uses java.util.Arrays.equals.
      • If both are Object[], uses java.util.Arrays.deepEquals and does not recursively call this method.
      • If both are lists, uses deepEquals recursively on each element.
      • For other types, just uses equals() and does not recursively call this method.
      Parameters:
      o1 - first value to compare
      o2 - second value to compare
      Returns:
      true iff o1 and o2 are deeply equal

    • mapList

      public static <@KeyForBottom FROM extends @Nullable @UnknownKeyFor Object, @KeyForBottom TO extends @Nullable @UnknownKeyFor Object> List<TO> mapList(Function<? super @KeyForBottom FROM,? extends @KeyForBottom TO> f, Iterable<@KeyForBottom FROM> iterable)
      Applies the function to each element of the given iterable, producing a new list of the results. The point of this method is to make mapping operations more concise. You can write 
        return mapList(LemmaAnnotation::get, tokens);
      instead of 
        return tokens
            .stream()
            .map(LemmaAnnotation::get)
            .collect(Collectors.toList());
      Import this method with 
      import static org.plumelib.util.CollectionsPlume.mapList;
      This method is just like transform(java.lang.Iterable<FROM>, java.util.function.Function<? super FROM, ? extends TO>), but with the arguments in the other order.

      To perform replacement in place, see List.replaceAll.

      Type Parameters:
      FROM - the type of elements of the given iterable
      TO - the type of elements of the result list
      Parameters:
      f - a function
      iterable - an iterable
      Returns:
      a list of the results of applying f to the elements of iterable

    • mapList

      public static <@KeyForBottom FROM extends @Nullable @UnknownKeyFor Object, @KeyForBottom TO extends @Nullable @UnknownKeyFor Object> List<TO> mapList(Function<? super @KeyForBottom FROM,? extends @KeyForBottom TO> f, @KeyForBottom FROM[] a)
      Applies the function to each element of the given array, producing a list of the results.

      This produces a list rather than an array because it is problematic to create an array with generic compontent type.

      The point of this method is to make mapping operations more concise. Import it with 

      import static org.plumelib.util.CollectionsPlume.mapList;
      This method is just like transform(java.lang.Iterable<FROM>, java.util.function.Function<? super FROM, ? extends TO>), but with the arguments in the other order.
      Type Parameters:
      FROM - the type of elements of the given array
      TO - the type of elements of the result list
      Parameters:
      f - a function
      a - an array
      Returns:
      a list of the results of applying f to the elements of a

    • transform

      public static <@KeyForBottom FROM extends @Nullable @UnknownKeyFor Object, @KeyForBottom TO extends @Nullable @UnknownKeyFor Object> List<TO> transform(Iterable<@KeyForBottom FROM> iterable, Function<? super @KeyForBottom FROM,? extends @KeyForBottom TO> f)
      Applies the function to each element of the given iterable, producing a new list of the results. The point of this method is to make mapping operations more concise. You can write 
        return transform(tokens, LemmaAnnotation::get);
      instead of 
        return tokens
            .stream()
            .map(LemmaAnnotation::get)
            .collect(Collectors.toList());
      Import this method with 
      import static org.plumelib.util.CollectionsPlume.transform;
      This method is just like mapList(java.util.function.Function<? super FROM, ? extends TO>, java.lang.Iterable<FROM>), but with the arguments in the other order. To perform replacement in place, see List.replaceAll.
      Type Parameters:
      FROM - the type of elements of the given collection
      TO - the type of elements of the result list
      Parameters:
      iterable - an iterable
      f - a function
      Returns:
      a list of the results of applying f to the elements of list

    • cloneElements

      public static <T extends @Nullable Object, C extends @Nullable Collection<T>> @PolyNull C cloneElements(@PolyNull C orig)
      Returns a copy of orig, where each element of the result is a clone of the corresponding element of orig.
      Type Parameters:
      T - the type of elements of the collection
      C - the type of the collection
      Parameters:
      orig - a collection
      Returns:
      a copy of orig, as described above

    • deepCopy

      public static <T extends @Nullable DeepCopyable<T>, C extends @Nullable Collection<T>> @PolyNull C deepCopy(@PolyNull C orig)
      Returns a copy of orig, where each element of the result is a deep copy (according to the DeepCopyable interface) of the corresponding element of orig.
      Type Parameters:
      T - the type of elements of the collection
      C - the type of the collection
      Parameters:
      orig - a collection
      Returns:
      a copy of orig, as described above

    • listFilter

      @Deprecated public static <T> List<T> listFilter(Iterable<T> coll, Predicate<? super T> filter)
      Deprecated.
      use filter(java.lang.Iterable<T>, java.util.function.Predicate<? super T>) instead
      Returns a new list containing only the elements for which the filter returns true. To modify the collection in place, use Collection#removeIf instead of this method.

      Using streams gives an equivalent list but is less efficient and more verbose: 

      
 coll.stream().filter(filter).collect(Collectors.toList());
      Type Parameters:
      T - the type of elements
      Parameters:
      coll - a collection
      filter - a predicate
      Returns:
      a new list with the elements for which the filter returns true

    • filter

      public static <T> List<T> filter(Iterable<T> coll, Predicate<? super T> filter)
      Returns a new list containing only the elements for which the filter returns true. To modify the collection in place, use Collection#removeIf instead of this method.

      Using streams gives an equivalent list but is less efficient and more verbose: 

      
 coll.stream().filter(filter).collect(Collectors.toList());
      Type Parameters:
      T - the type of elements
      Parameters:
      coll - a collection
      filter - a predicate
      Returns:
      a new list with the elements for which the filter returns true

    • anyMatch

      public static <T> boolean anyMatch(Iterable<T> coll, Predicate<? super T> predicate)
      Returns true if any element of the collection matches the predicate.

      Using streams gives an equivalent result but is less efficient: 

      
 coll.stream().anyMatch(predicate);
      Type Parameters:
      T - the type of elements
      Parameters:
      coll - a collection
      predicate - a non-interfering, stateless predicate
      Returns:
      true if any element of the collection matches the predicate

    • allMatch

      public static <T> boolean allMatch(Iterable<T> coll, Predicate<? super T> predicate)
      Returns true if all elements of the collection match the predicate.

      Using streams gives an equivalent result but is less efficient: 

      
 coll.stream().allMatch(predicate);
      Type Parameters:
      T - the type of elements
      Parameters:
      coll - a collection
      predicate - a non-interfering, stateless predicate
      Returns:
      true if all elements of the collection match the predicate

    • noneMatch

      public static <T> boolean noneMatch(Iterable<T> coll, Predicate<? super T> predicate)
      Returns true if no element of the collection matches the predicate.

      Using streams gives an equivalent result but is less efficient: 

      
 coll.stream().noneMatch(predicate);
      Type Parameters:
      T - the type of elements
      Parameters:
      coll - a collection
      predicate - a non-interfering, stateless predicate
      Returns:
      true if no element of the collection matches the predicate

    • indexOf

      public static int indexOf(List<?> list, Object value, int start)
      Returns the first index of the given value in the list, starting at the given index. Uses Object.equals() for comparison.
      Parameters:
      list - a list
      value - the value to search for
      start - the starting index
      Returns:
      the index of the value in the list, at or after the given index

    • replace

      public static <T> List<T> replace(Iterable<T> c, Iterable<CollectionsPlume.Replacement<T>> replacements)
      Performs a set of replacements on the given collection, returning the transformed result (as a list).
      Type Parameters:
      T - the type of collection elements
      Parameters:
      c - a collection
      replacements - the replacements to perform on the collection, in order from the beginning of the collection to the end
      Returns:
      the transformed collection, as a new list (even if no changes were made)

    • replace

      public static <T> List<T> replace(T[] c, Collection<CollectionsPlume.Replacement<T>> replacements)
      Performs a set of replacements on the given array, returning the transformed result (as a list).
      Type Parameters:
      T - the type of collection elements
      Parameters:
      c - an array
      replacements - the replacements to perform on the arary, in order from the beginning of the list to the end
      Returns:
      the transformed collection, as a list

    • isSubsequenceMaybeNonContiguous

      public static <T> boolean isSubsequenceMaybeNonContiguous(Iterable<T> longer, Iterable<T> shorter)
      Returns true if the second list is a subsequence (not necessarily contiguous) of the first.
      Type Parameters:
      T - the type of elements of the list
      Parameters:
      longer - a list
      shorter - a list
      Returns:
      true if the second list is a subsequence (not necessarily contiguous) of the first

    • sortedSetEquals

      public static <T> boolean sortedSetEquals(SortedSet<T> set1, SortedSet<T> set2)
      Returns true if the two sets contain the same elements in the same order. This is faster than regular equals(), for sets with the same ordering operator, especially for sets that are not extremely small.
      Type Parameters:
      T - the type of elements in the sets
      Parameters:
      set1 - the first set to compare
      set2 - the first set to compare
      Returns:
      true if the two sets contain the same elements in the same order

    • sortedSetContainsAll

      public static <T> boolean sortedSetContainsAll(SortedSet<T> set1, SortedSet<T> set2)
      Returns true if the two sets contain the same elements in the same order. This is faster than regular containsAll(), for sets with the same ordering operator, especially for sets that are not extremely small.
      Type Parameters:
      T - the type of elements in the sets
      Parameters:
      set1 - the first set to compare
      set2 - the first set to compare
      Returns:
      true if the first set contains all the elements of the second set

    • makeArrayList

      public static <T> ArrayList<T> makeArrayList(Enumeration<T> e)
      Returns a vector containing the elements of the enumeration.
      Type Parameters:
      T - type of the enumeration and vector elements
      Parameters:
      e - an enumeration to convert to a ArrayList
      Returns:
      a vector containing the elements of the enumeration

    • listOf

      public static <E> List<E> listOf(E e1, E e2)
      Creates an immutable list containing two elements. In Java 9+, use List.of().
      Type Parameters:
      E - the List's element type
      Parameters:
      e1 - the first element
      e2 - the second element
      Returns:
      a List containing the specified elements

    • append

      public static <T> List<T> append(Collection<T> list, T lastElt)
      Concatenates a list and an element into a new list.
      Type Parameters:
      T - the type of the list elements
      Parameters:
      list - the list; is not modified by this method
      lastElt - the new last elemeent
      Returns:
      a new list containing the list elements and the last element, in that order

    • concatenate

      public static <T> List<T> concatenate(Collection<T> list1, Collection<T> list2)
      Concatenates two lists into a new list.
      Type Parameters:
      T - the type of the list elements
      Parameters:
      list1 - the first list
      list2 - the second list
      Returns:
      a new list containing the contents of the given lists, in order

    • createCombinations

      public static <T> List<List<T>> createCombinations(@org.checkerframework.checker.index.qual.Positive int dims, @org.checkerframework.checker.index.qual.NonNegative int start, List<T> objs)
      Returns a list of lists of each combination (with repetition, but not permutations) of the specified objects starting at index start over dims dimensions, for dims > 0.

      For example, createCombinations(1, 0, {a, b, c}) returns a 3-element list of singleton lists: 

          {a}, {b}, {c}
      And createCombinations(2, 0, {a, b, c}) returns a 6-element list of 2-element lists: 
          {a, a}, {a, b}, {a, c}
    {b, b}, {b, c},
    {c, c}
      Type Parameters:
      T - type of the input list elements, and type of the innermost output list elements
      Parameters:
      dims - number of dimensions: that is, size of each innermost list
      start - initial index
      objs - list of elements to create combinations of
      Returns:
      list of lists of length dims, each of which combines elements from objs

    • createCombinations

      public static ArrayList<ArrayList<Integer>> createCombinations(int arity, @org.checkerframework.checker.index.qual.NonNegative int start, int cnt)
      Returns a list of lists of each combination (with repetition, but not permutations) of integers from start to cnt (inclusive) over arity dimensions.

      For example, createCombinations(1, 0, 2) returns a 3-element list of singleton lists: 

          {0}, {1}, {2}
      And createCombinations(2, 10, 2) returns a 6-element list of 2-element lists: 
          {10, 10}, {10, 11}, {10, 12}, {11, 11}, {11, 12}, {12, 12}
      The length of the list is (cnt multichoose arity), which is ((cnt + arity - 1) choose arity).
      Parameters:
      arity - size of each innermost list
      start - initial value
      cnt - maximum element value
      Returns:
      list of lists of length arity, each of which combines integers from start to cnt

    • iteratorToIterable

      public static <T> Iterable<T> iteratorToIterable(Iterator<T> source)
      Converts an Iterator to an Iterable. The resulting Iterable can be used to produce a single, working Iterator (the one that was passed in). Subsequent calls to its iterator() method will fail, because otherwise they would return the same Iterator instance, which may have been exhausted, or otherwise be in some indeterminate state. Calling iteratorToIterable twice on the same argument can have similar problems, so don't do that.
      Type Parameters:
      T - the element type
      Parameters:
      source - the Iterator to be converted to Iterable
      Returns:
      source, converted to Iterable

    • randomElements

      public static <T> List<T> randomElements(Iterator<T> itor, int numElts)
      Returns a List containing numElts randomly chosen elements from the iterator, or all the elements of the iterator if there are fewer. It examines every element of the iterator, but does not keep them all in memory.
      Type Parameters:
      T - type of the iterator elements
      Parameters:
      itor - elements to be randomly selected from
      numElts - number of elements to select
      Returns:
      list of numElts elements from itor

    • randomElements

      public static <T> List<T> randomElements(Iterator<T> itor, int numElts, Random random)
      Returns a List containing numElts randomly chosen elements from the iterator, or all the elements of the iterator if there are fewer. It examines every element of the iterator, but does not keep them all in memory.
      Type Parameters:
      T - type of the iterator elements
      Parameters:
      itor - elements to be randomly selected from
      numElts - number of elements to select
      random - the Random instance to use to make selections
      Returns:
      list of numElts elements from itor

    • incrementMap

      public static <K extends @NonNull Object> @Nullable Integer incrementMap(Map<K,Integer> m, K key)
      Increment the Integer which is indexed by key in the Map. Set the value to 1 if not currently mapped.
      Type Parameters:
      K - type of keys in the map
      Parameters:
      m - map from K to Integer
      key - the key whose value will be incremented
      Returns:
      the old value, before it was incremented; this might be null
      Throws:
      Error - if the key is in the Map but maps to a non-Integer

    • incrementMap

      public static <K extends @NonNull Object> @Nullable Integer incrementMap(Map<K,Integer> m, K key, int count)
      Increment the Integer which is indexed by key in the Map. Set the value to count if not currently mapped.
      Type Parameters:
      K - type of keys in the map
      Parameters:
      m - map from K to Integer
      key - the key whose value will be incremented
      count - how much to increment the value by
      Returns:
      the old value, before it was incremented; this might be null
      Throws:
      Error - if the key is in the Map but maps to a non-Integer

    • mapToString

      public static <K extends @Signed @Nullable Object, V extends @Signed @Nullable Object> String mapToString(Map<K,V> m)
      Returns a multi-line string representation of a map.
      Type Parameters:
      K - type of map keys
      V - type of map values
      Parameters:
      m - map to be converted to a string
      Returns:
      a multi-line string representation of m

    • mapToString

      public static <K extends @Signed @Nullable Object, V extends @Signed @Nullable Object> void mapToString(Appendable sb, Map<K,V> m, String linePrefix)
      Write a multi-line representation of the map into the given Appendable (e.g., a StringBuilder).
      Type Parameters:
      K - type of map keys
      V - type of map values
      Parameters:
      sb - an Appendable (such as StringBuilder) to which to write a multi-line string representation of m
      m - map to be converted to a string
      linePrefix - prefix to write at the beginning of each line

    • sortedKeySet

      public static <K extends Comparable<? super K>, V> Collection<@KeyFor("#1") K> sortedKeySet(Map<K,V> m)
      Returns a sorted version of m.keySet().
      Type Parameters:
      K - type of the map keys
      V - type of the map values
      Parameters:
      m - a map whose keyset will be sorted
      Returns:
      a sorted version of m.keySet()

    • sortedKeySet

      public static <K, V> Collection<@KeyFor("#1") K> sortedKeySet(Map<K,V> m, Comparator<K> comparator)
      Returns a sorted version of m.keySet().
      Type Parameters:
      K - type of the map keys
      V - type of the map values
      Parameters:
      m - a map whose keyset will be sorted
      comparator - the Comparator to use for sorting
      Returns:
      a sorted version of m.keySet()

    • mapCapacity

      public static int mapCapacity(int numElements)
      Given an expected number of elements, returns the capacity that should be passed to a HashMap or HashSet constructor, so that the set or map will not resize.
      Parameters:
      numElements - the maximum expected number of elements in the map or set
      Returns:
      the initial capacity to pass to a HashMap or HashSet constructor

    • mapCapacity

      public static <T> int mapCapacity(T[] a)
      Given an array, returns the capacity that should be passed to a HashMap or HashSet constructor, so that the set or map will not resize.
      Type Parameters:
      T - the type of elements of the array
      Parameters:
      a - an array whose length is the maximum expected number of elements in the map or set
      Returns:
      the initial capacity to pass to a HashMap or HashSet constructor

    • mapCapacity

      public static int mapCapacity(Collection<?> c)
      Given a collection, returns the capacity that should be passed to a HashMap or HashSet constructor, so that the set or map will not resize.
      Parameters:
      c - a collection whose size is the maximum expected number of elements in the map or set
      Returns:
      the initial capacity to pass to a HashMap or HashSet constructor

    • mapCapacity

      public static int mapCapacity(Map<?,?> m)
      Given a map, returns the capacity that should be passed to a HashMap or HashSet constructor, so that the set or map will not resize.
      Parameters:
      m - a map whose size is the maximum expected number of elements in the map or set
      Returns:
      the initial capacity to pass to a HashMap or HashSet constructor

    • deepCopy

      public static <K extends @Nullable DeepCopyable<K>, V extends @Nullable DeepCopyable<V>, M extends @Nullable Map<K, V>> @PolyNull M deepCopy(@PolyNull M orig)
      Returns a copy of orig, where each key and value in the result is a deep copy (according to the DeepCopyable interface) of the corresponding element of orig.
      Type Parameters:
      K - the type of keys of the map
      V - the type of values of the map
      M - the type of the map
      Parameters:
      orig - a map
      Returns:
      a copy of orig, as described above

    • deepCopyValues

      public static <K, V extends @Nullable DeepCopyable<V>, M extends @Nullable Map<K, V>> @PolyNull M deepCopyValues(@PolyNull M orig)
      Returns a copy of orig, where each value of the result is a deep copy (according to the DeepCopyable interface) of the corresponding value of orig, but the keys are the same objects.
      Type Parameters:
      K - the type of keys of the map
      V - the type of values of the map
      M - the type of the map
      Parameters:
      orig - a map
      Returns:
      a copy of orig, as described above

    • createLruCache

      public static <K, V> Map<K,V> createLruCache(@org.checkerframework.checker.index.qual.Positive int size)
      Creates a LRU cache.

      You might want to consider using a WeakHashMap or WeakIdentityHashMap instead

      Type Parameters:
      K - the type of keys
      V - the type of values
      Parameters:
      size - size of the cache
      Returns:
      a new cache with the provided size

    • cloneElements

      public static <K, V, M extends @Nullable Map<K, V>> @PolyNull M cloneElements(@PolyNull M orig)
      Returns a copy of orig, where each key and value in the result is a clone of the corresponding element of orig.
      Type Parameters:
      K - the type of keys of the map
      V - the type of values of the map
      M - the type of the map
      Parameters:
      orig - a map
      Returns:
      a copy of orig, as described above

    • cloneValues

      public static <K, V, M extends @Nullable Map<K, V>> @PolyNull M cloneValues(@PolyNull M orig)
      Returns a copy of orig, where each value of the result is a clone of the corresponding value of orig, but the keys are the same objects.
      Type Parameters:
      K - the type of keys of the map
      V - the type of values of the map
      M - the type of the map
      Parameters:
      orig - a map
      Returns:
      a copy of orig, as described above

    • getFromSet

      public static @Nullable Object getFromSet(Set<? extends @Nullable Object> set, Object key)
      Returns the object in the given set that is equal to key. The Set abstraction doesn't provide this; it only provides "contains". Returns null if the argument is null, or if it isn't in the set.
      Parameters:
      set - a set in which to look up the value
      key - the value to look up in the set
      Returns:
      the object in the given set that is equal to key, or null

    • adjoin

      public static <T> boolean adjoin(Collection<T> c, T e)
      Adds an element to the given collection, but only if it is not already present.
      Type Parameters:
      T - the type of the collection elements
      Parameters:
      c - a collection to be added to; is side-effected by this method
      e - an element to add to the collection
      Returns:
      true if the collection c changed (that is, if an element was added)

    • adjoinAll

      public static <T> boolean adjoinAll(Collection<T> c, Collection<? extends T> toAdd)
      Adds elements to the given collection, but only ones that are not already present.

      This method could alternately be named "union".

      Type Parameters:
      T - the type of the collection elements
      Parameters:
      c - a collection to be added to; is side-effected by this method
      toAdd - elements to add to the collection, if they are not already present
      Returns:
      true if the collection c changed (that is, if an element was added)

    • listUnion

      public static <T> List<T> listUnion(Collection<T> c1, Collection<T> c2)
      Returns a new list that is the union of the given collections. The given lists should be small, since the cost of this method is O(c1.size() * c2.size()). For small lists, this is more efficient than creating and using a Set.
      Type Parameters:
      T - the type of the collection elements
      Parameters:
      c1 - the first collection
      c2 - the second collection
      Returns:
      a duplicate-free list that is the union of the given collections

    • listIntersection

      public static <T> List<T> listIntersection(Collection<T> c1, Collection<T> c2)
      Returns a new list that is the intersection of the given collections. The given lists should be small, since the cost of this method is O(c1.size() * c2.size()). For small lists, this is more efficient than creating and using a Set.
      Type Parameters:
      T - the type of the collection elements
      Parameters:
      c1 - the first collection
      c2 - the second collection
      Returns:
      a duplicate-free list that is the union of the given collections

    • intersectionCardinalityAtLeast

      @Pure public static boolean intersectionCardinalityAtLeast(BitSet a, BitSet b, @org.checkerframework.checker.index.qual.NonNegative int i)
      Returns true if the cardinality of the intersection of the two BitSets is at least the given value.
      Parameters:
      a - the first BitSet to intersect
      b - the second BitSet to intersect
      i - the cardinality bound
      Returns:
      true iff size(a intersect b) ≥ i

    • intersectionCardinalityAtLeast

      @Pure public static boolean intersectionCardinalityAtLeast(BitSet a, BitSet b, BitSet c, @org.checkerframework.checker.index.qual.NonNegative int i)
      Returns true if the cardinality of the intersection of the three BitSets is at least the given value.
      Parameters:
      a - the first BitSet to intersect
      b - the second BitSet to intersect
      c - the third BitSet to intersect
      i - the cardinality bound
      Returns:
      true iff size(a intersect b intersect c) ≥ i

    • intersectionCardinality

      @Pure public static int intersectionCardinality(BitSet a, BitSet b)
      Returns the cardinality of the intersection of the two BitSets.
      Parameters:
      a - the first BitSet to intersect
      b - the second BitSet to intersect
      Returns:
      size(a intersect b)

    • intersectionCardinality

      @Pure public static int intersectionCardinality(BitSet a, BitSet b, BitSet c)
      Returns the cardinality of the intersection of the three BitSets.
      Parameters:
      a - the first BitSet to intersect
      b - the second BitSet to intersect
      c - the third BitSet to intersect
      Returns:
      size(a intersect b intersect c)