﻿<?xml version="1.0" encoding="utf-8"?>
<!--
  (c) 2010 Nesterovsky Bros. 

  An AVL tree (self-balancing binary search tree).
  Lookup, insertion, and deletion all take O(log n) time in both 
  the average and worst cases. Additions and deletions may require 
  the tree to be rebalanced by one or more tree rotations.
  
  The AVL tree is named after its two inventors, G.M. Adelson-Velsky and
  E.M. Landis, who published it in their 1962 paper 
  "An algorithm for the organization of information."
  
  Tree node is constructed with function tree:node().
  Tree navigator is a sequence of nodes, where index 1 corresponds 
  to the most nested node in navigation path, and last() corresponds 
  to the root.
  
  Algorithm assumes following functions:
    tuple:ref($items as item()*) to wrap items into a tuple.
    tuple:deref($tuple as item()?) as item()* to unwrap items from a tuple.
    tuple:is-same($first as item(), $second as item()) as xs:boolean to test 
      whether two tuples are equal.
      
  Compexity estimations are based on assumption that complexity of 
  tuple functions is O(1).
-->
<xsl:stylesheet version="2.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
  xmlns:xs="http://www.w3.org/2001/XMLSchema"
  xmlns:tuple="http://www.nesterovsky-bros.com/xslt/tuple"
  xmlns:tree="http://www.nesterovsky-bros.com/xslt/tree"
  xmlns:p="http://www.nesterovsky-bros.com/xslt/private/tree"
  exclude-result-prefixes="xs tree tuple p">

  <!--
    Creates a tree node.
      $left - optional left node.
      $right - optional right node.
      $value - a node value.
  -->
  <xsl:function name="tree:node" as="item()">
    <xsl:param name="left" as="item()*"/>
    <xsl:param name="right" as="item()*"/>
    <xsl:param name="value" as="item()*"/>

    <xsl:variable name="left-node" as="item()?" select="$left[last()]"/>
    <xsl:variable name="right-node" as="item()?" select="$right[last()]"/>

    <xsl:sequence select="
      tuple:ref
      (
        (
          tree:size($left-node) + tree:size($right-node) + 1,
          (
            if (exists($left-node))  then
              $left-node
            else
              'null'
          ),
          (
            if (exists($right-node))  then
              $right-node
            else
              'null'
          ),
          $value
        )
      )"/>
  </xsl:function>

  <!--
    Gets a left node, if any, for a node.
      $path - a tree path.
      Returns a left node, if any.
  -->
  <xsl:function name="tree:left" as="item()*">
    <xsl:param name="path" as="item()*"/>

    <xsl:variable name="left" as="item()?" 
      select="tuple:deref($path[1])[2]"/>

    <xsl:sequence select="
      if ($left instance of xs:string) then
        ()
      else
        ($left, $path)"/>
  </xsl:function>

  <!--
    Gets a right node, if any, for a node.
      $path - a tree path.
      Returns a right node, if any.
  -->
  <xsl:function name="tree:right" as="item()*">
    <xsl:param name="path" as="item()*"/>

    <xsl:variable name="right" as="item()?"
      select="tuple:deref($path[1])[3]"/>

    <xsl:sequence select="
      if ($right instance of xs:string) then
        ()
      else
        ($right, $path)"/>
  </xsl:function>

  <!--
    Gets a size of subtree, including this node.
      $path - a tree path.
      Returns a size of subtree.
  -->
  <xsl:function name="tree:size" as="xs:integer">
    <xsl:param name="path" as="item()*"/>

    <xsl:sequence select="
      if (exists($path)) then
        tuple:deref($path[1])[1]
      else
        0"/>
  </xsl:function>

  <!--
    Gets a node value.
      $path - a tree path.
      Returns a node value.
  -->
  <xsl:function name="tree:value" as="item()*">
    <xsl:param name="path" as="item()*"/>

    <xsl:sequence select="subsequence(tuple:deref($path[1]), 4)"/>
  </xsl:function>

  <!--
    Creates a tree from a sequence of values.
      $values - values to pupulate nodes (one item for one node). 
      Returns a root path for the tree.
  -->  
  <xsl:function name="tree:create" as="item()?">
    <xsl:param name="values" as="item()*"/>

    <xsl:sequence select="
      tree:create
      (
        $values, 
        (
          for $i in 1 to count($values) return
            1
        )
      )"/>
  </xsl:function>

  <!--
    Creates a tree from a sequence of values.
      $values - values to pupulate nodes. 
      $sizes - sizes of groups of values that form one node.
      Returns a root path for the tree.
  -->
  <xsl:function name="tree:create" as="item()?">
    <xsl:param name="values" as="item()*"/>
    <xsl:param name="sizes" as="xs:integer*"/>

    <xsl:sequence select="p:create($values, $sizes, 1, 1, count($sizes))[2]"/>
  </xsl:function>

  <!--
    Gets an index of the node in the tree.
      $path - an tree path.
      Returns a node index.
  -->
  <xsl:function name="tree:index" as="xs:integer">
    <xsl:param name="path" as="item()*"/>

    <xsl:variable name="index" as="xs:integer*">
      <xsl:for-each select="$path">
        <xsl:variable name="index" as="xs:integer" select="position()"/>
        <xsl:variable name="left" as="item()?" 
          select="tree:left($path[$index + 1])[1]"/>

        <xsl:if test="not(tuple:is-same($left, .))">
          <xsl:sequence select="tree:size($left) + 1"/>
        </xsl:if>
      </xsl:for-each>
    </xsl:variable>

    <xsl:sequence select="sum($index)"/>
  </xsl:function>

  <!--
    Gets a path to the leftmost node in a subtree.
      $path - a tree path.
      Returns a path to the leftmost node in a subtree.
  -->
  <xsl:function name="tree:leftmost" as="item()*">
    <xsl:param name="path" as="item()*"/>

    <xsl:variable name="left" as="item()*" select="tree:left($path)"/>
    
    <xsl:sequence select="
      if (empty($left)) then
        $path
      else
        tree:leftmost($left)"/>
  </xsl:function>

  <!--
    Gets a path to the rightmost node in a subtree.
      $path - a tree path.
      Returns a path to then rightmost node in a subtree.
  -->
  <xsl:function name="tree:rightmost" as="item()*">
    <xsl:param name="path" as="item()*"/>

    <xsl:variable name="right" as="item()*" select="tree:right($path)"/>

    <xsl:sequence select="
      if (empty($right)) then
        $path
      else
        tree:rightmost($right)"/>
  </xsl:function>

  <!--
    Gets a predecessor path for a specified tree path.
      $path - a tree path.
      Returns a predecessor path for a specified tree path.
  -->
  <xsl:function name="tree:predecessor" as="item()*">
    <xsl:param name="path" as="item()*"/>

    <xsl:variable name="left" as="item()*" select="tree:left($path)"/>

    <xsl:sequence select="
      if (empty($path)) then
        ()
      else if (exists($left)) then
        tree:rightmost($left)
      else
        tree:predecessor(subsequence($path, 2))"/>
  </xsl:function>

  <!--
    Gets a successor path for a specified tree path.
      $path - a tree path.
      Returns a successor path for a specified tree path.
  -->
  <xsl:function name="tree:successor" as="item()*">
    <xsl:param name="path" as="item()*"/>

    <xsl:variable name="right" as="item()*" select="tree:right($path)"/>

    <xsl:sequence select="
      if (empty($path)) then
        ()
      else if (exists($right)) then
        tree:leftmost($right)
      else
        tree:successor(subsequence($path, 2))"/>
  </xsl:function>

  <!--
    Returns a tree path of a node with a specified index.
      $path - a tree path.
      $index - an index of the node to navigate to.
      Returns a tree path of a node with a specified index.
  -->
  <xsl:function name="tree:index" as="item()*">
    <xsl:param name="path" as="item()*"/>
    <xsl:param name="index" as="xs:integer"/>

    <xsl:variable name="left" as="item()*" select="tree:left($path)"/>
    <xsl:variable name="right" as="item()*" select="tree:right($path)"/>
    <xsl:variable name="size" as="xs:integer" select="tree:size($left)"/>

    <xsl:sequence select="
      if ($index = $size + 1) then
        $path
      else
        tree:index
        (
          (
            if ($size >= $index) then
              $left
            else
              $right
          ),
          (
            if ($size >= $index) then
              $index
            else
              $index - $size - 1
          )
        )"/>
  </xsl:function>

  <!--
    Finds a tree node with a specified string key.
    Note that tree should be ordered according to key.
      $path - a tree path.
      $value - a string key to find.
      Returns a closure of ($c as xs:integer, $path as item()+), where
        $c is a comparision result (-1, 0, or 1), and $path is a tree path.
  -->
  <xsl:function name="tree:find" as="item()*">
    <xsl:param name="path" as="item()+"/>
    <xsl:param name="value" as="xs:string"/>

    <xsl:variable name="node-value" as="xs:string"
      select="tree:value($path)[1]"/>
    <xsl:variable name="c" as="xs:integer" select="compare($node-value, $value)"/>

    <xsl:variable name="next" as="item()*" select="
      if ($c > 0) then
        tree:left($path)
      else
        tree:right($path)"/>

    <xsl:sequence select="
      if (($c = 0) or empty($next)) then
        ($c, $path)
      else
        tree:find($next, $value)"/>
  </xsl:function>

  <!--
    Finds a tree node with a specified string key.
    Note that tree should be ordered according to key.
      $path - a tree path.
      $value - a key to find.
      $comparator - a key comparator.
      Comparision is used as:
        <xsl:variable name="c" as="xs:integer">
          <xsl:apply-templates mode="tree:call" select="$comparator">
            <xsl:with-param name="value" select="$value"/>
            <xsl:with-param name="node-value" select="$node-value"/>
          </xsl:apply-templates>
        </xsl:variable>
      Returns a closure of ($c as xs:integer, $path as item()+), where
        $c is a comparision result (-1, 0, or 1), and $path is a tree path.
  -->
  <xsl:function name="tree:find" as="item()*">
    <xsl:param name="path" as="item()+"/>
    <xsl:param name="value" as="item()*"/>
    <xsl:param name="comparator" as="element()"/>

    <xsl:variable name="node-value" as="item()*"
      select="tree:value($path)"/>

    <xsl:variable name="c" as="xs:integer">
      <xsl:apply-templates mode="tree:call" select="$comparator">
        <xsl:with-param name="value" select="$value"/>
        <xsl:with-param name="node-value" select="$node-value"/>
      </xsl:apply-templates>
    </xsl:variable>

    <xsl:variable name="next" as="item()*" select="
      if ($c > 0) then
        tree:left($path)
      else
        tree:right($path)"/>

    <xsl:sequence select="
      if (($c = 0) or empty($next)) then
        ($c, $path)
      else
        tree:find($next, $value, $comparator)"/>
  </xsl:function>

  <!--
    Gets node values for the tree.
      $path - a tree path.
      Returns a sequence of value for the tree in order 
      from the leftmost to the rightmost node.
  -->
  <xsl:function name="tree:values" as="item()*">
    <xsl:param name="path" as="item()*"/>

    <xsl:sequence select="p:values(tree:leftmost($path), ())"/>
  </xsl:function>

  <!--
    Insert a new node before or after a specified node.
      $path - a tree path.
      $value - a new value to insert into the tree.
      $before - true to insert before, and false to insert after.
      Returns a new root node.
  -->
  <xsl:function name="tree:insert" as="item()">
    <xsl:param name="path" as="item()*"/>
    <xsl:param name="value" as="item()*"/>
    <xsl:param name="before" as="xs:boolean"/>

    <xsl:sequence select="
      if (empty($path)) then
        tree:node((), (), $value)
      else if ($before) then 
        if (exists(tree:left($path))) then
          p:insert(tree:predecessor($path), $value, false())
        else
          p:insert($path, $value, true())
      else
        if (exists(tree:right($path))) then
          p:insert(tree:successor($path), $value, true())
        else
          p:insert($path, $value, false())"/>
  </xsl:function>

  <!--
    Inserts a value into the tree.
      $path - a tree path.
      $value - a value to insert (key is a first item of type xs:string).
      $insert-duplicate - true to insert, and false to ignore duplicates.
      Returns a new tree root.
  -->
  <xsl:function name="tree:insert-ordered" as="item()">
    <xsl:param name="path" as="item()*"/>
    <xsl:param name="value" as="item()+"/>
    <xsl:param name="insert-duplicate" as="xs:boolean"/>

    <xsl:choose>
      <xsl:when test="empty($path)">
        <xsl:sequence select="tree:node((), (), $value)"/>
      </xsl:when>
      <xsl:otherwise>
        <xsl:variable name="closure" as="item()+"
          select="tree:find($path[last()], $value[1])"/>

        <xsl:variable name="c" as="xs:integer" select="$closure[1]"/>
        <xsl:variable name="reference-path" as="item()+"
         select="subsequence($closure, 2)"/>

        <xsl:sequence select="
          if ($c = 0) then
            $path
          else
            tree:insert($reference-path, $value, $c > 0)"/>
      </xsl:otherwise>
    </xsl:choose>
  </xsl:function>

  <!--
    Inserts a value into the tree.
      $path - a tree path.
      $value - a value to insert (key is a first item).
      $comparator - a key comparator.
      $insert-duplicate - true to insert, and false to ignore duplicates.
      Returns a new tree root.
  -->
  <xsl:function name="tree:insert-ordered" as="item()">
    <xsl:param name="path" as="item()*"/>
    <xsl:param name="value" as="item()*"/>
    <xsl:param name="comparator" as="element()"/>
    <xsl:param name="insert-duplicate" as="xs:boolean"/>

    <xsl:choose>
      <xsl:when test="empty($path)">
        <xsl:sequence select="tree:node((), (), $value)"/>
      </xsl:when>
      <xsl:otherwise>
        <xsl:variable name="closure" as="item()+"
          select="tree:find($path[last()], $value, $comparator)"/>
        <xsl:variable name="c" as="xs:integer" select="$closure[1]"/>
        <xsl:variable name="reference-path" as="item()+"
         select="subsequence($closure, 2)"/>

        <xsl:sequence select="
          if ($c = 0) then
            $path
          else
           tree:insert($reference-path, $value, $c > 0)"/>
      </xsl:otherwise>
    </xsl:choose>
  </xsl:function>

  <!--
    Replaces a node value.
      $path - a tree path.
      $value - a new value.
      Returns a new root node.
  -->
  <xsl:function name="tree:replace-value" as="item()+">
    <xsl:param name="path" as="item()+"/>
    <xsl:param name="value" as="item()*"/>

    <xsl:sequence select="
      p:replace
      (
        $path,
        tree:node
        (
          tree:left($path)[1],
          tree:right($path)[1],
          tree:value($path)
        ),
        1,
        ()
      )"/>
  </xsl:function>

  <!--
    Removes a node.
      $path - a tree path.
      Returns a new root node.
  -->
  <xsl:function name="tree:remove" as="item()*">
    <xsl:param name="path" as="item()*"/>

    <xsl:if test="exists($path)">
      <xsl:variable name="left" as="item()*" select="tree:left($path)"/>
      <xsl:variable name="right" as="item()*" select="tree:right($path)"/>

      <xsl:choose>
        <xsl:when test="exists($left) and exists($right)">
          <xsl:sequence select="p:remove-and-balance($path)"/>
        </xsl:when>
        <xsl:when test="count($path) = 1">
          <!-- Delete root node. -->
          <xsl:sequence select="$left, $right"/>
        </xsl:when>
        <xsl:otherwise>
          <xsl:variable name="parent" as="item()+" select="$path[2]"/>
          <xsl:variable name="parent-left" as="item()?"
            select="tree:left($parent)[1]"/>
          <xsl:variable name="parent-right" as="item()?"
            select="tree:right($parent)[1]"/>
          
          <xsl:choose>
            <xsl:when test="empty($left)">
              <xsl:choose>
                <xsl:when test="empty($right)">
                  <!-- Remove leaf node. -->
                  <xsl:sequence select="
                    if (tuple:is-same($parent-left, $path[1])) then
                      p:balance($path, (), $parent-right)
                    else
                      p:balance($path, $parent-left, ())"/>
                </xsl:when>
                <xsl:otherwise>
                  <!-- There is only a right child. -->
                  <xsl:sequence select="
                    if (tuple:is-same($parent-left, $path[1])) then
                      p:balance($path, $right, $parent-right)
                    else
                      p:balance($path, $parent-left, $right)"/>
                </xsl:otherwise>
              </xsl:choose>
            </xsl:when>
            <xsl:otherwise>
              <!-- There is only a left child. -->
              <xsl:sequence select="
                if (tuple:is-same($parent-right, $path[1])) then
                  p:balance($path, $parent-left, $left)
                else
                  p:balance($path, $left, $parent-right)"/>
            </xsl:otherwise>
          </xsl:choose>         
        </xsl:otherwise>        
      </xsl:choose>
    </xsl:if>
  </xsl:function>

  <!--
    Removes a node from the tree.
      $path - a tree path.
      $value - a key for the node to remove.
      Returns a new tree root.
  -->
  <xsl:function name="tree:remove" as="item()?">
    <xsl:param name="path" as="item()*"/>
    <xsl:param name="value" as="xs:string"/>

    <xsl:if test="exists($path)">
      <xsl:variable name="closure" as="item()+"
        select="tree:find($path[last()], $value[1])"/>
      <xsl:variable name="c" as="xs:integer" select="$closure[1]"/>
      <xsl:variable name="reference-path" as="item()+"
       select="subsequence($closure, 2)"/>

      <xsl:sequence select="
        if ($c != 0) then
          $path
        else
          tree:remove($reference-path)"/>
    </xsl:if>
  </xsl:function>

  <!--
    Removes a node from the tree.
      $path - a tree path.
      $value - a key for the node to remove.
      $comparator - a key comparator.
      Returns a new tree root.
  -->
  <xsl:function name="tree:remove" as="item()?">
    <xsl:param name="path" as="item()*"/>
    <xsl:param name="value" as="item()*"/>
    <xsl:param name="comparator" as="element()"/>

    <xsl:if test="exists($path)">
      <xsl:variable name="closure" as="item()+"
        select="tree:find($path[last()], $value, $comparator)"/>
      <xsl:variable name="c" as="xs:integer" select="$closure[1]"/>
      <xsl:variable name="reference-path" as="item()+"
       select="subsequence($closure, 2)"/>

      <xsl:sequence select="
        if ($c != 0) then
          $path
        else
          tree:remove($reference-path)"/>
    </xsl:if>
  </xsl:function>

  <!--
    Replaces the current node.
      $path - a tree path.
      $new-node - a new node.
      $index - current index.
      $collected-path - collected path.
      Return new tree path.
  -->
  <xsl:function name="p:replace" as="item()+">
    <xsl:param name="path" as="item()+"/>
    <xsl:param name="new-node" as="item()?"/>
    <xsl:param name="index" as="xs:integer"/>
    <xsl:param name="collected-path" as="item()*"/>

    <xsl:variable name="node" as="item()" select="$path[$index]"/>
    <xsl:variable name="parent" as="item()?" select="$path[$index + 1]"/>
    <xsl:variable name="left" as="item()*" select="tree:left($parent)"/>
    <xsl:variable name="right" as="item()*" 
      select="tree:right($parent)"/>
    <xsl:variable name="is-left" as="xs:boolean" 
      select="tuple:is-same($node, $left[1])"/>

    <xsl:variable name="next-path" as="item()+" 
      select="$collected-path, $new-node"/>

    <xsl:sequence select="
      if (empty($parent)) then
        $next-path
      else
        p:replace
        (
          $path,
          tree:node
          (
            (
              if ($is-left) then
                $new-node
              else
                $left[1]
            ), 
            (
              if ($is-left) then
                $right[1]
              else
                $new-node
            ), 
            tree:value($parent)
          ),
          $index + 1,
          $next-path                    
        )"/>
  </xsl:function>

  <!--
    Removes node with two children and balances the tree.
      $path - a tree path.
      Returns a new root node.
  -->
  <xsl:function name="p:remove-and-balance" as="item()">
    <xsl:param name="path" as="item()+"/>

    <xsl:variable name="last-index" as="xs:integer" select="count($path)"/>

    <xsl:choose>
      <xsl:when test="
        tree:size(tree:left($path)) >=
          tree:size(tree:right($path))">

        <xsl:variable name="new-path" as="item()+"
          select="subsequence(tree:predecessor($path), 2)"/>
        <xsl:variable name="parent" as="item()" select="$new-path[1]"/>

        <xsl:sequence select="
          if ($last-index = count($new-path)) then
            p:remove-and-balance
            (
              $path,
              tree:left(tree:left($parent)),
              tree:right($parent),
              tree:value(tree:left($parent)),
              count($new-path),
              $last-index
            )
          else
            p:remove-and-balance
            (
              $path,
              tree:left($parent),
              tree:left(tree:right($parent)),
              tree:value(tree:right($parent)),
              count($new-path),
              $last-index
            )"/>
      </xsl:when>
      <xsl:otherwise>
        <xsl:variable name="new-path" as="item()+"
          select="subsequence(tree:successor($path), 2)"/>
        <xsl:variable name="parent" as="item()" select="$new-path[1]"/>

        <xsl:sequence select="
          if ($last-index = count($new-path)) then
            p:remove-and-balance
            (
              $path,
              tree:left($parent),
              tree:right(tree:right($parent)),
              tree:value(tree:right($parent)),
              count($new-path),
              $last-index
            )
          else
            p:remove-and-balance
            (
              $path,
              tree:right(tree:left($parent)),
              tree:right($parent),
              tree:value(tree:left($parent)),
              count($new-path),
              $last-index
            )"/>
      </xsl:otherwise>
    </xsl:choose>
  </xsl:function>

  <!--
    Removes node with two children and balances the tree.
      $path - a tree path.
      $left - a left node.
      $right - a right node.
      $value - a new parent value.
      $index - current index.
      $last-index - a last index.
      Returns a new root node.
  -->
  <xsl:function name="p:remove-and-balance" as="item()">
    <xsl:param name="path" as="item()+"/>
    <xsl:param name="left" as="item()*"/>
    <xsl:param name="right" as="item()*"/>
    <xsl:param name="value" as="item()*"/>
    <xsl:param name="index" as="xs:integer"/>
    <xsl:param name="last-index" as="xs:integer"/>

    <xsl:choose>
      <xsl:when test="$index = $last-index">
        <xsl:variable name="new-path" as="item()+" select="
          p:replace
          (
            subsequence($path, $index),
            tree:node($left[1], $right[1], $value), 
            1, 
            ()
          )"/>

        <xsl:variable name="new-node" as="item()" select="$new-path[1]"/>

        <xsl:sequence select="
          p:balance
          (
            $new-path, 
            tree:left($new-node), 
            tree:right($new-node)
          )"/>
      </xsl:when>
      <xsl:otherwise>
        <xsl:variable name="node" as="item()" select="$path[$index]"/>
        <xsl:variable name="new-node" as="item()" 
          select="tree:node($left[1], $right[1], tree:value($node))"/>
        <xsl:variable name="parent" as="item()" select="$path[$index + 1]"/>
        <xsl:variable name="left" as="item()*"
          select="tree:left($parent)"/>
        <xsl:variable name="right" as="item()*" 
          select="tree:right($parent)"/>
        <xsl:variable name="is-left" as="xs:boolean" 
          select="tuple:is-same($left[1], $node)"/>

        <xsl:sequence select="
          p:remove-and-balance
          (
            $path,
            (
              if ($is-left) then
                $new-node
              else
                $left
            ),
            (
              if ($is-left) then
                $right
              else
                $new-node
            ),
            $value,
            $index,
            $last-index
          )"/>
      </xsl:otherwise>
    </xsl:choose>
  </xsl:function>

  <!--
    tree:insert() implementation.
    Insert a new node before or after a specified node.
      $path - a tree path.
      $value - a new value to insert into the tree.
      $before - true to insert before, and false to insert after.
      Returns a new root node.
  -->
  <xsl:function name="p:insert" as="item()">
    <xsl:param name="path" as="item()*"/>
    <xsl:param name="value" as="item()*"/>
    <xsl:param name="before" as="xs:boolean"/>

    <xsl:variable name="node" as="item()?" select="tree:node((), (), $value)"/>

    <xsl:sequence select="
      if ($before) then
        p:balance($path, $node, tree:right($path))
      else
        p:balance($path, tree:left($path), $node)"/>
  </xsl:function>

  <!--
    Rebalances tree.
      $path - an tree path.
      $left - left node.
      $right - right node.
      Returns rebalanced root node.
  -->
  <xsl:function name="p:balance" as="item()?">
    <xsl:param name="path" as="item()+"/>
    <xsl:param name="left" as="item()*"/>
    <xsl:param name="right" as="item()*"/>

    <xsl:variable name="node-value" as="item()*"
      select="tree:value($path)"/>

    <xsl:variable name="next-path" as="item()*" 
      select="subsequence($path, 2)"/>
    <xsl:variable name="next-left" as="item()*"
      select="tree:left($next-path)"/>
    <xsl:variable name="next-right" as="item()*"
      select="tree:right($next-path)"/>
    <xsl:variable name="is-left" as="xs:boolean"
      select="tuple:is-same($next-left[1], $path[1])"/>

    <xsl:variable name="left-left" as="item()*"
      select="tree:left($left)"/>
    <xsl:variable name="left-right" as="item()*"
      select="tree:right($left)"/>
    <xsl:variable name="right-left" as="item()*"
      select="tree:left($right)"/>
    <xsl:variable name="right-right" as="item()*"
      select="tree:right($right)"/>

    <xsl:variable name="left-size" as="xs:integer"
      select="tree:size($left)"/>
    <xsl:variable name="left-left-size" as="xs:integer" 
      select="tree:size($left-left)"/>
    <xsl:variable name="left-right-size" as="xs:integer" 
      select="tree:size($left-right)"/>
    <xsl:variable name="right-size" as="xs:integer"
      select="tree:size($right)"/>
    <xsl:variable name="right-left-size" as="xs:integer"
      select="tree:size($right-left)"/>
    <xsl:variable name="right-right-size" as="xs:integer"
      select="tree:size($right-right)"/>
      
    <xsl:variable name="new-node" as="item()+" select="
      if 
      (
        ($left-left-size > $right-size) and 
        ($left-left-size > $left-right-size)
      )
      then
      (
        (: LL  :)
        tree:node
        (
          $left-left[1],
          tree:node($left-right[1], $right[1], $node-value),
          tree:value($left)
        )
      )
      else if
      (
        ($left-right-size > $right-size) or
        (
          ($left-left-size = $right-size) and
          exists($left-right) and
          exists(tree:left($left-right))
        )
      )
      then
      (
        (: LR :)
        tree:node
        (
          tree:node
          (
            $left-left[1], 
            tree:left($left-right)[1], 
            tree:value($left)
          ),
          tree:node(tree:right($left-right)[1], $right[1], $node-value),
          tree:value($left-right)
        )
      )
      else if 
      (
        ($right-right-size > $left-size) and 
        ($right-right-size > $right-left-size)
      ) 
      then
      (
        (: RR :)
        tree:node
        (
          tree:node($left[1], $right-left[1], $node-value),
          $right-right[1],
          tree:value($right)
        )
      )
      else if 
      (
        ($right-left-size > $left-size) or
        (
          ($right-right-size = $left-size) and
          exists($right-left) and
          exists(tree:right($right-left))
        )
      )
      then
      (
        (: RL :)
        tree:node
        (
          tree:node($left[1], tree:left($right-left)[1], $node-value),
          tree:node
          (
            tree:right($right-left)[1], 
            $right-right[1], 
            tree:value($right)
          ),
          tree:value($right-left)
        )
      )
      else if 
      (
        tuple:is-same(tree:left($path)[1], $left[1]) and
        tuple:is-same(tree:right($path)[1], $right[1])
      )
      then
      (
        $path
      )
      else
      (
        tree:node($left[1], $right[1], $node-value)
      )"/>

    <xsl:sequence select="
      if (empty($next-path)) then
        $new-node
      else
        p:balance
        (
          $next-path,
          (
            if ($is-left) then
              $new-node
            else
              $next-left
          ),
          (
            if ($is-left) then
              $next-right
            else
              $new-node
          )
        )"/>
  </xsl:function>

  <!--
    Creates a tree from a sequence of values.
      $values - values to pupulate nodes. 
      $sizes - sizes of groups of values that form one node.
      $values-index - current index in $values sequence.
      $sizes-index - current index in $sizes sequence.
      $count - a number of nodes to create.
      Returns a closure ($count as xs:integer, $node as item()), where
        $count - is a number of consumed values, and $node is created node.
  -->
  <xsl:function name="p:create" as="item()+">
    <xsl:param name="values" as="item()*"/>
    <xsl:param name="sizes" as="xs:integer*"/>
    <xsl:param name="values-index" as="xs:integer"/>
    <xsl:param name="sizes-index" as="xs:integer"/>
    <xsl:param name="count" as="xs:integer"/>

    <xsl:sequence select="$count"/>
    
    <xsl:if test="$count > 0">
      <xsl:variable name="left-count" as="xs:integer" select="$count idiv 2"/>
      <xsl:variable name="right-count" as="xs:integer" 
        select="$count - $left-count - 1"/>

      <xsl:variable name="left-closure" as="item()+" select="
        if ($left-count > 0) then
          p:create($values, $sizes, $values-index, $sizes-index, $left-count)
        else
          0"/>

      <xsl:variable name="value-index" as="xs:integer" select="$left-closure[1]"/>
      <xsl:variable name="size" as="xs:integer" 
        select="$sizes[$sizes-index + $left-count]"/>
      <xsl:variable name="values" as="item()*" 
        select="subsequence($values, $value-index, $size)"/>

      <xsl:variable name="right-closure" as="item()+" select="
        if ($right-count > 0) then
          p:create
          (
            $values, 
            $sizes, 
            $value-index + $size, 
            $sizes-index + $left-count, 
            $right-count
          )
        else
          0"/>

      <xsl:sequence 
        select="tree:node($left-closure[2], $right-closure[2], $values)"/>
    </xsl:if>
  </xsl:function>

  <!--
    tree:values() implementation.
    Gets node values for the tree.
      $path - a tree path.
      $collected-result - a collected result.
      Returns a sequence of value for the tree in order 
      from the leftmost to the rightmost node.
  -->
  <xsl:function name="p:values" as="item()*">
    <xsl:param name="path" as="item()*"/>
    <xsl:param name="collected-result" as="item()*"/>

    <xsl:sequence select="
      if (empty($path)) then
        $collected-result
      else
        p:values
        (
          tree:successor($path), 
          ($collected-result, tree:value($path))
        )"/>
  </xsl:function>

</xsl:stylesheet>
