/* 

  Global constraint balance in Picat.

  From Global Constraint Catalogue:
  http://www.emn.fr/x-info/sdemasse/gccat/Cbalance.html
  """
  BALANCE is equal to the difference between the number of occurrence of the 
  value that occurs the most and the value that occurs the least within the 
  collection of variables VARIABLES
  
  Example
     (2,<3,1,7,1,1>)

  In this example, values 1, 3 and 7 are respectively used 3, 1 and 1 times. 
  The balance constraint holds since its first argument BALANCE is assigned to 
  the difference between the maximum and minimum number of the previous 
  occurrences (i.e., 3−1).
  """


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

*/


import cp.

main => go.

go ?=>

  N = 5,
  M = 7,  
  X = new_list(N),
  X :: 1..M,

  Gcc = new_list(M),
  Gcc :: 0..N,

  Bal :: 0..M,

  %X = [3,1,7,1,1],
  balance(Bal, X),
  Bal #= 3,
  
  global_cardinality2(X, Gcc),


  Vars = X ++ Gcc ++ [Bal],
  solve(Vars),

  println(x=X),
  println(bal=Bal),
  println(gcc=Gcc),
  nl,

  fail,
  
  nl.

go => true.


balance(Bal, X) =>
   fd_min_max(X[1],Min,Max),
   Counts = new_list(Max),
   Counts :: 0..Max,
   XMin :: 1..Max,
   XMax :: Min..Max,
   global_cardinality2(X, Counts),
   XMax #= max(Counts),
   min_except_0(XMin, Counts),
   Bal #= XMax - XMin. % get the difference (the "balance")


%
% global_cardinality(A, Gcc)
%
% This version is bidirectional but limited:
%
% Both A and Gcc are (plain) lists.
%  
% The list A can contain only values 1..Max (i.e. the length of Gcc).
% This means that the caller must know the max values of A.
% Or rather: if A contains another values they will not be counted.
% 
global_cardinality2(A, Gcc) =>
   Len = length(A),
   Max = length(Gcc),
   Gcc :: 0..Len,
   foreach(I in 1..Max) count(I,A,#=,Gcc[I]) end.



%
% Ensure that the minumum value (> 0) is MinVal.
%
min_except_0(MinVal,X) =>
  Len = X.length,
  % ensure that MinVal is a value in X
  I :: 1..Len,
  element(I, X,MinVal),
  foreach(J in 1..Len)
    (X[J] #= 0) #\/ (MinVal #=< X[J]) 
  end.