Главная » XSLT » Выполнение обхода во внутреннем порядке

0

Задача

Имеется XML-документ или фрагмент документа, представляющий выраже­ние, которое требуется обработать во внутреннем порядке.

Решение

Обход во внутреннем порядке применяется как правило к двоичным деревь­ям. Общий вид алгоритма таков:

<xsl:template match="node()">

<!– Обработать левое поддерево –> <xsl:apply-templates select="*[1]"/>

<!– Сделать что-то с текущим узлом –>

<!– Обработать правое поддерево — > <xsl:apply-templates select="*[2]"/> </xsl:template>

Однако обход во внутреннем порядке можно обобщить и на n-арные деревья следующим образом:

<xsl:template match="node()">

<xsl:variable name="current-node" select="."/> <!– Обработать левое поддерево –> <xsl:apply-templates select="*[1]"/>

<!– Сделать что-то с текущим узлом –>

<!– Рекурсивно применить к средним дочерним элементам –> <xsl:for-each select="*[position() > 1 and position() &lt; last()">

<!– Обработать "левое" поддерево –> <xsl:apply-templates select="."/>

<!– Сделать что-то с узлом $current-node –> </xsl:for-each>

<!– Обработать правое поддерево — > <xsl:apply-templates select="*[last()]"/>

</xsl:template>

Смысл этого алгоритма будет проще понять, если обратиться к рис. 5.1, на ко­тором показан двоичный эквивалент n-арного дерева. Обобщенный обход n-арно- го дерева во внутреннем порядке дает тот же результат, что обход во внутреннем порядке эквивалентного ему двоичного дерева.

Рис. 5.1. Эквивалентность n-арного и двоичного дерева

Обсуждение

Этот вид обхода находит гораздо меньше применений, чем другие виды, рас­смотренные в настоящей главе. Одно из значимых приложений приведено в при­мерах 5.10 и 5.11. Это программа преобразования MathML-разметки в инфиксное выражение на языке C или Java. Результат работы показан в примере 5.12.

Пример 5.10. Фрагмент документа на языке MathML

<apply> <eq/> <apply>

<plus/> <apply>

<minus/> <ci>y</ci> <cn>2</cn> </apply> <apply>

<times/>

<cn>4</cn>

<apply>

<plus/> <ci>x</ci> <cn>1</cn> </apply>

</apply> <cn>8</cn> </apply> <cn>0</cn> </apply>

Пример 5.11. Обход фрагмента на языке MathML во внутреннем порядке, порождающий выражение на языке C

<?xml version="1.0" encoding="UTF-8"?> <xsl:stylesheet version="1.0"

xmlns:xsl="http://www.w3.org/1999/XSL/Transform" xmlns:C="http:www.oreilly.com/TheXSLTCoobook/nampespaces/C">

<xsl:output method="text"/> <xsl:strip-space elements="*"/>

<!— Таблица для преобразования имен MathML-операций в операторы C –>

<C:operator mathML="plus" c="+" precedence="2"/>

<C:operator mathML="minus" c="-" precedence="2"/>

<C:operator mathML="times" c="*" precedence="3"/>

<C:operator mathML="div" c="/" precedence="3"/>

<C:operator mathML="mod" c="%" precedence="3"/>

<C:operator mathML="eq" c="==" precedence="1"/>

<!– Загрузить таблицу преобразования операций в переменную –>

<xsl:variable name="ops" select="document(”)/*/C:operator"/>

<xsl:template match="apply">

<xsl:param name="parent-precedence" select="0"/>

<!– Сопоставить MathML-операции знак и приоритет оператора –> <xsl:variable name="mathML-opName" select="local-name(*[1])"/> <xsl:variable name="c-opName"

select="$ops[@mathML=$mathML-opName]/@c"/> <xsl:variable name="c-opPrecedence"

select="$ops[@mathML=$mathML-opName]/@precedence"/>

<!— Если приоритет охватывающего выражения больше, чем приоритет текущего подвыражения, необходима скобка —> <xsl:if test="$parent-precedence > $c-opPrecedence">

