The Binary Search Tree Data Structure–having fun with XPath 3.0

For a long time I have wanted to play with XSLT 3.0 and XPath 3.0. Despite these being in their WD status, the new features are so powerful and overwhelming.

Take just these: Higher Order Functions and the ability to create new anonymous functions in XPath.

In my quest to accomplish what no one has ever done before with XPath I was helped by the existence of an early Saxon implementation – Saxon 9.3.04 offers these in its XQuery 3.0 implementation and the XSLT 3.0 implementation will hopefully be soon fully usable, after fixing a few bugs. The beautifully high-lighted XQuery code below was copied from oXygen 12.1 and pasted onto Word, then to Windows Live Writer.

I decided to start with something not too-complex (are you dreaming of a finger tree written entirely in XPath ?) and the Binary Search tree persistent functional data structure fits well this requirement.

So, let’s start:

As always:

declare namespace tree =http://fxsl.sf.net;

A tree is a sequence (triple) of functions. Here is the definition of an empty tree:

declare functiontree:tree()          as (function() as item()*)+ {    (function() {()},   (: top() :)     function() {()},   (: left() :)     function() {()}    (: right() :)   ) };

The first function produces the top of the tree, which is the value ( item() ) of its top node.

The second function produces the left sub-tree, which is another sequence (triple) of functions.

The third function produces the right sub-tree, which is another sequence (triple) of functions.

Do you see the problem with the type of the tree:tree()  function? What would happen if I accidentally returned only a pair of functions? Nothing! No static or runtime error would occur and I could spend a lot of time trying to find this simple error. Obviously, a tuple datatype would solve this problem completely.

Now, the three functions top(), left() and right() :

declare function  tree:top          ($pTree as (function() as item()*)*)          as item()? {  if(empty($pTree))    then ()    else      $pTree[1]() };   declare function tree:left          ($pTree as (function() as item()*)*)          as (function() as item()*)* {  if(empty($pTree[2]))  then ()  else    $pTree[2]() };     declare function tree:right          ($pTree as (function() as item()*)*)          as (function() as item()*)* {  if(empty($pTree[3]))    then ()    else      $pTree[3]() };

A tree is empty when:

declare function tree:empty          ($pTree as (function() as item()*)*)          as xs:boolean {  empty($pTree) orempty($pTree[1]()) };

When does a tree contain an item?

declare function tree:contains          ($pTree as (function() as item()*)*,           $pItem as item()          )          as xs:boolean {  if(tree:empty($pTree))    then false()    else      let $top := tree:top($pTree)       return          ($pItem eq $top)         or          ($pItem lt $top          and           tree:contains(tree:left($pTree),$pItem)           )         or          ($pItem gt $top          and           tree:contains(tree:right($pTree),$pItem)           ) };

How to add a new node to a tree?

declare function tree:insert          ($pTree as (function() as item()*)*,           $pItem as item()          )          as (function() as item()*)+ {    if(tree:empty($pTree))       then       (        function() {$pItem},   (: top()   :)        function() {tree:tree()},         (: left()  :)        function() {tree:tree()}          (: right() :)        )       else        if($pItem lt tree:top($pTree))          then           (            function() {tree:top($pTree)},            function() {tree:insert(tree:left($pTree), $pItem)},            function() {tree:right($pTree)}            )          else           if($pItem gt tree:top($pTree))            then            (             function() {tree:top($pTree)},             function() {tree:left($pTree)},             function() {tree:insert(tree:right($pTree), $pItem)}            )            else             $pTree };

How to present a tree?

declare function tree:print         ($pTree as (function() as item()*)*)         as element()? {   if(not(tree:empty($pTree)))      then       <treeNode>            <value>{tree:top($pTree)}</value>            {             tree:print(tree:left($pTree)),             tree:print(tree:right($pTree))            }      </treeNode>      else () };

How to atomize a tree (and get a good sorting function as a side effect)?

(: tree:data()   Prints only the data — depth first.    In effect this is sort() — quite good    for random data.  :) declare function tree:data         ($pTree as (function() as item()*)*)         as item()* {    if(not(tree:empty($pTree)))      then      (       tree:data(tree:left($pTree)),       data(tree:top($pTree)),       tree:data(tree:right($pTree))       )      else () };

