%   File   : ASSOC.PL
%   Author : R.A.O'Keefe
%   Updated: 9 November 1983
%   Rewritten: K Johnson 25-5-87
%   Purpose: Binary tree implementation of "association lists".

%   Note   : the keys should be ground, the associated values need not be.

%   This stores association pairs in a tree structure; the empty tree
%   is just "t". For example, to store the pair "foo-moo"  in a hitherto
%   empty tree
%   put_assoc(foo,t,moo,T)
%   To add to tree T the pair "bee-flea" giving the tree U
%   put_assoc(bee,T,flea,U)
%   Test data are at the end of the file to help

% Create a new tree by putting a new pair into an existing one.
% Call: put_assoc(+Key,+Old_tree,?Value,-New_Tree).

put_assoc(Key, t(Key,_,L,R), Val, t(Key,Val,L,R)).  % Key = K. Replace.

put_assoc(Key, t(K,V,L,R), Val, t(K,V,Tree,R)) :-   % Key < K
    Key @< K,
    !,
    put_assoc(Key,L,Val,Tree).

put_assoc(Key, t(K,V,L,R), Val, t(K,V,L,Tree)) :-   % Key > K
    !,
    put_assoc(Key,R,Val,Tree).

put_assoc(Key, t, Val, t(Key,Val,t,t)).         % Empty tree

% get_assoc gets the Val associated with Key in a tree.
%   get_assoc(foo,+Tree,-V)
% will find the value associated with "foo" in "Tree".
% If Key is uninstantiated then get_assoc will work sensibly for the calling
% patterns
%   get_assoc(-Key,+Tree,-V)
% which will find every K-V pair on back tracking and
%   get_assoc(-Key,+Tree,+V)
% although the pattern get_assoc(-K,+T,+V) is *time consuming*.

get_assoc(Key, t(K,Val,_,_), Val) :-
    nonvar(Key),
    Key == K,
    !.

get_assoc(Key, t(K,_,L,_), Val) :-
    nonvar(Key),
    Key @< K,
    !,
    get_assoc(Key,L,Val).

get_assoc(Key, t(_,_,_,R), Val) :-
    nonvar(Key),
    !,
    get_assoc(Key,R,Val).


get_assoc(Key,t(_,_,L,_), Val) :-
    var(Key),
    get_assoc(Key,L,Val).

get_assoc(Key,t(K,Val,_,_), Val) :- % Note: if you put t(Key,Val...) in the
    var(Key),           % title line here, then var(Key) will
    Key = K.            % fail: the match instantiates it.

get_assoc(Key,t(_,_,_,R),Val) :-
    var(Key),
    get_assoc(Key,R,Val).

%
% assoc_to_list(+Assoc,-List)
% Converts the tree to a list of the form [Key1-Val1, Key2-Val2...]
% The other mode is possible: see below.
%

assoc_to_list(Assoc, List) :-
    var(List),
    assoc_to_list(Assoc, List, []).

assoc_to_list(t(Key,Val,L,R), List, Rest) :-
    var(List),
    assoc_to_list(L, List, [Key-Val|More]),
    assoc_to_list(R, More, Rest).

assoc_to_list(t, List, L) :-
    var(List),
    List = L.

%
% assoc_to_list(-Assoc,+List)
% produces the shortest possible Assoc tree
%

assoc_to_list(Assoc,List) :-
    var(Assoc),
    keysort(List, Keys),
    length(Keys, N),
    list_to_assoc(N, Keys, Assoc, []).


list_to_assoc(0, List, t, List) :-
    !.

list_to_assoc(N, List, t(Key,Val,L,R), Rest) :-
        A is (N-1) div 2,
        Z is (N-1)-A,
        list_to_assoc(A, List, L, [Key-Val|More]),
        list_to_assoc(Z, More, R, Rest).

%
% map_assoc(+Pred,+In_tree,-Out_tree)
% Calls Pred(X,Y) for every X on the tree.
% Constructs a tree of Ys.
%

map_assoc(Pred, t(Key,Val,L0,R0), t(Key,Ans,L1,R1)) :- !,
    functor(Term,Pred,2),
    arg(1,Term,Val),
    arg(2,Term,Ans),
    call(Term),
    map_assoc(Pred, L0, L1),
    map_assoc(Pred, R0, R1).

map_assoc(_, t, t).

% % Test
% 
% insert(K,V) :-            % Insert pair K,V into the recorded
%   recorded(tree,T,Ref),       % tree. Note, the code above does not
%   put_assoc(K,T,V,T1),        % record the tree anywhere. You have to
%   erase(Ref),         % do it yourself.
%   record(tree,T1,_).
% 
% test(_) :-                % Test(T) will build up a small tree
%   recorded(tree,_,Ref),       % Remove any existing tree(s)
%   erase(Ref),
%   fail.
% 
% test(T) :-
%   record(tree,t,_),       % Create an empty tree
%   insert(mean, bean),     % Hang some rhyming pairs off it
%   insert(hoe,go),
%   insert(foo,you),
%   insert(bee,flea),
%   insert(jack,stack),
%   insert(nick,quick),
%   insert(why,sky),
%   insert(word,bird),
%   insert(funny,money),
%   insert(ping,sing),
%   recorded(tree,T,_).
%                   % Usage of assoc_to_list
% balance_tree(T,B) :-          % This balances the tree +T giving -B
%   assoc_to_list(T,L),     % If you need balanced trees, of course,
%   assoc_to_list(B,L).     % there are better ways than this
% 
% % a test for map_assoc: the "abbrev" predicate deletes all letters
% % in a name after the third
% 
% test_map(T,U) :-      % Call test_map(-T,-U)
%   recorded(tree,T,_),
%   map_assoc(abbrev,T,U).
% 
% abbrev(Long,Cut) :-
%   name(Long,Letters),
%   abbrev_list(3,Letters,Fewer_letters),
%   name(Cut,Fewer_letters).
% 
% abbrev_list(_,[],[]) :- !.
% abbrev_list(0,_,[]) :- !.
% abbrev_list(N,[H|T],[H|U]) :-
%   M is N - 1,
%   abbrev_list(M,T,U).