TopSort.kt

/**
 * Topological sort of a dependency graph.
 */
object TopSort {

    fun <T : Any> parentsFirst(objects: Set<T>, isFirstChildOfSecond: (T, T) -> Boolean): List<T> =
        childrenFirst(objects, isFirstChildOfSecond).reversed()

    fun <T : Any> childrenFirst(objects: Set<T>, isFirstChildOfSecond: (T, T) -> Boolean): List<T> {
        val childToParents = HashMap<T, MutableList<T>>()
        val childCount = objects.associateWithTo(HashMap()) { 0 }

        for (type1 in objects) {
            for (type2 in objects) {
                if (type1 === type2) continue
                if (isFirstChildOfSecond(type2, type1)) {
                    childToParents.computeIfAbsent(type2) { mutableListOf() } += type1
                    childCount.compute(type1) { _, count -> count?.let { it + 1 } ?: 1 }
                }
            }
        }

        val queue = LinkedList(childCount.filterValues { it == 0 }.keys)
        val out = mutableListOf<T>()

        while (!queue.isEmpty()) {
            val obj = queue.poll()
            out += obj
            val parents = childToParents.getOrDefault(obj, listOf())
            for (parent in parents) {
                val count = childCount.compute(parent) { _, count ->
                    count?.let { it - 1 }
                }
                if (count == 0) queue.offer(parent)
            }
        }

        require(out.size == objects.size) { cyclicInfoMessage(childToParents) }
        return out
    }

    private fun cyclicInfoMessage(childToParents: Map<*, *>): String =
        "Looks like the graph contains cyclic dependencies:\n" +
            childToParents.entries.withIndex().joinToString(separator = "\n") { (i, e) ->
                "child #$i: ${e.key} -> parents: ${e.value}"
            }
}


// Tests

class TopSortTest {

    open class ParentA : RuntimeException()
    open class ParentB : RuntimeException()
    open class ChildA : ParentA()
    open class ChildB : ParentB()
    open class ChildAA : ChildA()
    open class ChildAAA : ChildAA()
    open class ChildAAAA1 : ChildAAA()
    open class ChildAAAA2 : ChildAAA()

    private val typeset = setOf(
        RuntimeException::class,
        ChildAAA::class,
        ParentB::class,
        ChildAAAA1::class,
        ChildB::class,
        Any::class,
        ChildAA::class,
        ParentA::class,
        Exception::class,
        ChildAAAA2::class,
        ChildA::class,
        Throwable::class
    )

    @Test
    fun testSortChildrenFirst() {
        val sorted = TopSort.childrenFirst(typeset, KClass<*>::isSubclassOf)

        sorted.assertFollowing(
            ChildAAAA2::class,
            ChildAAA::class,
            ChildAA::class,
            ChildA::class,
            ParentA::class,
            RuntimeException::class,
            Exception::class,
            Throwable::class,
            Any::class
        )
        sorted.assertFollowing(
            ChildB::class,
            ParentB::class,
            RuntimeException::class,
            Exception::class,
            Throwable::class,
            Any::class
        )
    }

    @Test
    fun testSortParentsFirst() {
        val sorted = TopSort.parentsFirst(typeset, KClass<*>::isSubclassOf)

        sorted.assertFollowing(
            Any::class,
            Throwable::class,
            Exception::class,
            RuntimeException::class,
            ParentA::class,
            ChildA::class,
            ChildAA::class,
            ChildAAA::class,
            ChildAAAA2::class,
        )
        sorted.assertFollowing(
            Any::class,
            Throwable::class,
            Exception::class,
            RuntimeException::class,
            ParentB::class,
            ChildB::class
        )
    }

    @Test
    fun testCyclic() {
        val e = assertThrows<IllegalArgumentException> {
            TopSort.childrenFirst(
                setOf(RuntimeException(), Throwable(), RuntimeException())
            ) { a, b -> a::class.isSubclassOf(b::class) }
        }

        assertThat(e)
            .hasMessageStartingWith("Looks like the graph contains cyclic dependencies")
    }

    private fun <T> List<T>.assertFollowing(vararg ordered: T) {
        val all = ordered.toList()
        assertThat(this).containsAll(all)
        all.zipWithNext().forEach { (first, second) ->
            assertThat(indexOf(first)).isLessThan(indexOf(second))
        }
    }
}