transforming sequence of elements to tree

Question

I have a list of elements with information about how deep they are located in an XML tree. The elements at "the bottom," i.e. those elements that occur before an element with a lower depth, contain text.

<input>
    <text n="x" xml:id="a" depth="1"/>
    <div xml:id="b" depth="2"/>
    <div xml:id="c" depth="3"/>
    <p xml:id="e" depth="4">text</p>
    <p xml:id="d" depth="4">text</p>
    <p xml:id="x" depth="4">text</p>
    <div xml:id="f" depth="3"/>
    <lg xml:id="j" depth="4"/>
    <l xml:id="k" depth="5">text</l>
    <l xml:id="l" depth="5">text</l>
    <p xml:id="n" depth="3">text</p>
</input>

I would like to reconstitute this as the XML tree below, in one operation.

<text n="x" xml:id="a" depth="1">
    <div xml:id="b" depth="2">
        <div xml:id="c" depth="3">
            <p xml:id="e" depth="4">text</p>
            <p xml:id="d" depth="4">text</p>
            <p xml:id="x" depth="4">text</p>
        </div>
        <div xml:id="f" depth="3">
            <lg xml:id="j" depth="4">
                <l xml:id="k" depth="5">text</l>
                <l xml:id="l" depth="5">text</l>
            </lg>
        </div>
        <p xml:id="n" depth="3">text</p>
    </div>
</text>

I think I need to start with the elements of the highest depth, i.e. with all elements of depth 5, and then wrap them up in the preceding element of depth 5-1, and so on, but I can't get my head around how to recurse through this.

The @xml:ids are just for reference.

My question is the converse of my earlier stackoverflow question. It resembles this stackoverflow question, but I need to use XQuery.

Answer 1

Build a function that recursively builds the tree. This code is very generic, by changing the local:getLevel($node) function it should work for arbitrary "flattened" trees.

declare function local:getLevel($node as element()) as xs:integer {
  $node/@depth
};

declare function local:buildTree($nodes as element()*) as element()* {
  let $level := local:getLevel($nodes[1])
  (: Process all nodes of current level :)
  for $node in $nodes
  where $level eq local:getLevel($node)

  (: Find next node of current level, if available :)
  let $next := ($node/following-sibling::*[local:getLevel(.) le $level])[1]
  (: All nodes between the current node and the next node on same level are children :)
  let $children := $node/following-sibling::*[$node << . and (not($next) or . << $next)]

  return
    element { name($node) } {
      (: Copy node attributes :)
      $node/@*,
      (: Copy all other subnodes, including text, pi, elements, comments :)
      $node/node(),

      (: If there are children, recursively build the subtree :)
      if ($children)
      then local:buildTree($children)
      else ()
    }
};

let $xml := document {
  <input>
    <text n="x" xml:id="a" depth="1"/>
    <div xml:id="b" depth="2"/>
    <div xml:id="c" depth="3"/>
    <p xml:id="e" depth="4">text</p>
    <p xml:id="d" depth="4">text</p>
    <p xml:id="x" depth="4">text</p>
    <div xml:id="f" depth="3"/>
    <lg xml:id="j" depth="4"/>
    <l xml:id="k" depth="5">text</l>
    <l xml:id="l" depth="5">text</l>
    <p xml:id="n" depth="3">text</p>
  </input>
}

return local:buildTree($xml/input/*)

Hereby I release this code to the public domain.

If your XQuery processor does not support enhanced FLWOR expressions, you need to reorder some of the lines; I omitted the comments:

  for $node in $nodes
  let $level := local:getLevel($nodes[1])
  let $next := ($node/following-sibling::*[local:getLevel(.) le $level])[1]
  let $children := $node/following-sibling::*[$node << . and (not($next) or . << $next)]
  where $level eq local:getLevel($node)

Answer 2

Just to propose another approach - I dont think I've used intersect in anger before!

declare function local:buildTree($nodes,$level)  {
  for $node in $nodes[@depth=$level]
  let $end := $node/following-sibling::*[@depth = $level][1]
  let $rest := 
       if ($end) 
       then $node/following-sibling::*  intersect  $end/preceding-sibling::*
       else $node/following-sibling::*
  return 
    element {$node/name()} {
        $node/@*,
        $node/node(),
        local:buildTree($rest,$level+1)
    }
};
declare function local:buildTree($node) {
       local:buildTree($node/*,1)
};
let $xml := document {
  <input>
    <text n="x" xml:id="a" depth="1"/>
    <div xml:id="b" depth="2"/>
    <div xml:id="c" depth="3"/>
    <p xml:id="e" depth="4">text</p>
    <p xml:id="d" depth="4">text</p>
    <p xml:id="x" depth="4">text</p>
    <div xml:id="f" depth="3"/>
    <lg xml:id="j" depth="4"/>
    <l xml:id="k" depth="5">text</l>
    <l xml:id="l" depth="5">text</l>
    <p xml:id="n" depth="3">text</p>
  </input>
}

return local:buildTree($xml/input)

Answer 3

Here is another version, based on Chris Wallace's approach, but using XQuery 3.0's tumbling window construct, which makes this code slightly simpler.

declare function local:buildTree($nodes,$level)  {
  for tumbling window $node-window in $nodes
  start $start when $start/@depth = $level
  let $rest := fn:tail($node-window)
  return 
    element {$start/fn:name()} {
        $start/@*,
        $start/node(),
        local:buildTree($rest,$level+1)
    }
};
declare function local:buildTree($node) {
       local:buildTree($node/*,1)
};
let $xml := document {
  <input>
    <text n="x" xml:id="a" depth="1"/>
    <div xml:id="b" depth="2"/>
    <div xml:id="c" depth="3"/>
    <p xml:id="e" depth="4">text</p>
    <p xml:id="d" depth="4">text</p>
    <p xml:id="x" depth="4">text</p>
    <div xml:id="f" depth="3"/>
    <lg xml:id="j" depth="4"/>
    <l xml:id="k" depth="5">text</l>
    <l xml:id="l" depth="5">text</l>
    <p xml:id="n" depth="3">text</p>
  </input>
}

return local:buildTree($xml/input)