convert a list of paths into a tree / published by https://github.com/dacr/code-examples-manager #0973ef6b-9a78-4e2d-a6fb-eb4e710b0283/97461ddca5fc8f0fbad7d6bf124d8ef116098635

algo-paths-to-tree.sc

// summary : convert a list of paths into a tree
// keywords : scala, algorithm, path, tree, node, @testable
// publish : gist
// authors : David Crosson
// license : Apache NON-AI License Version 2.0 (https://raw.githubusercontent.com/non-ai-licenses/non-ai-licenses/main/NON-AI-APACHE2)
// id : 0973ef6b-9a78-4e2d-a6fb-eb4e710b0283
// created-on : 2020-04-07T19:12:57Z
// managed-by : https://github.com/dacr/code-examples-manager
// run-with : scala-cli $file

// ---------------------
//> using scala  "3.2.1"
//> using dep "dev.zio::zio-test:2.0.5"
// ---------------------

import zio.*
import zio.test.*
import zio.test.TestAspect.*

// ----------------------------------------------------------------

object ThatSpec extends ZIOSpecDefault {

  sealed trait Tree[K, T] {
    val key: K
  }

  case class Leaf[K, T](key: K, content: T) extends Tree[K, T]

  case class Node[K, T](key: K, children: Set[Tree[K, T]] = Set.empty) extends Tree[K, T] {
    def isLeaf = children.isEmpty
  }

  /** Build a tree from a list of tuple made of path and content. The path must contain both the node keys and the leaf key.
    *
    * @param pathContentTuples
    *   the list of path/content tuple - <b>all path must at least contain one key</b>
    * @param rootKey
    *   the key used for the tree root
    * @tparam K
    *   the data type used for node key
    * @tparam T
    *   the data type used for content
    * @return
    *   the built tree
    * @author
    *   David Crosson
    */
  def pathsToTree[K, T](pathContentTuples: List[(List[K], T)], rootKey: K): Tree[K, T] = {
    def worker(PathContentTuples: List[(List[K], T)], currentKey: K): Tree[K, T] = {
      PathContentTuples.partition { case (path, _) => path.size == 1 } match {
        case (leafPaths, nodePaths) =>
          val nodeChildren: List[Tree[K, T]] =
            nodePaths
              .groupBy { case (path, _) => path.head }
              .map { case (key, subpaths) => key -> subpaths.map { case (path, item) => path.tail -> item } }
              .map { case (key, subpaths) => worker(subpaths, key) }
              .toList
          val leafChildren: List[Tree[K, T]] = leafPaths.collect { case (key :: Nil, item) => Leaf(key, item) }
          Node(currentKey, children = nodeChildren.toSet ++ leafChildren)
      }
    }

    worker(pathContentTuples, rootKey)
  }

  /** Build the list of all possible path and content tuples from a tree
    *
    * @param tree
    *   the tree to walk though in order to be build possible paths
    * @param ignoreRootKey
    *   do not insert the root key on generated paths
    * @tparam K
    *   the data type used for node key
    * @tparam T
    *   the data type used for content
    * @return
    *   the built list of path/content tuples
    * @author
    *   David Crosson
    */
  def treeToPaths[K, T](tree: Tree[K, T], ignoreRootKey: Boolean = true): List[(List[K], T)] = {
    def worker(subtrees: List[Tree[K, T]], currentPath: List[K]): List[(List[K], T)] = {
      subtrees.flatMap {
        case Leaf(key, content)  => List((key :: currentPath).reverse -> content)
        case Node(key, children) => worker(children.toList, key :: currentPath)
      }
    }

    tree match {
      case Leaf(key, content)  => List((key :: Nil) -> content)
      case Node(key, children) => worker(children.toList, if (ignoreRootKey) Nil else key :: Nil)
    }
  }

  def spec = suite("paths and trees test")(
    // -------------------------------------------------
    test("just a leaf") {
      val paths = List((1 :: Nil) -> "A")
      val tree  = Node(0, Set(Leaf(1, "A")))
      assertTrue(
        pathsToTree(paths, 0) == tree,
        treeToPaths(tree) == paths
      )
    },
    // -------------------------------------------------
    test("one path to tree") {
      val paths = List(
        (1 :: 1 :: 1 :: Nil) -> "A"
      )
      val tree  = Node(0, Set(Node(1, Set(Node(1, Set(Leaf(1, "A")))))))
      assertTrue(
        pathsToTree(paths, 0) == tree,
        treeToPaths(tree) == paths
      )
    },
    // -------------------------------------------------
    test("fixed size paths to tree") {
      val paths = List(
        (1 :: 1 :: Nil) -> "A",
        (1 :: 2 :: Nil) -> "B"
      )
      val tree  = Node("root", Set(Node(1, Set(Leaf(1, "A"), Leaf(2, "B")))))
      assertTrue(
        pathsToTree(paths, "root") == tree,
        treeToPaths(tree) == paths
      )
    }
  ) @@ sequential @@ timed
}

ThatSpec.main(Array.empty)