[m-rev.] for review: new funcs and preds in the bag module

[Ondrej Bojar]

An easy review for anyone. (Peter? Ralph?)

Estimated hours taken: 0.75
Branch: main

Add functions bag.count/1, bag.unique_elements/1 and predicates bag.member/2
and bag.member/3 to the bag module.

NEWS:
     Announce the added predicates and functions.
     Minor indentation unification.

library/bag.m:
     New functions and predicates.

tests/hard_coded/bag_various.m:
tests/hard_coded/bag_various.exp:
     A simple testcase for the new predicates, with expected results.

tests/hard_coded/Mmakefile:
     Enabled the test.


Index: NEWS
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/NEWS,v
retrieving revision 1.450
diff -u -r1.450 NEWS
--- NEWS	6 Mar 2007 04:22:37 -0000	1.450
+++ NEWS	8 Mar 2007 05:28:37 -0000
@@ -48,11 +48,17 @@
     determinism multi.

  * The following functions have been added to the string module:
-        string.split_at_separator/2
-        string.split_at_char/2
-        string.split_at_string/2
+	string.split_at_separator/2
+	string.split_at_char/2
+	string.split_at_string/2
  	string.remove_suffix_if_present/2

+* The following functions and predicates have been added to the bag module:
+	bag.count/1
+	bag.unique_elements/1
+	bag.member/2
+	bag.member/3
+
  * We have changed the interface of the ops module to make lookups of operators
    more efficient.

Index: library/bag.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/library/bag.m,v
retrieving revision 1.31
diff -u -r1.31 bag.m
--- library/bag.m	23 Oct 2006 00:32:55 -0000	1.31
+++ library/bag.m	8 Mar 2007 05:28:37 -0000
@@ -31,6 +31,16 @@
  :- pred bag.init(bag(T)::out) is det.
  :- func bag.init = bag(T).

+    % Return the number of elements in a bag, duplicit elements are counted
+    % as many times as they occur in the bag.
+    %
+:- func bag.count(bag(T)) = int.
+
+    % Return the number of unique elements in a bag, duplicit elements are
+    % counted only once.
+    %
+:- func bag.unique_elements(bag(T)) = int.
+
      % Insert a particular value in a bag.
      %
  :- pred bag.insert(bag(T)::in, T::in, bag(T)::out) is det.
@@ -46,6 +56,18 @@
  :- pred bag.insert_set(bag(T)::in, set(T)::in, bag(T)::out) is det.
  :- func bag.insert_set(bag(T), set(T)) = bag(T).

+    % bag.member(Elem, Bag) :
+    %   True iff `Bag' contains at least one occurrence of `Elem'.
+    %
+:- pred bag.member(T::in, bag(T)::in) is semidet.
+
+    % bag.member(Elem, Bag, Remainder) :
+    %   Nondeterministically returns all elements from Bag and the
+    %   corresponding bag after the element removed. Duplicit items are
+    %   returned as many times as they occur in the Bag.
+    %
+:- pred bag.member(T::out, bag(T)::in, bag(T)::out) is nondet.
+
      % Make a bag from a list.
      %
  :- func bag.bag(list(T)) = bag(T).
@@ -237,6 +259,18 @@

  %---------------------------------------------------------------------------%

