https://kotlinlang.org logo
#getting-started
Title
# getting-started
j

james

02/11/2022, 7:56 AM
I am trying to understand how I can rebuild a tree from a flat list which is given to me by an API. My model is simple:
data class Reply(id: Int, parentId: Int, replies: List<Reply>)
... and I'm attempting to:
Copy code
{
    "replies": [
        { id: 1, parent: 0 }  <- turn this     1
        { id: 2, parent: 1 }     into this ->  └── 2
        { id: 3, parent: 2 }                       ├── 3
        { id: 4, parent: 3 }                       │   └── 4
        { id: 5, parent: 2 }                       ├── 5
        { id: 6, parent: 2 }                       ├── 6
        { id: 7, parent: 2 }                       └── 7
    ]
}
does anyone have any experience in "unflattening" a list into a tree like this? I start out by using
associateBy
on my flat list and turn it into a mutable map, at which point I iterate the flat list itself and append the current item to any value in the map whose
id
matches the current iterator item's
parentId
. doing this I end up with a list where the first and second levels are correct, but third and deeper are empty I've spent about 10 hours on this over the past 3 days and I've really gotten nowhere, just going in circles really. would love some guidance from anyone who has done this kind of thing with Kotlin
👍 1
j

Joffrey

02/11/2022, 9:23 AM
The idea of the map is good, because you need to access any node in your tree by id. Then you can define the node of trees with a mutable list of children so you can append to it. Also I'd suggest using
null
instead of 0 to signify "no parent". Can there be multiple roots (parent=0) in your input?
One way to do it considering multiple top-level replies:
Copy code
// the input type with just id and parent
data class RawReply(val id: Int, val parent: Int)

// the target type, representing nodes of the tree
data class Reply(val id: Int, val parent: Int, val replies: List<Reply>)

// an intermediate private type, to enable building the tree
private class ReplyBuilder(
    val id: Int,
    val parent: Int,
    val children: MutableList<ReplyBuilder> = mutableListOf()
) {
    fun build(): Reply = Reply(
        id = id,
        parent = parent,
        replies = children.map { it.build() },
    )
}

fun List<RawReply>.toReplyTree(): List<Reply> {
    val repliesById = associate { it.id to ReplyBuilder(it.id, it.parent) }

    val roots = mutableListOf<ReplyBuilder>()

    repliesById.values.forEach {
        if (it.parent == 0) { // consider using null for "no parent", it's clearer
            roots.add(it)
        } else {
            val parent = repliesById[it.parent] ?: error("Unknown parent reply ${it.parent}")
            parent.children.add(it)
        }
    }
    return roots.map { it.build() }
}
🙌 1
r

Roukanken

02/11/2022, 9:38 AM
ye basically this ^ Idea is simple, you create a map of id -> mutable list of children and then for each entry in replies you add it to correct place (you know it's parent id, so you know in which list of children it belongs) and then you clean it up so you have nice data class
m

Michael de Kaste

02/11/2022, 10:06 AM
I'd do it the following way: declare an val-only interface with the values you've shown before:
Copy code
interface Reply {
    val id: Int
    val parentId: Int?
    val replies: List<Reply>
}
then in the API you get the following data class:
Copy code
data class ReplyImpl(
    override val id: Int,
    override val parentId: Int?,
    override val replies: MutableList<ReplyImpl> = mutableListOf()
) : Reply
now lets say you have the following list of ReplyImpls:
Copy code
val replies = listOf(
        ReplyImpl(1, null),
        ReplyImpl(2, 1),
        ReplyImpl(3, 2),
        ReplyImpl(4, 3),
        ReplyImpl(5, 2),
        ReplyImpl(6, 2),
        ReplyImpl(7, 2)
    )
we can now associate them by their ID to provide a lookup table and loop through all the replies and add yourself to the parent list like so:
Copy code
val repliesMap = replies.associateBy { it.id }
    var root: Reply? = null
    for (reply in replies) {
        if (reply.parentId != null) {
            repliesMap[reply.parentId]!!.replies.add(reply)
        } else {
            root = reply
        }
    }
printing the root afterwards gives (after some tidying)
Copy code
ReplyImpl(id=1, parentId=null, replies=[
	ReplyImpl(id=2, parentId=1, replies=[
		ReplyImpl(id=3, parentId=2, replies=[
			ReplyImpl(id=4, parentId=3, replies=[])
		]), 
		ReplyImpl(id=5, parentId=2, replies=[]), 
		ReplyImpl(id=6, parentId=2, replies=[]), 
		ReplyImpl(id=7, parentId=2, replies=[])
	])
])
🙌 1
you can also not declare an interface at all, but then you'd be communicating away a reply that's mutable.
e

ephemient

02/11/2022, 11:07 AM
you could also build the reverse mapping, which will make everything easy (as long as there are no cycles)
Copy code
val childrenByParentId = input.groupBy { it.parent }
fun getById(id: Int): Reply {
    val children = childrenByParentId[id]
        ?.map { getById(it.id) }
        .orEmpty()
    return Reply(id, children)
}
val root = input.singleOrNull { it.parent = 0 }
    ?.let { getById(it.id) }
j

Joffrey

02/11/2022, 11:28 AM
Yep, that works if you don't need to remember the parent in the
Reply
type
j

james

02/11/2022, 11:45 AM
you are all brilliant, thank you! an intermediate class was the key to it.. I just went back and tested some of the methods I had built previously and realised 2 of them worked with using a builder pattern, like Joffrey suggested. thank you all again. I don't feel quite so stupid now that I realise how close my solutions were, but I'm not sure how many days or weeks I would have continued going around in circles without your assistance 🙏
m

Michael de Kaste

02/11/2022, 2:57 PM
Never feel stupid for learning!
e

ephemient

02/11/2022, 4:29 PM
if you need the parent ID, or even the whole original reply object, that wouldn't be hard to set up with the reverse mapping. the only thing that it really doesn't handle is cycles, for which you need some mutability to build up piece-wise