Kotlin containers

Containers that are used in other projects.

The following are provided:

• copy-on-write MutableList
• copy-on-write MutableMap
• copy-on-write MutableSet
• circular iterator for List

Copy on first write

We use the modify-copy concept from java.util.concurrent.CopyOnWriteArrayList and adapt it as follows: there is a kotlin.collections.List unlocked view for read operations and write operations are performed on a copy of the data while holding a lock.

However, instead of implementing the entire MutableList interface, we use a <R> write(MutableList.()->R) method to centralize the writes. So instead of

val al = java.util.concurrent.CopyOnWriteArrayList<Int>()
// ...
al.add(1)

we do

val al = CopyOnWriteArrayList<Int>()
// ...
al.write {
    add(1)
}

This makes the code slightly more verbose but makes it easier to do transactional operations like:

val al = CopyOnWriteArrayList<Int>()
val toAdd = getList()
// ...
al.write {
    for (v in toAdd) {
        require(v !in al)
        add(v)
    }
}

It also makes it clearer to see where copying (and possibly coroutine suspension) is(/are) occurring.

The same principle applies for Map and Set, with implementations for HashMap, LinkedHashMap and HashSet. CopyOnWriteHashSet is expected to be faster than j.u.c.CopyOnWriteArraySet because hashtable lookup is faster than a linear scan.

For custom types, the user may use CopyOnWriteList, CopyOnWriteMap, or CopyOnWriteSet and supply the necessary initial data and copy constructor parameters. For more exotic cases, CopyOnWriteContainer can be used.

CopyOnWriteCollection is unimplemented because it would be unused by both CopyOnWriteList and CopyOnWriteSet as the casting necessary to make it work negatively impacts readability without a good reason. Implementing it would be a trivial copy-paste of CoWTracer inside [test/kotlin/CopyOnWriteContainerTest].

Some users may prefer using Kotlin-style concurrency with suspending coroutines instead of threads, as Java interoperability is not a concern to them. To use those, import com.moshy.containers.coroutines.CopyOnWriteXXX. Those containers are interoperable with each other when reads are concerned.

Caveat(s):

• CopyOnWriteList - subList returns a snapshot, just like iterator; this is because any write qualifies as a structural modification, and only non-structural writes need to be transparent.

Circular iterator

Inspired by Python's itertools.cycle, this presents an infinite cyclical view of a List<E>'s contents.

Example:

listOf(1, 2, 3).circularIterator()
// >>> 1, 2, 3, 1, 2, 3, ...

This is only implemented as an extension method for List because that is the base interface for ordered collection with indexed access and both are certainly necessary here. An extension for Collection may be made but it will have a memory cost because it will have to store a List of the iterator contents then return a List.circularIterator for that (which Python does).

A neat thing that can be done here is to use subList to yield a circular iterator over part of the List:

val l = listOf(1, 2, 3, 4, 5)
val inner = l.subList(2, 4)
val iter = inner.circularIterator()
iter
// >>> 2, 3, 2, 3, ...

Multiple

Like Iterable<T>.single(), but generalized to any number of items, which is passed as the first argument.

multipleOrNull can be used so nulls are used instead of exceptions, as long as the item count is non-negative.

List transpose

Reasons for needing the transpose of a list are straightforward. What's special here is a transform function can be used to aggregate the transpose inner row:

val l = listOf(
  listOf(1, 2, 3),
  listOf(4, 5, 6),
  listOf(7, 8, 9)
)
l.transpose { it.sum() } // * HERE *
// =>
listOf(
  listOf(1, 4, 7).sum(),
  listOf(2, 5, 8).sum(),
  listOf(3, 6, 9).sum()
)
// =>
listOf(12, 15, 18)