path: root/src/ch/epfl/xblast/Lists.java

package ch.epfl.xblast;

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;

/**
 * Lists utility class providing common operations on lists.
 *
 * @author Pacien TRAN-GIRARD (261948)
 * @author Timothée FLOURE (257420)
 */
public final class Lists {

    /**
     * Returns an immutable copy of a list.
     *
     * @param l   a list
     * @param <T> the element type
     * @return the immutable list
     */
    public static <T> List<T> immutableList(List<T> l) {
        return Collections.unmodifiableList(new ArrayList<>(l));
    }

    /**
     * Returns an immutable copy of a map.
     *
     * @param m   a mab
     * @param <K> the key type
     * @param <V> the value type
     * @return the immutable copy
     */
    public static <K, V> Map<K, V> immutableMap(Map<K, V> m) {
        return Collections.unmodifiableMap(new HashMap<>(m));
    }

    /**
     * Returns a copy of the given list with element e prepended.
     *
     * @param l   the list
     * @param e   the element to prepend
     * @param <T> the type of the list's elements
     * @return a copy of the list with the element prepended
     */
    public static <T> List<T> prepended(List<T> l, T e) {
        return Lists.inserted(l, 0, e);
    }

    /**
     * Returns a copy of the given list with element e appended.
     *
     * @param l   the list
     * @param e   the element to append
     * @param <T> the type of the list's elements
     * @return a copy of the list with the element appended
     */
    public static <T> List<T> appended(List<T> l, T e) {
        return Lists.inserted(l, l.size(), e);
    }

    /**
     * Returns an immutable copy of the given list, sorted using the supplied comparator.
     *
     * @param l   the list to sort
     * @param cmp the Comparator to use
     * @param <T> the type of the list's elements
     * @return the sorted list
     */
    public static <T> List<T> sorted(List<T> l, Comparator<T> cmp) {
        List<T> r = new ArrayList<>(l);
        Collections.sort(r, cmp);
        return Collections.unmodifiableList(r);
    }

    /**
     * Returns a copy of the given list surrounded with element e.
     *
     * @param l   the list
     * @param e   the element to insert
     * @param <T> the type of the list's elements
     * @return a copy of the list with the element inserted at start and end
     */
    public static <T> List<T> surrounded(List<T> l, T e) {
        return Lists.appended(Lists.prepended(l, e), e);
    }

    /**
     * Returns a symmetric version of the list, without repeating the last element of the input list.
     * For instance, mirrored([kay]) will return [kayak].
     *
     * @param l   the input list
     * @param <T> the type of the list's elements
     * @return the mirrored list
     * @throws IllegalArgumentException if the given list is empty
     */
    public static <T> List<T> mirrored(List<T> l) {
        if (l == null || l.size() == 0) throw new IllegalArgumentException();

        return Stream
                .concat(l.stream(), Lists.reversed(l).stream().skip(1))
                .collect(Collectors.toList());
    }

    /**
     * Returns all the permutations of the elements of the given list.
     *
     * @param l   given list
     * @param <T> the type of the list's elements
     * @return a list of all the permutations of the list
     * @throws IllegalArgumentException if the given list is null
     */
    public static <T> List<List<T>> permutations(List<T> l) {
        if (l == null) throw new IllegalArgumentException();
        if (l.size() <= 1) return Collections.singletonList(l);
        if (l.size() == 2) return Arrays.asList(l, Lists.reversed(l));

        List<List<T>> p = new LinkedList<>();
        for (List<T> sp : Lists.permutations(l.subList(1, l.size())))
            for (int i = 0; i <= sp.size(); ++i)
                p.add(Lists.inserted(sp, i, l.get(0)));

        return p;
    }

    /**
     * Returns a copy of the given list with the first n items dropped.
     *
     * @param l   given list
     * @param n   number of items to drop
     * @param <T> the type of the list's elements
     * @return a copy of the list with the n first element dropped
     */
    public static <T> List<T> firstDropped(List<T> l, int n) {
        if (Objects.isNull(l))
            return Collections.emptyList();

        return new ArrayList<>(l.subList(n, l.size()));
    }

