https://github.com/RichardMoot/LinearOne
Tip revision: 55540e9a91b7a5c7722775f39ffbf50f5b472a7e authored by Richard Moot on 12 November 2020, 17:47:42 UTC
Update .gitignore
Update .gitignore
Tip revision: 55540e9
ordset.pl
% -*- Mode: Prolog -*-
% This is the file ordset.pl from the Public Domain DEC-10 Prolog
% Library. The only changes and additions to the code are the
% following. They are marked as such in the source code. 20030605 RM
%
% Replaced ord_union with an improved, pure version, also due to
% R.A.O'Keefe. RM
%
% Added an ord_member predicate, which functions like member_chk for
% lists, using the order of the elements. RM
%
% Added an ord_select predicate, which is deterministic when we know
% the element to be selected. RM
%
% Added an ord_dup_insert predicate, which is exactly like ord_insert
% except for the fact that the result is an ordered multiset instead
% of an ordered set RM
% File : ORDSET.PL
% Author : R.A.O'Keefe
% Updated: 22 May 1983
% Purpose: Ordered set manipulation utilities
% In this module, sets are represented by ordered lists with no
% duplicates. Thus {c,r,a,f,t} would be [a,c,f,r,t]. The ordering
% is defined by the @< family of term comparison predicates, which
% is the ordering used by sort/2 and setof/3.
% The benefit of the ordered representation is that the elementary
% set operations can be done in time proportional to the Sum of the
% argument sizes rather than their Product. Some of the unordered
% set routines, such as member/2, length/2,, select/3 can be used
% unchanged. The main difficulty with the ordered representation is
% remembering to use it!
:- module(ordset, [
list_to_ord_set/2, % List -> Set
ord_merge/3, % OrdList x OrdList -> OrdList
ord_disjoint/2, % Set x Set ->
ord_insert/3, % Set x Elem -> Set
ord_intersect/2, % Set x Set ->
ord_intersect/3, % Set x Set -> Set
ord_seteq/2, % Set x Set ->
ord_subset/2, % Set x Set ->
ord_subtract/3, % Set x Set -> Set
ord_symdiff/3, % Set x Set -> Set
ord_union/3, % Set x Set -> Set
ord_key_intersect/3, % Set x Set -> Set
ord_key_union/3, % Set x Set -> Set
ord_key_union_i/3, % Set x Set -> Set
ord_key_union_u/3, % Set x Set -> Set
ord_key_select/4, % Key x Set -> Value x Set
ord_key_delete/3, % Set x Key -> Set
ord_key_insert/4, % Set x Key x Value -> Set
ord_member/2, % Elem x Set ->
ord_key_member/3, % Key x Set -> Value
ord_dup_insert/3, % Set x Elem -> Set
ord_delete/3, % Set x Elem -> Set
ord_select/3] ). % Elem x Set -> Set
% list_to_ord_set(+List, ?Set)
% is true when Set is the ordered representation of the set represented
% by the unordered representation List. The only reason for giving it
% a name at all is that you may not have realised that sort/2 could be
% used this way.
list_to_ord_set(List, Set) :-
sort(List, Set).
% ord_merge(+List1, +List2, -Merged)
% is true when Merged is the stable merge of the two given lists.
% If the two lists are not ordered, the merge doesn't mean a great
% deal. Merging is perfectly well defined when the inputs contain
% duplicates, and all copies of an element are preserved in the
% output, e.g. merge("122357", "34568", "12233455678"). Study this
% routine carefully, as it is the basis for all the rest.
ord_merge([Head1|Tail1], [Head2|Tail2], [Head2|Merged]) :-
Head1 @> Head2, !,
ord_merge([Head1|Tail1], Tail2, Merged).
ord_merge([Head1|Tail1], List2, [Head1|Merged]) :-
List2 \== [], !,
ord_merge(Tail1, List2, Merged).
ord_merge([], List2, List2) :- !.
ord_merge(List1, [], List1).
% ord_disjoint(+Set1, +Set2)
% is true when the two ordered sets have no element in common. If the
% arguments are not ordered, I have no idea what happens.
ord_disjoint([], _) :- !.
ord_disjoint(_, []) :- !.
ord_disjoint([Head1|Tail1], [Head2|Tail2]) :-
compare(Order, Head1, Head2),
ord_disjoint(Order, Head1, Tail1, Head2, Tail2).
ord_disjoint(<, _, Tail1, Head2, Tail2) :-
ord_disjoint(Tail1, [Head2|Tail2]).
ord_disjoint(>, Head1, Tail1, _, Tail2) :-
ord_disjoint([Head1|Tail1], Tail2).
% ord_insert(+Set1, +Element, ?Set2)
% is the equivalent of add_element for ordered sets. It should give
% exactly the same result as merge(Set1, [Element], Set2), but a bit
% faster, and certainly more clearly.
ord_insert([], Element, [Element]).
ord_insert([Head|Tail], Element, Set) :-
compare(Order, Head, Element),
ord_insert(Order, Head, Tail, Element, Set).
ord_insert(<, Head, Tail, Element, [Head|Set]) :-
ord_insert(Tail, Element, Set).
ord_insert(=, Head, Tail, _, [Head|Tail]).
ord_insert(>, Head, Tail, Element, [Element,Head|Tail]).
% ord_intersect(+Set1, +Set2)
% is true when the two ordered sets have at least one element in common.
% Note that the test is == rather than = .
ord_intersect([Head1|Tail1], [Head2|Tail2]) :-
compare(Order, Head1, Head2),
ord_intersect(Order, Head1, Tail1, Head2, Tail2).
ord_intersect(=, _, _, _, _).
ord_intersect(<, _, Tail1, Head2, Tail2) :-
ord_intersect(Tail1, [Head2|Tail2]).
ord_intersect(>, Head1, Tail1, _, Tail2) :-
ord_intersect([Head1|Tail1], Tail2).
% ord_intersect(+Set1, +Set2, ?Intersection)
% is true when Intersection is the ordered representation of Set1
% and Set2, provided that Set1 and Set2 are ordered sets.
% modified to work without cuts, like ord_union/3 20040429 RM
% removed error in the base case 20040503 RM
ord_intersect([], _, []).
ord_intersect([H1|T1], Set2, Intersection) :-
ord_intersect_2(Set2, H1, T1, Intersection).
ord_intersect_2([], _, _, []).
ord_intersect_2([H2|T2], H1, T1, Intersection) :-
compare(Order, H1, H2),
ord_intersect_3(Order, H1, T1, H2, T2, Intersection).
ord_intersect_3(<, _, T1, H2, T2, Intersection) :-
ord_intersect_2(T1, H2, T2, Intersection).
ord_intersect_3(=, H1, T1, _, T2, [H1|Intersection]) :-
ord_intersect(T1, T2, Intersection).
ord_intersect_3(>, H1, T1, _, T2, Intersection) :-
ord_intersect_2(T2, H1, T1, Intersection).
/* original code
ord_intersect(_, [], []) :- !.
ord_intersect([], _, []) :- !.
ord_intersect([Head1|Tail1], [Head2|Tail2], Intersection) :-
compare(Order, Head1, Head2),
ord_intersect(Order, Head1, Tail1, Head2, Tail2, Intersection).
ord_intersect(=, Head, Tail1, _, Tail2, [Head|Intersection]) :-
ord_intersect(Tail1, Tail2, Intersection).
ord_intersect(<, _, Tail1, Head2, Tail2, Intersection) :-
ord_intersect(Tail1, [Head2|Tail2], Intersection).
ord_intersect(>, Head1, Tail1, _, Tail2, Intersection) :-
ord_intersect([Head1|Tail1], Tail2, Intersection).
*/
% ord_seteq(+Set1, +Set2)
% is true when the two arguments represent the same set. Since they
% are assumed to be ordered representations, they must be identical.
ord_seteq(Set1, Set2) :-
Set1 == Set2.
% ord_subset(+Set1, +Set2)
% is true when every element of the ordered set Set1 appears in the
% ordered set Set2.
ord_subset([], _) :- !.
ord_subset([Head1|Tail1], [Head2|Tail2]) :-
compare(Order, Head1, Head2),
ord_subset(Order, Head1, Tail1, Head2, Tail2).
ord_subset(=, _, Tail1, _, Tail2) :-
ord_subset(Tail1, Tail2).
ord_subset(>, Head1, Tail1, _, Tail2) :-
ord_subset([Head1|Tail1], Tail2).
% ord_subtract(+Set1, +Set2, ?Difference)
% is true when Difference contains all and only the elements of Set1
% which are not also in Set2.
ord_subtract(Set1, [], Set1) :- !.
ord_subtract([], _, []) :- !.
ord_subtract([Head1|Tail1], [Head2|Tail2], Difference) :-
compare(Order, Head1, Head2),
ord_subtract(Order, Head1, Tail1, Head2, Tail2, Difference).
ord_subtract(=, _, Tail1, _, Tail2, Difference) :-
ord_subtract(Tail1, Tail2, Difference).
ord_subtract(<, Head1, Tail1, Head2, Tail2, [Head1|Difference]) :-
ord_subtract(Tail1, [Head2|Tail2], Difference).
ord_subtract(>, Head1, Tail1, _, Tail2, Difference) :-
ord_subtract([Head1|Tail1], Tail2, Difference).
% ord_symdiff(+Set1, +Set2, ?Difference)
% is true when Difference is the symmetric difference of Set1 and Set2.
ord_symdiff(Set1, [], Set1) :- !.
ord_symdiff([], Set2, Set2) :- !.
ord_symdiff([Head1|Tail1], [Head2|Tail2], Difference) :-
compare(Order, Head1, Head2),
ord_symdiff(Order, Head1, Tail1, Head2, Tail2, Difference).
ord_symdiff(=, _, Tail1, _, Tail2, Difference) :-
ord_symdiff(Tail1, Tail2, Difference).
ord_symdiff(<, Head1, Tail1, Head2, Tail2, [Head1|Difference]) :-
ord_symdiff(Tail1, [Head2|Tail2], Difference).
ord_symdiff(>, Head1, Tail1, Head2, Tail2, [Head2|Difference]) :-
ord_symdiff([Head1|Tail1], Tail2, Difference).
% ord_union(+Set1, +Set2, ?Union)
% is true when Union is the union of Set1 and Set2. Note that when
% something occurs in both sets, we want to retain only one copy.
% replaced original code with improved code from Richard A. O'Keefe's
% `The Craft of Prolog' (1990) MIT Press. Read this book for discussion
% and comments on the code. RM
ord_union([], Set2, Set2).
ord_union([H1|T1], Set2, Union) :-
ord_union_2(Set2, H1, T1, Union).
ord_union_2([], H1, T1, [H1|T1]).
ord_union_2([H2|T2], H1, T1, Union) :-
compare(Order, H1, H2),
ord_union_3(Order, H1, T1, H2, T2, Union).
ord_union_3(<, H1, T1, H2, T2, [H1|Union]) :-
ord_union_2(T1, H2, T2, Union).
ord_union_3(=, H1, T1, _, T2, [H1|Union]) :-
ord_union(T1, T2, Union).
ord_union_3(>, H1, T1, H2, T2, [H2|Union]) :-
ord_union_2(T2, H1, T1, Union).
/* original code
ord_union(Set1, [], Set1) :- !.
ord_union([], Set2, Set2) :- !.
ord_union([Head1|Tail1], [Head2|Tail2], Union) :-
compare(Order, Head1, Head2),
ord_union(Order, Head1, Tail1, Head2, Tail2, Union).
ord_union(=, Head, Tail1, _, Tail2, [Head|Union]) :-
ord_union(Tail1, Tail2, Union).
ord_union(<, Head1, Tail1, Head2, Tail2, [Head1|Union]) :-
ord_union(Tail1, [Head2|Tail2], Union).
ord_union(>, Head1, Tail1, Head2, Tail2, [Head2|Union]) :-
ord_union([Head1|Tail1], Tail2, Union).
*/
% ord_dup_insert(+Set1, +Element, ?Set2)
%
% implementation of ord_insert for ordered *multisets* RM
ord_dup_insert([], Element, [Element]).
ord_dup_insert([Head|Tail], Element, Set) :-
compare(Order, Head, Element),
ord_dup_insert(Order, Head, Tail, Element, Set).
ord_dup_insert(<, Head, Tail, Element, [Head|Set]) :-
ord_dup_insert(Tail, Element, Set).
ord_dup_insert(=, Head, Tail, Element, [Element,Head|Tail]).
ord_dup_insert(>, Head, Tail, Element, [Element,Head|Tail]).
% = ord_member(+Element, +OrdSet)
%
% given that the OrdSet is ordered, if we know Element, we can use the
% order to get this element deterministically. RM
ord_member(Element, [Head|Tail]) :-
compare(Order, Element, Head),
ord_member(Order, Element, Tail).
ord_member(=, _, _).
ord_member(>, Element, Tail) :-
ord_member(Element, Tail).
% = ord_select(+Element, +OrdSet, ?OrdSet)
%
% given that the OrdSet is ordered, if we know Element, we can use the
% order to get this element deterministically. RM
ord_select(Element, [Head|Tail], Rest) :-
compare(Order, Element, Head),
ord_select(Order, Element, Tail, Head, Rest).
ord_select(=, _, Rest, _, Rest).
ord_select(>, Element, Tail, Head, [Head|Rest]) :-
ord_select(Element, Tail, Rest).
% = ord_delete(+OrdSet, +Element, -OrdSet)
%
% as ord_select/3, but succeeds even if the Element is not in OrdSet
% RM
ord_delete([], _, []).
ord_delete([Head|Tail], Element, Rest) :-
compare(Order, Element, Head),
ord_delete(Order, Tail, Element, Head, Rest).
ord_delete(<, Tail, _, Head, [Head|Tail]).
ord_delete(=, Rest, _, _, Rest).
ord_delete(>, Tail, Element, Head, [Head|Rest]) :-
ord_delete(Tail, Element, Rest).
% = ord_key_member(+Key, +OrdSet, ?Value)
%
% as ord_member/2, but assumes the elements of OrdSet are Key-Value
% pairs. RM
ord_key_member(Element, [Head-Data0|Tail], Data) :-
compare(Order, Element, Head),
ord_key_member(Order, Element, Tail, Data0, Data).
ord_key_member(=, _, _, Data, Data).
ord_key_member(>, Element, Tail, _, Data) :-
ord_key_member(Element, Tail, Data).
% = ord_key_select(+Key, +OrdSet, -Value, -OrdSet)
%
% as ord_select/3, but assumes the elements of OrdSet are Key-Value
% pairs. RM
ord_key_select(Element, [Head-Data0|Tail], Data, Rest) :-
compare(Order, Element, Head),
ord_key_select(Order, Element, Tail, Head, Data0, Data, Rest).
ord_key_select(=, _, Rest, _, Data, Data, Rest).
ord_key_select(>, Element, Tail, Head, Data0, Data, [Head-Data0|Rest]) :-
ord_key_select(Element, Tail, Data, Rest).
% = ord_key_delete(+OrdSet, +Key, -OrdSet)
%
% as ord_delete/3, but assumes the elements of OrdSet are Key-Value
% pairs. RM
ord_key_delete([], _, []).
ord_key_delete([Key-Data|Tail], Element, Rest) :-
compare(Order, Element, Key),
ord_key_delete(Order, Tail, Element, Key, Data, Rest).
ord_key_delete(<, Tail, _, Key, Data, [Key-Data|Tail]).
ord_key_delete(=, Rest, _, _, _, Rest).
ord_key_delete(>, Tail, Element, Key, Data, [Key-Data|Rest]) :-
ord_key_delete(Tail, Element, Rest).
% = ord_key_insert(+OrdSet, +Key, +Data, -OrdSet)
%
% as ord_insert/3, but assumes the elements of OrdSet are Key-Value
% pairs. RM
ord_key_insert([], Key, Data, [Key-Data]).
ord_key_insert([Key-Data|Tail], Key0, Data0, Rest) :-
compare(Order, Key0, Key),
ord_key_insert(Order, Tail, Key0, Data0, Key, Data, Rest).
ord_key_insert(<, Tail, Key0, Data0, Key, Data, [Key0-Data0,Key-Data|Tail]).
ord_key_insert(=, Rest, Key, Data0, Key, _Data, [Key-Data0|Rest]).
ord_key_insert(>, Tail, Key0, Data0, Key, Data, [Key-Data|Rest]) :-
ord_key_insert(Tail, Key0, Data0, Rest).
% = ord_key_union(+Map1, +Map2, ?Map3)
%
% as ord_union/3, but for ordered sets of Key-Value pairs, where Value
% is itself an ordered set. If Map1 and Map2 contain the same Key,
% Map3 will contain the ord_union of the two values. RM
ord_key_union([], Set2, Set2).
ord_key_union([H1-V1|T1], Set2, Union) :-
ord_key_union_2(Set2, H1, V1, T1, Union).
ord_key_union_2([], H1, V1, T1, [H1-V1|T1]).
ord_key_union_2([H2-V2|T2], H1, V1, T1, Union) :-
compare(Order, H1, H2),
ord_key_union_3(Order, H1, V1, T1, H2, V2, T2, Union).
ord_key_union_3(<, H1, V1, T1, H2, V2, T2, [H1-V1|Union]) :-
ord_key_union_2(T1, H2, V2, T2, Union).
ord_key_union_3(=, H1, V1, T1, _, V2, T2, [H1-V|Union]) :-
ord_union(V1, V2, V),
ord_key_union(T1, T2, Union).
ord_key_union_3(>, H1, V1, T1, H2, V2, T2, [H2-V2|Union]) :-
ord_key_union_2(T2, H1, V1, T1, Union).
% = ord_key_union_i(+Map1, +Map2, ?Map3)
%
% as ord_union/3, but for ordered sets of Key-Value pairs, where Value
% is itself an ordered set. If Map1 and Map2 contain the same Key,
% Map3 will contain the ord_interset of the two values. RM
ord_key_union_i([], Set2, Set2).
ord_key_union_i([H1-V1|T1], Set2, Union) :-
ord_key_union_i2(Set2, H1, V1, T1, Union).
ord_key_union_i2([], H1, V1, T1, [H1-V1|T1]).
ord_key_union_i2([H2-V2|T2], H1, V1, T1, Union) :-
compare(Order, H1, H2),
ord_key_union_i3(Order, H1, V1, T1, H2, V2, T2, Union).
ord_key_union_i3(<, H1, V1, T1, H2, V2, T2, [H1-V1|Union]) :-
ord_key_union_i2(T1, H2, V2, T2, Union).
ord_key_union_i3(=, H1, V1, T1, _, V2, T2, [H1-V|Union]) :-
ord_intersect(V1, V2, V),
ord_key_union_i(T1, T2, Union).
ord_key_union_i3(>, H1, V1, T1, H2, V2, T2, [H2-V2|Union]) :-
ord_key_union_i2(T2, H1, V1, T1, Union).
% = ord_key_union_u(+Map1, +Map2, ?Map3)
%
% as ord_union/3, but for ordered sets of Key-Value pairs, where Value
% is itself an ordered set. If Map1 and Map2 contain the same Key,
% Map3 will unify the two values (and fail in case of conflic). RM
ord_key_union_u([], Set2, Set2).
ord_key_union_u([H1-V1|T1], Set2, Union) :-
ord_key_union_u2(Set2, H1, V1, T1, Union).
ord_key_union_u2([], H1, V1, T1, [H1-V1|T1]).
ord_key_union_u2([H2-V2|T2], H1, V1, T1, Union) :-
compare(Order, H1, H2),
ord_key_union_u3(Order, H1, V1, T1, H2, V2, T2, Union).
ord_key_union_u3(<, H1, V1, T1, H2, V2, T2, [H1-V1|Union]) :-
ord_key_union_u2(T1, H2, V2, T2, Union).
ord_key_union_u3(=, H1, V, T1, _, V, T2, [H1-V|Union]) :-
ord_key_union_u(T1, T2, Union).
ord_key_union_u3(>, H1, V1, T1, H2, V2, T2, [H2-V2|Union]) :-
ord_key_union_u2(T2, H1, V1, T1, Union).
% = ord_key_intersect(+Map1, +Map2, ?Map3)
%
% as ord_intersect/3, but for ordered sets of Key-Value pairs, where
% Value is itself an ordered set. If Map1 and Map2 contain the same Key,
% Map3 will contain the ord_intersect of the two values. RM
ord_key_intersect([], _, []).
ord_key_intersect([H1-V1|T1], Set2, Intersection) :-
ord_key_intersect_2(Set2, H1, V1, T1, Intersection).
ord_key_intersect_2([], _, _, _, []).
ord_key_intersect_2([H2-V2|T2], H1, V1, T1, Intersection) :-
compare(Order, H1, H2),
ord_key_intersect_3(Order, H1, V1, T1, H2, V2, T2, Intersection).
ord_key_intersect_3(<, _, _, T1, H2, V2, T2, Intersection) :-
ord_key_intersect_2(T1, H2, V2, T2, Intersection).
ord_key_intersect_3(=, H1, V1, T1, _, V2, T2, [H1-V|Intersection]) :-
ord_intersect(V1, V2, V),
ord_key_intersect(T1, T2, Intersection).
ord_key_intersect_3(>, H1, V1, T1, _, _, T2, Intersection) :-
ord_key_intersect_2(T2, H1, V1, T1, Intersection).