SetOperations.java

/*
 * Copyright 2020 Collect Utils Authors
 *
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements. See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership. The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License. You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied. See the License for the
 * specific language governing permissions and limitations
 * under the License.
 */
package net.morimekta.collect.util;

import net.morimekta.collect.SetBuilder;
import net.morimekta.collect.UnmodifiableSet;

import java.util.Comparator;
import java.util.Objects;
import java.util.Set;
import java.util.SortedSet;

import static net.morimekta.collect.UnmodifiableSet.asSet;
import static net.morimekta.collect.UnmodifiableSet.setOf;
import static net.morimekta.collect.UnmodifiableSortedSet.asSortedSet;
import static net.morimekta.collect.UnmodifiableSortedSet.newBuilderOrderedBy;

/**
 * Utility class containing set-math operations.
 * <p>
 * See <a href="https://www.probabilitycourse.com/chapter1/1_2_2_set_operations.php">probabilitycouse</a>
 * or <a href="https://www.britannica.com/science/set-theory/Operations-on-sets">britannica</a>
 * for definitions and theory.
 */
public final class SetOperations {
    /**
     * Get the union of all the set's provided. Essentially a set
     * of all elements in each set in the input.
     *
     * @param of  Sets to make union of.
     * @param <E> The item type.
     * @return The union set.
     */
    @SafeVarargs
    public static <E> Set<E> union(Set<E>... of) {
        Objects.requireNonNull(of);
        if (of.length == 0) {
            return setOf();
        }
        SetBuilder<E> builder;
        if (of[0] instanceof SortedSet) {
            SortedSet<E> first = (SortedSet<E>) of[0];
            builder = newBuilderOrderedBy(first.comparator());
        } else {
            builder = UnmodifiableSet.newBuilder();
        }
        for (Set<E> set : of) {
            builder.addAll(set);
        }
        return builder.build();
    }

    /**
     * Get the intersection between the sets. These are the items contains
     * in all the sets provided.
     *
     * @param set  The main set to make intersection with.
     * @param with Sets to intersect with.
     * @param <E>  The item type.
     * @return The intersected set.
     */
    @SafeVarargs
    public static <E> Set<E> intersect(Set<E> set, Set<E>... with) {
        if (with.length == 0) {
            if (set instanceof SortedSet) {
                return asSortedSet(set);
            }
            return asSet(set);
        }
        SetBuilder<E> builder;
        if (set instanceof SortedSet) {
            SortedSet<E> first = (SortedSet<E>) set;
            builder = newBuilderOrderedBy(set.size(), first.comparator());
        } else {
            builder = UnmodifiableSet.newBuilder(set.size());
        }
        setLoop:
        for (E e : set) {
            for (Set<E> w : with) {
                if (!w.contains(e)) {
                    continue setLoop;
                }
            }
            builder.add(e);
        }
        return builder.build();
    }

    /**
     * Take the minuend, and subtract all elements contained in all the subtrahend sets.
     *
     * @param minuend     The source set to be removed elements from.
     * @param subtrahends The sets with elements to remove.
     * @param <E>         The element type.
     * @return The difference set from the subtraction.
     */
    @SafeVarargs
    @SuppressWarnings("unchecked,rawtypes")
    public static <E> Set<E> subtract(Set<E> minuend, Set<E>... subtrahends) {
        if (subtrahends.length == 0) {
            if (minuend instanceof SortedSet) {
                return asSortedSet(minuend);
            }
            return asSet(minuend);
        }
        SetBuilder<E> builder;
        if (minuend instanceof SortedSet) {
            SortedSet<E> first = (SortedSet<E>) minuend;
            builder = newBuilderOrderedBy((Comparator) first.comparator());
        } else {
            builder = UnmodifiableSet.newBuilder();
        }

        setLoop:
        for (E e : minuend) {
            for (Set<E> w : subtrahends) {
                if (w.contains(e)) {
                    continue setLoop;
                }
            }
            builder.add(e);
        }
        return builder.build();
    }

