https://kotlinlang.org logo
Title
m

Mark

06/07/2022, 2:05 AM
fun <T> Iterable<T>.splitByIndex(index: Int): Pair<List<T>, List<T>> {
    if (index <= 0) {
        return emptyList<T>() to this.toList()
    }
    val iterator = this.iterator()
    val firstList = mutableListOf<T>()
    val secondList = mutableListOf<T>()
    var activeList = firstList
    while (iterator.hasNext()) {
        if (activeList.size == index) {
            activeList = secondList
        }
        activeList.add(iterator.next())
    }
    return firstList to secondList
}
Is it okay to check the
size
each time or better to maintain a local
Int
count?
e

ephemient

06/07/2022, 2:09 AM
for a
List
it is definitely more efficient to use
fun <T> List<T>.splitAt(index: Int) = take(index) to drop(index)
since that uses
.subList()
underneath which most
List
implementations override (e.g.
ArrayList
which returns a view with no extra allocation)
👍 2
and for a not-
List
index
is usually not very meaningful
…hmm, I thought it used
subList
but it doesn't seem to after all
slice
does, though
m

Mark

06/07/2022, 2:14 AM
Yes, I was just looking at
Iterable.take()
and I noticed something else:
if (this is Collection<T>) {
    if (n >= size) return toList()
    if (n == 1) return listOf(first())
}
Doesn’t that second line run into the problem you mentioned earlier?
e

ephemient

06/07/2022, 2:15 AM
yep
sometimes those trade-offs are acceptable - in almost all cases, concurrent modification of a data structure is a broken idea. I specifically use
CopyOnWriteArrayList
because it's one of the few data structures that actually has well-defined and useful behavior on concurrent modification. I would write generic code to make as few assumptions about the underlying data as possible, but it seems kotlin.collections is more optimized around non-mutating collections - which is probably reasonable for most Kotlin applications
(e.g. if you were to mutate a
mutableListOf(...)
in one thread while reading it in another, there's no guarantees about consistency whatsoever, regardless of how safe the reader code is; it's only specific concurrent collections such as
CopyOnWriteArrayList
which promise
iterator()
stability)
👍 1
m

Mark

06/07/2022, 2:23 AM
fun <T> Iterable<T>.splitAt(index: Int): Pair<List<T>, List<T>> {
    if (index <= 0) {
        return emptyList<T>() to this.toList()
    }
    if (this is List) { // optimization to avoid iterator
        val safeList = this.toList()
        if (index >= safeList.size) {
            return safeList to emptyList()
        }
        return safeList.subList(0, index) to safeList.subList(index, safeList.size)
    }
    val iterator = this.iterator()
    val firstList = mutableListOf<T>()
    val secondList = mutableListOf<T>()
    var activeList = firstList
    while (iterator.hasNext()) {
        if (activeList.size == index) {
            activeList = secondList
        }
        activeList.add(iterator.next())
    }
    return firstList to secondList
}
BTW, I do have a use case for non-Lists. For example, a sorted set where you want to take the first few items and also do something with the remainder. I suppose to be ultra safe, I should convert the
List
using
toList()
and only then apply
subList
(UPDATED CODE)
e

ephemient

06/07/2022, 2:33 AM
sure, that's one approach. I would tend to prefer
buildList {
    repeat(index) {
        if (!iterator.hasNext()) return@buildList
        add(iterator.next())
    }
} to buildList {
    while (iterator.hasNext()) add(iterator.next())
}
but you could even do tricks like
Iterable { iterator }.take(index) to Iterable { iterator }.toList()
👍 2
m

Mark

06/07/2022, 2:33 AM
Hmm, so perhaps even create the
safeList
anyway straight after the initial index check
fun <T> Iterable<T>.splitAt(index: Int): Pair<List<T>, List<T>> {
    if (index <= 0) {
        return emptyList<T>() to this.toList()
    }
    val safeList = this.toList()
    if (index >= safeList.size) {
        return safeList to emptyList()
    }
    return safeList.subList(0, index) to safeList.subList(index, safeList.size)
}
e

ephemient

06/07/2022, 2:35 AM
I think there's a few other places in stdlib which do a similar defensive copy to an Array, but generally you don't need to go for that
there isn't really much difference between doing the iteration yourself and the list copy, both of them go through the iterator once
m

Mark

06/07/2022, 2:37 AM
Yeah fair enough, but less code
subList
returns a view on the original list, so that may be why it’s better to first create a read-only list, but actually I prefer your idea:
fun <T> Iterable<T>.splitAt(index: Int): Pair<List<T>, List<T>> {
    if (index <= 0) {
        return emptyList<T>() to this.toList()
    }
    val iterator = iterator()
    return Iterable { iterator }.take(index) to Iterable { iterator }.toList()
}