%
% Ex.4 on-line median estimation
%
% Haixun Wang, hxwang@cs.ucla.edu

%%
database( {
	q(P:float, X:integer)
} ).

%%
export pipe($D, $LO, LN).
export p(X).
%%

p(median<X>)<-q(P,X).

single(median, X, (1,[nil, X])).
multi(median, X,  (C2, OldL), (C, L))<-
    pipe(X, OldL, L),
    C=1+C2,
    C<600.

return(median, X, (C1, OldL), (C1, OldL))<-
    X~=nil,
    mod(C1,10).


mod(X,X).
mod(X,Y)<-X>Y, mod(X-Y,Y).

return(median, nil, (C,OldL), V)<-
    weighted_avg(OldL,A,C), V=A/C.

weighted_avg([],0, 0).
weighted_avg([X,Y|Z], V, C)<-
    weighted_avg(Z,A,B),
    if (X = nil, Y=nil then V=A*3, C=B*3
	else if (X=nil  then V=A*3+Y, C=B*3+1
	     else V=A*3+X+Y, C=B*3+2)).

pipe(D, [nil,nil|Y], [nil,D|Y]).
pipe(D, [nil,X|Y], [X,D|Y]) <- X ~= nil, X>=D.
pipe(D, [nil,X|Y], [D,X|Y]) <- X ~= nil, D>X.
pipe(D, [X,Y], [nil, nil, nil, Z]) <-
    X ~= nil,
    median(D,X,Y,Z).

pipe(D, [X,Y|T], L)<-
    X ~= nil,
    median(D,X,Y,M),
    pipe(M, T, NT),
    L=[nil, nil |NT].
median(D,X,Y,Z)<-
    if (D>X then Z=X
    else if (D>Y then Z=D
	else Z=Y)
    ).