Sorting list according to another list

Support
1

I want to sort a list by the elements of another list. So the second list should explicitly define the order of the resulting (ordered) list.

The best I came up with is this:

fun main() {
    val things = setOf(Thing(2, "x"), Thing(1, "y"), Thing(3, "z"), Thing(4, "a"))
    val desiredOrder = listOf(3, 4, 1, 2)
    val sortedThings = things.sortedWith { a, b -> 
        desiredOrder.indexOf(a.id).compareTo(desiredOrder.indexOf(b.id)) 
    }
    println(sortedThings)
    // prints: [Thing(id=3, name=z), Thing(id=4, name=a), Thing(id=1, name=y), Thing(id=2, name=x)]
}

data class Thing(val id: Int, val name: String)

https://pl.kotl.in/C_JkL57H8

However, compared to Guava’s Ordering.explicit it is quite verbose:

List<User> users = userDao.loadUsersWithIds(userIds);
Ordering<User> orderById = Ordering.explicit(userIds).onResultOf(UserFunctions.getId());
return orderById.immutableSortedCopy(users);

Is there a better way in Kotlin?

2

You are doing two scans of disiredOrder everytime there’s a comparison. Guava uses a Map to avoid this. Also, sortedBy is feels more analogous to onResultOf.

To match guava, you’ll want to do something more like this:

fun main() {
    val things = setOf(Thing(2, "x"), Thing(1, "y"), Thing(3, "z"), Thing(4, "a"))
    val desiredOrder = listOf(3, 4, 1, 2).indexMap()
    val sortedThings = things.sortedBy { desiredOrder[it.id] }
    println(sortedThings)
    // prints: [Thing(id=3, name=z), Thing(id=4, name=a), Thing(id=1, name=y), Thing(id=2, name=x)]
}

data class Thing(val id: Int, val name: String)

fun <T> Iterable<T>.indexMap(): Map<T, Int> {
    val map = mutableMapOf<T, Int>()
    forEachIndexed { i, v ->
        map.put(v, i)
    }
    return map
}
3 Likes
3

I hoped that there might be something in the standard lib. Anyway, I like your implementation!

A slightly more concise variant of your indexMap function:

fun <T> Iterable<T>.indexMap(): Map<T, Int> = 
    this.mapIndexed { i, v -> Pair(v, i) }.toMap()

However, your version might be a bit more efficient, since no intermediate list as a result of mapIndexed is needed.

2 Likes
4

Do we actually need sorting here? What about something like this?

fun main() {
    val things = setOf(Thing(2, "x"), Thing(1, "y"), Thing(3, "z"), Thing(4, "a"))
    val desiredOrder = listOf(3, 4, 1, 2)
    val thingsById = things.associateBy { it.id }
    val sortedThings = desiredOrder.map { thingsById[it] }
    println(sortedThings)
    // prints: [Thing(id=3, name=z), Thing(id=4, name=a), Thing(id=1, name=y), Thing(id=2, name=x)]
}

data class Thing(val id: Int, val name: String)

Alternatively, if some of ids in desiredOrder may not be present in things, as in the linked topic, it’s enough to change map to mapNotNull:

fun main() {
    val things = setOf(Thing(2, "x"), Thing(3, "z"), Thing(4, "a"))
    val desiredOrder = listOf(3, 4, 1, 2)
    val thingsById = things.associateBy { it.id }
    val sortedThings = desiredOrder.mapNotNull { thingsById[it] }
    println(sortedThings)
    // prints: [Thing(id=3, name=z), Thing(id=4, name=a), Thing(id=2, name=x)]
}

data class Thing(val id: Int, val name: String)
5 Likes