:- module(_,[serialize0/2],[assertions,regtypes,nativeprops]).

:- entry serialize0(X,Y) : ( numlist(X), var(Y) ).
:- pred serialize0(X,Y) : ( numlist(X), var(Y) ).

serialize0(L,R) :- serialize0_(L,R).

:- pred serialize0_/2 : numlist * var => numlist * list.

serialize0_(L,R) :-
        pairlists(L,R,A),
        arrange0(A,T),
        numbered(T,1,_N).

:- pred pairlists(L,R,A) : numlist(L) => (list(R), aripair_list(A)).

pairlists([X|L],[Y|R],[pair(X,Y)|A]) :-
        pairlists(L,R,A).
pairlists([],[],[]).

:- pred arrange0(L,T) : aripair_list(L) => pairtree(T).

arrange0([X|L],tree(T1,X,T2)) :-
        split0(L,X,L1,L2),
        arrange0(L1,T1),
        arrange0(L2,T2).
arrange0([],void).

:- pred split0(L1,P,L2,L2Tail) : (aripair_list(L1), aripair(P))
                              => (aripair_list(L2), aripair_list(L2Tail)).

split0([pair(X1,N1)|L],pair(X2,Y2),[pair(X1,N1)|L1],L2) :-
        X1<X2,
        !,
        split0(L,pair(X2,Y2),L1,L2).
split0([pair(X1,N1)|L],pair(X2,N2),L1,L2) :-
        X1=:=X2,
        N1=N2,
        !,
        split0(L,pair(X2,N2),L1,L2).
split0([pair(X1,N1)|L],pair(X2,Y2),L1,[pair(X1,N1)|L2]) :-
        X1>X2,
        !,
        split0(L,pair(X2,Y2),L1,L2).
split0([],_1,[],[]).

:- pred numbered(T,N,_) : (pairtree(T), num(N)).

numbered(tree(T1,pair(_X,N1),T2),N0,N) :-
        numbered(T1,N0,N1),
        N2 is N1+1,
        numbered(T2,N2,N).
numbered(void,N,N).

:- regtype numpair/1.

numpair(pair(T1,T2)) :- num(T1), term(T2).

:- regtype numpair_list/1.

numpair_list([]).
numpair_list([X|Xs]) :-
    numpair(X),
    numpair_list(Xs).

:- regtype aripair/1.

aripair(pair(T1,T2)) :- arithexpression(T1), term(T2).

:- regtype aripair_list/1.

aripair_list([]).
aripair_list([X|Xs]) :-
    aripair(X),
    aripair_list(Xs).

:- regtype termpair/1.

termpair(pair(T1,T2)) :- term(T1), term(T2).

:- regtype termpair_list/1.

termpair_list([]).
termpair_list([X|Xs]) :-
    termpair(X),
    termpair_list(Xs).

:- regtype pairtree/1.

pairtree(void).
pairtree(tree(L,Root,R)) :-
        pairtree(L),
        termpair(Root),
        pairtree(R).

:- regtype numlist/1.

numlist([]).
numlist([X|Xs]) :-
    num(X),
    numlist(Xs).
