N:integer        := 0
V:array<integer> := make_array(N,integer,-1)
D:array<set>     := make_array(N,set,{})
CD:array<set>    := make_array(N,set,{})
RP:array<any> := make_array(N,any,{})                // resume point
C:set            := {}

CHECKS:integer   := 0
NODES:integer    := 0

CONSISTENT:boolean := true

[make_array(m:integer,n:integer) : array
 -> let v :=  make_array(m,any,{})
    in (for i in (1 .. m)
        v[i] := make_array(n,integer,-1),
        v)]

[make_array(l:integer,m:integer,n:integer) : array
 -> let v := make_array(l,any,{})
    in (for i in (1 .. l)
        v[i] := make_array(m,n),
        v)]

[stats() : void
 -> list("nodes",NODES,"checks",CHECKS)]

[reset(i:integer) : void
 -> V[i]  := -1,
    CD[i] := copy(D[i])]
//
// reset a variable
//

[reset() : void
 -> CHECKS := 0,
    NODES  := 0,
    CONSISTENT := true,
    RP := make_array(N,N,size(D[1])),
    for i in (1 .. N) reset(i)]
//
// reset everything
// assume uniform domain size, because I'm lazy
//

[look(i:integer) : void
 -> list(i,V[i],CD[i],D[i])]
//
// look at the ith variable, showing its
// index, value, and domain
//

[look() : boolean
 -> for i in (1 .. N) printf("\n~S",look(i)),
    CONSISTENT]
//
// look at everything
//

[getRelation(h:integer,i:integer,c:set) : set
 -> {z in c | (z[2] = h & z[3] = i)}]

[check(c:tuple,x:integer,y:integer) : boolean
 -> //[4] check(~S,~S,~S) // c,x,y,
    let l := list{c[k] | k in (4 .. length(c))} /+ list(x,y)
    in (CHECKS := CHECKS + 1,apply(c[1],l))]
//
// This now allows us binary constraints that involve
// more than just 2 arguments. For example, nqueens
// need to know rows and columns for two positions.
// We can now also produce extensional constraints as 
// sets of goods or nogoods
//

[check(h:integer,x:integer,i:integer,y:integer,c:set) : boolean
 -> let f := getRelation(h,i,c)
    in (if (size(f) = 0) 
          true           // no relation exists, therefore compatible
        else
            (//[3] check(~S, v[~S] = ~S & v[~S] = ~S) // f[1][1],h,x,i,y,
             check(f[1],x,y)))]


[succ(x:integer,l:list) : integer
 -> if (l = nil) -1
    else if (l[1] > x) l[1]
         else succ(x,cdr(l))]
//
// find the successor of x in ordered list l
// NOTE: in the ac2001 algorithms we assume 
//       we can do this in O(1)
//

[existsY(d:array<set>,c:tuple,i:integer,j:integer,x:integer) : boolean
 -> let y := RP[i][j][x]
    in (if (y % d[j])
          true
        else let supported := false
             in (y := succ(y,list!(d[j])),
                 while (y > 0 & not(supported))
                  (if check(c,x,y)
                    (RP[i][j][x] := y,
                     supported := true)
                   else y := succ(y,list!(d[j]))),
                  supported))]
//
// find the first value y in d[j] that supports x in d[i]
// if found return true otherwise false
//

[revise(d:array<set>,c:tuple,i:integer,j:integer) : boolean
 -> //[3] revise(~S): d[~S] = ~S, d[~S] = ~S// c,i,d[i],j,d[j],
    let revised := false
    in (for x in copy(d[i])
          (if not(existsY(d,c,i,j,x))
            (delete(d[i],x),
             revised := true)),
         CONSISTENT := d[i] != {},
         //[3] revised(~S): d[~S] = ~S// c,i,d[i],
         //[3] ---------//,
         revised)]

[ac3(d:array<set>,constraints:set) : boolean
 -> //[3] ac3(~S) // constraints,
    let Q := copy(constraints)
    in (while (Q != {} & CONSISTENT)
        let c := Q[1],
            i := c[2],
            j := c[3]
        in (delete(Q,c),
            if revise(d,c,i,j)
               Q := Q U {z in constraints | z[3] = i})),
    CONSISTENT]