[m-rev.] diff: avoid some redundant list/set conversions

Zoltan Somogyi zs at csse.unimelb.edu.au
Thu May 26 16:19:06 AEST 2011
Previous message: [m-rev.] diff: reuse int constants in polymorphism
Next message: [m-rev.] for post-commit review: configure.in enhancements
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
compiler/stack_alloc.m:
	Avoid some redundant conversions between lists and sets. The main
	performance win is from avoiding a list_to_set conversion that
	requires sorting.

library/*set*.m:
	The change to stack_alloc.m requires the ability to partition a set
	based on predicate. Implement a version of filter that returns the
	false as well as the true cases in all the set modules. (Most set
	modules lacked the return-the-trues-only version of filter as well.)

NEWS:
	Mention the additions to the standard library.

Zoltan.

cvs diff: Diffing .
Index: NEWS
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/NEWS,v
retrieving revision 1.577
diff -u -b -r1.577 NEWS
--- NEWS	25 May 2011 02:02:51 -0000	1.577
+++ NEWS	26 May 2011 03:02:06 -0000
@@ -132,9 +132,15 @@
 * The following predicates have been added to the modules that provide sets
   in the library: set.is_empty/1, set_bbbtree.is_empty/1,
   set_ctree234.is_empty/1, set_ordlist.is_empty/1, set_tree234.is_empty/1,
-  set_unordlist.is_empty/1, sparse_bitset.is_empty/1, tree_bitset.is_empty/1.
+  set_unordlist.is_empty/1, sparse_bitset.is_empty/1, tree_bitset.is_empty/1,
+  set.filter/4, set_bbbtree.filter/3, set_bbbtree.filter/4, set_ctree.filter/3,
+  set_ctree.filter/4, set_ordlist.filter/3, set_ordlist.filter/4,
+  set_tree.filter/3, set_tree.filter/4, set_unordlist.filter/3,
+  set_unordlist.filter/4, sparse_bitset.filter/3, sparse_bitset.filter/4,
+  tree_bitset.filter/3, tree_bitset.filter/4.
 
-  All are synonyms for the existing empty/1 predicates in those modules.
+  All the is_empty predicates are synonyms for the existing empty/1 predicates
+  in those modules.
 
 * We have added the predicate pqueue.det_remove/4.  It is like pqueue.remove/4
   except that it throws an exception instead of failing if the priority queue
cvs diff: Diffing analysis
cvs diff: Diffing bindist
cvs diff: Diffing boehm_gc
cvs diff: Diffing boehm_gc/Mac_files
cvs diff: Diffing boehm_gc/cord
cvs diff: Diffing boehm_gc/cord/private
cvs diff: Diffing boehm_gc/doc
cvs diff: Diffing boehm_gc/extra
cvs diff: Diffing boehm_gc/include
cvs diff: Diffing boehm_gc/include/extra
cvs diff: Diffing boehm_gc/include/private
cvs diff: Diffing boehm_gc/libatomic_ops
cvs diff: Diffing boehm_gc/libatomic_ops/doc
cvs diff: Diffing boehm_gc/libatomic_ops/src
cvs diff: Diffing boehm_gc/libatomic_ops/src/atomic_ops
cvs diff: Diffing boehm_gc/libatomic_ops/src/atomic_ops/sysdeps
cvs diff: Diffing boehm_gc/libatomic_ops/src/atomic_ops/sysdeps/armcc
cvs diff: Diffing boehm_gc/libatomic_ops/src/atomic_ops/sysdeps/gcc
cvs diff: Diffing boehm_gc/libatomic_ops/src/atomic_ops/sysdeps/hpc
cvs diff: Diffing boehm_gc/libatomic_ops/src/atomic_ops/sysdeps/ibmc
cvs diff: Diffing boehm_gc/libatomic_ops/src/atomic_ops/sysdeps/icc
cvs diff: Diffing boehm_gc/libatomic_ops/src/atomic_ops/sysdeps/msftc
cvs diff: Diffing boehm_gc/libatomic_ops/src/atomic_ops/sysdeps/sunc
cvs diff: Diffing boehm_gc/libatomic_ops/tests
cvs diff: Diffing boehm_gc/libatomic_ops-1.2
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/doc
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src/atomic_ops
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src/atomic_ops/sysdeps
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/tests
cvs diff: Diffing boehm_gc/m4
cvs diff: Diffing boehm_gc/tests
cvs diff: Diffing browser
cvs diff: Diffing bytecode
cvs diff: Diffing compiler
Index: compiler/stack_alloc.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/stack_alloc.m,v
retrieving revision 1.28
diff -u -b -r1.28 stack_alloc.m
--- compiler/stack_alloc.m	6 May 2011 05:03:23 -0000	1.28
+++ compiler/stack_alloc.m	25 May 2011 08:31:21 -0000
@@ -130,16 +130,13 @@
         [LiveSet0 | LiveSets0], LiveSets, !Dummies) :-
     filter_out_dummy_values_2(ModuleInfo, VarTypes, LiveSets0, LiveSets1,
         !Dummies),
-    set.to_sorted_list(LiveSet0, LiveList0),
-    list.filter(var_is_of_dummy_type(ModuleInfo, VarTypes), LiveList0,
+    set.filter(var_is_of_dummy_type(ModuleInfo, VarTypes), LiveSet0,
         DummyVars, NonDummyVars),
-    set.insert_list(DummyVars, !Dummies),
-    (
-        NonDummyVars = [],
+    set.union(DummyVars, !Dummies),
+    ( set.empty(NonDummyVars) ->
         LiveSets = LiveSets1
     ;
-        NonDummyVars = [_ | _],
-        LiveSets = [list_to_set(NonDummyVars) | LiveSets1]
+        LiveSets = [NonDummyVars | LiveSets1]
     ).
 
 %-----------------------------------------------------------------------------%
cvs diff: Diffing compiler/notes
cvs diff: Diffing deep_profiler
cvs diff: Diffing deep_profiler/notes
cvs diff: Diffing doc
cvs diff: Diffing extras
cvs diff: Diffing extras/base64
cvs diff: Diffing extras/cgi
cvs diff: Diffing extras/complex_numbers
cvs diff: Diffing extras/complex_numbers/samples
cvs diff: Diffing extras/complex_numbers/tests
cvs diff: Diffing extras/curs
cvs diff: Diffing extras/curs/samples
cvs diff: Diffing extras/curses
cvs diff: Diffing extras/curses/sample
cvs diff: Diffing extras/dynamic_linking
cvs diff: Diffing extras/error
cvs diff: Diffing extras/fixed
cvs diff: Diffing extras/gator
cvs diff: Diffing extras/gator/generations
cvs diff: Diffing extras/gator/generations/1
cvs diff: Diffing extras/graphics
cvs diff: Diffing extras/graphics/easyx
cvs diff: Diffing extras/graphics/easyx/samples
cvs diff: Diffing extras/graphics/mercury_allegro
cvs diff: Diffing extras/graphics/mercury_allegro/examples
cvs diff: Diffing extras/graphics/mercury_allegro/samples
cvs diff: Diffing extras/graphics/mercury_allegro/samples/demo
cvs diff: Diffing extras/graphics/mercury_allegro/samples/mandel
cvs diff: Diffing extras/graphics/mercury_allegro/samples/pendulum2
cvs diff: Diffing extras/graphics/mercury_allegro/samples/speed
cvs diff: Diffing extras/graphics/mercury_cairo
cvs diff: Diffing extras/graphics/mercury_cairo/samples
cvs diff: Diffing extras/graphics/mercury_cairo/samples/data
cvs diff: Diffing extras/graphics/mercury_cairo/tutorial
cvs diff: Diffing extras/graphics/mercury_glut
cvs diff: Diffing extras/graphics/mercury_opengl
cvs diff: Diffing extras/graphics/mercury_tcltk
cvs diff: Diffing extras/graphics/samples
cvs diff: Diffing extras/graphics/samples/calc
cvs diff: Diffing extras/graphics/samples/gears
cvs diff: Diffing extras/graphics/samples/maze
cvs diff: Diffing extras/graphics/samples/pent
cvs diff: Diffing extras/lazy_evaluation
cvs diff: Diffing extras/lex
cvs diff: Diffing extras/lex/samples
cvs diff: Diffing extras/lex/tests
cvs diff: Diffing extras/log4m
cvs diff: Diffing extras/logged_output
cvs diff: Diffing extras/monte
cvs diff: Diffing extras/moose
cvs diff: Diffing extras/moose/samples
cvs diff: Diffing extras/moose/tests
cvs diff: Diffing extras/mopenssl
cvs diff: Diffing extras/morphine
cvs diff: Diffing extras/morphine/non-regression-tests
cvs diff: Diffing extras/morphine/scripts
cvs diff: Diffing extras/morphine/source
cvs diff: Diffing extras/net
cvs diff: Diffing extras/odbc
cvs diff: Diffing extras/posix
cvs diff: Diffing extras/posix/samples
cvs diff: Diffing extras/quickcheck
cvs diff: Diffing extras/quickcheck/tutes
cvs diff: Diffing extras/references
cvs diff: Diffing extras/references/samples
cvs diff: Diffing extras/references/tests
cvs diff: Diffing extras/solver_types
cvs diff: Diffing extras/solver_types/library
cvs diff: Diffing extras/trailed_update
cvs diff: Diffing extras/trailed_update/samples
cvs diff: Diffing extras/trailed_update/tests
cvs diff: Diffing extras/windows_installer_generator
cvs diff: Diffing extras/windows_installer_generator/sample
cvs diff: Diffing extras/windows_installer_generator/sample/images
cvs diff: Diffing extras/xml
cvs diff: Diffing extras/xml/samples
cvs diff: Diffing extras/xml_stylesheets
cvs diff: Diffing java
cvs diff: Diffing java/runtime
cvs diff: Diffing library
Index: library/set.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/library/set.m,v
retrieving revision 1.93
diff -u -b -r1.93 set.m
--- library/set.m	19 May 2011 07:33:23 -0000	1.93
+++ library/set.m	25 May 2011 08:31:05 -0000
@@ -1,5 +1,5 @@
 %---------------------------------------------------------------------------%
-% vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
+% vim: ts=4 sw=4 et ft=mercury
 %---------------------------------------------------------------------------%
 % Copyright (C) 1994-1997, 1999-2011 The University of Melbourne.
 % This file may only be copied under the terms of the GNU Library General
@@ -83,7 +83,6 @@
     %
 :- pred set.is_empty(set(T)::in) is semidet.
 
-
     % `set.subset(SetA, SetB)' is true iff `SetA' is a subset of `SetB'.
     %
 :- pred set.subset(set(T)::in, set(T)::in) is semidet.
@@ -246,13 +245,19 @@
 :- mode set.map_fold(pred(in, out, di, uo) is semidet, in, out,
     di, uo) is semidet.
 
-
+    % Return the set of items for which the given predicate succeeds.
     % set.filter(P, S) =
     %   sorted_list_to_set(list.filter(P, to_sorted_list(S))).
     %
 :- func set.filter(pred(T1), set(T1)) = set(T1).
 :- mode set.filter(pred(in) is semidet, in) = out is det.
 
+    % Return the set of items for which the given predicate succeeds,
+    % and the set of items for which it fails.
+    %
+:- pred set.filter(pred(T1), set(T1), set(T1), set(T1)).
+:- mode set.filter(pred(in) is semidet, in, out, out) is det.
+
     % set.filter_map(PF, S) =
     %   list_to_set(list.filter_map(PF, to_sorted_list(S))).
     %
@@ -559,45 +564,48 @@
     list.map(P, L1, L2),
     set.list_to_set(L2, S2).
 
-set.map(F, S1) = S2 :-
-    S2 = set.list_to_set(list.map(F, set.to_sorted_list(S1))).
+set.map(F, Set) = TransformedSet :-
+    List = set.to_sorted_list(Set),
+    TransformedList = list.map(F, List),
+    TransformedSet = set.list_to_set(TransformedList).
 
 set.map_fold(P, S0, S, A0, A) :-
     L0 = set.to_sorted_list(S0),
     list.map_foldl(P, L0, L, A0, A),
     S = set.list_to_set(L).
 
-set.filter(P, S1) = S2 :-
-    S2 = set.sorted_list_to_set(list.filter(P, set.to_sorted_list(S1))).
+set.filter(P, Set) =
+    set_ordlist.filter(P, Set).
 
-set.filter_map(PF, S1) = S2 :-
-    S2 = set.list_to_set(list.filter_map(PF, set.to_sorted_list(S1))).
+set.filter(P, Set, TrueSet, FalseSet) :-
+    set_ordlist.filter(P, Set, TrueSet, FalseSet).
 
-set.filter_map(P, S1, S2) :-
-    set.to_sorted_list(S1, L1),
-    list.filter_map(P, L1, L2),
-    set.list_to_set(L2, S2).
+set.filter_map(PF, Set) = 
+    set_ordlist.filter_map(PF, Set).
+
+set.filter_map(P, Set, TransformedTrueSet) :-
+    set_ordlist.filter_map(P, Set, TransformedTrueSet).
 
-set.fold(F, S, A) = B :-
-    B = list.foldl(F, set.to_sorted_list(S), A).
+set.fold(F, S, A) =
+    set_ordlist.fold(F, S, A).
 
 set.fold(F, S, !A) :-
-    list.foldl(F, set.to_sorted_list(S), !A).
+    set_ordlist.fold(F, S, !A).
 
 set.fold2(F, S, !A, !B) :-
-    list.foldl2(F, set.to_sorted_list(S), !A, !B).
+    set_ordlist.fold2(F, S, !A, !B).
 
 set.fold3(F, S, !A, !B, !C) :-
-    list.foldl3(F, set.to_sorted_list(S), !A, !B, !C).
+    set_ordlist.fold3(F, S, !A, !B, !C).
 
 set.fold4(F, S, !A, !B, !C, !D) :-
-    list.foldl4(F, set.to_sorted_list(S), !A, !B, !C, !D).
+    set_ordlist.fold4(F, S, !A, !B, !C, !D).
 
 set.fold5(F, S, !A, !B, !C, !D, !E) :-
-    list.foldl5(F, set.to_sorted_list(S), !A, !B, !C, !D, !E).
+    set_ordlist.fold5(F, S, !A, !B, !C, !D, !E).
 
 set.fold6(F, S, !A, !B, !C, !D, !E, !F) :-
-    list.foldl6(F, set.to_sorted_list(S), !A, !B, !C, !D, !E, !F).
+    set_ordlist.fold6(F, S, !A, !B, !C, !D, !E, !F).
 
 set.divide(P, Set, TruePart, FalsePart) :-
     set_ordlist.divide(P, Set, TruePart, FalsePart).
Index: library/set_bbbtree.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/library/set_bbbtree.m,v
retrieving revision 1.38
diff -u -b -r1.38 set_bbbtree.m
--- library/set_bbbtree.m	19 May 2011 07:33:23 -0000	1.38
+++ library/set_bbbtree.m	25 May 2011 08:31:05 -0000
@@ -1,5 +1,5 @@
 %-----------------------------------------------------------------------------%
-% vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
+% vim: ts=4 sw=4 et ft=mercury
 %-----------------------------------------------------------------------------%
 % Copyright (C) 1995-1997, 1999-2006, 2010-2011 The University of Melbourne.
 % This file may only be copied under the terms of the GNU Library General
@@ -268,12 +268,6 @@
 :- pred set_bbbtree.superset(set_bbbtree(T)::in, set_bbbtree(T)::in)
     is semidet.
 
-:- func set_bbbtree.map(func(T1) = T2, set_bbbtree(T1)) = set_bbbtree(T2).
-
-:- func set_bbbtree.filter_map(func(T1) = T2, set_bbbtree(T1))
-    = set_bbbtree(T2).
-:- mode set_bbbtree.filter_map(func(in) = out is semidet, in) = out is det.
-
 :- func set_bbbtree.fold(func(T1, T2) = T2, set_bbbtree(T1), T2) = T2.
 :- pred set_bbbtree.fold(pred(T1, T2, T2), set_bbbtree(T1), T2, T2).
 :- mode set_bbbtree.fold(pred(in, in, out) is det, in, in, out) is det.
@@ -381,6 +375,25 @@
     pred(in, in, out, in, out, in, out, in, out, in, out, di, uo) is semidet, 
     in, in, out, in, out, in, out, in, out, in, out, di, uo) is semidet.
 
+:- func set_bbbtree.map(func(T1) = T2, set_bbbtree(T1)) = set_bbbtree(T2).
+
+:- func set_bbbtree.filter_map(func(T1) = T2, set_bbbtree(T1))
+    = set_bbbtree(T2).
+:- mode set_bbbtree.filter_map(func(in) = out is semidet, in) = out is det.
+
+    % set_bbbtree.filter(Pred, Items, Trues):
+    % Return the set of items for which Pred succeeds.
+    %
+:- pred set_bbbtree.filter(pred(T)::in(pred(in) is semidet),
+    set_bbbtree(T)::in, set_bbbtree(T)::out) is det.
+
+    % set_bbbtree.filter(Pred, Items, Trues, Falses):
+    % Return the set of items for which Pred succeeds,
+    % and the set for which it fails.
+    %
+:- pred set_bbbtree.filter(pred(T)::in(pred(in) is semidet),
+    set_bbbtree(T)::in, set_bbbtree(T)::out, set_bbbtree(T)::out) is det.
+
 %------------------------------------------------------------------------------%
 %------------------------------------------------------------------------------%
 
@@ -1334,12 +1347,27 @@
 %--------------------------------------------------------------------------%
 
 set_bbbtree.map(F, S1) = S2 :-
-    S2 = set_bbbtree.list_to_set(list.map(F,
-        set_bbbtree.to_sorted_list(S1))).
+    set_bbbtree.to_sorted_list(S1, L1),
+    L2 = list.map(F, L1),
+    set_bbbtree.list_to_set(L2, S2).
 
 set_bbbtree.filter_map(PF, S1) = S2 :-
-    S2 = set_bbbtree.list_to_set(list.filter_map(PF,
-        set_bbbtree.to_sorted_list(S1))).
+    set_bbbtree.to_sorted_list(S1, L1),
+    L2 = list.filter_map(PF, L1),
+    set_bbbtree.list_to_set(L2, S2).
+
+%-----------------------------------------------------------------------------%
+
+set_bbbtree.filter(P, Set, TrueSet) :-
+    set_bbbtree.to_sorted_list(Set, List),
+    list.filter(P, List, TrueList),
+    set_bbbtree.list_to_set(TrueList, TrueSet).
+
+set_bbbtree.filter(P, Set, TrueSet, FalseSet) :-
+    set_bbbtree.to_sorted_list(Set, List),
+    list.filter(P, List, TrueList, FalseList),
+    set_bbbtree.list_to_set(TrueList, TrueSet),
+    set_bbbtree.list_to_set(FalseList, FalseSet).
 
 %-----------------------------------------------------------------------------%
 :- end_module set_bbbtree.
Index: library/set_ctree234.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/library/set_ctree234.m,v
retrieving revision 1.15
diff -u -b -r1.15 set_ctree234.m
--- library/set_ctree234.m	10 May 2011 05:26:51 -0000	1.15
+++ library/set_ctree234.m	25 May 2011 08:31:05 -0000
@@ -1,5 +1,5 @@
 %---------------------------------------------------------------------------%
-% vim:ts=4 sw=4 expandtab
+% vim: ts=4 sw=4 et ft=mercury
 %---------------------------------------------------------------------------%
 % Copyright (C) 2005-2006, 2010-2011 The University of Melbourne.
 % This file may only be copied under the terms of the GNU Library General
@@ -15,7 +15,8 @@
 % ordered lists, but it has much better worst-case complexity, and is likely
 % to be faster for large sets. Specifically,
 %
-% - the cost of lookups is only logarithmic in the size of the set, not linear
+% - the cost of lookups is only logarithmic in the size of the set, not linear;
+%
 % - for operations that are intrinsically linear in the size of one input
 %   operand or the other, the counts allow us to choose to be linear in the
 %   size of the smaller set.
@@ -335,9 +336,21 @@
     pred(in, in, out, in, out, in, out, in, out, in, out, di, uo) is semidet,
     in, in, out, in, out, in, out, in, out, in, out, di, uo) is semidet.
 
+    % Return the set of items for which the predicate succeeds.
+    %
+:- pred set_ctree234.filter(pred(T)::in(pred(in) is semidet),
+    set_ctree234(T)::in, set_ctree234(T)::out) is det.
+
+    % Return the set of items for which the predicate succeeds,
+    % and the set for which it fails.
+    %
+:- pred set_ctree234.filter(pred(T)::in(pred(in) is semidet),
+    set_ctree234(T)::in, set_ctree234(T)::out, set_ctree234(T)::out) is det.
+
     % set_ctree234.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.
+    % NOTE: This is the same as filter/4.
     %
 :- pred set_ctree234.divide(pred(T)::in(pred(in) is semidet),
     set_ctree234(T)::in, set_ctree234(T)::out, set_ctree234(T)::out) is det.
@@ -2732,6 +2745,13 @@
 
 %------------------------------------------------------------------------------%
 
+set_ctree234.filter(Pred, Set, TrueSet) :-
+    % XXX This should be more efficient.
+    set_ctree234.divide(Pred, Set, TrueSet, _FalseSet).
+
+set_ctree234.filter(Pred, Set, TrueSet, FalseSet) :-
+    set_ctree234.divide(Pred, Set, TrueSet, FalseSet).
+
 set_ctree234.divide(Pred, ct(_, Tree), TrueSet, FalseSet) :-
     set_ctree234.do_divide(Pred, Tree,
         set_ctree234.init, TrueSet, set_ctree234.init, FalseSet).
@@ -2741,6 +2761,7 @@
     set_ctree234(T)::in, set_ctree234(T)::out,
     set_ctree234(T)::in, set_ctree234(T)::out) is det.
 
+    % XXX This should be more efficient.
 set_ctree234.do_divide(_Pred, empty, !TrueSet, !FalseSet).
 set_ctree234.do_divide(Pred, Tin, !TrueSet, !FalseSet) :-
     Tin = two(E0, T0, T1),
@@ -2789,6 +2810,7 @@
     set_ctree234.do_divide(Pred, T3, !TrueSet, !FalseSet).
 
 set_ctree234.divide_by_set(DivideBySet, Set, TrueSet, FalseSet) :-
+    % XXX This should be more efficient.
     set_ctree234.divide(set_ctree234.contains(DivideBySet), Set,
         TrueSet, FalseSet).
 
@@ -2818,3 +2840,5 @@
     do_verify_depths(T1, Depth + 1, !Depths),
     do_verify_depths(T2, Depth + 1, !Depths),
     do_verify_depths(T3, Depth + 1, !Depths).
+
+%------------------------------------------------------------------------------%
Index: library/set_ordlist.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/library/set_ordlist.m,v
retrieving revision 1.38
diff -u -b -r1.38 set_ordlist.m
--- library/set_ordlist.m	19 May 2011 07:33:23 -0000	1.38
+++ library/set_ordlist.m	25 May 2011 08:31:05 -0000
@@ -1,5 +1,5 @@
 %---------------------------------------------------------------------------%
-% vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
+% vim: ft=mercury ts=4 sw=4 et
 %---------------------------------------------------------------------------%
 % Copyright (C) 1996-1997,1999-2002, 2004-2006, 2008-2011 The University of Melbourne.
 % This file may only be copied under the terms of the GNU Library General
@@ -223,12 +223,28 @@
 :- pred set_ordlist.count(set_ordlist(T)::in, int::out) is det.
 :- func set_ordlist.count(set_ordlist(T)) = int.
 
+    % Return the set of items for which the given predicate succeeds.
+    %
+:- func set_ordlist.filter(pred(T1), set_ordlist(T1)) = set_ordlist(T1).
+:- mode set_ordlist.filter(pred(in) is semidet, in) = out is det.
+
+    % Return the set of items for which the given predicate succeeds,
+    % and the set of items for which it fails.
+    %
+:- pred set_ordlist.filter(pred(T1), set_ordlist(T1),
+    set_ordlist(T1), set_ordlist(T1)).
+:- mode set_ordlist.filter(pred(in) is semidet, in, out, out) is det.
+
 :- func set_ordlist.map(func(T1) = T2, set_ordlist(T1)) = set_ordlist(T2).
 
 :- func set_ordlist.filter_map(func(T1) = T2, set_ordlist(T1))
     = set_ordlist(T2).
 :- mode set_ordlist.filter_map(func(in) = out is semidet, in) = out is det.
 
+:- pred set_ordlist.filter_map(pred(T1, T2), set_ordlist(T1),
+    set_ordlist(T2)).
+:- mode set_ordlist.filter_map(pred(in, out) is semidet, in, out) is det.
+
 :- func set_ordlist.fold(func(T1, T2) = T2, set_ordlist(T1), T2) = T2.
 :- pred set_ordlist.fold(pred(T1, T2, T2), set_ordlist(T1), T2, T2).
 :- mode set_ordlist.fold(pred(in, in, out) is det, in, in, out) is det.
@@ -687,12 +703,33 @@
 
 %-----------------------------------------------------------------------------%
 
-set_ordlist.map(F, S1) = S2 :-
-    S2 = set_ordlist.list_to_set(list.map(F, set_ordlist.to_sorted_list(S1))).
+set_ordlist.filter(P, Set) = TrueSet :-
+    List = set_ordlist.to_sorted_list(Set),
+    list.filter(P, List, TrueList),
+    set_ordlist.sorted_list_to_set(TrueList, TrueSet).
+
+set_ordlist.filter(P, Set, TrueSet, FalseSet) :-
+    List = set_ordlist.to_sorted_list(Set),
+    list.filter(P, List, TrueList, FalseList),
+    set_ordlist.sorted_list_to_set(TrueList, TrueSet),
+    set_ordlist.sorted_list_to_set(FalseList, FalseSet).
+
+%-----------------------------------------------------------------------------%
 
-set_ordlist.filter_map(PF, S1) = S2 :-
-    S2 = set_ordlist.list_to_set(list.filter_map(PF,
-        set_ordlist.to_sorted_list(S1))).
+set_ordlist.map(F, Set) = TransformedSet :-
+    List = set_ordlist.to_sorted_list(Set),
+    TransformedList = list.map(F, List),
+    set_ordlist.list_to_set(TransformedList, TransformedSet).
+
+set_ordlist.filter_map(PF, Set) = TransformedTrueSet :-
+    set_ordlist.to_sorted_list(Set, List),
+    TransformedTrueList = list.filter_map(PF, List),
+    set_ordlist.list_to_set(TransformedTrueList, TransformedTrueSet).
+
+set_ordlist.filter_map(PF, Set, TransformedTrueSet) :-
+    set_ordlist.to_sorted_list(Set, List),
+    list.filter_map(PF, List, TransformedTrueList),
+    set_ordlist.list_to_set(TransformedTrueList, TransformedTrueSet).
 
 %-----------------------------------------------------------------------------%
 
Index: library/set_tree234.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/library/set_tree234.m,v
retrieving revision 1.17
diff -u -b -r1.17 set_tree234.m
--- library/set_tree234.m	10 May 2011 05:26:51 -0000	1.17
+++ library/set_tree234.m	25 May 2011 08:31:05 -0000
@@ -10,7 +10,7 @@
 % Author: zs.
 % Stability: high.
 % 
-% This modules implements sets using 2-3-4 trees.
+% This module implements sets using 2-3-4 trees.
 % 
 %--------------------------------------------------------------------------%
 %--------------------------------------------------------------------------%
@@ -321,6 +321,17 @@
     pred(in, in, out, in, out, in, out, in, out, in, out, di, uo) is semidet,
     in, in, out, in, out, in, out, in, out, in, out, di, uo) is semidet.
 
+    % Return the set of items for which the predicate succeeds.
+    %
+:- pred set_tree234.filter(pred(T)::in(pred(in) is semidet),
+    set_tree234(T)::in, set_tree234(T)::out) is det.
+
+    % Return the set of items for which the predicate succeeds,
+    % and the set for which it fails.
+    %
+:- pred set_tree234.filter(pred(T)::in(pred(in) is semidet),
+    set_tree234(T)::in, set_tree234(T)::out, set_tree234(T)::out) is det.
+
     % set_tree234.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.
@@ -2333,6 +2344,13 @@
 
 %------------------------------------------------------------------------------%
 
+set_tree234.filter(Pred, Set, TrueSet) :-
+    % XXX This should be more efficient.
+    set_tree234.divide(Pred, Set, TrueSet, _FalseSet).
+
+set_tree234.filter(Pred, Set, TrueSet, FalseSet) :-
+    set_tree234.divide(Pred, Set, TrueSet, FalseSet).
+
 set_tree234.divide(Pred, Set, TrueSet, FalseSet) :-
     set_tree234.divide_2(Pred, Set, empty, TrueSet, empty, FalseSet).
 
@@ -2341,6 +2359,7 @@
     set_tree234(T)::in, set_tree234(T)::out,
     set_tree234(T)::in, set_tree234(T)::out) is det.
 
+    % XXX This should be more efficient.
 set_tree234.divide_2(_Pred, empty, !TrueSet, !FalseSet).
 set_tree234.divide_2(Pred, Tin, !TrueSet, !FalseSet) :-
     Tin = two(E0, T0, T1),
@@ -2389,6 +2408,7 @@
     set_tree234.divide_2(Pred, T3, !TrueSet, !FalseSet).
 
 set_tree234.divide_by_set(DivideBySet, Set, TrueSet, FalseSet) :-
+    % XXX This should be more efficient.
     set_tree234.divide(set_tree234.contains(DivideBySet), Set,
         TrueSet, FalseSet).
 
Index: library/set_unordlist.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/library/set_unordlist.m,v
retrieving revision 1.35
diff -u -b -r1.35 set_unordlist.m
--- library/set_unordlist.m	19 May 2011 07:33:23 -0000	1.35
+++ library/set_unordlist.m	25 May 2011 08:31:05 -0000
@@ -1,5 +1,5 @@
 %---------------------------------------------------------------------------%
-% vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
+% vim: ft=mercury ts=4 sw=4 et
 %---------------------------------------------------------------------------%
 % Copyright (C) 1995-1997,1999-2002, 2004-2006, 2010-2011 The University of Melbourne.
 % This file may only be copied under the terms of the GNU Library General
@@ -348,13 +348,24 @@
     pred(in, in, out, in, out, in, out, in, out, in, out, di, uo) is semidet,
     in, in, out, in, out, in, out, in, out, in, out, di, uo) is semidet.
 
+    % Return the set of items for which the predicate succeeds.
+    %
+:- pred set_unordlist.filter(pred(T)::in(pred(in) is semidet),
+    set_unordlist(T)::in, set_unordlist(T)::out) is det.
+
+    % Return the set of items for which the predicate succeeds,
+    % and the set for which it fails.
+    %
+:- pred set_unordlist.filter(pred(T)::in(pred(in) is semidet),
+    set_unordlist(T)::in, set_unordlist(T)::out, set_unordlist(T)::out) is det.
+
     % 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.
+    % NOTE: this is the same as filter/4.
     %
-:- 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.
+:- pred set_unordlist.divide(pred(T)::in(pred(in) is semidet),
+    set_unordlist(T)::in, set_unordlist(T)::out, set_unordlist(T)::out) is det.
 
 %--------------------------------------------------------------------------%
 %--------------------------------------------------------------------------%
@@ -586,6 +597,15 @@
     S2 = set_unordlist.list_to_set(list.filter_map(PF,
         set_unordlist.to_sorted_list(S1))).
 
+%-----------------------------------------------------------------------------%
+
+set_unordlist.filter(Pred, Set, TrueSet) :-
+    % XXX This should be more efficient.
+    set_unordlist.divide(Pred, Set, TrueSet, _FalseSet).
+
+set_unordlist.filter(Pred, Set, TrueSet, FalseSet) :-
+    set_unordlist.divide(Pred, Set, TrueSet, FalseSet).
+
 set_unordlist.divide(Pred, sul(Set), sul(RevTruePart), sul(RevFalsePart)) :-
     set_unordlist.divide_2(Pred, Set, [], RevTruePart, [], RevFalsePart).
 
Index: library/sparse_bitset.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/library/sparse_bitset.m,v
retrieving revision 1.38
diff -u -b -r1.38 sparse_bitset.m
--- library/sparse_bitset.m	19 May 2011 13:11:45 -0000	1.38
+++ library/sparse_bitset.m	25 May 2011 08:31:05 -0000
@@ -1,5 +1,5 @@
 %-----------------------------------------------------------------------------%
-% vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
+% vim: ts=4 sw=4 et ft=mercury
 %-----------------------------------------------------------------------------%
 % Copyright (C) 2000-2007, 2011 The University of Melbourne.
 % This file may only be copied under the terms of the GNU Library General
@@ -289,13 +289,19 @@
 :- mode foldr2(pred(in, in, out, in, out) is cc_multi, in, in, out, in, out)
     is cc_multi.
 
-    % `filter(Pred, Set)' removes those elements from `Set' for which
-    % `Pred' fails. In other words, it returns the set consisting of those
-    % elements of `Set' for which `Pred' succeeds.
+    % `filter(Pred, Set) = TrueSet' returns the elements of Set for which
+    % Pred succeeds.
     %
 :- func filter(pred(T), sparse_bitset(T)) = sparse_bitset(T) <= enum(T).
 :- mode filter(pred(in) is semidet, in) = out is det.
 
+    % `filter(Pred, Set, TrueSet, FalseSet)' returns the elements of Set
+    % for which Pred succeeds, and those for which it fails.
+    %
+:- pred filter(pred(T), sparse_bitset(T), sparse_bitset(T), sparse_bitset(T))
+    <= enum(T).
+:- mode filter(pred(in) is semidet, in, out, out) is det.
+
 %-----------------------------------------------------------------------------%
 %-----------------------------------------------------------------------------%
 
@@ -658,9 +664,18 @@
 
 %-----------------------------------------------------------------------------%
 
-% XXX could make this more efficient.
+% XXX We should make these more efficient.
 
-filter(P, S) = S ^ to_sorted_list ^ list.filter(P) ^ sorted_list_to_set.
+filter(Pred, Set) = TrueSet :-
+    SortedList = to_sorted_list(Set),
+    SortedTrueList = list.filter(Pred, SortedList),
+    TrueSet = sorted_list_to_set(SortedTrueList).
+
+filter(Pred, Set, TrueSet, FalseSet) :-
+    SortedList = to_sorted_list(Set),
+    list.filter(Pred, SortedList, SortedTrueList, SortedFalseList),
+    TrueSet = sorted_list_to_set(SortedTrueList),
+    FalseSet = sorted_list_to_set(SortedFalseList).
 
 %-----------------------------------------------------------------------------%
 
Index: library/tree_bitset.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/library/tree_bitset.m,v
retrieving revision 1.8
diff -u -b -r1.8 tree_bitset.m
--- library/tree_bitset.m	19 May 2011 16:20:55 -0000	1.8
+++ library/tree_bitset.m	25 May 2011 08:31:05 -0000
@@ -288,13 +288,19 @@
 :- mode foldr2(pred(in, in, out, in, out) is cc_multi, in, in, out, in, out)
     is cc_multi.
 
-    % `filter(Pred, Set)' removes those elements from `Set' for which
-    % `Pred' fails. In other words, it returns the set consisting of those
-    % elements of `Set' for which `Pred' succeeds.
+    % `filter(Pred, Set) = TrueSet' returns the elements of Set for which
+    % Pred succeeds.
     %
 :- func filter(pred(T), tree_bitset(T)) = tree_bitset(T) <= enum(T).
 :- mode filter(pred(in) is semidet, in) = out is det.
 
+    % `filter(Pred, Set, TrueSet, FalseSet)' returns the elements of Set
+    % for which Pred succeeds, and those for which it fails.
+    %
+:- pred filter(pred(T), tree_bitset(T), tree_bitset(T), tree_bitset(T))
+    <= enum(T).
+:- mode filter(pred(in) is semidet, in, out, out) is det.
+
 %-----------------------------------------------------------------------------%
 %-----------------------------------------------------------------------------%
 
@@ -887,14 +893,20 @@
 
 %-----------------------------------------------------------------------------%
 
-% XXX We should make this more efficient. At least, we could filter the bits in
-% the leaf nodes, yielding a new list of leaf nodes, and we could put the
+% XXX We should make these more efficient. At least, we could filter the bits
+% in the leaf nodes, yielding a new list of leaf nodes, and we could put the
 % interior nodes on top, just as we do in sorted_list_to_set.
 
-filter(Pred, Set0) = Set :-
-    SortedList0 = to_sorted_list(Set0),
-    FilteredList = list.filter(Pred, SortedList0),
-    Set = sorted_list_to_set(FilteredList).
+filter(Pred, Set) = TrueSet :-
+    SortedList = to_sorted_list(Set),
+    SortedTrueList = list.filter(Pred, SortedList),
+    TrueSet = sorted_list_to_set(SortedTrueList).
+
+filter(Pred, Set, TrueSet, FalseSet) :-
+    SortedList = to_sorted_list(Set),
+    list.filter(Pred, SortedList, SortedTrueList, SortedFalseList),
+    TrueSet = sorted_list_to_set(SortedTrueList),
+    FalseSet = sorted_list_to_set(SortedFalseList).
 
 %-----------------------------------------------------------------------------%
 
cvs diff: Diffing mdbcomp
cvs diff: Diffing profiler
cvs diff: Diffing robdd
cvs diff: Diffing runtime
cvs diff: Diffing runtime/GETOPT
cvs diff: Diffing runtime/machdeps
cvs diff: Diffing samples
cvs diff: Diffing samples/c_interface
cvs diff: Diffing samples/c_interface/c_calls_mercury
cvs diff: Diffing samples/c_interface/cplusplus_calls_mercury
cvs diff: Diffing samples/c_interface/mercury_calls_c
cvs diff: Diffing samples/c_interface/mercury_calls_cplusplus
cvs diff: Diffing samples/c_interface/mercury_calls_fortran
cvs diff: Diffing samples/c_interface/simpler_c_calls_mercury
cvs diff: Diffing samples/c_interface/simpler_cplusplus_calls_mercury
cvs diff: Diffing samples/c_interface/standalone_c
cvs diff: Diffing samples/concurrency
cvs diff: Diffing samples/concurrency/dining_philosophers
cvs diff: Diffing samples/concurrency/midimon
cvs diff: Diffing samples/diff
cvs diff: Diffing samples/java_interface
cvs diff: Diffing samples/java_interface/java_calls_mercury
cvs diff: Diffing samples/java_interface/mercury_calls_java
cvs diff: Diffing samples/muz
cvs diff: Diffing samples/rot13
cvs diff: Diffing samples/solutions
cvs diff: Diffing samples/solver_types
cvs diff: Diffing samples/tests
cvs diff: Diffing samples/tests/c_interface
cvs diff: Diffing samples/tests/c_interface/c_calls_mercury
cvs diff: Diffing samples/tests/c_interface/cplusplus_calls_mercury
cvs diff: Diffing samples/tests/c_interface/mercury_calls_c
cvs diff: Diffing samples/tests/c_interface/mercury_calls_cplusplus
cvs diff: Diffing samples/tests/c_interface/mercury_calls_fortran
cvs diff: Diffing samples/tests/c_interface/simpler_c_calls_mercury
cvs diff: Diffing samples/tests/c_interface/simpler_cplusplus_calls_mercury
cvs diff: Diffing samples/tests/diff
cvs diff: Diffing samples/tests/muz
cvs diff: Diffing samples/tests/rot13
cvs diff: Diffing samples/tests/solutions
cvs diff: Diffing samples/tests/toplevel
cvs diff: Diffing scripts
cvs diff: Diffing slice
cvs diff: Diffing ssdb
cvs diff: Diffing tests
cvs diff: Diffing tests/analysis
cvs diff: Diffing tests/analysis/ctgc
cvs diff: Diffing tests/analysis/excp
cvs diff: Diffing tests/analysis/ext
cvs diff: Diffing tests/analysis/sharing
cvs diff: Diffing tests/analysis/table
cvs diff: Diffing tests/analysis/trail
cvs diff: Diffing tests/analysis/unused_args
cvs diff: Diffing tests/benchmarks
cvs diff: Diffing tests/debugger
cvs diff: Diffing tests/debugger/declarative
cvs diff: Diffing tests/dppd
cvs diff: Diffing tests/general
cvs diff: Diffing tests/general/accumulator
cvs diff: Diffing tests/general/string_format
cvs diff: Diffing tests/general/structure_reuse
cvs diff: Diffing tests/grade_subdirs
cvs diff: Diffing tests/hard_coded
cvs diff: Diffing tests/hard_coded/exceptions
cvs diff: Diffing tests/hard_coded/purity
cvs diff: Diffing tests/hard_coded/sub-modules
cvs diff: Diffing tests/hard_coded/typeclasses
cvs diff: Diffing tests/invalid
cvs diff: Diffing tests/invalid/purity
cvs diff: Diffing tests/misc_tests
cvs diff: Diffing tests/mmc_make
cvs diff: Diffing tests/mmc_make/lib
cvs diff: Diffing tests/par_conj
cvs diff: Diffing tests/recompilation
cvs diff: Diffing tests/stm
cvs diff: Diffing tests/stm/orig
cvs diff: Diffing tests/stm/orig/stm-compiler
cvs diff: Diffing tests/stm/orig/stm-compiler/test1
cvs diff: Diffing tests/stm/orig/stm-compiler/test10
cvs diff: Diffing tests/stm/orig/stm-compiler/test2
cvs diff: Diffing tests/stm/orig/stm-compiler/test3
cvs diff: Diffing tests/stm/orig/stm-compiler/test4
cvs diff: Diffing tests/stm/orig/stm-compiler/test5
cvs diff: Diffing tests/stm/orig/stm-compiler/test6
cvs diff: Diffing tests/stm/orig/stm-compiler/test7
cvs diff: Diffing tests/stm/orig/stm-compiler/test8
cvs diff: Diffing tests/stm/orig/stm-compiler/test9
cvs diff: Diffing tests/stm/orig/stm-compiler-par
cvs diff: Diffing tests/stm/orig/stm-compiler-par/bm1
cvs diff: Diffing tests/stm/orig/stm-compiler-par/bm2
cvs diff: Diffing tests/stm/orig/stm-compiler-par/stmqueue
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test1
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test10
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test11
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test2
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test3
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test4
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test5
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test6
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test7
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test8
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test9
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test1
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test2
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test3
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test4
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test5
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test6
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test7
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test8
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test9
cvs diff: Diffing tests/tabling
cvs diff: Diffing tests/term
cvs diff: Diffing tests/trailing
cvs diff: Diffing tests/valid
cvs diff: Diffing tests/warnings
cvs diff: Diffing tools
cvs diff: Diffing trace
cvs diff: Diffing util
cvs diff: Diffing vim
cvs diff: Diffing vim/after
cvs diff: Diffing vim/ftplugin
cvs diff: Diffing vim/syntax
--------------------------------------------------------------------------
mercury-reviews mailing list
Post messages to:       mercury-reviews at csse.unimelb.edu.au
Administrative Queries: owner-mercury-reviews at csse.unimelb.edu.au
Subscriptions:          mercury-reviews-request at csse.unimelb.edu.au
--------------------------------------------------------------------------
Previous message: [m-rev.] diff: reuse int constants in polymorphism
Next message: [m-rev.] for post-commit review: configure.in enhancements
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
More information about the reviews mailing list