[m-rev.] for review: fix behaviour of multi_map.det_update/4

Julien Fischer juliensf at csse.unimelb.edu.au
Mon Jul 11 14:06:10 AEST 2011


Branches: main, 11.07

Fix a bug reported by Tomas By on mercury-bugs: the behaviour of
multi_map.det_update/4 did not match the documentation.

library/multi_map.m:
 	Fix the behaviour of det_update/4.

 	Add replace/4, a semidet version of det_replace/4.

 	Reformat some documentation.

NEWS:
 	Announce the above fix and addition.

tests/hard_coded/multi_map_test.{m,exp}:
 	Replace the existing test for multi_maps with something a bit
 	stronger: in particular check the semantics of update, replace,
 	insert and set.

Julien.

Index: NEWS
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/NEWS,v
retrieving revision 1.587
diff -u -r1.587 NEWS
--- NEWS	26 Jun 2011 14:12:49 -0000	1.587
+++ NEWS	11 Jul 2011 02:52:24 -0000
@@ -193,4 +193,8 @@
    additional modes for maybe.fold_maybe/4, maybe.map_fold_maybe/5,
    and maybe.map_fold2_maybe/7.

+* The implementation of multi_map.det_update/4 has been fixed so that it
+  conforms the documented behaviour.  The new predicate multi_map.replace/4
+  has been added.
+
  For news about earlier versions, see the HISTORY file.
Index: library/multi_map.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/library/multi_map.m,v
retrieving revision 1.26
diff -u -r1.26 multi_map.m
--- library/multi_map.m	3 May 2011 04:35:01 -0000	1.26
+++ library/multi_map.m	11 Jul 2011 03:59:25 -0000
@@ -78,27 +78,33 @@
      multi_map(K, V)::in, multi_map(K, V)::out) is semidet.

      % Insert a new key and corresponding value into a multi_map.
-    % Abort if the key already exists.
+    % Aborts if the key already exists.
      %
  :- func multi_map.det_insert(multi_map(K, V), K, V) = multi_map(K, V).
  :- pred multi_map.det_insert(K::in, V::in,
      multi_map(K, V)::in, multi_map(K, V)::out) is det.

      % Update (add) the value corresponding to a given key.
-    % Fail if the key does not already exist.
+    % Fails if the key does not already exist.
      %
  :- pred multi_map.update(K::in, V::in,
      multi_map(K, V)::in, multi_map(K, V)::out) is semidet.

      % Update (add) the value corresponding to a given key.
-    % Abort if the key does not already exist.
+    % Aborts if the key does not already exist.
      %
  :- func multi_map.det_update(multi_map(K, V), K, V) = multi_map(K, V).
  :- pred multi_map.det_update(K::in, V::in,
      multi_map(K, V)::in, multi_map(K, V)::out) is det.

      % Update (replace) the value corresponding to a given key.
-    % Abort if the key does not already exist.
+    % Fails if the key does not already exist.
+    %
+:- pred multi_map.replace(K::in, list(V)::in,
+    multi_map(K, V)::in, multi_map(K, V)::out) is semidet.
+
+    % Update (replace) the value corresponding to a given key.
+    % Aborts if the key does not already exist.
      %
  :- func multi_map.det_replace(multi_map(K, V), K, list(V)) = multi_map(K, V).
  :- pred multi_map.det_replace(K::in, list(V)::in,
@@ -174,13 +180,13 @@
      multi_map(K, V)::in, multi_map(K, V)::out) is det.

      % Delete a key-value pair from a multi_map and return the value.
-    % fail if the key is not present.
+    % Fails if the key is not present.
      %
  :- pred multi_map.remove(K::in, list(V)::out,
      multi_map(K, V)::in, multi_map(K, V)::out) is semidet.

      % Delete a key-value pair from a multi_map and return the value.
-    % Abort if the key is not present.
+    % Aborts if the key is not present.
      %
  :- pred multi_map.det_remove(K::in, list(V)::out,
      multi_map(K, V)::in, multi_map(K, V)::out) is det.
@@ -246,8 +252,8 @@
  :- func multi_map.optimize(multi_map(K, V)) = multi_map(K, V).
  :- pred multi_map.optimize(multi_map(K, V)::in, multi_map(K, V)::out) is det.

