/* 

  Averages/Median in Picat.

  From Rosetta Code:
  http://rosettacode.org/wiki/Averages/Median
  """
  Write a program to find the median value of a vector of floating-point numbers. The 
  program need not handle the case where the vector is empty, but must handle the case 
  where there are an even number of elements.

  There are several approaches to this. One is to sort the elements, and then pick the one 
  in the middle. Sorting would take at least O(n logn). Another would be to build a priority 
  queue from the elements, and then extract half of the elements to get to the middle one(s). 
  This would also take O(n logn). The best solution is to use the selection algorithm to find 
  the median in O(n) time. 
  """

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

*/


% import util.
% import cp.


main => go.



go => 

   Lists = [
             [1.121,10.3223,3.41,12.1,0.01],
             1..10,
             1..11,
             [3],
             [],
             [4.1, 5.6, 7.2, 1.7, 9.3, 4.4, 3.2],
             [4.1, 7.2, 1.7, 9.3, 4.4, 3.2],
             [5.1, 2.6, 6.2, 8.8, 4.6, 4.1],
             [5.1, 2.6, 8.8, 4.6, 4.1]],

   foreach(Median in [median, median1, median2, median3])
      writeln(Median),
      foreach(List in Lists) 
         writeln([List, apply(Median,List)])
      end,
      nl
   end,

   nl.

%
% The traditional approach
%
median([])  = undef.
median([X]) = X.
median(L)   = Median =>
   Len = L.length,
   H = Len // 2,
   LL = sort(L), 
   Median=cond(Len mod 2 == 1, LL[H+1], avg([LL[H],LL[H+1]])).


% Variant on median/1: Using conditions instead of cond/3.
median1([])  = undef.
median1([X]) = X.
median1(L)   = LL[(L.length//2)+1], L.length mod 2 == 1 =>  LL = sort(L).
median1(L)   = avg([LL[H],LL[H+1]]) => H = L.length // 2, LL = sort(L).



%
% A variant: shave off the endpoints.
%
median2([])    = undef.
median2([X])   = X.
median2([X,Y]) = avg([X,Y]).
median2(L)     = median2_shrink(L.sort()).
% assume a sorted list
median2_shrink(L) = median2([L[I] : I in 2..L.length-1]).


%
% Another version, kind of same approach as median2/1:
% If there are more than 2 elements, remove the min and max values,
% and then recurse. No need to sort but it need to go through the 
% lists (Len - 2)*2 times to find the min and max.
%
median3([])    = undef.
median3([X])   = X.
median3([X,Y]) = avg([X,Y]).
median3(L) = L.delete_min().delete_max().median3().

delete_min(L) = delete(L,min(L)).
delete_max(L) = delete(L,max(L)).