/*----------------------------------------------------------*/
/*  K-Nearest Neighbour Algorithm (SICStus Prolog 3)        */
/*----------------------------------------------------------*/
/*  (C) 1998 Zdravko Markov                                 */
/*----------------------------------------------------------*/
knn(X,K,Class) :-
    findall(D-C,(example(_,C,Y),dist(X,Y,D)),Ds),
    keysort(Ds,L),
    first(K,L,FK),
    count(FK,CF),
    max(CF,_-Class).    
    
dist([],[],0).
dist([X|T],[X|V],N) :- !, 
    dist(T,V,N).
dist([_|T],[_|V],N) :- 
    dist(T,V,M), 
    N is M+1.

first(0,_,[]).
first(N,[X|T],[X|V]) :-
    M is N-1,
    first(M,T,V).

count([],[]).
count([_-C|T],[N-C|R]) :-
    delc(_-C,T,V,N),
    count(V,R).

delc(_,[],[],1).
delc(_-X,[_-X|T],V,N) :- !,
    delc(_-X,T,V,M),
    N is M+1.
delc(X,[Y|T],[Y|V],N) :-
    delc(X,T,V,N).

max([X],X) :- !.
max([M-X|T],N-Y) :- 
    max(T,K-Z), 
    (M>K,N-Y=M-X;N-Y=K-Z), !.