如果我知道節點及其父母，如何構建樹？

Question

說我已經得到了一些節點和他們的父母直接，如：

case class Mapping(name: String, parents: Seq[String] = Nil) 

val mappings = Seq(
    Mapping("aaa"), 
    Mapping("bbb"), 
    Mapping("ccc"), 
    Mapping("ddd", Seq("aaa", "bbb")), 
    Mapping("eee", Seq("ccc")), 
    Mapping("fff", Seq("ddd")), 
    Mapping("ggg", Seq("aaa", "fff")), 
    Mapping("hhh") 
) 

如何寫Scala中的一個功能，將建立基於這些樹？

def buildTrees(data: Seq[Mapping]): Seq[Node] = ??? 

case class Node(name: String, children: Seq[Node] = Nil) 

val trees = buildTrees(mappings) 

private val expectedTree = Seq(
    Node("aaa", Seq(
    Node("ggg"), 
    Node("ddd", Seq(
     Node("fff", Seq(
     Node("ggg") 
    )))) 
)), 
    Node("bbb", Seq(
    Node("ddd", Seq(
     Node("fff", Seq(
     Node("ggg") 
    )))) 
)), 
    Node("ccc", Seq(
    Node("eee") 
)), 
    Node("hhh", Seq()) 
) 

if (trees == expectedTree) { 
    println("OK") 
} else { 
    println("Not equal") 
} 

如何實施buildTrees方法？我想了一會兒，但可以得到一個優雅的解決方案。

---

更新：希望看到一成不變的數據

Answer 1

def buildTrees(data: Seq[Mapping]): Seq[Node] = { 
    def attachToParents(newChild: Mapping, parents: Seq[Node]): Seq[Node] = { 
    for (parent <- parents) yield { 
     val attachedChildren = attachToParents(newChild, parent.children) 
     if (newChild.parents.contains(parent.name)) 
     parent.copy(children = Node(newChild.name) +: attachedChildren) 
     else 
     parent.copy(children = attachedChildren) 
    } 
    } 

    @tailrec 
    def helper(xs: Seq[Mapping], accu: Seq[Node]): Seq[Node] = xs match { 
    case Seq() => accu 
    case head +: tail => head match { 
     case Mapping(name, Seq()) => helper(tail, accu :+ Node(name)) 
     case Mapping(name, parents) => helper(tail, attachToParents(head, accu)) 
    } 
    } 
    helper(data, Seq()) 
} 

Answer 2

解決又一實現其功能是：

• 高效
• 棧 - 不溢出
• 純函數

。

import scala.collection.immutable.Queue 

class CyclicReferences(val nodes: Seq[String]) 
    extends RuntimeException(f"elements withing cycle detected: ${nodes mkString ","}") 

def buildTrees(data: Seq[Mapping]): Seq[Node] = { 
    val parents = data.map(m => (m.name, m.parents)).toMap withDefaultValue Seq.empty 
    val children = data.flatMap(m => m.parents map ((_, m.name))).groupBy(_._1).mapValues(_.map(_._2)) 

    def loop(queue: Queue[String], unresolved: Map[String, Set[String]], nodes: Map[String, Node]): TraversableOnce[Node] = queue match { 
    case Seq() => if (unresolved.isEmpty) nodes.values else throw new CyclicReferences(unresolved.keys.toSeq) 
    case key +: rest => 
     val (newQueue, newUnresolved) = ((rest, unresolved) /: parents(key)) { (pair, parent) => 
     val (queue, children) = pair 
     val ch = children(parent) - key 
     if (ch.isEmpty) (queue :+ parent, children - parent) 
     else (queue, children.updated(parent, ch)) 
     } 
     val node = Node(key, children.getOrElse(key, Seq.empty) map nodes) 
     loop(newQueue, newUnresolved, nodes + (key -> node)) 
    } 
    val initial = Queue(parents.keys.filter(key => !children.contains(key)).toSeq: _*) 
    val unresolved = children mapValues (_.toSet) withDefaultValue Set.empty 
    loop(initial, unresolved, Map()).filter(node => parents(node.name).isEmpty).toIndexedSeq 
} 

與瀉肺的解決方案主要區別是：

• 每個節點建設只有一次，他所有的孩子已經 後已建成，即沒有copy呼叫
• 檢測循環引用
• 所有發現均通過高效Map和Set操作實施

所以它可能不是最簡單但50％的生產準備。