kotlin: sort List<T> with T being a class

user_15448482 0
Viewed 430

I have a public class defined in Kotlin: public class Edge(val v: Int, val u: Int, val weight: Double) that helps me define weighted edges of a graph.

Now, in another class, I need to make a list, which I defined as var Sides = mutableListOf<Edge>() but I need to order the list in ascending order which depends on the third parameter of Edge (which is weight). So that if I have the list:

Sides = {Edge(4, 8, 4.1), Edge(20, 9, 7.5), Edge(5, 4, 0.0)}, it becomes:

Sides = {Edge(5, 4, 0.0), Edge(4, 8, 4.1), Edge(20, 9, 7.5)}

Is there any function like .sort() I can use to order this list? or do I have to manually make a function of a sorting method for this?

Thanks in advance

kotlin list sorting
3 Answers

For a mutable collection like MutableList, you can use the sortBy function to sort the original list itself.

sides.sortBy { it.weight }

And, if you have an immutable collection like List, you can use the sortedBy function which returns a new sorted list.

val sortedList = sides.sortedBy { it.weight }

Also, you have sortByDescending and sortedByDescending for sorting in descending order.

user_133089910

You're looking for sortBy. Given a list of T, sortBy takes a mapping function from T to R (where R is some type which has an ordering defined on it). Consider

Sides.sortBy { n -> n.weight }
user_22886590

You have two basic approaches:

  1. Give Edge a natural ordering. Then all the sort functions will use it by default — as will anything else that can use an ordering (such as the order of keys in a SortedMap, and the binarySearch() method).

You do this by implementing the Comparable interface.  This has a single method, compareTo(), which could be as simple as:

public class Edge(val v: Int, val u: Int, val weight: Double) : Comparable<Edge> {
    override fun compareTo(other: Edge) = weight.compareTo(other.weight)
}

However, that doesn't give a consistent ordering to instances which have the same weight, so you might also want to use the other properties as tie-breakers, e.g.:

    override fun compareTo(other: Edge)
        = weight.compareTo(other.weight).takeIf{ it != 0 }
        ?: v.compareTo(other.v).takeIf{ it != 0 }
        ?: u.compareTo(other.u)

(There are a few subtleties in implementing that, especially if you're not also overriding equals() to correspond directly. The Java documentation is worth reading.)

Note that a data class automatically implements Comparable, using the properties in its constructor, in that order. So you don't usually need to worry about ordering for that.

  1. Provide an ordering when you sort.

Other answers discuss this. Perhaps the simplest way is:

sides.sortBy{ it.weight }

Though there are many alternatives, such as:

sides.sortWith{ a, b -> a.weight.compareTo(b.weight) }

Or you could create a Comparator instance that could be reused as necessary:

val comparator = Comparator<Edge>{ o1, o2 -> o1.weight.compareTo(o2.weight) }
sides.sortWith(comparator)

Again, a comparator can be used with many functions in the standard library, so you can avoid repeating the weight comparison code.

Which approach to choose depends on your needs.

If it makes intuitive sense for your edges to be always arranged by weight, then a natural ordering would be a good fit. That's concise to code: you just have to implement Comparable in one place (or make your class a data class with the weight property specified first), and you then get the full benefit of ordering everywhere. (Of course, you can only do that if you have control over the Edge source code.)

On the other hand, if the weight-based ordering is specific to a particular method — if you might want different orderings in other places — then it would make more sense to specify the ordering when you sort.

Of course, you can do both, if needed: you could give your object a natural ordering which applied for most things, but then specify a different ordering for particular operations.

user_101342090
Related