Generating an XML document based on a hierarchy structure

Question

My database table looks like:

Category
  id
  parent_id
  path_url
  name
  sort_order

So a row may look like:

1  NULL  /cars       cars    1
2  1     /cars/honda honda   2

I have all the categories loaded in a List:

   val categories: List[Category] = .....

Now I want to generate an XML representation of this hierarchial structure like:

<root>
  <category id="1" path_url="/cars" name="cars">
     <category id="5" path_url="/cars/honda" name="honda">
        <category id="12" path_url="/cars/honda/accord" name="accord"></category>
        <category id="3" path_url="/cars/honda/civic" name="civic"></category>
     </category>
     <category id="15" path_url="/cars/ford" name="ford">
          <category id="12" path_url="/cars/ford/escort" name="escort"></category>
     </category>
  </category>
  <category id="23423" path_url="/food" name="food>
  ....
  </category>
  ...
</root>

Key points:

The sub-items should be ordered by sort order (INT)

So what seems to be a problem ? I'd probably first create tree of `Category` (which has parent field) objects and then generate `Node`-s from then recursively. I'd envision it as `Category.toXML` method. — expert, Dec 12 '14 at 20:12
@ruslan need some help with the recursion part of it, and new to xml with scala. — Blankman, Dec 12 '14 at 20:28
@CuriousMind I'm using postgresql but I don't want this to be a db specific answer, i'm looking for a scala solution. — Blankman, Dec 21 '14 at 23:39

score 2 · Answer 1 · edited May 23 '17 at 12:17

This is the parent pointer tree data structure. Something like that may help:

import scala.xml._

case class Category(parentId: Int, id: Int, name: String, order: Ordering[Category])

val rootOrder = Ordering.by[Category, String](_.name) //ordering example

def unflatten(c: List[Category])(implicit rootOrder: Ordering[Category]): NodeSeq = <root>{
  unflatten(0, c.groupBy(_.parentId))
}</root>

def unflatten(id: Int, all: Map[Int, List[Category]])(implicit order: Ordering[Category]): NodeSeq = 
  all.get(id).map(_.sorted.map(c => 
     <category id = {c.id.toString} name = {c.name}>{
         unflatten(c.id, all)(c.order) // attaching sub-elements
     }</category>)).getOrElse(Nil) // or nothing

scala> unflatten(List(Category(0, 1, "aaa", rootOrder), Category (1,2, "bbb", rootOrder), Category(0, 3, "aaa", rootOrder)))(rootOrder)
res11: scala.xml.NodeSeq = <root><category id="1" name="aaa"><category id="2" name="bbb"></category></category><category id="3" name="aaa"></category></root>

Ordering should be passed as implicit parameter to the sorted function.

It's not tail recursive, but requires a stack with size equals max nesting levels in your structure - so as you have a whole list of categories in the memory and it fits - stack won't be more than that. If you need something more scalable - it's better to use your DB for unflattening, like CONECT BY in Oracle: http://docs.oracle.com/cd/B19306_01/server.102/b14200/queries003.htm

You can also traverse tree starting from its leafs (it will be tail recursive) using groupBy, something like:

import scala.annotation._

type Cat = Category

case class Node(cat: Cat, children: List[Node]) {
   /** can't be added as implicit because of potential stackoverflow */
   val xml: scala.xml.NodeSeq = <category id = {cat.id.toString} name = {cat.name}>{
       implicit val sort = cat.order.on[Node](_.cat)   
       children.sorted.map(_.xml) // attaching sub-elements
   }</category>
}

@tailrec def unflatten(leafs: List[Node], acc: Map[Int, Node]) : List[Node] = {
    val parents = 
       for((id, children) <- leafs.groupBy(_.cat.parentId);
            p <- acc.get(id)) 
       yield id -> Node(p.cat, (p.children ++ children))
    if (parents.nonEmpty) unflatten(parents.values.toList, acc ++ parents) else all.values.toList.filter(_.cat.parentId == 0)
 }

 def unflatten(cats: List[Cat]): List[Node] = {
     val grouped = cats.groupBy(_.id).mapValues(_.map(Node(_, Nil)).head) //Map[Int, Node]
     val byParent = cats.groupBy(_.parentId)
     val leafs = grouped.filter(x => !byParent.contains(x._1)).values.toList //no children      
     unflatten(leafs, grouped)    
 }

 def unflattenXml(cats: List[Cat])(implicit ord: Ordering[Node] = rootOrder.on(_.cat)) = 
    <root>{unflatten(cats).sorted.map(_.xml)}</root>

scala> unflatten(List(Category(0, 1, "aaa", rootOrder), Category (1,2, "bbb", rootOrder), Category(0, 3, "aaa", rootOrder)))
res15: List[Node] = 
List(Node(Category(0,1,aaa,scala.math.Ordering$$anon$9@2412c5e9),
       List(Node(Category(1,2,bbb,scala.math.Ordering$$anon$9@2412c5e9),List()))), 
     Node(Category(0,3,aaa,scala.math.Ordering$$anon$9@2412c5e9),List()))

scala> unflattenXml(List(Category(0, 1, "aaa", rootOrder), Category (1,2, "bbb", rootOrder), Category(0, 3, "aaa", rootOrder)))
res29: scala.xml.Elem = <root><category id="1" name="aaa"><category id="2" name="bbb"></category></category><category id="3" name="aaa"></category></root>

If you're looking for sources:

Generating an XML document based on a hierarchy structure

1 Answers1