[Solved] Sorting List of List of Long [closed]

by


Use element wise comparator

Compare 2 lists by

  1. compare in increasing order of index location
  2. if any non-zero value is found, return the result
  3. else compare the size of the lists
  4. sort the lists using this comparator logic

Use per index comparator chain. Based on WJS’s approach

  1. Compute the maximum list size across all of the inner lists
  2. Create a chain of comparator for every index from 0 to the computed maximum size
  3. Use this decorated(chain of responsibility) comparator to sort the lists
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.Objects;
import java.util.function.IntFunction;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class SortNestedList {

    protected List<List<Long>> transform(Long[][] inputArray) {
        return Arrays.stream(inputArray)
            .filter(Objects::nonNull) // filter outer null lists
            .map(nested -> Arrays.stream(nested)
                .filter(Objects::nonNull)
                .collect(Collectors.toList())) // generate nested list by filtering any null values
            .collect(Collectors.toList());
    }

    protected void sortWithElementComparator(List<List<Long>> lists) {
        lists.sort((a, b) -> {
            return IntStream.range(0, Math.min(a.size(), b.size())) // check till end of minimum sized list
                .map(i -> Long.compare(a.get(i), b.get(i))) // compare elements at same index
                .filter(i -> i != 0) // ignore equal values comparison
                .findFirst() // get first non-zero comparison result (unequal)
                .orElse(Integer.compare(a.size(), b.size())); // if nothing, then compare size
        });

        lists.forEach(System.out::println);
    }

    protected void sortWithDecoratedComparator(List<List<Long>> lists) {
        // comparator for an index
        IntFunction<Comparator<List<Long>>> elementAtIndexComparator =
            index -> (a, b) -> index < Math.min(a.size(), b.size()) ?
                Long.compare(a.get(index), b.get(index)) : // compare elements if index is valid for both lists
                Integer.compare(a.size(), b.size()); // compare size if index is invalid for atleast 1 list

        final int maxInnerIndices = lists.stream()
            .mapToInt(List::size)
            .max().orElse(0); // get max inner list size or 0 if empty

        Comparator<List<Long>> listComparator = IntStream.range(0, maxInnerIndices)
            .mapToObj(elementAtIndexComparator) // index comparator for every index
            .reduce(Comparator::thenComparing) // kind of chain of responsibility / decorator
            .orElse((a, b) -> 0);

        lists.sort(listComparator);

        lists.forEach(System.out::println);
    }

    protected void sort(Long[][] inputArray, int run) {
        System.out.println("Sort input using direct element comparator: " + run);
        sortWithElementComparator(transform(inputArray));
        System.out.println("Sort input using decorated comparator: " + run);
        sortWithDecoratedComparator(transform(inputArray));
    }
}

Test code

    public static void main(String[] args) {
        final SortNestedList sortNestedList = new SortNestedList();
        int run = 0;

        Long[][] inputArray = new Long[][]{};
        sortNestedList.sort(inputArray, ++run);

        inputArray = new Long[][]{{null}};
        sortNestedList.sort(inputArray, ++run);

        inputArray = new Long[][]{{null}, {1L}};
        sortNestedList.sort(inputArray, ++run);

        inputArray = new Long[][]{null, {1L}};
        sortNestedList.sort(inputArray, ++run);

        inputArray = new Long[][]{{1L}, {1L}};
        sortNestedList.sort(inputArray, ++run);

        inputArray = new Long[][]{{2L}, {1L}};
        sortNestedList.sort(inputArray, ++run);

        inputArray = new Long[][]{{2L, 1L}, {1L, 3L}};
        sortNestedList.sort(inputArray, ++run);

        inputArray = new Long[][]{{Long.MAX_VALUE, 1L}, {Long.MIN_VALUE, 3L}};
        sortNestedList.sort(inputArray, ++run);

        inputArray = new Long[][]{{1L}, {2L, 5L, 6L},
            {1L, 2L}, {2L}, {1L, 2L, 3L}, {3L, 2L}, {2L, 3L},
            {1L, 2L, 3L, 4L, 6L}, {1L, 2L, 3L, 4L, 5L},
            {1L, 2L, 3L, 4L, 6L, 2L}, {1L, 2L, 3L, 4L, 5L, 3L, 5L},
            {Long.MAX_VALUE, Long.MAX_VALUE, 1L, 5L, Long.MIN_VALUE + 1, Long.MAX_VALUE - 1},
            {Long.MAX_VALUE, Long.MIN_VALUE, 1L, 5L, Long.MIN_VALUE + 1, Long.MAX_VALUE - 1},
            {Long.MIN_VALUE}, {Long.MAX_VALUE}};
        sortNestedList.sort(inputArray, ++run);
    }

Thanks to Holger and WJS

3

solved Sorting List of List of Long [closed]