CODEWITHSUNDEEP
javaeclipse-collections
Jochem Kuijpers
Jochem Kuijpers

Reputation: 1797

Eclipse Collections sorting an IntList by a custom comparator-like function without boxing

I'm trying to sort a few (Mutable)IntList objects. The cost of boxing/unboxing integers is relevant in my program (which is exactly why I am using the primitive collections). I want to sort by the following criteria:

[1, 7, 0, -9, -3] -> [-3, -9, 0, 1, 7]

Is there a sorting method for the IntList class in the Eclipse Collections library that allow a custom comparator? So far I have not found it, but the list of defined symbols is large, the search box only matches exact strings and documentation is hardly existent (mostly automatically generated from method signatures, I believe).

My last resort is to write my own int-int comparator and sorting function, which is not a big deal, but I'd rather not.

Please do not waste your time writing a proof of concept sorter, as much as I'd appreciate it.. I know how to sort a list, I just can't figure out how to locate stuff in the Eclipse Collections documentation. If you can help with that, feel free to include it in your answer.

Upvotes: 3

Views: 359

Answers (3)

zakhav
zakhav

Reputation: 56

Indirect sort support for primitive collections was introduced in Eclipse Collections starting with version 10.3. It is supported on mutable primitive collections. You can see more details and usage examples at https://medium.com/javarevisited/eclipse-collections-now-supports-indirect-sorting-of-primitive-lists-e2447ca5dbc3

The OP example would look like this:

@Test
public void soTest()
{
    // [1, 7, 0, -9, -3] -> [-3, -9, 0, 1, 7]
    MutableIntList list = IntLists.mutable.of(1, 7, 0, -9, -3);

    list.sortThis((a, b) -> {
        // negative before non-negative
        // otherwise, smallest numbers first
        if (a == b) { return 0; }
        if (a < 0 && b < 0) {
            return (a < b) ? 1 : -1;
        }
        return (a < b) ? -1 : 1;}
    );

    Assert.assertEquals(IntLists.immutable.of(-3, -9, 0, 1, 7), list);
}

The comparator lambda may be simplified to:

list.sortThis((a, b) ->
        (a < 0 && b < 0) ? Integer.compare(b, a) : Integer.compare(a, b));

Upvotes: 3

Jochem Kuijpers
Jochem Kuijpers

Reputation: 1797

Since there was no 'quick' answer here either, I went ahead and implemented such a sorting device myself.

public class IntListUtils {
    public interface IntIntComparator {
        int compare(int a, int b);
    }

    public static void sort(MutableIntList subject, IntIntComparator comparator) {
        quicksort(subject, 0, subject.size() - 1, comparator);
    }

    public static void quicksort(MutableIntList subject, int low, int high, IntIntComparator comparator) {
        if (low >= high) { return; }
        int pivot = partition(subject, low, high, comparator);
        quicksort(subject, low, pivot - 1, comparator);
        quicksort(subject, pivot, high, comparator);
    }

    private static int partition(MutableIntList subject, int low, int high, IntIntComparator comparator) {
        int pivot = subject.get(high);
        int i = low;
        for (int j = low; j <= high - 1; j++) {
            if (comparator.compare(subject.get(j), pivot) < 0) {
                int t = subject.get(i);
                subject.set(i, subject.get(j));
                subject.set(j, t);
                i += 1;
            }
        }
        int t = subject.get(i);
        subject.set(i, subject.get(high));
        subject.set(high, t);
        return i;
    }
}

Which can be used as such to achieve the sorting order as I described above:

MutableIntList list = ...;
IntListUtils.sort(list, (a, b) -> {
    // negative before non-negative
    // otherwise, smallest numbers first
    if (a == b) { return 0; }
    if (a < 0 && b < 0) {
        return (a < b) ? 1 : -1;
    }
    return (a < b) ? -1 : 1;
});

EDIT: I realize this quicksort is not the fastest sort method out there, but all it has to do is be faster than converting my entire IntList into a List<Integer> and back after sorting, which allocates O(n) memory (n is large) while this sorting method happens in-place.

Upvotes: 1

Nghia Do
Nghia Do

Reputation: 2668

IntList is the interface which MutableIntList and ImmutableIntList extended.

I'm seeing there is an implementation class which may help you in this case is IntArrayList which is implementation of MutableIntList.

There is a sortThis() method which is performing

Arrays.sort(this.items, 0, this.size);

So for you example it will return -9, -3, 0, 1, 7

But I noticed you would like to have -3, -9, 0, 1, 7. I'm not sure this is a typo or this is a requirement. When you check it, we can discuss further

Upvotes: 1

Related Questions