james
02/11/2022, 7:56 AMdata class Reply(id: Int, parentId: Int, replies: List<Reply>)
... and I'm attempting to:
{
"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 KotlinJoffrey
02/11/2022, 9:23 AMnull
instead of 0 to signify "no parent".
Can there be multiple roots (parent=0) in your input?// 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() }
}
Roukanken
02/11/2022, 9:38 AMMichael de Kaste
02/11/2022, 10:06 AMinterface Reply {
val id: Int
val parentId: Int?
val replies: List<Reply>
}
then in the API you get the following data class:
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:
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:
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)
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=[])
])
])
ephemient
02/11/2022, 11:07 AMval 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) }
Joffrey
02/11/2022, 11:28 AMReply
typejames
02/11/2022, 11:45 AMMichael de Kaste
02/11/2022, 2:57 PMephemient
02/11/2022, 4:29 PM