%
% Seance 4 - Complexite calculatoire
%

% Exercice 2 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
declare
fun {Nth L N}
   if N==1 then L.1 else {Nth L.2 N-1} end
end

% Exercice 3 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
declare
fun {ShiftLeft L}
   case L of H|T then
      H|{ShiftLeft T}
   else [0] end
end
fun {ShiftRight L} 0|L end

% Exercice 4 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
declare
proc {Turlututu T}
   N={Width T}
   proc {Loop1 I}
      proc {Loop2 J}
	 if J=<N then {Browse T.I} {Loop2 J+1} end
      end
   in
      if I=<N then {Loop2 I} {Loop1 I+1} end
   end
in
   {Loop1 1}
end

{Turlututu t(42 17 23)}

% Exercice 6 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
declare
%% insere X dans la liste triee Ys
fun {Insert X Ys}
   case Ys
   of nil  then [X]
   [] Y|Yr then if X=<Y then X|Ys else Y|{Insert X Yr} end
   end
end
%% insere les elements de Xs dans la liste triee Ys
fun {InsertList Xs Ys}
   case Xs
   of nil  then Ys
   [] X|Xr then {InsertList Xr {Insert X Ys}}
   end
end
%% renvoie la liste Xs triee
fun {InsertionSort Xs}
   {InsertList Xs nil}
end

% Exercice 7 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
declare
fun {IsInTuple T X}
   N={Width T}
   fun {Loop I}
      if I>N then false else
	 if T.I==X then true else {Loop I+1} end
      end
   end
in
   {Loop 1}
end

declare
fun {IsInOrderedTuple T X}
   %% renvoie true si X est egal a T.K, pour un K tel que I=<K=<J
   fun {FindBetween I J}
      if I==J then X==T.I
      else local K in
	      K=(I+J) div 2   % I=<K<J
	      if X=<T.K then {FindBetween I K} else {FindBetween K+1 J} end
	   end
      end
   end
in
   {FindBetween 1 {Width T}}
end

% Exercice supplementaire 1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
declare
fun {MeasureTime P}
   T0 T1
in
   T0={Property.get time} {P} T1={Property.get time}
   (T1.user+T1.system)-(T0.user+T0.system)
end

{Browse {MeasureTime proc {$}
			{Browse {InsertionSort {List.number 1 1000 1}}}
		     end}}

{Browse {Tuple.make foo 7}}   %% affiche foo(_ _ _ _ _ _ _)

% Exercice supplementaire 3 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
declare
fun {Tails L}
   case L
   of nil then nil
   [] X|T then L|{Tails T}
   end
end

{Browse {Tails [a b c]}}