java.util.Arrays

Arrays provides extensive operations for working with arrays, offering valuable insights into various algorithms.

Sorting

The sort methods come in multiple overloaded forms. Here's the implementation for int[]:

public static void sort(int[] data) {
    DualPivotQuicksort.sort(data, 0, data.length - 1, null, 0, 0);
}
public static void sort(int[] data, int start, int end) {
    rangeCheck(data.length, start, end);
    DualPivotQuicksort.sort(data, start, end - 1, null, 0, 0);
}

Each data type variant follows this pattern: one accepts the full range while the other accepts explicit start and end indices. Both delegate to DualPivotQuicksort.sort internally.

DualPivotQuicksort determines the optimal sorting strategy based on the input characteristics. The algorithm selection includes:

• Merge Sort (optimized into TimSort)
• Insertion Sort
• Quick Sort
• Counting Sort

Merge Sort divides the sequence recursively until reaching atomic elements, then merges them back in sorted order. However, many sequences already contain ordered subsequences, making full division wasteful. TimSort addresses this by first identifying pre-sorted runs and only merging those. When the number of runs exceeds MAX_RUN_COUNT, DualPivotQuicksort switches to quicksort.

Quick Sort selects a pivot value and partitions the array so elements less than the pivot move left while elements greater move right. This recursively continues until sorted. Traditional quicksort uses a single pivot. DualPivotQuicksort optimizes this to use two pivots, partitioning into three sections:

* Partitioning:
*
*   left section    middle section           right section
* +----------------------------------------------------------+
* | == pivot1 |  pivot1 < && < pivot2  |    ?    | == pivot2 |
* +----------------------------------------------------------+
*              ^                        ^       ^
*              |                        |       |
*             less                      k     great
*
* Invariants:
*
*              all in (*,  less) == pivot1
*     pivot1 < all in [less,  k)  < pivot2
*              all in (great, *) == pivot2
*
* Pointer k marks the start of the ?-section.

The algorithm traverses from k and great toward eachother, placing elements into their appropriate sections, then recursively processes the three partitions.

Counting Sort: /todo

Binary Search

The binary search implementations require pre-sorted input. The implementation repeatedly halves the search space using the >>> operator instead of division by 2.

public static int binarySearch(int[] dataset, int target) {
    return binarySearch0(dataset, 0, dataset.length, target);
}

public static int binarySearch(int[] dataset, int from, int to, int target) {
    rangeCheck(dataset.length, from, to);
    return binarySearch0(dataset, from, to, target);
}

private static int binarySearch0(int[] dataset, int from, int to, int target) {
    int start = from;
    int finish = to - 1;

    while (start <= finish) {
        int mid = (start + finish) >>> 1;
        int midValue = dataset[mid];
        if (midValue < target)
            start = mid + 1;
        else if (midValue > target)
            finish = mid - 1;
        else
            return mid;
    }
    return -(start + 1);
}

Returns a negative value when the target is not found.

Equality Comparison

Arrays support two comparison modes: primitive type comparisons using == and object comparisons using equals().

public static boolean equals(int[] first, int[] second) {
    if (first == second)
        return true;
    if (first == null || second == null)
        return false;

    int len = first.length;
    if (second.length != len)
        return false;

    for (int i = 0; i < len; i++)
        if (first[i] != second[i])
            return false;

    return true;
}

public static boolean equals(Object[] first, Object[] second) {
    if (first == second)
        return true;
    if (first == null || second == null)
        return false;

    int len = first.length;
    if (second.length != len)
        return false;

    for (int i = 0; i < len; i++) {
        Object a = first[i];
        Object b = second[i];
        if (!(a == null ? b == null : a.equals(b)))
            return false;
    }

    return true;
}

Deep equality recursively compares nested arrays:

public static boolean deepEquals(Object[] source, Object[] target) {
    if (source == target)
        return true;
    if (source == null || target == null)
        return false;
    int len = source.length;
    if (target.length != len)
        return false;

    for (int i = 0; i < len; i++) {
        Object elem1 = source[i];
        Object elem2 = target[i];

        if (elem1 == elem2)
            continue;
        if (elem1 == null)
            return false;

        if (!deepEquals0(elem1, elem2))
            return false;
    }
    return true;
}

