% Solution to EE 4785 (1996) Homework 2.

%
% Problem 1
%
% Two solutions are shown. The second one is prefered.

%
% Add-to-beginning version of index.
%

% Idea: Search the old list for the element; this is done using
% index1. If found, return as the index the length of the part of the
% list following the element. If the element is not found index1
% fails, the element is added at the beginning of the list, and the
% length of the old list is returned as the index.

len([],0).
len([_|T],L):- len(T,L2),L is L2+1.

idx(List,E,Ind,List):-idx1(List,E,Ind),!.
idx(List,E,Ind,[E|List]):-len(List,Ind).
idx1([E|T],E,I):-len(T,I).
idx1([H|T],E,I):-idx1(T,E,I).

%
% Add-to-end version of index. (More efficient than version above.)
%
% Note that if Index is bound and Element is unbound, Element will be
% bound to appropriate element.

index(Old,Element,Index,New):-index1(Old,Element,0,Index,New).

index1([E|More],E,I,I,[E|More]):-!.
index1([H|More],E,C,I,[H|New]):-
    C2 is C+1,
    index1(More,E,C2,I,New).
index1([],E,I,I,[E]).

%
% Problem 2: Prolog Compression Program
%

pzip(List,z(D,C)):-pzip1(List,[],D,C).

pzip1([],D,D,[]).
pzip1([E|More],Dict1,Dict3,[e(Index,Count)|C2]):-
    ( var(Dict3),Dict=Dict1 ; nonvar(Dict3),Dict=Dict3 ),
    index(Dict,E,Index,Dict2),
    pzip2(E,More,1,Count,Rest),
    pzip1(Rest,Dict2,Dict3,C2).


% pzip2(Elem,OldList,Num,Count,NewList) either 1) binds Count to the
% number of consecutive elements that match Elem and binds
% NewList to the portion of OldList following the last consecutive
% Elem, or 2) creates a list, OldList, which consists of Count
% occurrences of Elem followed by NewList.

pzip2(E,Rest,C,T,Rest):-number(T),T=C,!.

pzip2(E,[E|More],C,Total,Rest):-!,
    C2 is C+1,
    pzip2(E,More,C2,Total,Rest).

pzip2(E,Rest,T,T,Rest).