% File : SORTS.PL % Author : R.A.O'Keefe % Updated: 23 July 1984 and by KJ 11-8-87 % Purpose: Specify generalised sorting routines. /* Note: these definitions are to be read as specifications of what arguments are acceptable and what results should be obtained. They are NOT to be read as being the code which should actually be used. I have C versions of these routines which are efficient with no redundant storage turnover and which make using the general routines nearly as fast as using the specific versions would be. The C code can also exploit any existing order or reversed order. ---> Since keysort/2 and sort/2 are built into Edinburgh Prolog, ---> this file CANNOT be consulted without first renaming the ---> predicates in it. */ :- public keysort/2, merge/3, merge/5, msort/2, sort/2, sort/4. :- mode combine(+, +, -), compare(+, +, +, -), compare(+, +, +, +, -), halve(+, +, -, -), keysort(+, -), merge(+, +, -), merge(+, +, +, +, -), msort(+, -), sort(+, -), sort(+, +, +, -). sort(_, _, [], []). sort(_, _, [X], [X]). sort(Key, Order, [X,Y|L], Sorted) :- halve(L, [Y|L], Front, Back), sort(Key, Order, [X|Front], F), sort(Key, Order, Back, B), merge(Key, Order, F, B, Sorted). halve([_,_|Count], [H|T], [H|F], B) :- !, halve(Count, T, F, B). halve(_, B, [], B). merge(Key, Order, [H1|T1], [H2|T2], [Hm|Tm]) :- !, compare(Key, Order, H1, H2, R), ( R = (<), !, Hm = H1, merge(Key, Order, T1, [H2|T2], Tm) ; R = (>), !, Hm = H2, merge(Key, Order, [H1|T1], T2, Tm) ; R = (=), !, Hm = H1, merge(Key, Order, T1, T2, Tm) ). merge(_, _, [], L, L) :- !. merge(_, _, L, [], L). compare(Key, Order, X, Y, R) :- compare(Key, X, Y, R0), combine(Order, R0, R). compare(0, X, Y, R) :- !, compare(R, X, Y). compare(N, X, Y, R) :- arg(N, X, Xn), arg(N, Y, Yn), compare(R, Xn, Yn). combine(<, R, R). combine(=<, >, >) :- !. combine(=<, _, <). combine(>=, <, >) :- !. combine(>=, _, <). combine(>, <, >) :- !. combine(>, >, <) :- !. combine(>, =, =). keysort(R, S) :- sort(1, =<, R, S). msort(R, S) :- sort(0, =<, R, S). sort(R, S) :- sort(0, <, R, S). merge(A, B, M) :- merge(0, =<, A, B, M).