/*

  Pancake sort in Picat.

  See 
   * http://en.wikipedia.org/wiki/Pancake_sorting
   * http://rosettacode.org/wiki/Sorting_algorithms/Pancake_sort


  Model created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/
import util.

main => go.

go => 
   % Nums = [15, 8, 9, 1, 78, 15, 30, 69, 4, 10],
   Nums = (1..9).reverse, % [6,7,8,9,2,5,3,4,1],
   println(nums=Nums),
   Sorted = pancake_sort(Nums),
   println(sorted=Sorted),
   println(nums=Nums),

   nl.

go1 => 
   Nums = [15, 8, 9, 1, 78, 15, 30, 69, 4, 10],
   % Nums = [6,7,8,9,2,5,3,9,4,1],   
   % pancake_sort(Nums),
   pancake_sort2(Nums),
   println(Nums),

   nl.


go2 => 
   foreach(N in 1..5) 
      M = 10**N, 
      printf("M: %d\n", M),
      R1 = [random() mod M  : _I in 1..M],
      time(_S=pancake_sort(R1))
   end,   
   nl.

% comparison, using built-in sort
go3 => 
   foreach(N in 1..5) 
      M = 10**N, 
      println(M),
      R1 = [random() mod M  : _I in 1..M],
      time(_S = sort(R1))
   end,   
   nl.


pancake_sort(L) = L =>
  T = L.len,
  while (T > 1)
    Ix = argmax(L[1..T]),
    if Ix == 1 then
      L := L[1..T].reverse ++ L.slice(T+1),
      T := T-1
    else
      L := L[1..Ix].reverse ++ L.slice(Ix+1)
    end
 end.

% Get the index of the (first) maximal value in L
argmax(L) = MaxIx =>
  Max = max(L),
  MaxIx = [I : I in 1..L.length, L[I] == Max].first.


%
% Port the of the pseudo code at Wikipedia entry on
% Pancake_sorting
% (inplace)
pancake_sort2(Arr) => 
  N = len(Arr),
  while (N > 1)
    MaxDex = max_index(Arr, N),
    flip(Arr, MaxDex),
    flip(Arr, N),
    N := N - 1
  end.

flip(Arr, K) =>
  println($flip(Arr, K)),
  Left = 1,
  while (Left < K)
    Tmp = Arr[Left],
    Arr[Left] := Arr[K],
    Arr[K] := Tmp,
    K := K - 1,
    Left := Left + 1
  end.
    
max_index(Arr, K) = Index =>
  Index = 1,
  foreach(I in 1..K)
    if Arr[I] > Arr[Index] then
      Index := I
    end
  end.