递归处理关系列表

Question

给定以下数据模型，其中元素通过带分隔符的字符串路径记录它们与祖先的关系：

case class Entity(id:String, ancestorPath:Option[String] = None)

val a = Entity("a")
val c = Entity("c")
val b = Entity("b", Some("a"))
val d = Entity("d", Some("a/b"))

val test = a :: c :: b :: d :: Nil

将关系处理成嵌套结构的好方法是什么，例如：

case class Entity2(id:String, children:List[Entity])

所需的函数将输出嵌套 children 的 Entity2 列表。因此，元素本身就是根节点。我们可以假设输入列表按 parentId 的值按字典顺序排序，并且 None 被认为早于列表，与上面的 test 完全相同。

示例所需输出：

List(
  Entity2("a", List(
    Entity2("b", List(
      Entity2("d", Nil)
    ),
  ),
  Entity2("c", Nil)
)

我已经尝试了几次，但让我感到困惑的是找到一个很好的方法来反转关系...递归 Entity 类给你倒退(my parent/ancestors is/are) 参考，而所需的输出记录前向 (my children are) 参考。谢谢！

Answer 1

从一个空列表开始，然后通过一次向其中添加一个实体来逐步构建它。每次添加实体时，都必须检查其祖先路径，然后遍历新列表中的相应路径以将实体插入正确的位置。目标列表实际上是一个树结构，因为您有嵌套的组件；您只需要在树中找到要插入的正确位置。

如果使用地图而不是列表，效率会更高，但两种方式都应该可行。如果您使用可变结构，您可能会发现更容易构建结果，但也应该可以使用任何一种方式。

Answer 2

一个直接的解决方案如下：

case class Entity(id:String, ancestorPath:Option[String] = None)
case class Entity2(id:String, children:List[Entity2])

object Main {

  def main(args: Array[String]) {
    val a = Entity("a")
    val c = Entity("c")
    val b = Entity("b", Some("a"))
    val d = Entity("d", Some("a/b"))

    val test = a :: c :: b :: d :: Nil

    println(buildTree(test))
  }

  def immediateParent(path: String) = {
    val pos = path.lastIndexOf('/')
    if (pos == -1) path
    else path.substring(pos+1)
  }

  def buildTree(all: List[Entity]): List[Entity2] = {
    val childEntitiesByParentId = all.groupBy(_.ancestorPath.map(immediateParent _))
    val roots = childEntitiesByParentId.getOrElse(None, Nil)

    roots.map({ root => buildTreeHelper(root, childEntitiesByParentId) })
  }

  def buildTreeHelper(
    parent: Entity,
    childEntitiesByParentId: Map[Option[String], List[Entity]]): Entity2 = {

    val children = childEntitiesByParentId.getOrElse(Some(parent.id), Nil).map({ child =>
      buildTreeHelper(child, childEntitiesByParentId)
    })
    Entity2(parent.id, children)
  }
}

如果你的树很深，你会炸毁堆栈 - 蹦床是一个很好的解决方案：

import scala.util.control.TailCalls

def buildTree(all: List[Entity]): List[Entity2] = {
  val childEntitiesByParentId = all.groupBy(_.ancestorPath.map(immediateParent _))
  val roots = childEntitiesByParentId.getOrElse(None, Nil)

  buildTreeHelper(roots, childEntitiesByParentId).result
}

def buildTreeHelper(
  parents: List[Entity], 
  childEntitiesByParentId: Map[Option[String], List[Entity]]): TailCalls.TailRec[List[Entity2]] = {

  parents match {
    case Nil => TailCalls.done(Nil)
    case parent :: tail =>
      val childEntities = childEntitiesByParentId.getOrElse(Some(parent.id), Nil)
      for {
        children <- TailCalls.tailcall(buildTreeHelper(childEntities, childEntitiesByParentId))
        siblings <- buildTreeHelper(tail, childEntitiesByParentId)
      } yield Entity2(parent.id, children) :: siblings
  }
}

递归处理关系列表

Recursively process list of relations

scala

recursion

relation