CODEWITHSUNDEEP
scalatree
Freewind
Freewind

Reputation: 198218

How to build the tree if I know nodes and their parents?

Say I've gotten some nodes and their direct parents, like:

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")
)

How to write a function in Scala, that will build a tree based on them?

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")
}

How to implement the buildTrees method? I've thought for a while, but can get a elegant solution.

Update: hope to see a solution with immutable data

Upvotes: 0

Views: 1733

Answers (2)

xiefei
xiefei

Reputation: 6599

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())
}

Upvotes: 1

Odomontois
Odomontois

Reputation: 16308

Yet another implementation which is:

  • efficient
  • stack-not-overflowing
  • pure functional

.

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
}

Main differences with xiefei's solution is:

  • Each node is constructing only one time, after all his children have been already constructed, i.e. no copy call
  • Detecting circular references
  • All discoveries are implemented via efficient Map and Set operations

So it maybe not the simpliest but 50% production ready.

Upvotes: 4

Related Questions