    /**
     * Returns an immutable copy of the given lists, concatenated.
     *
     * @param lists the lists to concatenate
     * @param <T>   the type of the list's elements
     * @return the list result of the concatenation
     * @deprecated Use List<T> concatenated(List<List<T>> lists) instead to avoid parametrized varargs.
     */
    public static <T> List<T> concatenated(List<T>... lists) {
        return concatenated(Arrays.asList(lists));
    }

    /**
     * Returns an immutable copy of the given lists, concatenated.
     *
     * @param lists the lists to concatenate
     * @param <T>   the type of the list's elements
     * @return the list result of the concatenation
     */
    public static <T> List<T> concatenated(List<List<T>> lists) {
        return Collections.unmodifiableList(
                lists.stream()
                        .map(List::stream)
                        .reduce(Stream::concat).orElseGet(Stream::empty)
                        .collect(Collectors.toList()));
    }

    /**
     * Returns a reversed copy of the given list, leaving the original one unmodified.
     *
     * @param l   the list to reverse
     * @param <T> the type of the list's elements
     * @return a reversed copy of the list
     */
    private static <T> List<T> reversed(List<T> l) {
        List<T> r = new ArrayList<>(l);
        Collections.reverse(r);
        return r;
    }

    /**
     * Returns a copy of the given list with element e inserted at index i.
     *
     * @param l   the list
     * @param i   the insertion index
     * @param e   the element to insert
     * @param <T> the type of the list's elements
     * @return a copy of the list with the element inserted
     */
    private static <T> List<T> inserted(List<T> l, int i, T e) {
        List<T> r = new LinkedList<>(l);
        r.add(i, e);
        return r;
    }

    /**
     * Maps linearly two lists.
     *
     * @param kl  the keys list
     * @param vl  the values list
     * @param <K> the key type
     * @param <V> the value type
     * @return the map
     */
    public static <K, V> Map<K, V> linearMap(List<K> kl, List<V> vl) {
        if (Objects.isNull(kl) || Objects.isNull(vl) || kl.size() != vl.size())
            throw new IllegalArgumentException();

        Map<K, V> m = new HashMap<>();
        Iterator<K> ki = kl.iterator();
        Iterator<V> vi = vl.iterator();

        while (ki.hasNext() && vi.hasNext())
            m.put(ki.next(), vi.next());

        return Collections.unmodifiableMap(m);
    }

    /**
     * Maps linearly two lists, adjusting their respective size by truncating the key list or completing the value list
     * with null values.
     *
     * @param kl  the keys list
     * @param vl  the values list
     * @param <K> the key type
     * @param <V> the value type
     * @return the map
     */
    public static <K, V> Map<K, V> linearAdjustedMap(List<K> kl, List<V> vl) {
        if (Objects.isNull(kl) || Objects.isNull(vl))
            throw new IllegalArgumentException();

        if (kl.size() <= vl.size())
            return Lists.linearMap(kl, vl.subList(0, kl.size()));
        else
            return Lists.linearMap(
                    kl,
                    concatenated(Arrays.asList(vl, Collections.nCopies(kl.size() - vl.size(), null))));
    }

    /**
     * Merges two maps Map<K1, IK> and Map<IK, V> -> Map<K1, V>.
     *
     * @param m1   key maps
     * @param m2   values maps
     * @param <K>  the keys type
     * @param <IK> the intermediate keys type
     * @param <V>  the values type
     * @return the traversing map
     */
    public static <K, IK, V> Map<K, V> traverseMaps(Map<K, IK> m1, Map<IK, V> m2) {
        return Collections.unmodifiableMap(m1.entrySet().stream()
                .filter(e -> Objects.nonNull(e.getValue()))
                .filter(e -> Objects.nonNull(m2.get(e.getValue())))
                .collect(Collectors.toMap(Map.Entry::getKey, e -> m2.get(e.getValue()))));
    }

    /**
     * Returns an inverted copy of a bijective map.
     *
     * @param m   the map to invert
     * @param <K> the keys type
     * @param <V> the values type
     * @return the inverted map
     */
    public static <K, V> Map<K, V> invertMap(Map<V, K> m) {
        return Collections.unmodifiableMap(m.entrySet().stream()
                .filter(e -> Objects.nonNull(e.getKey()))
                .filter(e -> Objects.nonNull(e.getValue()))
                .collect(Collectors.toMap(Map.Entry::getValue, Map.Entry::getKey)));
    }

}