<xsl:text>(</xsl:text> </xsl:if>

<!– Рекурсивно обработать левое поддерево, которое находится

в позиции 2, считая от элeмeнтa apply –> <xsl:apply-templates select="*[2]">

<xsl:with-param name="parent-precedence"

select="$c-opPrecedence"/> </xsl:apply-templates>

<!– Oбpaбoтaть тeкyщий узел (т-e. oпepaтop в позиции 1, считая от элeмeнтa apply –> <xsl:value-of select="concat(‘ ‘,$c-opName,’ ‘)"/>

<!– Peкypcивнo oбpaбoтaть cpen^e дoчepниe элeмeнты –> <xsl:for-each select="*[position()>2 and

position() &lt; last()]"> <xsl:apply-templates select=".">

<xsl:with-param name="parent-precedence" select="$c-opPrecedence"/> </xsl:apply-templates>

<xsl:value-of select="concat(‘ ‘,$c-opName,’ ‘)"/> </xsl:for-each>

<!– Peкypcивнo oбpaбoтaть пpaвoe пoддepeвo –> <xsl:apply-templates select="*[last()]"> <xsl:with-param name="parent-precedence" select="$c-opPrecedence"/> </xsl:apply-templates>

<!— Если пpиopитeт охватывающего выpaжeния бoльшe, чeм пpиopитeт тeкyщeгo пoдвыpaжeния, необходима скобка –> <xsl:if test="$parent-precedence > $c-opPrecedence"> <xsl:text>)</xsl:text> </xsl:if>

</xsl:template>

<xsl:template match="ci|cn">

<xsl:value-of select="."/> </xsl:template>

</xsl:stylesheet>

Пример 5.12. Результат

y – 2 + 4 * (x + 1) + 8 == 0

Понятно, что эту таблицу стилей нельзя назвать полноценным транслятором с языка MathML. Впрочем, в главе 9 мы обсудим эту проблему более детально.

Требуется упорядочить элементы по возрастанию уровня (глубины в дереве). Другими словами, нужно обойти дерево в ширину.

Решение

Эта задача буквально создана для применения команды xsl:for-each со­вместно с xsl:sort.

<xsl:for-each select="//*">

<xsl:sort select="count(ancestor::*)" data-type="number"/> <!– Обработать текущий элемент –> </xsl:for-each>

Рекурсивное решение длиннее и не так очевидно.

<xsl:template match="/*">

<xsl:call-template name="level-order"/> </xsl:template>

<xsl:template name="level-order"> <xsl:param name="max-level" select="10"/> <xsl:param name="current-depth" select="1"/>

<xsl:choose>

<xsl:when test="$current-depth &lt; = $max-level"> <!– обработать текущий уровень –> <xsl:call-template name="level-order-aux"> <xsl:with-param name="level"

select="$current-level"/> <xsl:with-param name="actual-level"

select="$current-level"/> </xsl:call-template>

<!– обработать предыдущий уровень –> <xsl:call-template name="level-order"> <xsl:with-param name="current-level"

select="$current-level + 1"/> </xsl:call-template> </xsl:when> </xsl:choose>

</xsl:template>

<xsl:template name="level-order-aux">

<xsl:param name="level" select="1"/> <xsl:param name="actual-level" select="1"/> <xsl:choose>

<xsl:when test="$level = 1">

<!— Здесь обрабатывается текущий элемент —> <!— $actual-level — номер текущего уровня —> </xsl:when> <xsl:otherwise>

<!– Рекурсивно переходим к следующему уровню для всех дочерних элементов –> <xsl:for-each select="*"> <xsl:call-template name="level-order-aux"> <xsl:with-param name="level"

select="$level – 1"/> <xsl:with-param name="actual-level" select="$actual-level"/> </xsl:call-template> </xsl:for-each> </xsl:otherwise> </xsl:choose> </xsl:template>

В этом решении требуется, чтобы вы либо задали произвольную верхнюю гра­ницу глубины дерева, либо предварительно вычислили ее. Решить эту задачу можно, например, отыскав узел, у которого нет детей и который имеет больше предков, чем любой другой узел, не имеющий детей.

<xsl:param name="max-level">

<xsl:for-each select="//*[not(*)]">