-    % Remove the smallest item from the multi_map, fail if
-    % the multi_map is empty.
+    % Remove the smallest item from the multi_map.
+    % Fails if the multi_map is empty.
      %
  :- pred multi_map.remove_smallest(K::out, list(V)::out,
      multi_map(K, V)::in, multi_map(K, V)::out) is semidet.
@@ -302,7 +308,14 @@
      map.update(Key, Values, !MultiMap).

  multi_map.det_update(Key, Value, !MultiMap) :-
-    map.det_update(Key, [Value], !MultiMap).
+    ( if multi_map.update(Key, Value, !MultiMap) then
+        true
+      else
+         report_lookup_error("multi_map.det_update: key not found", Key)
+    ).
+
+multi_map.replace(Key, Value, !MultiMap) :-
+    map.update(Key, Value, !MultiMap).

  multi_map.det_replace(Key, Value, !MultiMap) :-
      map.det_update(Key, Value, !MultiMap).
Index: tests/hard_coded/multi_map_test.exp
===================================================================
RCS file: /home/mercury/mercury1/repository/tests/hard_coded/multi_map_test.exp,v
retrieving revision 1.1
diff -u -r1.1 multi_map_test.exp
--- tests/hard_coded/multi_map_test.exp	20 Aug 2002 00:44:20 -0000	1.1
+++ tests/hard_coded/multi_map_test.exp	11 Jul 2011 03:58:10 -0000
@@ -1 +1,14 @@
-[11, 13]
+[13, 11]
+PASSED: is_empty(EmptyMap) succeeded
+PASSED: is_empty(Map) failed
+det_insert/4: [1 - [13, 11], 2 - [22], 3 - [34]]
+insert/4 (test 1): PASSED: [1 - [13, 11], 2 - [22], 3 - [34]]
+insert/4 (test 2) PASSED
+det_update/4: [1 - [14, 13, 11], 2 - [22]]
+update/4 (test 1): PASSED: [1 - [14, 13, 11], 2 - [22]]
+update/4 (test 2): PASSED
+det_replace/4: [1 - [561, 562, 563], 2 - [22]]
+replace/4 (test 1): PASSED: [1 - [561, 562, 563], 2 - [22]]
+replace/4 (test 2): PASSED
+set/4 (test 1): [1 - [12]]
+set/4 (test 2): [1 - [14, 13, 11], 2 - [22]]
Index: tests/hard_coded/multi_map_test.m
===================================================================
RCS file: /home/mercury/mercury1/repository/tests/hard_coded/multi_map_test.m,v
retrieving revision 1.1
diff -u -r1.1 multi_map_test.m
--- tests/hard_coded/multi_map_test.m	20 Aug 2002 00:44:20 -0000	1.1
+++ tests/hard_coded/multi_map_test.m	11 Jul 2011 03:57:49 -0000
@@ -1,14 +1,129 @@
+% vim: ft=mercury ts=4 sw=4 et
+
  :- module multi_map_test.
  :- interface.
+
  :- import_module io.
-:- pred main(io__state::di, io__state::uo) is det.
+
+:- pred main(io::di, io::uo) is det.
+
  :- implementation.
-:- import_module multi_map, list, std_util.

