how can I move a node before its sibling and give it an attribute related to parent?

Question

I've got the following document structure:

<?xml version="1.0"?>
<catalog>
  <navigationRoot>
    <!-- more elements-->
    <navigation id="123" type="level0">
      <!-- more elements-->
      <navigationNodes>
        <navigationNode>
          <!-- more elements-->
        </navigationNode>
        <navigationNode>
          <!-- more elements-->
        </navigationNode>
        <!--...-->
      </navigationNodes>
      <children>
        <navigation idref="196439"/>
        <navigation idref="196459"/>
        <!--...-->
      </children>
      <!-- more elements-->
    </navigation>
    <navigation id="196439" type="level1">
      <!-- more elements-->
      <navigationNodes>
        <navigationNode>
          <!-- more elements-->
        </navigationNode>
        <navigationNode>
          <!-- more elements-->
        </navigationNode>
        <!--...-->
      </navigationNodes>
      <children>
        <navigation idref="19643261"/>
        <navigation idref="196463463"/>
        <!--...-->
      </children>
      <!-- more elements-->
    </navigation>   
    <navigation id="196459" type="level1">
      <!-- more elements-->
      <navigationNodes>
        <navigationNode>
          <!-- more elements-->
        </navigationNode>
        <navigationNode>
          <!-- more elements-->
        </navigationNode>
        <!--...-->
      </navigationNodes>
      <children>
        <navigation idref="19644361"/>
        <navigation idref="19643467"/>
        <!--...-->
      </children>
      <!-- more elements-->
    </navigation>       
  </navigationRoot>
</catalog>

I need to move the "children" element before the "navigationNodes" element within the "navigation id=..." elements. further I have to give the "navigation idref=..." elements another attribute "type" that equals level++ of the parent element. For example, in this document, within the "navigation id=123" node the children node should be placed above the "navigationNode" element and have the type of "level1", like this:

   <navigation id="123" type="level0">
      <!-- more elements-->
      <children>
        <navigation idref="196439" type="level1"/>
        <navigation idref="196459" type="level1"/>
        <!--...-->
      </children>
      <navigationNodes>
        <navigationNode>
          <!-- more elements-->
        </navigationNode>
        <navigationNode>
          <!-- more elements-->
        </navigationNode>
        <!--...-->
      </navigationNodes>
      <!-- more elements-->
    </navigation>

How do I achieve that?

Answer 1

Four steps:

1. Identity transform.
2. Design a template to insert new @type on children/navigation. In this solution, the attribute is added only when any element with the @id given in @idref exists (you can consider xml:id and just use id() instead). You could also narrow it down to navigation.
3. Then, on matching children, copy it, apply children/navigation, and append any following navigationNodes. So children will practically be "moved" before navigation. I naively assumed that there is only one children in each navigation.
4. Finally, ignore all navigationNodes, which were already copied in step 3.

<xsl:template match="node() | @*">
    <xsl:copy>
        <xsl:apply-templates select="node() | @*"/>
    </xsl:copy>
</xsl:template>

<xsl:template match="children/navigation[@idref]">
    <xsl:variable name="type" select="//*[@id = current()/@idref]/@type"/>
    <xsl:copy>
        <xsl:if test="$type">
            <xsl:attribute name="type">
                <xsl:value-of select="$type"/>
            </xsl:attribute>
        </xsl:if>
        <xsl:apply-templates select="node() | @*"/>
    </xsl:copy>
</xsl:template>

<xsl:template match="children">
    <xsl:copy>
        <xsl:apply-templates select="node() | @*"/>
    </xsl:copy>
    <xsl:copy-of select="preceding-sibling::navigationNodes"/>
</xsl:template>

<xsl:template match="navigationNodes"/>

Done! Hope this helps.