/* 
 * Union-Find algorithm in CHR(chr)
 * Author: Seiji OGAWA, 2011-03-31
 * 
 * Examples are taken from:
 *   http://dtai.cs.kuleuven.be/CHR/examples.shtml
 *
 * If you'd like to change parameter N, 
 * please change the 1st argument of query: start("N").
 *
 */

:- module(unionfind_opt, [make/1,union/2,find/2,root/2,(~>)/2]).
:- use_module(library(chr)).

:- op(700, xfx, '~>').

%% Syntax for SWI / SICStus 4.x
:- chr_constraint
    make(+element),
    find(?element,?element),
    union(+element,+element),
    (?element) ~> (+element),
    link(+element,?element),
    root(+element,?natural),
    start(+int),
    i(+int, +int),
    j(+int, +int),
    time(+float),
    list(+), l(+).

:- chr_option(optimize, full).

:- chr_type element == dense_int.          % efficient: arrays
%:- chr_type element == int.                % less efficient: hashtables


make     @ make(A) <=> root(A,0).

union    @ union(A,B) <=> find(A,X), find(B,Y), link(X,Y).

findNode @ A ~> B, find(A,X) <=> find(B,X), A ~> X.
findRoot @ root(B,_) \ find(B,X) <=> X=B.

linkEq   @ link(A,A) <=> true.  
linkLeft @ link(A,B), root(A,NA), root(B,NB) <=> NA>=NB | 
                B ~> A, NA1 is max(NA,NB+1), root(A,NA1).
linkRight@ link(B,A), root(A,NA), root(B,NB) <=> NA>=NB |
                B ~> A, NA1 is max(NA,NB+1), root(A,NA1).

start(S) <=>
  S > 0 |
  cputime(X),
  i(S, 0), 
  list([]),
  cputime(Y),
  Z is Y-X,
  time(Z).

i(M, I), list(H) <=> M > I | I1 is I+1, i(M, I1), list([I|H]).
i(M1,M2), list(H) <=> M1==M2 | l(H).
l([X, Y|R]) <=> l([X|R]), root(Y, 0), union(Y, X).
l([X]) <=> root(X, 0).