A general sequence diffing algorithm, with a very specific purpose

SortedDifference.kt

// Imitated from https://github.com/groue/SortedDifference

class SortedDifference<LeftSequence: Collection<LeftElement>, RightSequence: Collection<RightElement>, LeftElement, RightElement, ID: Comparable<ID>>(
    private val left: LeftSequence,
    private val leftID: (LeftElement) -> ID,
    private val right: RightSequence,
    private val rightID: (RightElement) -> ID
) : Iterable<SortedDifferenceChange<LeftElement, RightElement>> {
    override fun iterator(): Iterator {
        return Iterator(
            left.iterator(),
            right.iterator(),
            leftID,
            rightID
        )
    }

    inner class Iterator(
        private val lIterator: kotlin.collections.Iterator<LeftElement>,
        private val rIterator: kotlin.collections.Iterator<RightElement>,
        private val lID: (LeftElement) -> ID,
        private val rID: (RightElement) -> ID
    ): kotlin.collections.Iterator<SortedDifferenceChange<LeftElement, RightElement>> {

        private var lOpt: LeftElement? = null
        private var rOpt: RightElement? = null

        init {
            lOpt = lIterator.next()
            rOpt = rIterator.next()
        }

        override fun hasNext(): Boolean {
            return lIterator.hasNext() || rIterator.hasNext()
        }

        override fun next(): SortedDifferenceChange<LeftElement, RightElement> {
            val (lElem, rElem) = (lOpt to rOpt)
            if (lElem != null && rElem != null) {
                val (lID, rID) = (this.lID(lElem) to this.rID(rElem))
                return when {
                    lID > rID -> {
                        this.rOpt = rIterator.next()
                        assertIncreasingRightId(rID)
                        SortedDifferenceChange.right(rElem)
                    }
                    lID == rID -> {
                        this.lOpt = lIterator.next()
                        this.rOpt = rIterator.next()
                        assertIncreasingLeftId(lID)
                        assertIncreasingRightId(rID)
                        SortedDifferenceChange.common(lElem, rElem)
                    }
                    else -> {
                        this.lOpt = lIterator.next()
                        assertIncreasingLeftId(lID)
                        SortedDifferenceChange.left(lElem)
                    }
                }
            } else if (lElem == null && rElem != null) {
                this.rOpt = rIterator.next()
                assertIncreasingRightId(rID(rElem))
                return SortedDifferenceChange.right(rElem)
            } else if (lElem != null && rElem == null) {
                this.lOpt = lIterator.next()
                assertIncreasingLeftId(lID(lElem))
                return SortedDifferenceChange.left(lElem)
            } else {
                throw AssertionError()
            }
        }

        private fun assertIncreasingLeftId(previousId: ID) {
            assert(lOpt?.let { previousId < lID(it) } ?: true, { "" })
        }

        private fun assertIncreasingRightId(previousId: ID) {
            assert(rOpt?.let { previousId < rID(it) } ?: true, { "" })
        }
    }
}

sealed class SortedDifferenceChange<Left, Right> {
    class left<Left, Right>(val left: Left): SortedDifferenceChange<Left, Right>()
    class right<Left, Right>(val right: Right): SortedDifferenceChange<Left, Right>()
    class common<Left, Right>(val left: Left, val right: Right): SortedDifferenceChange<Left, Right>()

    override fun equals(other: Any?): Boolean {
        return (other as? SortedDifferenceChange<*, *>)?.let {
            when (it) {
                is left -> {
                    this is left && this.left == it.left
                }
                is right -> {
                    this is right && this.right == it.right
                }
                is common -> {
                    this is common && this.left == it.left && this.right == it.right
                }
            }
        } ?: false
    }
}