Mayer's Diff in Kotlin

gistfile1.txt

sealed class DiffOp {

    data class Insert(val oldPos: Int, val newPos: Int) : DiffOp()
    data class Delete(val oldPos: Int) : DiffOp()

}

fun <T> diff(list1: MutableList<T>, list2: MutableList<T>, i: Int = 0, j: Int = 0): List<DiffOp> {

    val N = list1.size
    val M = list2.size
    val L = N + M
    val Z = 2 * min(N, M) + 2

    when {
        N > 0 && M > 0 -> {
            val w = N - M
            val g = ArrayList<Int>(Z).also {
                for (x in 0 until Z) {
                    it.add(0)
                }
            }
            val p = ArrayList<Int>(Z).also {
                for (x in 0 until Z) {
                    it.add(0)
                }
            }
            for (h in 0..(L / 2 + if (L % 2 != 0) 1 else 0) + 1) {
                for (r in 0..2) {
                    val (c, d, o, m) = if (r == 0) Tuple4(g, p, 1, 1) else Tuple4(p, g, 0, -1)
                    for (k in (-(h - 2 * max(0, h - M))..(h - 2 * max(0, h - N) + 1)) step 2) {
                        var a = if (k == -h or k != h and c.cyclicAt((k - 1) % Z) < c.cyclicAt(k + 1 % Z))
                            c.cyclicAt((k + 1) % Z)
                        else
                            c.cyclicAt((k - 1) % Z) + 1
                        var b = a - k
                        val s = a
                        val t = b
                        while (a < N && b < M &&
                                list1.cyclicAt((1 - o) * N + m * a + (o - 1)) == list2.cyclicAt((1 - o) * M + m * b + (o - 1))) {
                            a += 1
                            b += 1
                        }
                        c.cyclicSet(k % Z, a)
                        val z = -(k - w)
                        if (L % 2 == o && z >= -(h - o) && z <= h - o && c.cyclicAt(k % Z) + d.cyclicAt(z % Z) >= N) {
                            val (D, x, y, u, v) = if (o == 1)
                                Tuple5(2 * h - 1, s, t, a, b)
                            else
                                Tuple5(2 * h, N - a, M - b, N - s, M - t)
                            return when {
                                D > 1 || x != u && y != v -> diff(
                                        list1.subList(0, x),
                                        list2.subList(0, y), i, j) +
                                        diff(
                                                list1.subList(u, N),
                                                list2.subList(v, M), i + u, j + v)
                                M > N -> diff(mutableListOf(), list2.subList(N, M), i + N, j + N)
                                M < N -> diff(list1.subList(M, N), mutableListOf(), i + M, j + M)
                                else -> emptyList()
                            }
                        }
                    }
                }
            }
        }
        N > 0 -> return (0..N).map { n ->
            DiffOp.Delete(i + n)
        }
        else -> return (0..M).map { n ->
            DiffOp.Insert(i, j + n)
        }
    }

    return emptyList()

}