CODEWITHSUNDEEP
xmlscalacollections
Michael
Michael

Reputation: 42050

Transforming XML to a list of Elements in Scala

This is a follow-up to my previous question. I would like to linearize an XML tree eagerly (not lazy). I assume for simplicity that an XML tree is a tree of Elem nodes, so I am transforming an XML to a sequence of Elem.

import scala.xml.{Elem, Node}
import PartialFunction._

def linearize(node: Node): List[Node] = {
  val children = node.child.filter(cond(_) {case _: Elem => true}).toList
  children match {
    case Nil => List(node)
    case list => node :: list.flatMap(linearize)
  }
}

It seems working but I don't like that val children = ... How would you suggest change/fix it?

Upvotes: 0

Views: 546

Answers (2)

Ionuț G. Stan
Ionuț G. Stan

Reputation: 179098

You can traverse the tree in both depth-first and breath-first fashion. I've created functions for these two modes. Both are tail-recursive so you can save some stack frames at the expense of heap.

import scala.xml.{ Elem, Node }

def linearizeDepthFirst(node: Node): List[Node] = {
  @annotation.tailrec
  def loop(toVisit: Vector[Node], result: Vector[Node]): List[Node] = {
    if (toVisit.isEmpty) {
      result.toList
    } else {
      val children = toVisit.head.collect({ case e: Elem => e }).toVector
      loop(children ++ toVisit.tail, result ++ children)
    }
  }

  loop(Vector(node), Vector(node))
}

def linearizeBreadthFirst(node: Node): List[Node] = {
  @annotation.tailrec
  def loop(toVisit: Vector[Node], result: Vector[Node]): List[Node] = {
    if (toVisit.isEmpty) {
      result.toList
    } else {
      val children = toVisit.head.collect({ case e: Elem => e }).toVector
      loop(toVisit.tail ++ children, result ++ children)
    }
  }

  loop(Vector(node), Vector(node))
}

Upvotes: 1

Johnny Everson
Johnny Everson

Reputation: 8601

Since you are already transforming node.child into List, you don't need to match on it, you can flatMap directly, since it will return Nil in case the child is empty. The following code yields the same result as your solution for a simple test case.

import scala.xml.{Elem, Node}
import PartialFunction._

def linearize(node: Node): List[Node] = {

  node :: node.child.flatMap {
    case e: Elem => linearize(e)
    case _ => Nil
  }.toList

}

Upvotes: 2

Related Questions