How to return a subtree and its depth?

declare function tree:findSubtree          ($pTree as (function() as item()*)*,           $pItem as item()          )          as (function() as item()*)* {  if(tree:empty($pTree))    then (tree:tree(), function() as item()* {–1})    else      let $depth := 1,          $top := tree:top($pTree)        return          if($pItem eq $top)            then ($pTree,function() as item()* {$depth})            else              if($pItem lt $top)                then                  let $lsubtree                        := tree:findSubtree(tree:left($pTree),$pItem),                      $ldepth := $lsubtree[4]()                    return                      if($ldepth eq –1)                        then $lsubtree                        else                          (subsequence($lsubtree,1,3),                           function() as item()* {1+$ldepth}                           )                else                  let $rsubtree                        := tree:findSubtree(tree:right($pTree),$pItem),                      $rdepth := $rsubtree[4]()                    return                      if($rdepth eq –1)                        then $rsubtree                        else                          (subsequence($rsubtree,1,3),                           function() as item()* {1+$rdepth}                           ) };

Finally, lets see how all this executes together:

let $vEmptyTree := tree:tree(),     $vFilledTree := tree:insert($vEmptyTree,5)  ,     $vFilledTree2 := tree:insert($vFilledTree,3),       $vFilledTree3 := tree:insert($vFilledTree2,7),     $vFilledTree4 := tree:insert($vFilledTree3,1),     $vFilledTree5 := tree:insert($vFilledTree4,9)     return       (tree:print($vFilledTree5),        ‘ tree:contains($vFilledTree5,1): ‘,        tree:contains($vFilledTree5,1),        ‘ tree:contains($vFilledTree5,9): ‘,        tree:contains($vFilledTree5,9),        ‘ tree:contains($vFilledTree5,2): ‘,        tree:contains($vFilledTree5,2),        ‘ tree:contains($vFilledTree5,11): ‘,        tree:contains($vFilledTree5,11),        ‘ tree:findSubtree($vFilledTree5,9)[4](): ‘,        tree:findSubtree($vFilledTree5,9)[4](),        ‘ tree:findSubtree($vFilledTree5,1)[4](): ‘,        tree:findSubtree($vFilledTree5,1)[4](),        ‘ tree:findSubtree($vFilledTree5,3)[4](): ‘,        tree:findSubtree($vFilledTree5,3)[4](),        ‘ tree:findSubtree($vFilledTree5,7)[4](): ‘,        tree:findSubtree($vFilledTree5,7)[4](),        ‘ tree:findSubtree($vFilledTree5,5)[4](): ‘,        tree:findSubtree($vFilledTree5,5)[4](),        ‘ tree:findSubtree($vFilledTree5,12)[4](): ‘,        tree:findSubtree($vFilledTree5,12)[4](),        ‘ tree:data($vFilledTree5): ‘,        tree:data($vFilledTree5)       )

And the result:

<treeNode>    <value>5</value>    <treeNode>       <value>3</value>       <treeNode>          <value>1</value>       </treeNode>    </treeNode>    <treeNode>       <value>7</value>       <treeNode>          <value>9</value>       </treeNode>    </treeNode> </treeNode> tree:contains($vFilledTree5,1):  true tree:contains($vFilledTree5,9):  true tree:contains($vFilledTree5,2):  false tree:contains($vFilledTree5,11):  false tree:findSubtree($vFilledTree5,9)[4]():  3 tree:findSubtree($vFilledTree5,1)[4]():  3 tree:findSubtree($vFilledTree5,3)[4]():  2 tree:findSubtree($vFilledTree5,7)[4]():  2 tree:findSubtree($vFilledTree5,5)[4]():  1 tree:findSubtree($vFilledTree5,12)[4]():  -1 tree:data($vFilledTree5):  1 3 5 7 9

What next?

As you, my observant reader, probably have noticed, there is no tree:deleteItem() yet. This is a little bit more tricky and will be the topic for my next post.

Summary: A fully functional, persistent functional data structure – the Binary Search Tree has been implemented in pure XPath 3.0. We have observed how the new features of HOF and dynamically created anonymous function items make XPath 3.0 shine and how severely it lacks a simple yet most needed datatype – the tuple – to make our code more elegant and reliable.