Cours XSLT : Transformation et Formatage de documents XML
Récursivité en XSL
Pourquoi et comment utiliser la récursivité dans les transformations XSL ?
1
Les limites de XSL
n La modification des variables est impossible
n Pas de boucle de type pour i de 1 à n
n Complexifie le codage de certains algorithmes pourtant simples à la base
Solution : la récursivité
n Utilisation de template récursif
n C’est-à-dire un template qui se rappelle lui-même
n Au lieu de modifier les variables, on modifie les paramètres du template
Exemple de problème n°1
n On cherche à déterminer le maximum dans une liste de nombres :
<ListeNombres>
<nombre>111</nombre> <nombre>27</nombre> <nombre>9</nombre>
<nombre>57</nombre>
<nombre>2</nombre>
<nombre>363</nombre> </ListeNombres>
Algorithme simple
max ß premier élément nombre de listeNombres
Pour chaque élément nombre de listeNombres si nombre > max
alors max ß nombre
fsi
Finpour
Écrire max
Problème :
en XSL on ne peut pas modifier la valeur de max
Algorithme récursif
Fonction RechercheMax(max, indice){ si indice = nbéléments(listeNombres) alors si listNombre[indice] > max
alors écrire listNombre(indice) sinon écrire max
fsi
sinon si listNombre[indice] > max alors rechercheMax(listNombre[indice], indice + 1)
sinon rechercheMax(max, indice +1) fsi fsi
}
Premier appel : RechercheMax(listNombres[1],2)
<xsl:template name="RechercheMax"> <xsl:param name="max"></xsl:param> <xsl:param name="indice"></xsl:param> |
<xsl:choose>
<!-- On teste si on a atteint le dernier élément nombre -->
<xsl:when test="$indice= count(//nombre)">
<xsl:choose>
<!-- On teste si la valeur de l'élément courant est supérieure à max -->
<xsl:when test="//nombre[position() = $indice] > $max">
<!-- On affiche la valeur de l’élément à l’indice -->
<xsl:value-of select="//nombre[position() = $indice]"/>…
<xsl:otherwise>
<!– Sinon on affiche max -->
<xsl:value-of select="$max"/>
<!– Si on n’a pas atteint le dernier élément -->
<xsl:choose>
<!-- On teste si la valeur de l'élément courant est supérieure à max -->
<xsl:when test="//nombre[position() = $indice] > $max">
<!-- on rapelle le template avec la nouvelle valeur de max et on incrémente l'indice -->
<xsl:call-template name="RechercheMax">
<xsl:with-param name="max"><xsl:value-of select="//nombre[position()
= $indice]"/></xsl:with-param>
<xsl:with-param name="indice"><xsl:value-of select="$indice +1"/> </xsl:with-param>
</xsl:call-template>…
Exemple de problème n°2
n Énoncé
n A partir d’une liste de nombres décimaux naturels, on souhaite récupérer un fichier XML contenant les mêmes nombres en
binaire
Exemple de problème n°2
<ListeNombre> <nombre>0</nombre> <nombre>1</nombre> <nombre>2</nombre> <nombre>3</nombre> <nombre>4</nombre> </ListeNombre> | <ListeNombreBinaire> <nombreBinaire VD="0">0</nombreBinaire> <nombreBinaire VD="1">1</nombreBinaire> <nombreBinaire VD="2">10</nombreBinaire> <nombreBinaire VD="3">11</nombreBinaire> <nombreBinaire VD="4">100</nombreBi naire> </ListeNombreBinaire> |
9
Algorithme récursif
Algorithme à appliquer pour chaque nombre de la listeNombre
fonction transformationBinaire(n:entier)
début si n < 2
alors écrire(n)
sinon transformationBinaire(n ÷ 2) écrire(n mod 2) fsi fin
Template XSL correspondant
<xsl:template name="transformationBinaire">
<xsl:param name="nb"></xsl:param>
<xsl:choose>
<xsl:when test="$nb < 2">
<xsl:value-of select="$nb"/> //écrire nb
</xsl:when>
<xsl:otherwise>
<xsl:call-template name="transformationBinaire">
<xsl:with-param name="nb" select="($nb - ($nb mod 2)) div 2"/>
</xsl:call-template>
<xsl:value-of select="$nb mod 2"/> //écrire nb mod 2
</xsl:otherwise>
</xsl:choose> </xsl:template>
Exemple de problème n°3
n Énoncé
n A partir d’une liste de nombres décimaux naturels, on souhaite récupérer un fichier XML contenant les factoriels de chaque nombre
n Rappels :
n 0! = 1
n 1! = 1
n 4! = 4x3x2x1
n 5! = 5x4x3x2x1 = 5x4! (d’où la récursivité)
Exemple de problème n°3
<ListeNombre> <nombre>0</nombre> <nombre>1</nombre> <nombre>2</nombre> <nombre>3</nombre> <nombre>4</nombre> </ListeNombre> | <ListeFactoriel> <factoriel nombreBase="0">1</factoriel> <factoriel nombreBase="1">1</factoriel> <factoriel nombreBase="2">2</factoriel> <factoriel nombreBase="3">6</factoriel> <factoriel nombreBase="4">24</factoriel> </ListeFactoriel> |
Algorithme non récursif
Fonction calculFactoriel (n:entier) début pour i de n à 1
résultat= résultat * i
finpour écrire résultat
fin
Problèmes:
n Pas de boucles de ce type en XSL
n Impossible de revaloriser une variable en XSl
n Pas propre : ne suit pas la définition mathématique n! = n x (n-1)!
Algorithme récursif
n Il suffit de reprendre la définition mathématique :
n n!= n x (n-1)!
n 0! = 1
Fonction calculFactoriel(n:entier) début
si n=0 alors résultat ß 1
sinon résultat ß n * calculFactoriel (n-1)
fsi
écrire résultat fin
n Ecrire la XSL correspondante
n Solution
n ,
n Représentation en XML
n Parcours
n Algorithmes divers
17
Représentation des arbres B
n Essayons de représenter l’arbre suivant en fichier XML
Représentation des arbres B
Représentation arborescente
<Arbre>
<nœud val=1>
<nœud val = 2>
<nœud val = 4/>
<nœud val = 5>
<nœud val = 7/>
<nœud val = 8/>
</nœud>
</nœud>
<nœud val = 3>
<nœud val = 6>
<nœud val = 9/>
</nœud>
</nœud>
</nœud>
<Arbre>
Représentation des arbres B
Représentation « à plat »
<Arbre>
<nœud ID= ‘n1’ fg= ‘n2’ fd= ‘n3’ >1<nœud>
<nœud ID= ‘n2’ fg= ‘n4’ fd= ‘n5’ >2<nœud>
<nœud ID= ‘n3’ fg= ‘n6’ >3<nœud>
<nœud ID= ‘n4’ >4<nœud>
<nœud ID= ‘n5’ fg= ‘n7’ fd= ‘n8’ >5<nœud>
<nœud ID= ‘n6’ fg= ‘n9’ >6<nœud>
<nœud ID= ‘n7’ >7<nœud> <nœud ID= ‘n8’ >8<nœud>
<nœud ID= ‘n9’ >9<nœud>
</Arbre>
Avec fg: fils gauche et fd: fils droit
Les parcours d’arbres
n Parcours préfixé
n Parcours infixé
n Parcours postfixé
n Principe
n Il consiste à visiter le contenu du nœud dès qu'on est dessus, ensuite on parcourt son fils gauche puis son fils droit
Ainsi l’affichage de cet arbre en ordre préfixé donnerait :
1,2,4,5,7,8,3,6,9
n Algorithme :
fonction imprimerPréfixé(arbre : ArbreBinaireChaîne, noeud : Noeud)
début si non noeudvide(arbre,noeud) alors écrire(val(arbre, noeud))
imprimerPréfixé(arbre, fg(arbre, noeud)) imprimerPréfixé(arbre, fd(arbre, noeud))
fsi
fin
n Remarque :
n le paramètre noeud est nécessaire pour pouvoir utiliser la récursivité, il est la racine du sous-arbre en cours de traitement
n A l'appel de la fonction, noeud est la racine de arbre
Parcours préfixé en XSL:
<xsl:template match="/">
<xsl:apply-templates select="//arbre"/>
</xsl:template>
<!– Premier appel sur la racine de l’arbre -->
<xsl:template match="arbre">
<xsl:apply-templates select="child::noeud"/>
</xsl:template>
<!-- fonction récursive -->
<xsl:template match="noeud">
<!-- Impression de la valeur du noeud -->
<xsl:value-of select="concat(attribute::val,', ')"/>
<!-- Rappel de la fonction pour le fils gauche -->
<xsl:apply-templates select="child::noeud[position()='1']"/> <!-- Rappel de la fonction pour le fils droit -->
<xsl:apply-templates select="child::noeud[position()='2']"/> </xsl:template>
Parcours postfixé
n Principe
n Il consiste à afficher le contenu du nœud après avoir parcouru et affiché ses deux fils
Ainsi l’affichage de cet arbre en ordre postfixé donnerait : 4,7,8,5,2,9,6,3,1
25
Parcours postfixé
n Algorithme
n Voici l’algorithme qui imprime un arbre dans l’ordre postfixé :
fonction imprimerPostfixé(arbre : ArbreBinaireChaîne, noeud : Noeud) début si non noeudvide(arbre, noeud) alors imprimerPostfixé(arbre, fg(arbre, noeud)) imprimerPostfixé(arbre, fd(arbre, noeud)) écrire(val(arbre, noeud))
fsi
fin
26
Parcours postfixé XSL: ,
<xsl:template match="/">
<xsl:apply-templates select="//arbre"/>
</xsl:template>
<!– Premier appel sur la racine de l’arbre -->
<xsl:template match="arbre">
<xsl:apply-templates select="child::noeud"/>
</xsl:template>
<!-- fonction récursive -->
<xsl:template match="noeud">
<!-- Rappel de la fonction pour le fils gauche -->
<xsl:apply-templates select="child::noeud[position()='1']"/>
<!-- Rappel de la fonction pour le fils droit -->
<xsl:apply-templates select="child::noeud[position()='2']"/>
<!-- Impression de la valeur du noeud -->
<xsl:value-of select="concat(attribute::val,', ')"/> </xsl:template>
n Principe
n Il consiste à visiter le contenu du noeud après avoir visité le contenu de son fils gauche; une fois que c'est fait, on visite son fils droit
Ainsi l’affichage de cet arbre en ordre infixé donnerait :
1,3,4,6,7,7,10,14,13
On remarque que cela affiche les valeurs dans l’ordre croissant lorsqu’on a affaire avec un arbre de recherche
28
n Algorithme :
fonction imprimerPostfixé(arbre : ArbreBinaireChaîne, noeud : Noeud) début si non noeudvide(arbre, noeud) alors imprimerPostfixé(arbre, fg(arbre, noeud)) écrire(val(arbre, noeud))
imprimerPostfixé(arbre, fd(arbre, noeud))
fsi
fin
29
Parcours infixé XSL: ,
<xsl:template match="/">
<xsl:apply-templates select="//arbre"/>
</xsl:template>
<!– Premier appel sur la racine de l’arbre -->
<xsl:template match="arbre">
<xsl:apply-templates select="child::noeud"/>
</xsl:template>
<!-- fonction récursive -->
<xsl:template match="noeud">
<!-- Rappel de la fonction pour le fils gauche -->
<xsl:apply-templates select="child::noeud[position()='1']"/>
<!-- Impression de la valeur du noeud -->
<xsl:value-of select="concat(attribute::val,', ')"/>
<!-- Rappel de la fonction pour le fils droit -->
<xsl:apply-templates select="child::noeud[position()='2']"/> </xsl:template>
Évaluation d’une expression
n Création de l’arbre d’une expression booléenne
n Évaluation de l’expression
31
n Représentation
n L’opérateur dans la racine et les valeurs dans les fils
32
Évaluation d’une expression booléenne représentée sous forme d’un arbre binaire
Les étapes de résolution
33
Algorithme
fonction evaluerExpression(arbre:arbreBin, nœud:Noeuds){
si val(arbre, nœud) = vrai
alors retourne vrai fsi
si val(arbre, nœud) = faux
alors retourne faux
fsi si val (arbre, nœud) = ‘et’
alors valFg ß evaluerExpression(arbre, fg(arbre, nœud) valFd ß evaluerExpression(arbre, fd(arbre, nœud) retrourne ( valFg et valFd)
fsi si val (arbre, nœud) = ‘ou’
alors valFg ß evaluerExpression(arbre, fg(arbre, nœud) valFd ß evaluerExpression(arbre, fd(arbre, nœud) retrourne ( valFg ou valFd)
fsi
}
valFg, valFd : booléen
XSL
<xsl:template match="noeud">
<xsl:choose>
<xsl:when test= "./@val='et' ">
<xsl:variable name="fg">
<xsl:apply-templates select="child::noeud[position()='1']"/>
</xsl:variable>
<xsl:variable name="fd">
<xsl:apply-templates select="child::noeud[position()='2']"/>
</xsl:variable>
<xsl:value-of select="$fg= 'vrai' and $fd='vrai'"/> //résultat du template
</xsl:when>
<xsl:when test="./@val ='ou' ">
<xsl:variable name="fg">
<xsl:apply-templates select="child::noeud[position()='1']"/>
</xsl:variable>
<xsl:variable name="fd">
<xsl:apply-templates select="child::noeud[position()='2']"/>
</xsl:variable>
<xsl:value-of select="$fg= 'vrai' or $fd='vrai'"/> //résultat du template
</xsl:when>
<xsl:otherwise>
<xsl:value-of select="./@val"/> //résultat du template
</xsl:otherwise>
</xsl:choose>
</xsl:template>
Combinaison de deux templates récursifs
n Principe
n Cette technique est très utile pour traiter la plupart
des problèmes à plusieurs dimensions n Elle consiste à utiliser plusieurs templates récursifs, dont certains font appel à d’autres
36
n Création d’une table de multiplication
n Une table de multiplication est représentée par un tableau à deux dimensions
n C’est pourquoi, il est judicieux de combiner deux templates récursifs
Exemple
n Les templates
n Le premier dessinera les lignes du tableau et utilisera le deuxième afin de dessiner les cellules pour chaque colonne de la ligne
Exemple :
Création d’une table de multiplication
n Objectif :
n A partir d’un fichier XML contenant des informations sur le nombre de lignes et de colonnes, il s’agit de créer une table de multiplication au format HTML
Template drawRow
<xsl:template name="drawRow">
<xsl:param name="currentRow"/>
<xsl:param name="totalRows"/>
<xsl:param name="totalCols"/>
<xsl:if test="$currentRow <= $totalRows">
<tr> //création de la ligne courante
<xsl:call-template name="drawCell">
<xsl:with-param name="currentRow" select="$currentRow"/>
<xsl:with-param name="currentCol" select="0"/>
<xsl:with-param name="totalCols" select="$totalCols"/>
</xsl:call-template>
</tr>
<xsl:call-template name="drawRow"> // ligne suivante
<xsl:with-param name="currentRow" select="$currentRow + 1"/>
<xsl:with-param name="totalRows" select="$totalRows"/>
<xsl:with-param name="totalCols" select="$totalCols"/> </xsl:call-template>
</xsl:if>
</xsl:template>
<xsl:template name="drawCell"> | |
<xsl:param name="currentRow"/> <xsl:param name="currentCol"/> |
Template drawCell
<xsl:param name="totalCols"/>
<xsl:if test="$currentCol <= $totalCols"> //test de la position
<xsl:variable name="bgColor">
<xsl:choose>
<xsl:when test="$currentRow = 0 or $currentCol = 0">#CCCCCC</xsl:when> <xsl:otherwise>white</xsl:otherwise>
</xsl:choose>
</xsl:variable>
<xsl:variable name="value">
<xsl:choose>
<xsl:when test="$currentRow = 0 and $currentCol = 0"></xsl:when>
<xsl:when test="$currentRow = 0"><xsl:value-of select="$currentCol"/></xsl:when> <xsl:when test="$currentCol = 0"><xsl:value-of select="$currentRow"/></xsl:when> <xsl:otherwise><xsl:value-of select="$currentRow * $currentCol"/></xsl:otherwise> </xsl:choose>
</xsl:variable>
<td bgcolor="{$bgColor}" align="center" valign="top"><xsl:value-of select="$value"/></td>
<xsl:call-template name="drawCell">
<xsl:with-param name="currentRow" select="$currentRow"/>
<xsl:with-param name="currentCol" select="$currentCol + 1"/>
<xsl:with-param name="totalCols" select="$totalCols"/> </xsl:call-template>
</xsl:if></xsl:template>
n Énoncé
n Inspirez-vous de l’exemple précédent pour construire le triangle de Pascal. On peut griser les 1
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
n Algorithme récursif function Pascal(x, y: integer): integer;
begin
if (x = 1) or (y = x) then Pascal := 1 else Pascal := Pascal(x, y - 1) + Pascal(x -
1, y - 1); end;
43
n Solution :
n
Les tours de Hanoi
n Résolution du problème des tours de
Hanoi
45
Les tours de Hanoi
n Explications
n Soient trois tours. Sur l'une d'entre sont empilés des disques par taille décroissante :
T1 T2 T3
n Le but du jeu consiste à déplacer les n disques de la tour de départ vers une des deux autres tours
Les tours de Hanoi
n Règles de déplacement :
n on ne peut déplacer qu'un seul disque à la fois
n un disque ne peut pas se trouver sur un disque de diamètre inférieur
Les tours de Hanoi
Algorithme de résolution du problème
fonction hanoï(nombredisques: entier, départ: chaîne, arrivée: chaîne, intermédiaire: chaîne)
début si nombredisques 0 alors hanoï(nombredisques-1, départ, intermédiaire, arrivée ) écrire(" déplacer le disque ", nombredisques, " de ", départ, " vers ", arrivée)
hanoï(nombredisques-1, intermédiaire, arrivée, départ )
fsi fin
Les tours de Hanoi
<?xml version="1.0"?>
<?xml-stylesheet type="text/xsl" href="/"?>
<Test>
<HanoiSize="3"/> </Test>
// Appel
<xsl:template match="/">
<xsl:variable name="size" select="number(/*/Hanoi/@Size)"/>
<HanoiSolution Size="{$size}">
<xsl:call-template name="hanoi">
<xsl:with-param name="height" select="$size"/>
<xsl:with-param name="fromTower" select="'A'"/>
<xsl:with-param name="toTower" select="'B'"/>
<xsl:with-param name="withTower" select="'C'"/>
</xsl:call-template>
</HanoiSolution>
</xsl:template>
<xsl:template name="hanoi">
<xsl:param name="height"/>
<xsl:param name="fromTower"/> <xsl:param name="toTower"/>
<xsl:param name="withTower"/>
<xsl:if test="$height >= 1">
<xsl:call-template name="hanoi">
<xsl:with-param name="height" select="$height - 1"/>
<xsl:with-param name="fromTower" select="$fromTower"/>
<xsl:with-param name="toTower" select="$withTower"/>
<xsl:with-param name="withTower" select="$toTower"/>
</xsl:call-template>
<Move FromTower="{$fromTower}" ToTower="{$toTower}"/>
<xsl:call-template name="hanoi">
<xsl:with-param name="height" select="$height - 1"/>
<xsl:with-param name="fromTower" select="$withTower"/>
<xsl:with-param name="toTower" select="$toTower"/>
<xsl:with-param name="withTower" select="$fromTower"/> </xsl:call-template>
</xsl:if>
</xsl:template>
Résultat
<?xml version="1.0" encoding="UTF-16"?>
<HanoiSolution Size="3" xmlns:xalan=";>
<Move FromTower="A" ToTower="B" />
<Move FromTower="A" ToTower="C" />
<Move FromTower="B" ToTower="C" /> <Move FromTower="A" ToTower="B" />
<Move FromTower="C" ToTower="A" />
<Move FromTower="C" ToTower="B" />
<Move FromTower="A" ToTower="B" /> </HanoiSolution>
n Énoncé
n TD-XSL-recursif
53