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)

List subListFrom, subListTo

List<E>.subList(fromIndex, toIndex) provides view of a list bound on both sides. This provides a one-sided view. Semantics are the same as subList in terms of non-structural changes.

The OrNull variants return null instead of throwing IndexOutOfBoundsException if indexes are invalid.

ListAsSortedSet (LaSS)

If the producer of some List<T> produces a sorted set, like the output of a database fetch with distinct and ordered elements, we can convert the list to an ordered set view with .assertIsSortedSet().

This provides performance opportunities as search and intersection can go from possibly N^2 time to N lg N time or even linear time. (Note: there is no JMH code in the test suite to verify this performance improvement.)

An existing ListAsSortedSet<T> can be mutated with buildCopy, which behaves like buildSet with initial set.

If a list that isn't both distinct and sorted is used with assertIsSortedList(), the behavior is undefined. copyToSortedSet() can be used to create a sorted set copy, which behaves as if toSet().toMutableList().apply { sort() }.assertIsSortedList(), with appropriate overloads for Comparator.

Because Kotlin doesn't have a SortedSet interface, the following methods from java.util.SortedSet are ported over:

• subSet(fromElement, toElement): SortedSet
• headSet(toElement): SortedSet
• tailSet(fromElement): SortedSet

The distinct sorted list is accessible with .list.