<xsl:sort select="count(ancestor::*)" data-type="number"

order="descending" /> <xsl:if test="position() = 1">

<xsl:value-of select="count(ancestor::*) + 1" /> </xsl:if> </xsl:for-each> </xsl-param>

Обсуждение

Необходимость обходить XML-документ по уровням возникает, пожалуй, не слишком часто. Группировка узлов по глубине или по расстоянию от корня плохо согласуется с естественным потоком управления в XSLT, который рассчитан на обход дерева в глубину. Это с очевидностью следует из того факта, что для обра­ботки узлов по глубине или, что эквивалентно, по числу предков приходится ис­пользовать команду xsl:sort. Сложность рекурсивного решения также свиде­тельствует о неестественности этого процесса.

Тем не менее, такой вид обхода иногда оказывается полезным. Например, с его помощью можно обработать структурную диаграмму организации так, что­бы работники выводились по удаленности от главы компании. Соответствующий код приведен в примере 5.13, а результат его работы – в примере 5.14.

Пример 5.13. Обход файла orgchart.xml по уровням с использованием сор­тировки

<?xml version="1.0" encoding="UTF-8"?>

<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform"> <xsl:output method="text"/>

<xsl:template match="/">

<xsl:for-each select="//employee">

<xsl:sort select="count(ancestor::*)" order="ascending"/> <xsl:variable name="level" select="count(ancestor::*)"/> <xsl:choose>

<xsl:when test="$level = 0">

<xsl:value-of select="@name"/> <xsl:text> глава компании.&#xA;</xsl:text> </xsl:when>

<xsl:otherwise>

<xsl:value-of select="@name"/> <xsl:text> имеет </xsl:text> <xsl:value-of select="$level"/> <xsl:text> начальников(а).&#xA;</xsl:text> </xsl:otherwise> </xsl:choose> </xsl:for-each> </xsl:template>

</xsl:stylesheet>

Пример 5.14. Результат

Jil Michel глава компании.

Nancy Pratt имеет 1 начальников(а).

JaneDoe имеет 1 начальников(а).

Mike Rosenbaum имеет 1 начальников(а).

Phil McKraken имеет 2 начальников(а).

Ima Little имеет 2 начальников(а).

Walter H. Potter имеет 2 начальников(а).

Wendy B.K. MacDonald имеет 2 начальников(а).

Cindy Post-Kellog имеет 2 начальников(а).

Oscar A. Winner имеет 2 начальников(а).

Betsy Ross имеет 3 начальников(а). Craig F. Frye имеет 3 начальников(а). Hardy Hamburg имеет 3 начальников(а). Rich Shaker имеет 3 начальников(а). Allen Bran имеет 3 начальников(а). Frank N. Berry имеет 3 начальников(а). Jack Apple имеет 3 начальников(а). Jack Nicklaus имеет 3 начальников(а). Tom Hanks имеет 3 начальников(а). Susan Sarandon имеет 3 начальников(а). R.P. McMurphy имеет 4 начальников(а). Forrest Gump имеет 4 начальников(а). Andrew Beckett имеет 4 начальников(а). Helen Prejean имеет 4 начальников(а).

Один из плюсов рекурсивного решения состоит в том, что легко понять, когда происходит переход на следующий уровень. Этой информацией можно восполь­зоваться для форматирования результата, как показано в примерах 5.15 и 5.16.

Пример 5.15. Обход файла orgchart.xml по уровням с использованием рекурсии

<?xml version="1.0" encoding="UTF-8"?>

<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">

<xsl:output method="text" version="1.0" encoding="UTF-8"/>

<xsl:strip-space elements="*"/>

<xsl:template match="/employee">

<xsl:call-template name="level-order"/> </xsl:template>

<xsl:template name="level-order"> <xsl:param name="max-depth" select="10"/> <xsl:param name="current-depth" select="0"/>

<xsl:choose>

<xsl:when test="$current-depth &lt; = $max-depth"> <xsl:variable name="text">

<xsl:call-template name="level-order-aux">

<xsl:with-param name="level" select="$current-depth"/> <xsl:with-param name="actual-level" select="$current-depth"/> </xsl:call-template> </xsl:variable>

