[m-dev.] for review: set__divide

[Zoltan Somogyi]

For review by anyone.

Estimated hours taken: 1

Add a predicate to each of the set, set_ordlist and set_unordlist modules
that divides a set into two parts: the elements for which a test succeeds
and the elements for which it fails.

library/set.m:
library/set_ordlist.m:
library/set_unordlist.m:
	Add {set,set_ordlist,set_unordlist}_divide.

Zoltan.

cvs diff: Diffing library
Index: library/set.m
===================================================================
RCS file: /home/mercury1/repository/mercury/library/set.m,v
retrieving revision 1.55
diff -u -b -r1.55 set.m
--- library/set.m	2000/11/12 08:51:36	1.55
+++ library/set.m	2001/01/03 12:56:57
@@ -1,5 +1,5 @@
 %---------------------------------------------------------------------------%
-% Copyright (C) 1994-1997, 1999-2000 The University of Melbourne.
+% Copyright (C) 1994-1997, 1999-2001 The University of Melbourne.
 % This file may only be copied under the terms of the GNU Library General
 % Public License - see the file COPYING.LIB in the Mercury distribution.
 %---------------------------------------------------------------------------%
@@ -245,6 +245,12 @@
 
 :- func set__fold(func(T1, T2) = T2, set(T1), T2) = T2.
 
+	% set__divide(Pred, Set, TruePart, FalsePart):
+	% TruePart consists of those elements of Set for which Pred succeeds;
+	% FalsePart consists of those elements of Set for which Pred fails.
+:- pred set__divide(pred(T1), set(T1), set(T1), set(T1)).
+:- mode set__divide(pred(in) is semidet, in, out, out) is det.
+
 %--------------------------------------------------------------------------%
 
 :- implementation.
@@ -426,3 +432,5 @@
 set__fold(F, S, A) = B :-
 	B = list__foldl(F, set__to_sorted_list(S), A).
 
+set__divide(P, Set, TruePart, FalsePart) :-
+	set_ordlist__divide(P, Set, TruePart, FalsePart).
Index: library/set_ordlist.m
===================================================================
RCS file: /home/mercury1/repository/mercury/library/set_ordlist.m,v
retrieving revision 1.12
diff -u -b -r1.12 set_ordlist.m
--- library/set_ordlist.m	2000/11/12 08:51:36	1.12
+++ library/set_ordlist.m	2001/01/03 13:27:11
@@ -230,6 +230,13 @@
 
 :- func set_ordlist__fold(func(T1, T2) = T2, set_ordlist(T1), T2) = T2.
 
+	% set_ordlist__divide(Pred, Set, TruePart, FalsePart):
+	% TruePart consists of those elements of Set for which Pred succeeds;
+	% FalsePart consists of those elements of Set for which Pred fails.
+:- pred set_ordlist__divide(pred(T1), set_ordlist(T1), set_ordlist(T1),
+	set_ordlist(T1)).
+:- mode set_ordlist__divide(pred(in) is semidet, in, out, out) is det.
+
 %--------------------------------------------------------------------------%
 
 :- implementation.
@@ -487,3 +494,27 @@
 set_ordlist__fold(F, S, A) = B :-
 	B = list__foldl(F, set_ordlist__to_sorted_list(S), A).
 
+	% The calls to reverse allow us to make set_ordlist__divide_2 tail
+	% recursive. This costs us a higher constant factor, but allows
+	% set_ordlist__divide to work in constant stack space.
+set_ordlist__divide(Pred, Set, TruePart, FalsePart) :-
+	set_ordlist__divide_2(Pred, Set, [], RevTruePart, [], RevFalsePart),
+	list__reverse(RevTruePart, TruePart),
+	list__reverse(RevFalsePart, FalsePart).
+
+:- pred set_ordlist__divide_2(pred(T1), set_ordlist(T1),
+	set_ordlist(T1), set_ordlist(T1),
+	set_ordlist(T1), set_ordlist(T1)).
+:- mode set_ordlist__divide_2(pred(in) is semidet, in, in, out, in, out)
+	is det.
+
+set_ordlist__divide_2(_Pred, [], RevTrue, RevTrue, RevFalse, RevFalse).
+set_ordlist__divide_2(Pred, [H | T], RevTrue0, RevTrue, RevFalse0, RevFalse) :-
+	( call(Pred, H) ->
+		RevTrue1 = [H | RevTrue0],
+		RevFalse1 = RevFalse0
+	;
+		RevTrue1 = RevTrue0,
+		RevFalse1 = [H | RevFalse0]
+	),
+	set_ordlist__divide_2(Pred, T, RevTrue1, RevTrue, RevFalse1, RevFalse).
Index: library/set_unordlist.m
===================================================================
RCS file: /home/mercury1/repository/mercury/library/set_unordlist.m,v
retrieving revision 1.17
diff -u -b -r1.17 set_unordlist.m
--- library/set_unordlist.m	2000/11/12 08:51:36	1.17
+++ library/set_unordlist.m	2001/01/04 04:10:04
@@ -226,6 +226,12 @@
 
 :- func set_unordlist__fold(func(T1, T2) = T2, set_unordlist(T1), T2) = T2.
 
+	% set_unordlist__divide(Pred, Set, TruePart, FalsePart):
+	% TruePart consists of those elements of Set for which Pred succeeds;
+	% FalsePart consists of those elements of Set for which Pred fails.
+:- pred set_unordlist__divide(pred(T1), set_unordlist(T1), set_unordlist(T1),
+	set_unordlist(T1)).
+:- mode set_unordlist__divide(pred(in) is semidet, in, out, out) is det.
 
 %--------------------------------------------------------------------------%
 
@@ -417,3 +423,24 @@
 set_unordlist__fold(F, S, A) = B :-
 	B = list__foldl(F, set_unordlist__to_sorted_list(S), A).
 
+set_unordlist__divide(Pred, Set, RevTruePart, RevFalsePart) :-
+	set_unordlist__divide_2(Pred, Set, [], RevTruePart, [], RevFalsePart).
+
+:- pred set_unordlist__divide_2(pred(T1), set_unordlist(T1),
+	set_unordlist(T1), set_unordlist(T1),
+	set_unordlist(T1), set_unordlist(T1)).
+:- mode set_unordlist__divide_2(pred(in) is semidet, in, in, out, in, out)
+	is det.
+
+set_unordlist__divide_2(_Pred, [], RevTrue, RevTrue, RevFalse, RevFalse).
+set_unordlist__divide_2(Pred, [H | T],
+		RevTrue0, RevTrue, RevFalse0, RevFalse) :-
+	( call(Pred, H) ->
+		RevTrue1 = [H | RevTrue0],
+		RevFalse1 = RevFalse0
+	;
+		RevTrue1 = RevTrue0,
+		RevFalse1 = [H | RevFalse0]
+	),
+	set_unordlist__divide_2(Pred, T,
+		RevTrue1, RevTrue, RevFalse1, RevFalse).
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------