/* 

  Global constraint same_and_global_cardinality_low_up in Picat.

  From Global Constraint Catalogue
  http://www.emn.fr/x-info/sdemasse/gccat/Csame_and_global_cardinality_low_up.html
  """
  Constraint

      same_and_global_cardinality_low_up(VARIABLES1,VARIABLES2,VALUES)

  Purpose

      The variables of the VARIABLES2 collection correspond to the variables 
      of the VARIABLES1 collection according to a permutation. In addition, 
      each value VALUES[i].val (1<=i<=|VALUES|) should be taken by at 
      least VALUES[i].omin and at most VALUES​[i]​.omax variables of the 
      VARIABLES1 collection.

  Example
      (
      <1,9,1,5,2,1>,
      <9,1,1,1,2,5>,
      <
      val-1	omin-2	omax-3,
      val-2	omin-1	omax-1,
      val-5	omin-1	omax-1,
      val-7	omin-0	omax-2,
      val-9	omin-1	omax-1
      >
      )

      The same_and_global_cardinality_low_up constraint holds since:
      * The values 1, 9, 1, 5, 2, 1 assigned to |VARIABLES1| correspond 
        to a permutation of the values 9, 1, 1, 1, 2, 5 assigned to 
        |VARIABLES2|.     
      * The values 1, 2, 5, 7 and 6 are respectively used 3 (2<=3<=3), 
        1 (1<=1<=1), 1 (1<=1<=1), 0 (0<=0<=2) and 1 (1<=1<=1) times.
  """


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

*/

import cp.

main => go.

go =>
  N = 6,
  M = 5,


  Variables1 = new_list(N),
  Variables1 :: 0..9,

  Variables2 = new_list(N),
  Variables2 :: 0..9,

  Values = new_array(M, 3),
  Values :: 0..9,

  % Here I assume that Value is a constant array.
  % However, the constraint can handle a free Values
  % array as well
  Values = {{1,2,3},
            {2,1,1},
            {5,1,1},
            {7,0,2},
            {9,1,1}},

  Variables1 = [1,9,1,5,2,1],
  % Variables2 = [9,1,1,1,2,5],

  same_and_global_cardinality_low_up(Variables1,Variables2, Values),

  Vars = Variables1 ++ Variables2 ++ Values.vars,
  solve(Vars),

  println(variables1=Variables1),
  println(variables2=Variables2),
  println("values:"),
  foreach(Row in Values)
    println(Row.to_list)
  end,
  nl,
  
  fail,
  
  nl.


global_cardinality_low_up_table(Variables,
                                Values) =>

  % If we let Values to be free, we must ensure
  % ensure that all values in Variables are in Values   
  foreach(V in Variables)
    sum([V #= Values[I,1] : I in 1..Values.len]) #= 1
  end,
  % Santity: The low up must be ordered
  foreach(I in 1..Values.len)
    Values[I,2] #<= Values[I,3],
    Values[I,3] :: 0..Variables.len
  end,
  % Symmetry breaking
  increasing_strict([Values[J,1] : J in 1..Values.len]),     

  % Here is the constraint proper.
  foreach(I in 1..Values.len)
      Sum #>= Values[I,2],
      Sum #<= Values[I,3],
      Sum #= sum([Variables[J] #= Values[I,1]
                 : J in 1..Variables.len
                 ])
  end.


same_and_global_cardinality_low_up(Variables1,Variables2, Values) =>
  same(Variables1, Variables2),
  global_cardinality_low_up_table(Variables1, Values),
  global_cardinality_low_up_table(Variables2, Values).

%
% same(VARIABLES1, VARIABLES2)
%
same(Variables1, Variables2) =>
   Len = Variables1.len,

   Ub = max([fd_max(V) : V in Variables1]),
   
   GCC = new_list(Ub+1),
   GCC :: 0..Len,

   global_cardinality2(Variables1, GCC),
   global_cardinality2(Variables2, GCC).


global_cardinality2(A, Gcc) =>
   Len = length(A),
   Max = length(Gcc),
   Gcc :: 0..Len,
   foreach(I in 0..Max-1) count(I,A,#=,Gcc[I+1]) end.