I am attempting to flatten and unflatten a tree structure to enable me to persist the tree structure within an sqlite database.

the tree structure is not in my control.

the tree can contain nodes that are have no children, nodes that have multiple children and nodes that have multiple children with children.

for example

A
B -> C
D -> E -> F
G
H ->  I
      |
      -> J
      |
      -> K
L ->  M
      |
      -> N
         |
          -> O
         |
          -> P
         |
          -> Q

In the above example A has no children B has one child C D has two children E & F G has no children H has one child I & two grandchildren J & K I has two children J & K L has one child I & one grandchild N & three great grandchildren O, P, Q

each entry in the tree is persisted in my data base as a single row

@Entity(
    tableName = "tree_data_table",
    indices = [
        Index(value = ["id", "parent_id"], unique = false),
        Index(value = ["id"], unique = false),
    ]
)
data class TreeDataDO(
    @ColumnInfo(name = "id") val id: String,
    @ColumnInfo(name = "is_leaf") val isLeaf: Boolean,
    @ColumnInfo(name = "name") val name: String,
    @ColumnInfo(name = "parent_id") val parentId: String?
) {
    @PrimaryKey(autoGenerate = true)
    @ColumnInfo(name = "tree_data_local_id")
    var treeDataLocalId: Long = 0L
}

I would like to transform the above tree in the following map

{A=[], B=[C], D=[E, F], G=[], H=[I, J, K], L=[M, N, O, P, Q]}

The closest I have got is this

rows.map { (if (it.parentId == null) it.id else it.parentId) to TREE_DATA_UI_MAPPER.map(it) }.groupBy({ it.first }, { it.second })

however this "solution" gives the following map

{A=[], B=[C], D=[E, F], G=[], H=[I], I=[J, K], L=[M], N=[O, P, Q]}

what am i missing? how can i achieve the desired map for the list of distinct rows?

CodePudding user response：

Assume you have an item, like this

Item(val id: String, val parentId; String?)

And what you want is to get this structure:

Map<String, List<Item>>()

where you will have a list of all children of parent items (or top items, where parentId == null).

I think it can be achieved with code like this:

private val items: List<Item> = ...

fun map(): Map<String, List<Item>> {
    val result = Map<String, List<Item>>()
    val topItems = items.filter { it.parentId == null }
    topItems.forEach {
        val ancestors = mutableListOf<Item>()
        getAllAncestors(it.id, ancestors)
        result[it.id] = ancestors
    }
    return result
}

fun getAllAncestors(itemId: String, into: MutableList<Item>) {
    items.forEach {
        if (itemId == it.parentId) {
            into.add(it)
            into.addAll(getAllAncestors(it.id, into))
        }
    }
}