static boolean deepEquals0(Object x, Object y) {
    assert x != null;
    boolean result;
    if (x instanceof Object[] && y instanceof Object[])
        result = deepEquals((Object[]) x, (Object[]) y);
    else if (x instanceof byte[] && y instanceof byte[])
        result = equals((byte[]) x, (byte[]) y);
    else if (x instanceof short[] && y instanceof short[])
        result = equals((short[]) x, (short[]) y);
    else if (x instanceof int[] && y instanceof int[])
        result = equals((int[]) x, (int[]) y);
    else if (x instanceof long[] && y instanceof long[])
        result = equals((long[]) x, (long[]) y);
    else if (x instanceof char[] && y instanceof char[])
        result = equals((char[]) x, (char[]) y);
    else if (x instanceof float[] && y instanceof float[])
        result = equals((float[]) x, (float[]) y);
    else if (x instanceof double[] && y instanceof double[])
        result = equals((double[]) x, (double[]) y);
    else if (x instanceof boolean[] && y instanceof boolean[])
        result = equals((boolean[]) x, (boolean[]) y);
    else
        result = x.equals(y);
    return result;
}

Fill Operation

The fill method populates an array with a specified value:

public static void fill(int[] buffer, int value) {
    for (int i = 0, len = buffer.length; i < len; i++)
        buffer[i] = value;
}
public static void fill(int[] buffer, int from, int to, int value) {
    rangeCheck(buffer.length, from, to);
    for (int i = from; i < to; i++)
        buffer[i] = value;
}

Copy Operations

copyOf copies array contents into a new array of specified length:

public static int[] copyOf(int[] source, int newSize) {
    int[] destination = new int[newSize];
    System.arraycopy(source, 0, destination, 0,
                     Math.min(source.length, newSize));
    return destination;
}

copyOfRange extracts a portion of the array. Using generics, it leverages Array.newInstance via reflection:

public static <T> T[] copyOfRange(T[] source, int from, int to) {
    return copyOfRange(source, from, to, (Class<? extends T[]>) source.getClass());
}
public static <T,U> T[] copyOfRange(U[] source, int from, int to, Class<? extends T[]> newType) {
    int length = to - from;
    if (length < 0)
        throw new IllegalArgumentException(from + " > " + to);
    @SuppressWarnings("unchecked")
    T[] result = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[length]
        : (T[]) Array.newInstance(newType.getComponentType(), length);
    System.arraycopy(source, from, result, 0,
                     Math.min(source.length - from, length));
    return result;
}

Hash Computation

Array hash incorporates all element values:

public static int hashCode(int[] values) {
    if (values == null)
        return 0;

    int hash = 1;
    for (int element : values)
        hash = 31 * hash + element;

    return hash;
}

This design creates hash collisions. For instance, [0,1] and [1,-31] produce identical hashes through the formula (31*1+0)31+1 = (311+1)*31-31.

Object arrays use the element's hashCode method:

public static int hashCode(Object[] values) {
    if (values == null)
        return 0;

    int hash = 1;

    for (Object element : values)
        hash = 31 * hash + (element == null ? 0 : element.hashCode());

    return hash;
}

Deep hash recursively processes nested arrays:

public static int deepHashCode(Object[] values) {
    if (values == null)
        return 0;

    int hash = 1;

    for (Object element : values) {
        int elementHash = 0;
        if (element instanceof Object[])
            elementHash = deepHashCode((Object[]) element);
        else if (element instanceof byte[])
            elementHash = hashCode((byte[]) element);
        else if (element instanceof short[])
            elementHash = hashCode((short[]) element);
        else if (element instanceof int[])
            elementHash = hashCode((int[]) element);
        else if (element instanceof long[])
            elementHash = hashCode((long[]) element);
        else if (element instanceof char[])
            elementHash = hashCode((char[]) element);
        else if (element instanceof float[])
            elementHash = hashCode((float[]) element);
        else if (element instanceof double[])
            elementHash = hashCode((double[]) element);
        else if (element instanceof boolean[])
            elementHash = hashCode((boolean[]) element);
        else if (element != null)
            elementHash = element.hashCode();

        hash = 31 * hash + elementHash;
    }

    return hash;
}

