时间戳

首页 > 解决方案 > Kotlin - 按 id 和 parentId 对对象列表进行排序

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

问题描述

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

考虑到以下 UnitTest，我将如何实现它？我在 google 和 SO 上找到了许多不同语言的示例，输出不同，但没有一个符合我的要求。我想要的基本上是一个平面列表，其中的评论排序为“深度优先”。

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)
        )

    }
}

标签： sortingkotlinparent-child

解决方案

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)]

如果我想找到父母的所有孩子，我可以这样做：

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)

推荐阅读