%%% Manipulations sur les listes
subtract(L1,L2,L3):-
	findall(X,(member(X,L1),\+member(X,L2)),L3).

flatten([],[]):-!.
flatten([L1|Rest],L):-
	append(L1,L2,L),
	flatten(Rest,L2).

% supprime les doublons d'une liste
no_doublon([],[]):-!.
no_doublon([Val|LVal],[Val|LVal2]):-
	subtract(LVal,[Val],LVal3),
	no_doublon(LVal3,LVal2).

% liste_num(-L_index,+I,+N):
% L_index est la liste des nombres de I à N 
liste_num([N],N,N):-!.
liste_num([I|L_index],I,N):-
	I2 is I+1,
	liste_num(L_index,I2,N).

% intersection de deux listes
intersect([],_,[]).
intersect([X|L1],L2,[X|L3]):-
	member(X,L2),!,
	subtract(L2,[X],L22),
	intersect(L1,L22,L3).
intersect([X|L1],L2,L3):-
	\+member(X,L2),
	intersect(L1,L2,L3).

% trie la liste L selon l'ordre donnée par la liste Order
list_sort(L,L_out,Order):-
	length(L,N),length(L_out,N),length(Order,N),
	list_sort2(L,L_out,Order).
list_sort2(_,_,[]).
list_sort2(L,[A|L_out],[Num|Order]):-
	nth(Num,L,A),
	list_sort2(L,L_out,Order).
	
% trie la liste par le milieu
list_sort_middle(L_init,L_sorted):-
	list_sort_extrem(L_init,L_aux),
	reverse(L_aux,L_sorted).
		
% trie la liste en commençant par les extrémités
list_sort_extrem([],[]).
list_sort_extrem([A],[A]).
list_sort_extrem([First|Tail],[First|[Last|L_sorted]]):-
	append(Rest,[Last],Tail),
	list_sort_extrem(Rest,L_sorted).


replace_list(I,L,X,L2):-
	length(L,N),
	length(L2,N),
	Deb is I-1,
	Fin is N-I,
	length(Ldeb,Deb),
	length(Lfin,Fin),
	append(Ldeb,[_|Lfin],L),
	append(Ldeb,[X|Lfin],L2).

init_list([],_).
init_list([X|L],X):-
	init_list(L,X).

retirer_liste(I,L1,L2):-
	retirer_I(1,I,L1,L2).
retirer_I(I,I,[_|L1],L1):-!.
retirer_I(C,I,[X|L1],[X|L2]):-
	Cp1 is C+1,
	retirer_I(Cp1,I,L1,L2).
