Home > Archive > Prolog > May 2004 > ord_union(OldSet,NewSet,Union,ReallyNew)
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
ord_union(OldSet,NewSet,Union,ReallyNew)
|
|
| Algernon 2004-05-24, 6:35 pm |
| I'm fooling around with Prolog and I've come across O'Keefe's search
algorithms, namely searching a possibly cyclic graph. The programs require
the use of ord_union/4 available in Qunitus but not in SWI-Prolog (As far as
I know), I can't find any implementation for it so I wrote one myself. My
question is, is the following correct and complete? And is it efficient?
/*
ord_union(+OldSet,+NewSet,?Union,?ReallyNew)
Union is the ordered union of the ordered sets OldSet and NewSet and
ReallyNew is the set of elements in NewSet not already in OldSet
*/
ord_union([], New, New, New) :- !.
ord_union(Old, [], Old, []) :- !.
ord_union([H1|T1], [H2|T2], Union, Subtract) :-
compare(C, H1, H2),
ord_union(C, H1, T1, H2, T2, Union, Subtract).
/* ord_union/5 */
ord_union(=, H, T1, _, T2, [H|Union], Subtract) :-
ord_union(T1, T2, Union, Subtract).
ord_union(<, H1, T1, H2, T2, [H1|Union], Subtract) :-
ord_union(T1, [H2|T2], Union, Subtract).
ord_union(>, H1, T1, H2, T2, [H2|Union], [H2|Subtract]) :-
ord_union([H1|T1], T2, Union, Subtract).
As long as OldSet and NewSet are ground and ordered it works but I'm not
good at testing my own code, so I would like some input and is there anyway
of making it faster? O'Keefe mentions that it would be nice to make it
proportional to the size of NewSet.
Thanks
|
|
|
|
|