CODEWITHSUNDEEP
scalarecursionrelation
Mark Grey
Mark Grey

Reputation: 10257

Recursively process list of relations

Given the following data model, where elements record their relations to ancestors by a delimited string path:

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

What would be a good way to process the relationship into a nested structure such as:

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

The desired function would output a list of Entity2s that nest their children. The elements themselves would therefore be the root nodes. We can assume the input list is sorted lexigraphically by the value of parentId and a None is considered earlier than a list, exactly as test is above.

Example desired output:

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

I've had a few tries at it but what's tripping me up is finding a good way to invert the relationship as you go... recursing the Entity classes gives you the backward (my parent/ancestors is/are) reference whereas the desired output records the forward (my children are) reference. Thanks!

Upvotes: 0

Views: 351

Answers (2)

wmmeyer
wmmeyer

Reputation: 466

One straight-forward solution looks like:

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

If your trees are very deep you will blow the stack - trampolines are a good solution:

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

Upvotes: 1

JimN
JimN

Reputation: 3150

Start with an empty list, and incrementally build this up by adding one entity at a time to it. Each time you add an entity, you have to inspect its ancestor path, and then traverse the corresponding path in the new list to insert the entity in the correct location. The destination list is really a tree structure, since you have nested components; you just need to find the correct location in the tree to insert into.

It will be more efficient if you use maps instead of lists, but should be possible either way. You may find it easier to build the results if you use mutable structures, but should be possible either way as well.

Upvotes: 0

Related Questions