Kotlin

Question

我有一个数据 class，其中包含一个强制性 ID 和一个可选的 parentId。

考虑到以下单元测试，我将如何实现它？我在 google 和 SO 上找到了许多具有不同输出的不同语言的示例，但是 none 符合我的要求。我想要的基本上是一个平面列表，其中的评论已排序 "depth first".

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 到 children

的映射

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 的所有 children 我可以这样做：

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 的 children，我需要再做一次。

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)

Kotlin - 按对象的 id 和 parentId 对对象列表进行排序

Kotlin - sort list of objects by their id and parentId

sorting

parent-child