+bag.count(Bag) =
+    list.foldl(func(A, B) = A+B,
+        map.values(Bag),
+        0
+    ).
+
+%---------------------------------------------------------------------------%
+
+bag.unique_elements(Bag) = map.count(Bag).
+
+%---------------------------------------------------------------------------%
+
  bag.insert(Bag0, Item, Bag) :-
      ( map.search(Bag0, Item, Count0) ->
          Count = Count0 + 1
@@ -257,6 +291,13 @@
      % XXX We should exploit the sortedness of List.
      bag.insert_list(Bag0, List, Bag).

+bag.member(M, Bag) :- map.search(Bag, M, _Occurrences).
+
+bag.member(OutElem, InBag, OutBag) :-
+  Elems = bag.to_list(InBag),
+  list.member(OutElem, Elems),
+  OutBag = bag.det_remove(InBag, OutElem).
+
  bag.from_list(List, Bag) :-
      bag.init(Bag0),
      bag.insert_list(Bag0, List, Bag).
Index: tests/hard_coded/Mmakefile
===================================================================
RCS file: /home/mercury/mercury1/repository/tests/hard_coded/Mmakefile,v
retrieving revision 1.312
diff -u -r1.312 Mmakefile
--- tests/hard_coded/Mmakefile	27 Feb 2007 02:12:37 -0000	1.312
+++ tests/hard_coded/Mmakefile	8 Mar 2007 05:28:37 -0000
@@ -12,6 +12,7 @@
  	any_free_unify \
  	array_test \
  	backquoted_qualified_ops \
+	bag_various \
  	bidirectional \
  	bitmap_test \
  	boyer \
Index: tests/hard_coded/bag_various.exp
===================================================================
RCS file: tests/hard_coded/bag_various.exp
diff -N tests/hard_coded/bag_various.exp
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ tests/hard_coded/bag_various.exp	8 Mar 2007 05:28:37 -0000
@@ -0,0 +1,7 @@
+bag.to_list: [1, 1, 1, 2, 3, 3, 4]
+bag.to_assoc_list: [1 - 3, 2 - 1, 3 - 2, 4 - 1]
+bag.count: 7
+bag.unique_elements: 4
+bag.member(4): yes
+bag.member(5): no
+unsorted_solutions(bag.member/3): [{4, [1, 1, 1, 2, 3, 3]}, {3, [1, 1, 1, 2, 3, 
4]}, {3, [1, 1, 1, 2, 3, 4]}, {2, [1, 1, 1, 3, 3, 4]}, {1, [1, 1, 2, 3, 3, 4]}, 
{1, [1, 1, 2, 3, 3, 4]}, {1, [1, 1, 2, 3, 3, 4]}]
Index: tests/hard_coded/bag_various.m
===================================================================
RCS file: tests/hard_coded/bag_various.m
diff -N tests/hard_coded/bag_various.m
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ tests/hard_coded/bag_various.m	8 Mar 2007 05:28:37 -0000
@@ -0,0 +1,41 @@
+:- module bag_various.
+% basic test of some bag predicates
+:- interface.
+:- import_module io.
+
+:- pred main(io::di, io::uo) is cc_multi.
+
+:- implementation.
+
+:- import_module bag, string, list, int, solutions, bool.
+
+main(!IO) :-
+  Bag = bag.from_list([1,1,1,2,3,3,4]),
+  dump("bag.to_list: ", []++bag.to_list(Bag), !IO),
+  dump("bag.to_assoc_list: ", []++bag.to_assoc_list(Bag), !IO),
+  dump("bag.count: ", 0+bag.count(Bag), !IO),
+  dump("bag.unique_elements: ", 0+bag.unique_elements(Bag), !IO),
+  (
+  if bag.member(4, Bag)
+  then dump("bag.member(4): ", yes, !IO)
+  else dump("bag.member(4): ", no, !IO)
+  ),
+  (
+  if bag.member(5, Bag)
+  then dump("bag.member(5): ", yes, !IO)
+  else dump("bag.member(5): ", no, !IO)
+  ),
+  unsorted_solutions(
+    (pred(O::out) is nondet:-
+      bag.member(M, Bag, Rest),
+      O = {M, []++to_list(Rest)}
+    ), Sols),
+  dump("unsorted_solutions(bag.member/3): ", Sols, !IO),
+  true.
+
+:- pred dump(string::in, T::in, io::di, io::uo) is det.
+dump(Msg, T, !IO) :-
+  io__write_string(Msg, !IO),
+  io__write(T, !IO),
+  io__nl(!IO).
+
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------