<div class="notebook">

<div class="nb-cell markdown" name="md1">
# Liste doublement chaînée (avec exemple de tri)

Une liste 1 2 3 4 5 sera représentée avec deux variables, contenant les éléments 1, 2, 3, ... avec dans la première liste, selon l'avancée dans le parcours de la liste, les éléments déjà passés (RevPrev) en ordre inverse, et dans la seconde liste les éléments à venir (Next). Exemple, si le parcours de la liste est arrivé à l'élément 3 : 
* RevPrev : [2, 1]
* Next : [3, 4, 5] 

## Déplacement dans une liste doublement chainée
Avancer d'un élément dans la liste consiste donc à faire passer un élément de Next dans RevPrev.
</div>

<div class="nb-cell program" name="p1">
%% avance(RevPrev0,Next0,  RevPrev1,Next1) vrai ssi {RevPrev0,Next0} et {RevPrev1,Next1} représentent la même liste
%%% la liste 1 représentant cette liste avancée d'un élément par rapport à la liste 0
avance(RevPrev0,Next0,  RevPrev1,Next1):-
    eq(Next0,[E|L]),
    eq(Next1,L),
    eq(RevPrev1,[E|RevPrev0]).
</div>

<div class="nb-cell markdown" name="md2">
soit :
</div>

<div class="nb-cell program" data-background="true" name="p2">
avance(RevPrev,[E|Next],  [E|RevPrev],Next).
</div>

<div class="nb-cell query" name="q1">
avance([2,1],[3,4,5],  RevPrev,Next).
</div>

<div class="nb-cell markdown" name="md3">
et pour reculer, il faut faire l'inverse
</div>

<div class="nb-cell program" data-background="true" name="p3">
recule([E|RevPrev],Next,  RevPrev,[E|Next]).
</div>

<div class="nb-cell query" name="q2">
recule([2,1,0],[3,4,5],  RevPrev,Next).
</div>

<div class="nb-cell markdown" name="md4">
## Insertion (dans une liste ordonnée croissante)
Il s'agit d'introduire un element E dans une liste RevPrev0, Next0 donnée, le premier élément de cette liste sera en début de Next0, le précédent élément (liste doublement chainée) sera en début de RevPrev0, en notant N et P ces éléments, on doit donc introduire E dans [P|RevPrev], [N|Next], avec quelques cas particulier à prendre en compte : si l'on est au début de la liste (RevPrev0=[]) ou en fin de liste (Next0=[]), le tout en prenant en compte l'ordre (croissant) des éléments de la liste (ordre à conserver pour l'insertion).
</div>

<div class="nb-cell program" data-background="true" name="p4">
%% insere(E,  RevPrev,Next,  RevPrevAvecE,NextAvecE) est vrai ssi il y a eu insertion (en respectant l'ordre)
%% de E dans RevPrev,Next pour obtenir RevPrevAvecE, NextAvecE
insere(E,  [],[],  [],[E]). 
insere(E,  [],[N|Next],  [],[E,N|Next]) :- 
    E =&lt; N.
insere(E,  [P|RevPrev],Next,  RevPrevResult,NextResult) :- 
    E &lt; P, 
    insere(E,  RevPrev,[P|Next],  RevPrevResult,NextResult).
insere(E,  [P|RevPrev],[N|Next],  [P|RevPrev],[E,N|Next]) :- 
    E &gt;= P,
    E =&lt; N.
insere(E,  RevPrev,[N|Next],  RevPrevResult,NextResult) :- 
    E &gt; N, 
    insere(E,  [N|RevPrev],Next,  RevPrevResult,NextResult).
insere(E,  [P|RevPrev],[],  [E,P|RevPrev],[]) :- 
    E &gt;= P.
</div>

<div class="nb-cell query" name="q3">
insere(3,[4,2,0],[6,8,10],RevPrev,Next).
</div>

<div class="nb-cell markdown" name="md5">
## Tri
</div>

<div class="nb-cell markdown" name="md6">
Pour obtenir un tri, il reste à enchaîner les insertions ... On pourra supposer que la liste à trier est donnée sous forme usuelle (liste simple, pas doublement chaînée) : L.
Remarque : pour en faire une liste doublement chaînée, il suffit de prendre le couple [], L.
</div>

<div class="nb-cell program" data-background="true" name="p5">
%% tri(L,  RevPrev,Next) est vrai ssi L est une liste simple et RevPrev,Next la même liste (doublement chainée) 
%% RevPrev,Next est triée par ordre croissant
tri([],  [],[]).
tri([E|L],  RevPrev,Next) :-
    tri(L,  RevPrev0,Next0),
    insere(E,  RevPrev0,Next0,  RevPrev,Next).
</div>

<div class="nb-cell query" name="q4">
tri([4,1,2,1,8,3,2,5,0],RevPrev,Next).
</div>

<div class="nb-cell markdown" name="md7">
## Supplément ...
Pour revenir dans le monde des listes habituelles, il reste à ajouter un petit prédicat pour "traduire" les listes doublement chaînées en listes usuelles. Pour cela il y a un cas simple : quand la liste des prédécésseurs est vide. Si ce n'est pas le cas, on peut s'y ramener en reculant dans la liste.
</div>

<div class="nb-cell program" data-background="true" name="p6">
%% versListeUsuelle(RevPrev,Next,  L) est vrai ssi L est une liste simple obtenue à partir de RevPrev,Next (doublement chainée)
versListeUsuelle([],L,   L).
versListeUsuelle([R|RevPrev],Next,  L) :-
    versListeUsuelle(RevPrev,[R|Next],   L).
</div>

<div class="nb-cell query" name="q5">
versListeUsuelle([3,2,1],[4,5,6],   L).
</div>

</div>