I have two entities : Item, and ItemWrapper.

1. ItemWrapper includes Items.
2. ItemWrapper can have an ItemWrapper parent reference

For simplicity, Item is a string "a", "b", ... ItemWrapper simply contains those items other ItemWrappers. They also have their own id.

So basically I have an input list like this :

I need to write an efficient kotlin function that take this input and returns :

{ 
  "Wrapper #1" : { 
      childrenWrappers: [
              "Wrapper #3" : { 
                 childrenWrappers: null, 
                 items: w,u 
               },
              "Wrapper #4" : { 
                 childrenWrappers: null, 
                 items: null
               }  
      ], 
      items: a,b,c 
  },
  "Wrapper #2" : { 
      childrenWrappers: null, 
      items: x,y,z
  }
}

The solution can use any data structures or classes, It doesn't have to be in JSON representation (though I will encode it to json for the API transfer)

CodePudding user response：

Assuming your data structure looks like the following:

data class ItemWrapper(
    val id: Int,
    val title: String,
    val items: List<String>,
    val parentId: Int? = null,
)

and your expected result data structure looks like this:

data class ItemWrapperNode(
    val items: List<String>,
    val childrenWrappers: Map<String, ItemWrapperNode>,
)

we can write conversion functions:

fun List<ItemWrapper>.toTree(): Map<String, ItemWrapperNode> =
    groupBy { it.parentId }.childrenOf(null)

fun Map<Int?,List<ItemWrapper>>.childrenOf(parentId: Int?): Map<String, ItemWrapperNode> = 
    get(parentId)
        ?.map { it.title to ItemWrapperNode(it.items, childrenOf(it.id)) }
        ?.toMap() ?: emptyMap()

Then for a list itemWrappers of ItemWrappers you can call itemWrappers.toTree() to obtain the desired output.

If you want to restrict the maximum depth of recursion, we can extend these functions in the following way by introducing an additional parameter maxDepth which is decremented on each recursion step:

fun List<ItemWrapper>.toTree(maxDepth: Int): Map<String, ItemWrapperNode> =
    groupBy { it.parentId }.childrenOf(null, maxDepth)

fun Map<Int?,List<ItemWrapper>>.childrenOf(parentId: Int?, maxDepth: Int): Map<String, ItemWrapperNode> = 
    if(maxDepth <= 0) emptyMap()
    else get(parentId)
        ?.map { it.title to ItemWrapperNode(it.items, childrenOf(it.id, maxDepth - 1)) }
        ?.toMap() ?: emptyMap()

Then, we can for instance write:

    val wrappers = listOf(
        ItemWrapper(1, "ItemWrapper #1", listOf("a")),
        ItemWrapper(2, "ItemWrapper #2", listOf("b")),
        ItemWrapper(3, "ItemWrapper #3", listOf("c"), 1),
        ItemWrapper(4, "ItemWrapper #4", listOf("d"), 1),
    )
    println(wrappers.toTree(0))

This yields an empty map as result. Using a maxDepth of 1 only ItemWrappers #1 and #2 are returned. With maxDepth of 2 or higher we obtain all ItemWrappers.