String Representation

toString generates a readable string representation:

public static String toString(int[] data) {
    if (data == null)
        return "null";
    int lastIndex = data.length - 1;
    if (lastIndex == -1)
        return "[]";

    StringBuilder output = new StringBuilder();
    output.append('[');
    for (int i = 0; ; i++) {
        output.append(data[i]);
        if (i == lastIndex)
            return output.append(']').toString();
        output.append(", ");
    }
}

deepToString handles nested arrays recursively:

public static String deepToString(Object[] data) {
    if (data == null)
        return "null";

    int bufSize = 20 * data.length;
    if (data.length != 0 && bufSize <= 0)
        bufSize = Integer.MAX_VALUE;
    StringBuilder output = new StringBuilder(bufSize);
    deepToString(data, output, new HashSet<Object[]>());
    return output.toString();
}

private static void deepToString(Object[] data, StringBuilder output,
                                 Set<Object[]> seen) {
    if (data == null) {
        output.append("null");
        return;
    }
    int lastIndex = data.length - 1;
    if (lastIndex == -1) {
        output.append("[]");
        return;
    }

    seen.add(data);
    output.append('[');
    for (int i = 0; ; i++) {

        Object item = data[i];
        if (item == null) {
            output.append("null");
        } else {
            Class<?> itemClass = item.getClass();

            if (itemClass.isArray()) {
                if (itemClass == byte[].class)
                    output.append(toString((byte[]) item));
                else if (itemClass == short[].class)
                    output.append(toString((short[]) item));
                else if (itemClass == int[].class)
                    output.append(toString((int[]) item));
                else if (itemClass == long[].class)
                    output.append(toString((long[]) item));
                else if (itemClass == char[].class)
                    output.append(toString((char[]) item));
                else if (itemClass == float[].class)
                    output.append(toString((float[]) item));
                else if (itemClass == double[].class)
                    output.append(toString((double[]) item));
                else if (itemClass == boolean[].class)
                    output.append(toString((boolean[]) item));
                else {
                    if (seen.contains(item))
                        output.append("[...]");
                    else
                        deepToString((Object[])item, output, seen);
                }
            } else {
                output.append(item.toString());
            }
        }
        if (i == lastIndex)
            break;
        output.append(", ");
    }
    output.append(']');
    seen.remove(data);
}

java.util.Collections

Unmodifiable Wrappers

Unmodifiable wrappers prevent any modification attempts, throwing UnsupportedOperationException:

public boolean add(E element) {
    throw new UnsupportedOperationException();
}

Available unmodifiable methods:

static Collection<T> unmodifiableCollection(Collection<T> source);
static List<T> unmodifiableList(List<T> source);
static Set<T> unmodifiableSet(Set<T> source);
static SortedSet<T> unmodifiableSortedSet(SortedSet<T> source);
static NavigableSet<T> unmodifiableNavigableSet(NavigableSet<T> source);
static Map<T> unmodifiableMap(Map<T> source);
static SortedMap<T> unmodifiableSortedMap(SortedMap<T> source);
static NavigableMap<T> unmodifiableNavigableMap(NavigableMap<T> source);

Synchronized Wrappers

Synchronized wrappers add synchronized blocks around each operation:

public boolean add(E element) {
    synchronized (lock) { return collection.add(element); }
}

The lock defaults to the wrapped collection but can be supplied externally:

public static <T> Collection<T> synchronizedCollection(Collection<T> collection) {
    return new SynchronizedCollection<>(collection);
}

static <T> Collection<T> synchronizedCollection(Collection<T> collection, Object lock) {
    return new SynchronizedCollection<>(collection, lock);
}

While these wrappers solve thread safety, they perform poorly under high concurrency. Consider java.util.concurrent alternatives like CopyOnWriteArrayList or ConcurrentHashMap.

Synchronized variants available:

static synchronizedSet(Set source);
static synchronizedSet(Set source, Object lock);
static synchronizedCollection(Collection source);
static synchronizedCollection(Collection source, Object lock);
static synchronizedList(List source);
static synchronizedList(List source, Object lock);
static synchronizedSortedSet(SortedSet source);
static synchronizedNavigableSet(NavigableSet source);
static synchronizedMap(Map source);
static synchronizedSortedMap(SortedMap source);
static synchronizedNavigableMap(NavigableMap source);

