/* 

  Global constraint precedence in Picat.

  From Toby Walsh Sliding Constraints (presentation)
  www.cse.unsw.edu.au/~tw/samos/slide.ppt
  page 43ff
  """
    precedence([X1,...Xn]) iff
      min({i | Xi=j or i=n+1}) <
      min({i | Xi=k or i=n+2}) for all j < k
  In other words
    * The first time we use j is before the first time we use k
  E.g. 
    precedence([1,1,2,1,3,2,4,2,3])
  but not
     precedence([1,1,2,1,4])
  
  """

  This model also contain a variant: precedence_all with
  the added constraint that X must contain all values 
  in Min..Max.

  Cf http://hakank.org/picat/value_precede_chain.pi

  The difference is that precedence/1 works on the 
  list X only, whereas value_precede_chain requires an 
  parameter of which values that must be preceded.

  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.

%
% precedence/1
%
go ?=>
  N = 9,
  X = new_list(N),
  X :: 1..4,

  X = [1,1,2,1,3,2,4,2,3],

  precedence(X),

  solve(X),

  println(X),
  fail,

  nl.

go => true.


%
% precedence/1 does _not_ hold for [1,1,2,1,4]
% since 4 is in the list before 3.
%
go2 ?=>
  N = 5,
  X = new_list(N),
  X :: 1..4,

  X = [1,1,2,1,4],

  precedence(X),

  solve(X),

  println(X),
  fail,

  nl.

go2 => true.

%
% precedence_all/1
% X must contain all values in its domain
%
go3 ?=>
  N = 6,
  X = new_list(N),
  X :: 1..4,

  precedence_all(X),

  solve(X),

  println(X),
  fail,

  nl.

go3 => true.



%
% does a contains e?
%
contains(E, A,B) =>
  B :: 0..1,
  sum([A[I] #= E : I in 1..A.len]) #>= 1 #<=> B #= 1.


%
% precedence
% 
% Note: This implementation is different from Walsh's suggestion.
% We can't assume that all values in fd_min(X)..fd_max(X)
% is in X, though if a value (I) exist, then all 1..i-1 must
% be in X.
%
precedence(X) =>
  Len = X.len,
  Max = fd_max_array(X),
  Min = fd_min_array(X),
  % must contain 1 (lb)
  contains(Min, X,1),
  foreach(I in Min..Max)
    contains(I, X,B),
    B #= 1 #=>
    (
       sum([X[J] #= I #/\ 
            sum([(X[K] #<= I) : K in 1..J-1]) #= J-1
       : J in 1..Len]) #>= 1
    ),
    
    foreach(K in Min..I-1)
      contains(K, X, 1)
    end
  end.



% As precedence with the added constraint that all
% values in lb_array(x)..ub_array(x) must be in x.
% Which is the same as saying that is must conform
% to precedence/1 and that the ub_array(x) must be
% in x.
precedence_all(X) =>
  precedence(X),
  Max = fd_max_array(X),
  contains(Max, X,1).



%
% Maximum/minimum domain value in array X
%
fd_max_array(X) = max([fd_max(V) : V in X]).
fd_min_array(X) = min([fd_min(V) : V in X]).