sorting - Kotlin-按对象ID和parentId对对象进行排序

Question

我有一个带有强制性ID和可选的parentId的数据类。

考虑以下UnitTest，我将如何实现呢？我在Google和SO上找到了许多示例，它们使用不同的语言并具有不同的输出，但是都没有满足我的要求。我想要的是一个平淡无奇的 list ，其注释按“深度优先”排序。

data class Comment(
    val id: Int,
    val parentId: Int?
)

class SandboxUnitTests {

    @Test
    fun sandboxTest() {

        val comments = listOf(
            Comment(6, 5),
            Comment(4, 1),
            Comment(2, null),
            Comment(1, null),
            Comment(5, null),
            Comment(3, 1),
            Comment(7, 2),
            Comment(8, 4)
        )


        // CODE TO SORT THIS LIST

       // EXPECTED OUTPUT:
       listOf(
            Comment(1, null),
            Comment(3, 1),
            Comment(4, 1),
            Comment(8, 4),

            Comment(2, null),
            Comment(7, 2),

            Comment(5, null),
            Comment(6, 5)
        )

    }
}

Answer 1

TLDR

// Get all of the parent groups
val groups = comments
    .sortedWith(compareBy({ it.parentId }, { it.id }))
    .groupBy { it.parentId }

// Recursively get the children
fun follow(comment: Comment): List<Comment> {
    return listOf(comment) + (groups[comment.id] ?: emptyList()).flatMap(::follow)
}

// Run the follow method on each of the roots
comments.map { it.parentId }
    .subtract(comments.map { it.id })
    .flatMap { groups[it] ?: emptyList() }
    .flatMap(::follow)
    .forEach(System.out::println)

这是基本的拓扑排序。我首先将列表按parentId排序，然后再排序id，然后将parentId映射到子级

val groups = comments
    .sortedWith(compareBy({ it.parentId }, { it.id }))
    .groupBy { it.parentId }

这给您:

null=[
    Comment(id=1, parentId=null),
    Comment(id=2, parentId=null),
    Comment(id=5, parentId=null)
],
1=[
    Comment(id=3, parentId=1),
    Comment(id=4, parentId=1)
], 
2=[Comment(id=7, parentId=2)], 
4=[Comment(id=8, parentId=4)], 
5=[Comment(id=6, parentId=5)]

如果我想找到 parent 的所有 child ，我可以做:

val children = groups.getOrDefault(1, emptyList())
// gives [Comment(id=3, parentId=1), Comment(id=4, parentId=1)]

val noChildren = groups.getOrDefault(123, emptyList())
// gives []

如果我想找到id=4的子级，则需要再次进行。

val children = groups.getOrDefault(1, emptyList())
        .flatMap{ listOf(it) + groups.getOrDefault(it.id, emptyList()) }

查看此模式，我可以很容易地将其转换为递归函数:

fun follow(c: Comment): List<Comment> {
    return listOf(c) + groups.getOrDefault(c.id, emptyList()).flatMap(::follow)
}

并通过跟随根parentId打印整个集合:

groups[null]?.flatMap(::follow)?.forEach(System.out::println)

这使:

Comment(id=1, parentId=null)
Comment(id=3, parentId=1)
Comment(id=4, parentId=1)
Comment(id=8, parentId=4)
Comment(id=2, parentId=null)
Comment(id=7, parentId=2)
Comment(id=5, parentId=null)
Comment(id=6, parentId=5)