%   File   : MAP.PL
%   Author : R.A.O'Keefe
%   Updated: 7 June 1984
%   Purpose: Implement finite maps.
%   Needs  : list_to_assoc from ASSOC.PL, ord_disjoint from ORDSET.PL

/*  A finite map is a function from terms to terms with a finite
    domain.  This definition actually implies that its domain
    consists of ground terms, and the code below assumes that.
    The representation is similar to the representation for bags
    (indeed a bag could be regarded as a map from keys to integers),
    that is, the empty map is 'map' and any other map is
	map(Key,Val,Map)
    where Map is a finite map and Key is @< than every key in Map.
*/

:- public
	is_map/1,		%  map ->
	list_to_map/2,		%  list -> map
	map_agree/2,		%  map x map ->
	map_compose/3,		%  map x map -> map
	map_disjoint/2,		%  map x map ->
	map_domain/2,		%  map -> ordset
	map_exclude/3,		%  map x ordset -> map
	map_include/3,		%  map x ordset -> map
	map_invert/2,		%  map -> map
	map_map/3,		%  relation x map -> map
	map_range/2,		%  map -> ordset
	map_to_assoc/2,		%  map -> tree
	map_union/3,		%  map x map -> map
	map_update/3,		%  map x map -> map
	map_update/4,		%  map x key x val -> map
	map_value/3,		%  map x dom -> rng
	portray_map/1.		%  map ->


:- mode
	is_map(+),
	    is_map(+, +),
	list_to_map(+, ?),
	    list_to_map_(+, ?),
	map_agree(+, +),
	    map_agree(+, +, +, +, +, +, +),
	map_compose(+, +, ?),
	    map_compose_(+, +, ?),
		map_compose_(+, +, +, +, +, +, +, ?),
	map_disjoint(+, +),
	map_domain(+, ?),
	map_exclude(+, +, ?),
	    map_exclude(+, +, +, +, +, +, ?),
	map_include(+, +, ?),
	    map_include(+, +, +, +, +, +, ?),
	map_invert(+, ?),
	    map_invert_(+, -),
	map_map(+, +, ?),
	map_range(+, ?),
	    map_range_(+, -),
	map_to_assoc(+, ?),
	map_to_list(+, ?),
	map_union(+, +, ?),
	    map_union(+, +, +, +, +, +, +, ?),
	map_update(+, +, ?),
	    map_update(+, +, +, +, +, +, +, ?),
	map_update(+, +, +, ?),
	    map_update(+, +, +, +, +, +, ?),
	map_value(+, +, ?),
	    map_value(+, +, +, +, ?),
	portray_map(+),
	    portray_map(+, +).

