Estimer une position d'insertion
Bonjour,
Tout d'abord, désolé pour ce titre peu explicite, j'espère qu'il le deviendra après l'exposé du problème.
Dans le cadre de la création d'un document DOM (XML, tout ça) je voudrais calculer (ou estimer) l'endroit où doit être inséré un nouvel élément dans une liste d'éléments existants en fonction de la DTD associée au parent.
Exemple :
Un élément test déclare la DTD suivante :
Code:
<!ELEMENT test (sub, (title, sub, text)*)
Etant donné que je suis en création, il est possible de n'avoir qu'une partie des éléments, comme par exemple :
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| <test>
<title/>
<sub/>
</test>
<!-- ou bien -->
<test>
<sub/>
<text/>
</test>
<!-- ou encore -->
<test>
<sub/>
<title/>
</test> |
Si je veux rajouter l'élément sub dans chacun de ces trois cas, je n'ai normalement qu'une seule solution "optimale" : celle qui me donne la DTD la plus valide possible :
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| <test>
<sub/><!-- nouvellement inséré -->
<title/>
<sub/>
</test>
<!-- ou bien -->
<test>
<sub/>
<sub/><!-- nouvellement inséré -->
<text/>
</test>
<!-- ou encore -->
<test>
<sub/>
<title/>
<sub/><!-- nouvellement inséré -->
</test> |
Ou, pour décrire ça de façon moins verbeuse et surtout plus proche de mon code actuel :
Code:
1
2
3
| [title, sub] -> [sub, title, sub]
[sub, text] -> [title, sub, sub]
[sub, title] -> [title, sub, sub] |
Le truc bien entendu c'est que je n'arrive à rien. :aie:
J'avais testé plusieurs algos dont le dernier en date ressemblait à ça :
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| fonction rechercheIndexPossible(filsActuels:Liste, nouveauFils:Element) : Entier {
dernierFils:Element;
pour (i := filsActuels.length ; i >= 0; i--) {
si (nouveauFils estInsérable entre filsActuels[i] et dernierFils) {
// on ajoute après l'élément actuel
return i + 1;
}
}
// le nouveau fils n'est insérable après aucun élément actuel, on teste s'il l'est avant le premier :
si (nouveauFils estInsérable avant dernierFils) {
return 0;
}
// impossible de l'insérer
return -1;
} |
Le problème c'est qu'en déroulant l'algo sur les exemple que j'ai donné, on voit tout de suite que ça ne fait pas ce que je veux.
Du coup je n'ai plus aucune idée de comment estimer l'index d'insertion pour que ça donne au moins un état qui soit compatible avec la DTD (si on considère qu'on ajoute suffisament d'éléments pour ça).
Je suppose qu'il faut passer par du backtracking pour ça mais mes cours d'IA remontent à loin et je serai actuellement incapable de faire un tel algo en partant de zéro.
Du coup si vous avez des pistes à me proposer ou un début d'algo, je suis preneur !
Merci d'avance,
Loceka.
