/*

  Decomposition of global constraint global_cardinality in Picat.

  See Global Constraint Catalog
  http://www.emn.fr/x-info/sdemasse/gccat/Cglobal_cardinality.html
  """
  Example:
  <3,3,8,6>,
   (val-3 noccurrence-2,
    val−5 noccurrence-0,
    val-6 noccurrence-1)

  The global_cardinality constraint holds since values 3, 5 and 6 
  respectively occur 2, 0 and 1 times within the collection 
  <3,3,8,6> and since no constraint was specified for value 8.
  """

  Notes: 
     - The version here is limited. See below for details.
     - Picat has already a global_cardinality/2, but the details
       of the parameters are different.


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

*/

import cp.


main => go.

go ?=>
   N = 5,
   A = new_list(N),
   A :: 1..N,
   % A = [1,2,1,1,1],

   GCC = new_list(N),
   GCC :: 0..N,
   global_cardinality2(A, GCC),

   Vars = A ++ GCC,
   solve(Vars),

   writeln(a=A),
   writeln(gcc=GCC), 
   nl,
   fail.

go => true.

% The same problem using Picat's built-in global_cardinality
go2 =>
   N = 5,
   A = new_list(N),
   A :: 1..N,
   % A = [1,2,1,1,1],

   V = new_list(N),
   V :: 0..N,
    
   V[1] :: [4],
   V[2] :: [1],
   V[3] :: [0],
   V[4] :: [0],
   V[5] :: [0],
   GCC = $[1-V[1],
           2-V[2],
           3-V[3],
           4-V[4],
           5-V[5]],
   global_cardinality(A, GCC),

   Vars = A ++ GCC,
   solve(Vars),

   writeln(a=A),
   writeln(gcc=GCC), 
   nl,
   fail.

%
% Both A and Gcc are lists.
% 
% This version is bidirectional but limited:
% 
% 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.