%   is_map(Thing)
%   is true when Thing is a map.  If you use the predicates in this
%   file, you have no way of constructing a map with an unbound tail,
%   so such structures are NOT recognised as bags (this avoids a
%   possible infinite loop.

is_map(map).
is_map(map(Key,_,Map)) :-
	nonvar(Map),
	is_map(Map, Key).

is_map(map, _).
is_map(map(Key,_,Map), PreviousKey) :-
	nonvar(Map),
	PreviousKey @< Key,
	is_map(Map, Key).

%   list_to_map(+KeyValList, ?Map)
%   takes a list of Key-Value pairs and orders them to form a representation
%   of a finite map.  The list may not have two elements with the same Key.

list_to_map(List, Map) :-
	keysort(List, Sorted),
	list_to_map_(Sorted, Map).

list_to_map_([], map).
list_to_map_([Key-Val|List], map(Key,Val,Map)) :-
	list_to_map_(List, Map).



%   map_agree(+Map1, Map2)
%   is true if whenever Map1 and Map2 have a key in common, they
%   agree on its value.  If they have no keys in common they agree.

map_agree(_, map) :- !.
map_agree(map, _).
map_agree(map(Key1,Val1,Map1), map(Key2,Val2,Map2)) :-
	compare(R, Key1, Key2),
	map_agree(R, Key1, Val1, Map1, Key2, Val2, Map2).

map_agree(<, _, _, Map1, Key2, Val2, Map2) :-
	map_agree(Map1, map(Key2,Val2,Map2)).
map_agree(>, Key1, Val1, Map1, _, _, Map2) :-
	map_agree(map(Key1,Val1,Map1), Map2).
map_agree(=, _, Val, Map1, _, Val, Map2) :-
	map_agree(Map1, Map2).



%   map_compose(Map1, Map2, Composition)
%   constructs Map1 o Map2.  That is, for each K-T in Map1 such that
%   there is a T-V in Map2, K-V is in Composition.  The way this is
%   done requires the range of Map1 to be ground as well as the domains
%   of both maps, but then any fast composition has the same problem.

map_compose(Map1, Map2, Composition) :-
	map_invert_(Map1, Inv0),
	keysort(Inv0, Inv1),
	map_compose_(Inv1, Map2, Mid0),
	keysort(Mid0, Mid1),
	list_to_map_(Mid1, Composition).

map_compose_(_, map, []) :- !.
map_compose_([], _, []).
map_compose_([Val1-Key1|Map1], map(Key2,Val2,Map2), Composition) :-
	compare(R, Val1, Key2),
	map_compose_(R, Val1, Key1, Map1, Key2, Val2, Map2, Composition).

map_compose_(<, _, _, Map1, Key2, Val2, Map2, Composition) :-
	map_compose_(Map1, map(Key2,Val2,Map2), Composition).
map_compose_(>, Val1, Key1, Map1, _, _, Map2, Composition) :-
	map_compose_([Val1-Key1|Map1], Map2, Composition).
map_compose_(=, Com, Key1, Map1, Com, Val2, Map2, [Key1-Val2|Composition]) :-
	map_compose_(Map1, map(Com,Val2,Map2), Composition).



%   map_disjoint(+Map1, +Map2)
%   is true when the two maps have no domain elements in common.
%   That is, if K-V1 is in Map1, there is no K-V2 in Map2 and conversely.
%   This implementation assumes you have loaded the ordered sets package.

map_disjoint(Map1, Map2) :-
	map_domain(Map1, Dom1),
	map_domain(Map2, Dom2),
	ord_disjoint(Dom1, Dom2).



%   map_domain(+Map, ?Domain)
%   unifies Domain with the ordered set representation of the domain
%   of the finite map Map.  As the keys (domain elements) of Map are
%   in ascending order and there are no duplicates, this is trivial.

map_domain(map, []).
map_domain(map(Key,_,Map), [Key|Domain]) :-
	map_domain(Map, Domain).



%   map_exclude(+Map, +Set, ?Restricted)
%   constructs a restriction of the Map by dropping members of the Set
%   from the Restricted map's domain.  That is, Restricted and Map agree,
%   but domain(Restricted) = domain(Map)\Set.
%   Set must be an *ordered* set.

map_exclude(Map, [], Map) :- !.
map_exclude(map, _, map).
map_exclude(map(Key,Val,Map), [Elt|Set], Restricted) :-
	compare(R, Key, Elt),
	map_exclude(R, Key, Val, Map, Elt, Set, Restricted).

map_exclude(<, Key, Val, Map, Elt, Set, map(Key,Val,Restricted)) :-
	map_exclude(Map, [Elt|Set], Restricted).
map_exclude(>, Key, Val, Map, _, Set, Restricted) :-
	map_exclude(map(Key,Val,Map), Set, Restricted).
map_exclude(=, _, _, Map, _, Set, Restricted) :-
	map_exclude(Map, Set, Restricted).



%   map_include(+Map, +Set, ?Restricted)
%   constructs a restriction of the Map by dropping everything which is
%   NOT a member of Set from the restricted map's domain.  That is, the
%   Restricted and original Map agree, but
%   domain(Restricted) = domain(Map) intersection Set.
%   Set must be an *ordered* set.

map_include(Map, [], Map) :- !.
map_include(map, _, map).
map_include(map(Key,Val,Map), [Elt|Set], Restricted) :-
	compare(R, Key, Elt),
	map_include(R, Key, Val, Map, Elt, Set, Restricted).

map_include(<, _, _, Map, Elt, Set, Restricted) :-
	map_include(Map, [Elt|Set], Restricted).
map_include(>, Key, Val, Map, _, Set, Restricted) :-
	map_include(map(Key,Val,Map), Set, Restricted).
map_include(=, Key, Val, Map, _, Set, map(Key,Val,Restricted)) :-
	map_include(Map, Set, Restricted).



%   map_invert(+Map, ?Inverse)
%   unifies Inverse with the inverse of a finite invertible map.
%   All we do is swap the pairs round, sort, and check that the
%   result is indeed a map.  

map_invert(Map, Inverse) :-
	map_invert_(Map, Inv0),
	keysort(Inv0, Inv1),
	list_to_map_(Inv1, Inverse).

%   map_invert_ takes a list of key-value pairs and swaps the pairs around.

map_invert_(map, []).
map_invert_(map(Key,Val,Map), [Val-Key|Inv]) :-
	map_invert_(Map, Inv).



%   map_map(+Predicate, +Map1, ?Map2)
%   composes Map1 with the Predicate, so that K-V2 is in Map2 if
%   K-V1 is in Map1 and Predicate(V1,V2).  Really, the predicate
%   should come second, but there is this convention that the
%   predicate being mapped always comes first.  It doesn't do
%   marvels for Dec-10 Prolog's indexing either.

map_map(_, map, map).
map_map(Pred, map(K,V1,Map1), map(K,V2,Map2)) :-
	apply(Pred, [V1,V2]),
	map_map(Pred, Map1, Map2).



%   map_range(+Map, ?Range)
%   unifies Range with the ordered set representation of the range of the
%   finite map Map.  Note that the cardinality (length) of the domain and
%   the range are seldom equal, except of course for invertible maps.

map_range(Map, Range) :-
	map_range_(Map, Random),
	sort(Random, Range).

map_range_(map, []).
map_range_(map(_,Val,Map), [Val|Range]) :-
	map_range_(Map, Range).



%   map_to_assoc(+Map, ?Assoc)
%   converts a finite map held as an ordered list of Key-Val pairs to
%   an ordered binary tree such as the library file ASSOC works on.
%   This predicate calls an internal routine of that file, so both
%   must be compiled or both interpreted.  Eventually the two files
%   should be combined.

map_to_assoc(Map, Assoc) :-
	map_to_list(Map, List),
	length(List, N),
	list_to_assoc(N, List, Assoc, []).



%   map_to_list(+Map, ?KeyValList)
%   converts a map from its compact form to a list of Key-Val pairs
%   such as keysort yields or list_to_assoc wants.

map_to_list(map, []).
map_to_list(map(Key,Val,Map), [Key-Val|List]) :-
	map_to_list(Map, List).



%   map_union(+Map1, +Map2, ?Union)
%   forms the union of the two given maps.  That is Union(X) =
%   Map1(X) if it is defined, or Map2(X) if that is defined.
%   But when both are defined, both must agree.  (See map_update
%   for a version where Map2 overrides Map1.)

map_union(Map, map, Map) :- !.
map_union(map, Map, Map).
map_union(map(Key1,Val1,Map1), map(Key2,Val2,Map2), Union) :-
	compare(R, Key1, Key2),
	map_union(R, Key1, Val1, Map1, Key2, Val2, Map2, Union).

map_union(<, Key1, Val1, Map1, Key2, Val2, Map2, map(Key1,Val1,Union)) :-
	map_union(Map1, map(Key2,Val2,Map2), Union).
map_union(>, Key1, Val1, Map1, Key2, Val2, Map2, map(Key2,Val2,Union)) :-
	map_union(map(Key1,Val1,Map1), Map2, Union).
map_union(=, Key, Val, Map1, Key, Val, Map2, map(Key,Val,Union)) :-
	map_union(Map1, Map2, Union).



%   map_update(+Base, +Overlay, ?Updated)
%   combines the finite maps Base and Overlay as map_union does,
%   except that when both define values for the same key, the
%   Overlay value is taken regardless of the Base value.  This
%   is useful for changing maps (you may know it as the "mu" function).

map_update(Map, map, Map) :- !.
map_update(map, Map, Map).
map_update(map(Key1,Val1,Map1), map(Key2,Val2,Map2), Updated) :-
	compare(R, Key1, Key2),
	map_update(R, Key1, Val1, Map1, Key2, Val2, Map2, Updated).

map_update(<, Key1, Val1, Map1, Key2, Val2, Map2, map(Key1,Val1,Updated)) :-
	map_update(Map1, map(Key2,Val2,Map2), Updated).
map_update(>, Key1, Val1, Map1, Key2, Val2, Map2, map(Key2,Val2,Updated)) :-
	map_update(map(Key1,Val1,Map1), Map2, Updated).
map_update(=, _, _, Map1, Key, Val, Map2, map(Key,Val,Updated)) :-
	map_update(Map1, Map2, Updated).



%   map_update(+Map, +Key, +Val, ?Updated)
%   computes an Updated map which is the same as Map except that the
%   image of Key is Val, rather than the image it had under Map if any.
%   This is an O(N) operation, not O(1).  By using trees we could get
%   O(lgN).  Eventually this package should be merged with ASSOC.PL.

map_update(map, Key, Val, map(Key,Val,map)).
map_update(map(Key1,Val1,Map), Key, Val, Updated) :-
	compare(R, Key1, Key),
	map_update(R, Key1, Val1, Map, Key, Val, Updated).

map_update(<, Key1, Val1, Map, Key, Val, map(Key1,Val1,Updated)) :-
	map_update(Map, Key, Val, Updated).
map_update(=, _, _, Map, Key, Val, map(Key,Val,Map)).
map_update(>, Key1, Val1, Map, Key, Val, map(Key,Val,map(Key1,Val1,Map))).



%   map_value(+Map, +Arg, ?Result)
%   applies the finite map Map to an argument, and unifies Result with
%   the answer.  It fails if Arg is not in the domain of Map, or if the
%   value does not unify with Result.  Note that this operation is O(N)
%   like all the others; this package is really meant for working on
%   maps as wholes.  We can achieve O(lgN) by using trees (as in ASSOC),
%   and eventually MAP and ASSOC should be merged.  In the mean time,
%   use map_to_assoc to convert a map to a tree for faster lookup.

map_value(map(Key,Val,Map), Arg, Result) :-
	compare(R, Key, Arg),
	map_value(R, Val, Map, Arg, Result).

map_value(<, _, Map, Arg, Result) :- !,
	map_value(Map, Arg, Result).
map_value(=, Result, _, _, Result).



%   portray_map(+Map)
%   writes a finite Map to the current output stream in a pretty
%   form so that you can easily see what it is.  Note that a map
%   written out this way can NOT be read back in.  The point of
%   this predicate is that you can add a clause
%	portray(X) :- is_map(X), !, portray_map(X).
%   to get maps displayed nicely by print/1.

portray_map(map) :- !,
	write('map{'), write('}').
portray_map(Map) :-
	portray_map(Map, 'map{').

portray_map(map, _) :-
	write('}').
portray_map(map(Key,Val,Map), Prefix) :-
	write(Prefix),
	print(Key), write('->'), print(Val),
	!,
	portray_map(Map, ', ').