CODEWITHSUNDEEP
sortingkotlinparent-child
muetzenflo
muetzenflo

Reputation: 5682

Kotlin - sort list of objects by their id and parentId

I have a data class with a mandatory id, and an optional parentId.

Considering the following UnitTest, how would I implement this? I found many examples on google and SO in different languages with different outputs, but none of the matched my requirements. What I want is basiacally a flat list that has the comments ordered "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)
        )

    }
}

Upvotes: 1

Views: 1292

Answers (1)

flakes
flakes

Reputation: 23624

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)

This is a basic topological sort. I would start by sorting the list by the parentId followed by the id and then making a map of parentId to children 

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

This gives you:

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

If I want to find all the children of a parent I can do:

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

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

If I want to find the children of id=4 I would need to do it again.

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

Looking at this pattern, I can turn this into a recursive function pretty easily:

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

And to print the whole set by following the root parentId:

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

Which gives:

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)

Upvotes: 4

Related Questions