[m-rev.] for review: efficient insertion of duplicate items into bags

[Julien Fischer]

For review by anyone.

----------

Efficient insertion of duplicate items into bags.

library/bag.m:
     Add predicates and a function for efficiently inserting multiple copies of
     an item into a bag.

NEWS:
     Announce the above additions.

tests/hard_coded/bag_various.{m,exp}:
     Extend this test to cover the above.

Julien.

diff --git a/NEWS b/NEWS
index 9c23b12f0..e1987374c 100644
--- a/NEWS
+++ b/NEWS
@@ -446,6 +446,12 @@ Changes to the Mercury standard library:
    - return_sccs_in_from_to_order/1
    - return_sccs_in_to_from_order/1

+* We have added the following predicates and function to the bag module:
+
+  - insert_duplicates/4
+  - det_insert_duplicates/4
+  - det_insert_duplicates/3
+
  Changes to the Mercury compiler:

  * We have added a new option --warn-dead-preds. While the existing option
diff --git a/library/bag.m b/library/bag.m
index 2cd115342..968725e26 100644
--- a/library/bag.m
+++ b/library/bag.m
@@ -83,6 +83,17 @@
  :- func insert_list(bag(T), list(T)) = bag(T).
  :- pred insert_list(list(T)::in, bag(T)::in, bag(T)::out) is det.

+    % Insert N copies of a particular value into a bag.
+    % Fails if N < 0.
+    %
+:- pred insert_duplicates(int::in, T::in, bag(T)::in, bag(T)::out)
+    is semidet.
+
+    % As above, but throws an exception if N < 0.
+    %
+:- func det_insert_duplicates(bag(T), int, T) = bag(T).
+:- pred det_insert_duplicates(int::in, T::in, bag(T)::in, bag(T)::out) is det.
+
      % Insert a set of values into a bag.
      %
  :- func insert_set(bag(T), set(T)) = bag(T).
@@ -433,6 +444,32 @@ insert_list([Item | Items], !Bag) :-
      bag.insert(Item, !Bag),
      bag.insert_list(Items, !Bag).

+insert_duplicates(N, Item, bag(!.Map), bag(!:Map)) :-
+    compare(CmpResult, N, 0),
+    (
+        CmpResult = (>),
+        ( if map.search(!.Map, Item, Count) then
+            map.det_update(Item, Count + N, !Map)
+        else
+            map.det_insert(Item, N, !Map)
+        )
+    ;
+        CmpResult = (=)
+    ;
+        CmpResult = (<),
+        fail
+    ).
+
+det_insert_duplicates(!.Bag, N, Item) = !:Bag :-
+    det_insert_duplicates(N, Item, !Bag).
+
+det_insert_duplicates(N, Item, !Bag) :-
+    ( if insert_duplicates(N, Item, !Bag) then
+        true
+    else
+        error("bag.det_insert_duplicates: number of items is negative")
+    ).
+
  insert_set(!.Bag, Xs) = !:Bag :-
      bag.insert_set(Xs, !Bag).

diff --git a/tests/hard_coded/bag_various.exp b/tests/hard_coded/bag_various.exp
index e8ae4c23e..3e8ef8510 100644
--- a/tests/hard_coded/bag_various.exp
+++ b/tests/hard_coded/bag_various.exp
@@ -5,3 +5,7 @@ bag.count_unique: 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]}]
+bag.insert_duplicates(5, "foo"): ["foo", "foo", "foo", "foo", "foo"]
+bag.insert_duplicates(0, "foo"): []
+bag.insert_duplicates(-1, "foo"): "fail"
+bag.insert_duplicates(4, "foo"): ["foo", "foo", "foo", "foo", "foo"]
diff --git a/tests/hard_coded/bag_various.m b/tests/hard_coded/bag_various.m
index f1e96b73e..c3eb24b48 100644
--- a/tests/hard_coded/bag_various.m
+++ b/tests/hard_coded/bag_various.m
@@ -39,11 +39,28 @@ main(!IO) :-
          O = {M, []++to_list(Rest)}
      ), Sols),
      dump("unsorted_solutions(bag.member/3): ", Sols, !IO),
+
+    test_insert_duplicates(5, bag.init, !IO),
+    test_insert_duplicates(0, bag.init, !IO),
+    test_insert_duplicates(-1, bag.init, !IO),
+    test_insert_duplicates(4, bag.from_list(["foo"]), !IO),
+
      true.

+:- pred test_insert_duplicates(int::in, bag(string)::in, io::di, io::uo)
+    is det.
+
+test_insert_duplicates(N, Bag0, !IO) :-
+    Prefix = "bag.insert_duplicates(" ++ int_to_string(N) ++ ", \"foo\"): ",
+    ( if bag.insert_duplicates(N, "foo", Bag0, Bag) then
+        bag.to_list(Bag, List),
+        dump(Prefix, List, !IO)
+    else
+        dump(Prefix, "fail", !IO)
+    ).
+
  :- 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).
+    io.write_string(Msg, !IO),
+    io.write_line(T, !IO).