Type-Safe Wrappers

checked~ methods create type-safe containers that reject incompatible elements. The type parameter defines the expected element type.

public static <E> Collection<E> checkedCollection(Collection<E> collection,
                                                  Class<E> type) {
    return new CheckedCollection<>(collection, type);
}

public boolean add(E element) {
    return collection.add(typeCheck(element));
}

E typeCheck(Object item) {
    if (item != null && !type.isInstance(item))
        throw new ClassCastException(invalidElementMessage(item));
    return (E) item;
}

Generics introduced in 1.6 largely supersede this functionality, but the API remains:

static checkedCollection(Collection source, Class type);
static checkedQueue(Queue source, Class type);
static checkedSet(Set source, Class type);
static checkedSortedSet(SortedSet source, Class type);
static checkedNavigableSet(NavigableSet source, Class type);
static checkedList(List source, Class type);
static checkedMap(Map source, Class keyType, Class valueType);
static checkedSortedMap(SortedMap source, Class keyType, Class valueType);
static checkedNavigableMap(NavigableMap source, Class keyType, Class valueType);

Empty Collections

empty~ methods return singleton instances of empty collections. These are immutable; any modification attempt delegates to AbstractList, which throws an exception.

public static final List EMPTY_LIST = new EmptyList<>();

public static final <T> List<T> emptyList() {
    return (List<T>) EMPTY_LIST;
}

Available empty collection factories:

static emptyListIterator();
static emptySet();
static emptySortedSet();
static emptyNavigableSet();
static emptyList();
static emptyMap();
static emptySortedMap();
static emptyNavigableMap();
static emptyEnumeration();
static emptyIterator();

Singleton Collections

Singleton collections hold exactly one immutable element:

public static <T> List<T> singletonList(T element) {
    return new SingletonList<>(element);
}

private static class SingletonList<E>
        extends AbstractList<E>
        implements RandomAccess, Serializable {

        private static final long serialVersionUID = 3093736618740652951L;

        private final E element;

        SingletonList(E item) { element = item; }

        public Iterator<E> iterator() {
            return singletonIterator(element);
        }

        public int size() { return 1; }

        public boolean contains(Object obj) { return eq(obj, element); }

        public E get(int index) {
            if (index != 0)
                throw new IndexOutOfBoundsException("Index: "+index+", Size: 1");
            return element;
        }

        @Override
        public void forEach(Consumer<? super E> action) {
            action.accept(element);
        }
        @Override
        public boolean removeIf(Predicate<? super E> filter) {
            throw new UnsupportedOperationException();
        }
        @Override
        public void replaceAll(UnaryOperator<E> operator) {
            throw new UnsupportedOperationException();
        }
        @Override
        public void sort(Comparator<? super E> comparator) {}
        @Override
        public Spliterator<E> spliterator() {
            return singletonSpliterator(element);
        }
    }

Singleton collection methods:

static singleton(Object element);
static singletonIterator(Object element);
static singletonSpliterator(Object element);
static singletonList(Object element);
static singletonMap(Object key, Object value);

Sorting

public static <T extends Comparable<? super T>> void sort(List<T> list) {
    list.sort(null);
}

public static <T> void sort(List<T> list, Comparator<? super T> comparator) {
    list.sort(comparator);
}

These delegate to the List's own sort method. For ArrayList:

public void sort(Comparator<? super E> comparator) {
    final int expectedModCount = modCount;
    Arrays.sort((E[]) elementData, 0, size, comparator);
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
    modCount++;
}

LinkedList implements this through ListIterator:

default void sort(Comparator<? super E> comparator) {
    Object[] arr = this.toArray();
    Arrays.sort(arr, (Comparator) comparator);
    ListIterator<E> iter = this.listIterator();
    for (Object e : arr) {
        iter.next();
        iter.set((E) e);
    }
}

Both ultimately delegate to Arrays.sort.

Binary Search

The list must be sorted. The implementation checks for RandomAccess to choose between indexed and iterator-based binary search.

