[xquery-talk] Building a tree from sequence of maps

[Michael Kay]

Start with a function that gets the children of an item:

declare variable $children := function($item) {return $xml / item[@refid = $item / @id ]};

Decide where to start:

declare variable $root := $xml / item[1];

Now process the items recursively:

declare function local:process-item($item, $get-children) {
  <section> {
     $item / (@*,  $get-children($item) / process-item(.))
  }</section>
};

and put it together like this:

local:process-item($root, $children);

I've deliberately written it this way using XQuery 3.1 higher-order functions to keep the recursion logic separate from the details of how you find the logical children of an item. But in XQuery 1.0 the same logic would work using a fixed function instead of a dynamic one.

A version that detects cycles in the data is a little bit trickier, but still quite doable.

Michael Kay
Saxonica

> On 21 Dec 2019, at 18:14, Andreas Mixich <mixich.andreas at gmail.com> wrote:
> 
> Hi,
> 
> I feel like I try to get a hold on a piece of wet soap with this...
> 
> Background: Atom Syndication has an extension[1], which allows threading of entries. These entries are ordered in a flat sequence, one by one.
> As a result we end up with an Atom feed, that has a bunch of entries, where each entry could have a reference to the ID of another entry, which would then be it's parent.
> No nesting is done.
> 
> A simplified input could look like this:
> 
> declare variable $local:example :=  
> let $xml := <xml>
>   <item id="e1" />
>   <item id="e2" refid="e1" />
>   <item id="e3" refid="e2" />
>   <item id="e4" refid="e2" />
>   <item id="e5" refid="e4" />
>   <item id="e6" />
> </xml>
> 
> The task I want to accomplish is to create an output tree of nested sections, resembling the natural flow of replies:
> 
> <result>
>   <section id="e1">
>     <section id="e2" refid="e1">
>       <section id="e3" refid="e2" />
>       <section id="e4" refid="e2">
>         <section id="e5" refid="e4" />
>       </section>
>     </section>
>   </section>
>   <section id="e6" />
> </result>
> 
> One of the many queries I tried is:
> 
> declare function local:rec($data) {
>   if (empty($data))
>   then ()
>   else (
>          let $current := head($data)
>          let $children := tail($data)[@refid = $current/@id]
>          return (
>                   <section id="{$current/@id}">
>                   { 
>                     $current/*
> (:                  , prof:dump("current: " || $current/@id/data() || " children: " || $children/@id/data() => string-join())
> :)
>                   , for $child in $children
>                     return local:rec($children)
>                   }
>                   </section>
>                   , local:rec(tail($data))
>                 )
>        )
> };
> 
> <result> 
>   { local:rec($local:example/item) } 
> </result>
> 
> Of course, this has not yet any logic, to keep out the already processed items (besides other issues). 
> When I tried that, however, by removing them from the return sequence, I found no way to break out 
> of scope and have that modified return sequence go back to the next recursion.
> 
> Previous example results in this, btw.:
> 
> <section id="e1">
>   <section id="e2"/>
> </section>
> <section id="e2">
>   <section id="e3"/>
>   <section id="e4"/>
>   <section id="e3"/>
>   <section id="e4"/>
> </section>
> <section id="e3"/>
> <section id="e4">
>   <section id="e5"/>
> </section>
> <section id="e5"/>
> <section id="e6"/>
> 
> I can't believe, that there is no super easy way to do it. Any help would be greatly appreciated!
> 
> -- 
> Minden jót, all the best, Alles Gute,
> Andreas Mixich
> _______________________________________________
> talk at x-query.com
> http://x-query.com/mailman/listinfo/talk

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://x-query.com/pipermail/talk/attachments/20191221/837910b7/attachment.html>