-main -->
-	{ multi_map__from_corresponding_lists([1,  2,  1], [11, 22, 13], M) },
-	{ multi_map__lookup(M, 1, Vs0) },
-	{ list__sort_and_remove_dups(Vs0, Vs) },
-	io__write(Vs),
-	io__nl.
+:- import_module assoc_list.
+:- import_module list.
+:- import_module multi_map.
+
+main(!IO) :-
+    multi_map.init(EmptyMap : multi_map(int, int)),
+    Map = multi_map.from_corresponding_lists([1,  2,  1], [11, 22, 13]),
+
+    % Test multi_map.lookup.
+    %
+    Vs = multi_map.lookup(Map, 1) : list(int),
+    io.write(Vs, !IO),
+    io.nl(!IO),
+
+    % Test is_empty.
+    %
+    ( if multi_map.is_empty(EmptyMap) then
+        io.write_string("PASSED: is_empty(EmptyMap) succeeded\n", !IO)
+      else
+        io.write_string("FAILED: is_empty(EmptyMap) failed\n", !IO)
+    ),
+    ( if multi_map.is_empty(Map) then
+        io.write_string("FAILED: is_empty(Map) succeeded\n", !IO)
+      else
+        io.write_string("PASSED: is_empty(Map) failed\n", !IO)
+    ),
+
+    % Test insertion.
+    %
+    multi_map.det_insert(3, 34, Map, InsertMap),
+    multi_map.to_assoc_list(InsertMap, AL),
+    io.write_string("det_insert/4: ", !IO),
+    io.write(AL, !IO),
+    io.nl(!IO),
+
+    ( if multi_map.insert(3, 34, Map, InsertMap2) then
+        multi_map.to_assoc_list(InsertMap2, AL2),
+        io.write_string("insert/4 (test 1): PASSED: ", !IO),
+        io.write(AL2, !IO),
+        io.nl(!IO)
+      else
+        io.write_string("insert/4 test 1): FAILED\n", !IO)
+    ),
+
+    ( if multi_map.insert(1, 14, Map, InsertMap3) then
+        multi_map.to_assoc_list(InsertMap3, AL3),
+        io.write_string("insert/4 (test 2) FAILED: ", !IO),
+        io.write(AL3, !IO),
+        io.nl(!IO)
+      else
+        io.write_string("insert/4 (test 2) PASSED\n", !IO)
+    ),
+
+    % Test update.
+    %
+    multi_map.det_update(1, 14, Map, UpdateMap),
+    multi_map.to_assoc_list(UpdateMap, UAL),
+    io.write_string("det_update/4: ", !IO),
+    io.write(UAL, !IO),
+    io.nl(!IO),
+
+    ( if multi_map.update(1, 14, Map, UpdateMap1) then
+        multi_map.to_assoc_list(UpdateMap1, UAL1),
+        io.write_string("update/4 (test 1): PASSED: ", !IO),
+        io.write(UAL1, !IO),
+        io.nl(!IO)
+     else 
+        io.write_string("update/4 (test 1): FAILED\n", !IO)
+    ),
+
+    ( if multi_map.update(1, 14, EmptyMap, UpdateMap2) then
+        multi_map.to_assoc_list(UpdateMap2, UAL2),
+        io.write_string("update/4 (test 2): FAILED: ", !IO),
+        io.write(UAL2, !IO),
+        io.nl(!IO)
+     else 
+        io.write_string("update/4 (test 2): PASSED\n", !IO)
+    ),
+
+    % Test replace.
+    %
+    multi_map.det_replace(1, [561, 562, 563], Map, ReplaceMap),
+    multi_map.to_assoc_list(ReplaceMap, RAL),
+    io.write_string("det_replace/4: ", !IO),
+    io.write(RAL, !IO),
+    io.nl(!IO),
+
+    ( if multi_map.replace(1, [561, 562, 563], Map, ReplaceMap1) then
+        multi_map.to_assoc_list(ReplaceMap1, RAL1),
+        io.write_string("replace/4 (test 1): PASSED: ", !IO),
+        io.write(RAL1, !IO),
+        io.nl(!IO)
+      else
+        io.write_string("replace/4 (test 1): FAILED\n", !IO)
+    ),
+
+    ( if multi_map.replace(1, [561, 562, 563], EmptyMap, ReplaceMap2) then
+        multi_map.to_assoc_list(ReplaceMap2, RAL2),
+        io.write_string("replace/4 (test 2): FAILED: ", !IO),
+        io.write(RAL2, !IO),
+        io.nl(!IO)
+      else 
+        io.write_string("replace/4 (test 2): PASSED\n", !IO)
+    ),
+ 
+    % Test set
+    %
+    multi_map.set(1, 12, EmptyMap, SetMap),
+    multi_map.to_assoc_list(SetMap, SAL),
+    io.write_string("set/4 (test 1): ", !IO),
+    io.write(SAL, !IO),
+    io.nl(!IO),

+    multi_map.set(1, 14, Map, SetMap2),
+    multi_map.to_assoc_list(SetMap2, SAL2),
+    io.write_string("set/4 (test 2): ", !IO),
+    io.write(SAL2, !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
--------------------------------------------------------------------------



More information about the reviews mailing list