public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key) {
    if (list instanceof RandomAccess || list.size() < BINARYSEARCH_THRESHOLD)
        return Collections.indexedBinarySearch(list, key);
    else
        return Collections.iteratorBinarySearch(list, key);
}

public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c) {
    if (c == null)
        return binarySearch((List<? extends Comparable<? super T>>) list, key);

    if (list instanceof RandomAccess || list.size() < BINARYSEARCH_THRESHOLD)
        return Collections.indexedBinarySearch(list, key, c);
    else
        return Collections.iteratorBinarySearch(list, key, c);
}

The underlying implementations:

private static <T> int indexedBinarySearch(List<? extends T> list, T key, Comparator<? super T> c) {
    int low = 0;
    int high = list.size() - 1;

    while (low <= high) {
        int mid = (low + high) >>> 1;
        T midValue = list.get(mid);
        int cmp = c.compare(midValue, key);

        if (cmp < 0)
            low = mid + 1;
        else if (cmp > 0)
            high = mid - 1;
        else
            return mid;
    }
    return -(low + 1);
}

private static <T> int iteratorBinarySearch(List<? extends T> list, T key, Comparator<? super T> c) {
    int low = 0;
    int high = list.size() - 1;
    ListIterator<? extends T> iter = list.listIterator();

    while (low <= high) {
        int mid = (low + high) >>> 1;
        T midValue = get(iter, mid);
        int cmp = c.compare(midValue, key);

        if (cmp < 0)
            low = mid + 1;
        else if (cmp > 0)
            high = mid - 1;
        else
            return mid;
    }
    return -(low + 1);
}

private static <T> T get(ListIterator<? extends T> iter, int index) {
    T obj = null;
    int pos = iter.nextIndex();
    if (pos <= index) {
        do {
            obj = iter.next();
        } while (pos++ < index);
    } else {
        do {
            obj = iter.previous();
        } while (--pos > index);
    }
    return obj;
}

The iterator-based approach uses sequential traversal to reach the mid position, making it less efficient for LinkedList.

Reverse

reverse swaps elements from both ends toward the center. For RandomAccess lists, it uses index-based swapping; otherwise, it uses iterators positioned at both ends.

public static void reverse(List<?> list) {
    int size = list.size();
    if (size < REVERSE_THRESHOLD || list instanceof RandomAccess) {
        for (int i = 0, mid = size >> 1, j = size - 1; i < mid; i++, j--)
            swap(list, i, j);
    } else {
        ListIterator forward = list.listIterator();
        ListIterator backward = list.listIterator(size);
        for (int i = 0, mid = list.size() >> 1; i < mid; i++) {
            Object temp = forward.next();
            forward.set(backward.previous());
            backward.set(temp);
        }
    }
}

Comparator Utilities

reverseOrder inverts a comparator's logic. ReverseComparator2 wraps the supplied comparator:

public static <T> Comparator<T> reverseOrder(Comparator<T> cmp) {
    if (cmp == null)
        return reverseOrder();

    if (cmp instanceof ReverseComparator2)
        return ((ReverseComparator2<T>)cmp).cmp;

    return new ReverseComparator2<>(cmp);
}

private static class ReverseComparator2<T> implements Comparator<T>, Serializable {
    private static final long serialVersionUID = 4374092139857L;
    final Comparator<T> cmp;

    ReverseComparator2(Comparator<T> cmp) {
        assert cmp != null;
        this.cmp = cmp;
    }

    public int compare(T a, T b) {
        return cmp.compare(b, a);
    }

    public boolean equals(Object o) {
        return (o == this) ||
            (o instanceof ReverseComparator2 &&
             cmp.equals(((ReverseComparator2)o).cmp));
    }

    public int hashCode() {
        return cmp.hashCode() ^ Integer.MIN_VALUE;
    }

    @Override
    public Comparator<T> reversed() {
        return cmp;
    }
}

reverseOrder() without arguments returns a natural-order reversing comparator:

public static <T> Comparator<T> reverseOrder() {
    return (Comparator<T>) ReverseComparator.REVERSE_ORDER;
}

