https://kotlinlang.org logo
Title
a

asavio

12/28/2021, 8:59 AM
Hey guys, Does anyone know a mechanism to sort a possibly infinite
Sequence
or one with a really a large count of objects lazily without it being too time consuming like the factory methods?
r

Ruckus

12/28/2021, 9:02 AM
If you can find a way to sort an infinite number of things in finite time, you get all the money.
😂 1
a

asavio

12/28/2021, 9:06 AM
True, I guess I worded it wrong. Let say it’s not infinite. It’s just a sequence with a thousand objects. Is there a way to yield objects in a sorted order without waiting for all of the objects to arrive beforehand?
e

ephemient

12/28/2021, 9:14 AM
unless you know something about the order they arrive in, you must receive every object to determine the minimum, which is the first element in the sorted result, so no.
1
with additional knowledge - for example, if there is a guarantee that objects won't come out of order by more than some displacement of
n
- then you have some options
a

asavio

12/28/2021, 10:57 AM
The use case is as follows. There are five sequences, each of them in ascending order; they are then flattened into a single sequence, which is expected to be in a sorted order.
// list.size == 5

list.map {
    `yield objects in ascending order`()
}.asSequence().flatten()
Is there a solution for this?
e

ephemient

12/28/2021, 12:11 PM
if they weren't flattened then there would be a solution
a

asavio

12/28/2021, 12:14 PM
Could you elaborate?
e

ephemient

12/28/2021, 12:41 PM
well-known CS algorithm,
fun <T : Comparable<T>> Iterable<Sequence<T>>.mergeSorted(): Sequence<T> = mergeSorted(comparator = naturalOrder())
fun <T> Iterable<Sequence<T>>.mergeSorted(comparator: Comparator<T>): Sequence<T> = sequence {
    val queue = PriorityQueue<Pair<Iterator<T>, T>>(compareBy(comparator) { it.second })
    mapNotNullTo(queue) { it.iterator().takeIf { it.hasNext() }?.let { it to it.next() } }
    while (queue.isNotEmpty()) {
        val (iterator, value) = queue.remove()
        yield(value)
        if (iterator.hasNext()) queue.add(iterator to iterator.next())
    }
}

fun main() {
    listOf(
        generateSequence(1) { 2 * it },
        generateSequence(1) { 3 * it },
        generateSequence(1) { 5 * it },
    ).mergeSorted().take(20).forEach { println(it) }
}
a

asavio

12/28/2021, 1:02 PM
I see it! Thank you very much, @ephemient!