Kotlin - сортировка списка объектов по их идентификатору и parentId - PullRequest
Новая
       5

Kotlin - сортировка списка объектов по их идентификатору и parentId

1 голос
/ 04 апреля 2020

У меня есть класс данных с обязательным идентификатором и необязательным 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)
        )

    }
}

1 Ответ

2 голосов
/ 04 апреля 2020

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)

Это базовая c топологическая сортировка. Я бы начал с сортировки списка по 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)
}

И распечатать весь набор, следуя root 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)
...