private static class ReverseComparator
    implements Comparator<Comparable<Object>>, Serializable {

    private static final long serialVersionUID = 7207038068494060240L;

    static final ReverseComparator REVERSE_ORDER = new ReverseComparator();

    public int compare(Comparable<Object> a, Comparable<Object> b) {
        return b.compareTo(a);
    }

    private Object readResolve() { return Collections.reverseOrder(); }

    @Override
    public Comparator<Comparable<Object>> reversed() {
        return Comparator.naturalOrder();
    }
}

Shuffle

shuffle randomizes list order using Random. Without a supplied Random instance, it creates one internally.

public static void shuffle(List<?> list) {
    Random generator = r;
    if (generator == null)
        r = generator = new Random();
    shuffle(list, generator);
}

private static Random r;

public static void shuffle(List<?> list, Random generator) {
    int size = list.size();
    if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
        for (int i = size; i > 1; i--)
            swap(list, i - 1, generator.nextInt(i));
    } else {
        Object[] arr = list.toArray();

        for (int i = size; i > 1; i--)
            swap(arr, i - 1, generator.nextInt(i));

        ListIterator iter = list.listIterator();
        for (int i = 0; i < arr.length; i++) {
            iter.next();
            iter.set(arr[i]);
        }
    }
}

private static void swap(Object[] arr, int i, int j) {
    Object tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

Fill

fill replaces all elements with a specified value. RandomAccess lists use indexed access; others use iterators.

public static <T> void fill(List<? super T> list, T value) {
    int size = list.size();

    if (size < FILL_THRESHOLD || list instanceof RandomAccess) {
        for (int i = 0; i < size; i++)
            list.set(i, value);
    } else {
        ListIterator<? super T> iter = list.listIterator();
        for (int i = 0; i < size; i++) {
            iter.next();
            iter.set(value);
        }
    }
}

Copy

copy replicates elements from the source to the destination. The destination must have sufficient capacity.

public static <T> void copy(List<? super T> dest, List<? extends T> src) {
    int srcSize = src.size();
    if (srcSize > dest.size())
        throw new IndexOutOfBoundsException("Source does not fit in dest");

    if (srcSize < COPY_THRESHOLD ||
        (src instanceof RandomAccess && dest instanceof RandomAccess)) {
        for (int i = 0; i < srcSize; i++)
            dest.set(i, src.get(i));
    } else {
        ListIterator<? super T> destIter = dest.listIterator();
        ListIterator<? extends T> srcIter = src.listIterator();
        for (int i = 0; i < srcSize; i++) {
            destIter.next();
            destIter.set(srcIter.next());
        }
    }
}

Logical Copies

nCopies creates a list of n copies of element o. The implementation reuses a single reference rather than creating n separate copies.

public static <T> List<T> nCopies(int count, T element) {
    if (count < 0)
        throw new IllegalArgumentException("List length = " + count);
    return new CopiesList<>(count, element);
}

final class CopiesList<E> extends AbstractList<E>
    implements RandomAccess, Serializable {

    final int count;
    final E element;

    CopiesList(int count, E element) {
        assert count >= 0;
        this.count = count;
        this.element = element;
    }
}

Rotation

rotate shifts elements circularly. For [1,2,3,4,5], rotate(1) yields [5,1,2,3,4]. RandomAccess lists use rotate1, others use rotate2.

public static void rotate(List<?> list, int distance) {
    if (list instanceof RandomAccess || list.size() < ROTATE_THRESHOLD)
        rotate1(list, distance);
    else
        rotate2(list, distance);
}

private static <T> void rotate1(List<T> list, int distance) {
    int size = list.size();
    if (size == 0)
        return;
    distance = distance % size;
    if (distance < 0)
        distance += size;
    if (distance == 0)
        return;

    for (int cycleStart = 0, moved = 0; moved != size; cycleStart++) {
        T displaced = list.get(cycleStart);
        int pos = cycleStart;
        do {
            pos += distance;
            if (pos >= size)
                pos -= size;
            displaced = list.set(pos, displaced);
            moved++;
        } while (pos != cycleStart);
    }
}

private static void rotate2(List<?> list, int distance) {
    int size = list.size();
    if (size == 0)
        return;
    int mid = -distance % size;
    if (mid < 0)
        mid += size;
    if (mid == 0)
        return;
    
    reverse(list.subList(0, mid));
    reverse(list.subList(mid, size));
    reverse(list);
}

rotate2 achieves rotation by reversing three segments: the elements before the split point, the elements after, and then the entire list.

Frequency Counting

public static int frequency(Collection<?> collection, Object target) {
    int count = 0;
    if (target == null) {
        for (Object e : collection)
            if (e == null)
                count++;
    } else {
        for (Object e : collection)
            if (target.equals(e))
                count++;
    }
    return count;
}

Disjoint Check

public static boolean disjoint(Collection<?> c1, Collection<?> c2) {
    Collection<?> contains = c2;
    Collection<?> iterate = c1;

    if (c1 instanceof Set) {
        iterate = c2;
        contains = c1;
    } else if (!(c2 instanceof Set)) {
        int size1 = c1.size();
        int size2 = c2.size();
        if (size1 == 0 || size2 == 0)
            return true;

        if (size1 > size2) {
            iterate = c2;
            contains = c1;
        }
    }

    for (Object e : iterate) {
        if (contains.contains(e))
            return false;
    }

    return true;
}

The algorithm chooses the more efficient approach based on collection types. Sets have O(1) contains operations, so they become the contains collection. For non-sets, the smaller collection is iterated.

Min/Max

public static <T extends Object & Comparable<? super T>> T min(Collection<? extends T> coll) {
    Iterator<? extends T> iter = coll.iterator();
    T current = iter.next();

    while (iter.hasNext()) {
        T next = iter.next();
        if (next.compareTo(current) < 0)
            current = next;
    }
    return current;
}

public static <T> T min(Collection<? extends T> coll, Comparator<? super T> comp) {
    if (comp == null)
        return (T) min((Collection) coll);

    Iterator<? extends T> iter = coll.iterator();
    T current = iter.next();

    while (iter.hasNext()) {
        T next = iter.next();
        if (comp.compare(next, current) < 0)
            current = next;
    }
    return current;
}

public static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll) {
    Iterator<? extends T> iter = coll.iterator();
    T current = iter.next();

    while (iter.hasNext()) {
        T next = iter.next();
        if (next.compareTo(current) > 0)
            current = next;
    }
    return current;
}

