Add zero-copy sorting

[altavir]

It is now possible (or soon will be) to access buffer through permutation indices. So it makes sense to add sorting methods to provide indices without changing the data similar to Julia sortperm

[alexismanin]

Would a simple (I might even say naïve) implementation enough ? Because I think Kotlin provides all utilities to create a simple prototype. Something like that :

/**
 * Model an object providing a set of keys with a way to retrieve value associated with each key.
 * Sort of a super simple map abstraction, to model indexed (numeric: buffer, array ; arbitrary: map, others)structures.
 */
interface Indexed<I, out V> {
    fun indices() : Sequence<I>;
    operator fun get(index: I) : V?
}

/**
 * Copy and return indices of the receiver, sorted by associated value.
 */
fun <I, V : Comparable<V>> Indexed<I, V>.permSort() : List<out I> = indices().sortedBy { get(it) }.toList()

fun <V : Comparable<V>> Buffer<V>.permSort() : List<Int> {
    val buf = this
    val indexed = object : Indexed<Int, V> {
        override fun indices() = (0 until buf.size).asSequence()
        override fun get(index: Int) = buf.get(index)
    }
    return indexed.permSort()
}

Example on stdlib arrays :

fun <V : Comparable<V>> Array<V>.permSort() : List<Int> {
    val arr = this
    val indexed = object : Indexed<Int, V> {
        override fun indices() = arr.indices.asSequence()
        override fun get(i: Int) = arr.get(i)
    }
    return indexed.permSort()
}

fun main() {
    val array = arrayOf(2, 3, 1, 5, 4)
    val sortedIndices = array.permSort()
    println("Permutation indices: $sortedIndices")
    val output = sortedIndices.asSequence().map { array[it] }.joinToString()
    println("Applied on values: $output")
}

outputs:

Permutation indices: [2, 0, 1, 4, 3]
Applied on values: 1, 2, 3, 4, 5

I hope I've understood correctly what is needed. If it looks right to you, I can try to provide a PR with a refined prototype in following days (with some doc and tests).

[altavir]

It would be nice to have anything for a start. Of course, later one could require more effective sorting algorithms. API for applying permutations is waiting to be merged: https://github.com/mipt-npm/kmath/blob/fa9ff4c9787ef18cacbcb4ea38aa30bedf7de681/kmath-core/src/commonMain/kotlin/space/kscience/kmath/structures/BufferView.kt#L121.

[alexismanin]

Ok, then I'll give it a try.

I hope to submit a PR somewhere before the end of week.