Mark
06/07/2022, 2:05 AMfun <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?ephemient
06/07/2022, 2:09 AMList
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)List
index
is usually not very meaningfulsubList
but it doesn't seem to after allslice
does, thoughMark
06/07/2022, 2:14 AMIterable.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?ephemient
06/07/2022, 2:15 AMCopyOnWriteArrayList
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 applicationsmutableListOf(...)
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)Mark
06/07/2022, 2:23 AMfun <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)ephemient
06/07/2022, 2:33 AMbuildList {
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()
Mark
06/07/2022, 2:33 AMsafeList
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)
}
ephemient
06/07/2022, 2:35 AMMark
06/07/2022, 2:37 AMsubList
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()
}