    /**
     * Create a difference set of the items contained only in either
     * of the two sets, but not both. This is the same as
     * <code>union(subtract(a, b), subtract(b, a))</code>, but much more
     * efficient.
     *
     * @param first  The first set.
     * @param second The second set.
     * @param <E>    The item type.
     * @return The difference set.
     */
    public static <E> Set<E> difference(Set<E> first, Set<E> second) {
        SetBuilder<E> builder;
        if (first instanceof SortedSet) {
            if (first.isEmpty()) {
                return asSortedSet(second);
            }
            if (second.isEmpty()) {
                return asSortedSet(first);
            }
            builder = newBuilderOrderedBy(
                    first.size() + second.size(),
                    ((SortedSet<E>) first).comparator());
        } else {
            if (first.isEmpty()) {
                return asSet(second);
            }
            if (second.isEmpty()) {
                return asSet(first);
            }
            builder = UnmodifiableSet.newBuilder(first.size() + second.size());
        }

        for (E e : first) {
            if (!second.contains(e)) {
                builder.add(e);
            }
        }
        for (E e : second) {
            if (!first.contains(e)) {
                builder.add(e);
            }
        }
        return builder.build();
    }

    /**
     * Calculate the cartesian product of the two sets. The cartesian product will
     * combine every element of A with every element of B, so the resulting set
     * will have a total of <code>size(A) * size(B)</code> elements each with a
     * unique combination of <code>(Ax, By)</code> pair.
     *
     * @param a   The first set
     * @param b   The second set
     * @param <A> The element type in first set
     * @param <B> The element type in second set
     * @return The cartesian product.
     */
    @SuppressWarnings("unchecked,rawtypes")
    public static <A, B> Set<Pair<A, B>> product(Set<A> a, Set<B> b) {
        SetBuilder<Pair<A, B>> builder;
        if (a instanceof SortedSet && b instanceof SortedSet) {
            SortedSet<A> sa = (SortedSet<A>) a;
            SortedSet<B> sb = (SortedSet<B>) b;

            Comparator<Pair<A, B>> comparator = sa.comparator() == null ?
                                                Comparator.comparing(p -> (Comparable) p.first) :
                                                Comparator.comparing(Pair::getFirst, sa.comparator());
            if (sb.comparator() == null) {
                comparator = comparator.thenComparing(p -> (Comparable) p.second);
            } else {
                comparator = comparator.thenComparing(p -> p.second, sb.comparator());
            }

            if (a.isEmpty() || b.isEmpty()) {
                return newBuilderOrderedBy(comparator).build();
            }

            builder = newBuilderOrderedBy(a.size() * b.size(), comparator);
        } else {
            if (a.isEmpty() || b.isEmpty()) {
                return UnmodifiableSet.setOf();
            }
            builder = UnmodifiableSet.newBuilder(a.size() * b.size());
        }

        for (A ia : a) {
            for (B ib : b) {
                builder.add(Pair.pairOf(ia, ib));
            }
        }
        return builder.build();
    }

    /**
     * Check if the first set is a subset of the second.
     *
     * @param set The set to check.
     * @param of  The set to check against.
     * @param <E> The item type.
     * @return True if the first set is a subset of the second.
     */
    public static <E> boolean subset(Set<E> set, Set<E> of) {
        if (set.size() > of.size()) {
            return false;
        }
        for (E e : set) {
            if (!of.contains(e)) {
                return false;
            }
        }
        return true;
    }

    /**
     * Check that the two sets are disjoint, meaning they have no items in common.
     * Same that the intersection between the sets are empty.
     *
     * @param first  The first set.
     * @param second The second set.
     * @param <E>    The item type.
     * @return True if the two sets are disjoint.
     */
    public static <E> boolean disjoint(Set<E> first, Set<E> second) {
        // We actually only need to check one way, as the equality
        // items always comes in pairs...
        for (E item : first) {
            if (second.contains(item)) {
                return false;
            }
        }
        return true;
    }

    private SetOperations() {}
}