CODEWITHSUNDEEP
scala
user5069994
user5069994

Reputation: 33

Extract all root-to-leaf paths in a general tree in Scala

My tree object:

    private[package] object Tree {

      /** A node in a  Tree. */
      class Node[T](val parent: Node[T]) extends Serializable {
        var item: T = _
        var count: Long = 0L
        val children: mutable.Map[T, Node[T]] = mutable.Map.empty

        def isRoot: Boolean = parent == null
      }

      /** Attribute in a tree */
      private class Attribute [T] extends Serializable {
        var count: Long = 0L
        val nodes: ListBuffer[Node[T]] = ListBuffer.empty
      }
    }

And the class:

    private[package] class Tree[T] extends Serializable {
      import Tree._
      val root: Node[T] = new Node(null)
      private val attributes: mutable.Map[T, Attribute[T]] = mutable.Map.empty

    def extract(
       minCount: Long,
       validateSuffix: T => Boolean = _ => true): Iterator[(List[T], Long)] = {
          //missing code
      }

Function extract must produce an Iterator[List[T]] which includes paths root-to-leaf. The path is valid if the count of each node is more than minCount.

EDIT: this is my try:

 def extract(minCount: Long, validateSuffix: T => Boolean = _ => true): Iterator[(List[T], Long)] = {

    def traverse(node: Node[T], path: List[T]): Iterator[(List[T], Long)] = {
      path.::(node.item)
      node.children.iterator.flatMap { case (item, child) =>
        traverse(child, path).map { case (t, c) =>
          (item :: t, c)
        }
      } ++ {
          if (node.children.isEmpty && node.count >= minCount) {
            Iterator.single((path, node.count))
          } else {
            Iterator.empty
          }
        }
    }
    traverse(root, List.empty)

EDIT: That's how I build a tree:

    val tree = new Tree[String]
      .add(Seq("a", "b", "c"))
      .add(Seq("a", "b", "y"))
      .add(Seq("a", "b"))
      .add(Seq("a"))
      .add(Seq("b"))
      .add(Seq("b", "n"))

    val paths = tree.extract(3L).map { case (items, count) =>
      (items.toSet, count)
    }.toSet

Upvotes: 0

Views: 1185

Answers (1)

qed
qed

Reputation: 23154

This does it:

import scala.collection.mutable.ArrayBuffer
import scala.reflect.ClassTag

/**
  * Created by IDEA on 2/26/16.
  */
class Tree[T:ClassTag](val value: T, val children: List[Tree[T]]) {
  def paths = {
    val pathsBuffer = new ArrayBuffer[Array[T]]()
    val pathBuffer = new ArrayBuffer[T]()
    def helper(tree: Tree[T]): Unit = {
      if (tree != null) {
        pathBuffer.append(tree.value)
        if (!tree.children.isEmpty) {
          tree.children.foreach {
            t => helper(t)
          }
        } else {
          pathsBuffer.append(pathBuffer.toArray)
        }
        pathBuffer.remove(pathBuffer.length - 1)
      }
    }
    helper(this)
    pathsBuffer.toArray
  }
}

object Tree {
  def makeTree: Tree[Int] = {
    new Tree[Int](
      1,
      List(
        new Tree[Int](
          2,
          List.empty[Tree[Int]]
        ),
        new Tree[Int](
          3,
          List(
            new Tree[Int](
              5,
              List.empty
            ),
            new Tree[Int](
              6,
              List.empty
            )
          )
        ),
        new Tree[Int](
          4,
          List(
            new Tree[Int](
              7,
              List.empty
            ),
            new Tree[Int](
              8,
              List.empty
            )
          )
        )
      )
    )
  }
}

object TestTree extends App {
  val t = Tree.makeTree
  println(t.paths.map(_.toList).toList)
}

The paths method returns an array of paths, each path is an array of values.

Upvotes: 1

Related Questions