<xsl:if test="normalize-space($text)"> <xsl:value-of select="$text"/>

<xsl:text>&#xa;</xsl:text> <xsl:call-template name="level-order">

<xsl:with-param name="current-depth" select="$current-depth + 1"/> </xsl:call-template> </xsl:if> </xsl:when> </xsl:choose>

</xsl:template>

<xsl:template name="level-order-aux">

<xsl:param name="level" select="0"/> <xsl:param name="actual-level" select="0"/> <xsl:choose>

<xsl:when test="$level = 0"> <xsl:choose>

<xsl:when test="$actual-level = 0"> <xsl:value-of select="@name"/> <xsl:text> глава компании.&#xA;</xsl:text> </xsl:when> <xsl:otherwise>

<xsl:value-of select="@name"/> <xsl:text> имеет </xsl:text> <xsl:value-of select="$actual-level"/> <xsl:text> начальников(а).&#xA;</xsl:text> </xsl:otherwise> </xsl:choose> </xsl:when> <xsl:otherwise>

<xsl:for-each select="employee">

<xsl:call-template name="level-order-aux"> <xsl:with-param name="level" select="$level – 1"/> <xsl:with-param name="actual-level" select="$actual-level"/> </xsl:call-template> </xsl:for-each> </xsl:otherwise> </xsl:choose> </xsl:template>

</xsl:stylesheet>

Пример 5.16. Результат

Jil Michel глава компании.

Nancy Pratt имеет 1 начальников(а).

JaneDoe имеет 1 начальников(а).

Mike Rosenbaum имеет 1 начальников(а).

Phil McKraken имеет 2 начальников(а). Ima Little имеет 2 начальников(а). Walter H. Potter имеет 2 начальников(а). Wendy B.K. MacDonald имеет 2 начальников(а). Cindy Post-Kellog имеет 2 начальников(а). Oscar A. Winner имеет 2 начальников(а).

Betsy Ross имеет 3 начальников(а). Craig F. Frye имеет 3 начальников(а). Hardy Hamburg имеет 3 начальников(а). Rich Shaker имеет 3 начальников(а). Allen Bran имеет 3 начальников(а). Frank N. Berry имеет 3 начальников(а). Jack Apple имеет 3 начальников(а). Jack Nicklaus имеет 3 начальников(а). Tom Hanks имеет 3 начальников(а). Susan Sarandon имеет 3 начальников(а).

R.P. McMurphy имеет 4 начальников(а). Forrest Gump имеет 4 начальников(а). Andrew Beckett имеет 4 начальников(а). Helen Prejean имеет 4 начальников(а).

Если вам почему-то захочется посещать узлы на одном из уровней в случай­ном порядке, то можно следующим образом определить ключ:

<xsl:key name="level" match="employee" use="count(ancestor::*)"/>

<xsl:template match="/">

<xsl:for-each select="key(‘level’, 3)">

<!– сделать что-то с узлами на уровне 3 –> </xsl:for-each> </xsl:template>

Можно также уточнить условие сопоставления или использовать предикат совместно с функцией key:

<xsl:key name="level" match="employee" use="count(ancestor::*)"/>

<xsl:template match="/">

<xsl:for-each select="key(‘level’, 3)[@sex=’female’]">

<!– сделать что-то с работниками-женщинами на уровне 3 –> </xsl:for-each> </xsl:template>

Прибегать к механизму определения ключей в XSLT необязательно, посколь­ку всегда можно написать select="//*[count(ancestor::*)=3]", если нужно получить все элементы на уровне level-3. Однако, если в таблице стилей будет многократно вычисляться такое выражение, то упадет производительность. Вообще, если исходный файл имеет четко определенную структуру, то гораздо эффективнее явно перейти на нужный уровень, например, с помощью выражения select="/employee/employee/employee", хотя подобная навигация может оказаться довольно громоздкой.

Мангано Сэл  XSLT. Сборник рецептов. – М.: ДМК Пресс, СПБ.: БХВ-Петербург, 2008. – 864 с.: ил.

По теме:

  • Комментарии