public static <T> T max(Collection<? extends T> coll, Comparator<? super T> comp) {
    if (comp == null)
        return (T) max((Collection) coll);

    Iterator<? extends T> iter = coll.iterator();
    T current = iter.next();

    while (iter.hasNext()) {
        T next = iter.next();
        if (comp.compare(next, current) > 0)
            current = next;
    }
    return current;
}

Conversion Utilities

static asLifoQueue(Deque source);
static newSetFromMap(Map source);
static enumeration(Collection source);
static list(Enumeration source);

java.lang.Objects

Objects provides straightforward utilities for comparison, hashing, and validation.

public static boolean equals(Object a, Object b) {
    return (a == b) || (a != null && a.equals(b));
}

public static boolean deepEquals(Object a, Object b) {
    if (a == b)
        return true;
    else if (a == null || b == null)
        return false;
    else
        return Arrays.deepEquals0(a, b);
}

public static int hashCode(Object o) {
    return o != null ? o.hashCode() : 0;
}

public static int hash(Object... values) {
    return Arrays.hashCode(values);
}

public static String toString(Object o) {
    return String.valueOf(o);
}

public static String toString(Object o, String nullDefault) {
    return (o != null) ? o.toString() : nullDefault;
}

public static <T> int compare(T a, T b, Comparator<? super T> c) {
    return (a == b) ? 0 : c.compare(a, b);
}

public static <T> T requireNonNull(T obj) {
    if (obj == null)
        throw new NullPointerException();
    return obj;
}

public static <T> T requireNonNull(T obj, String message) {
    if (obj == null)
        throw new NullPointerException(message);
    return obj;
}

public static boolean isNull(Object obj) {
    return obj == null;
}

public static boolean nonNull(Object obj) {
    return obj != null;
}

public static <T> T requireNonNull(T obj, Supplier<String> messageSupplier) {
    if (obj == null)
        throw new NullPointerException(messageSupplier.get());
    return obj;
}