[m-rev.] for review: Implement map.equal/2

Paul Bone paul at bone.id.au
Fri Oct 18 15:12:22 AEDT 2013


For review.

Branches: release, master

I'm keen to get this into the next point release so that MCit can use it.


Implement map.equal/2

The equality test operation on 2-3-4 trees tests if they are structurally
equal.  They might also be considered equal if their sets of key-value pairs
are equivalent.  I've created an equal/2 predicate in the tree234 and
map modules in the standard library to test this.

library/tree234.m:
    Implement a predicate to test for tree234 equivalence.

library/map.m:
    Forward map.equal/2 to tree234.equal/2.

NEWS:
    Announce this change in the news file.

tests/general/map_equal.m:
tests/general/map_equal.exp:
    Add test case for map.equal/2

tests/general/Mmakefile:
    Include the new test case.
---
 NEWS                        |   4 ++
 library/map.m               |  21 +++++++
 library/tree234.m           | 131 +++++++++++++++++++++++++++++++++++++++++++-
 tests/general/Mmakefile     |   1 +
 tests/general/map_equal.exp |  10 ++++
 tests/general/map_equal.m   |  65 ++++++++++++++++++++++
 6 files changed, 231 insertions(+), 1 deletion(-)
 create mode 100644 tests/general/map_equal.exp
 create mode 100644 tests/general/map_equal.m

diff --git a/NEWS b/NEWS
index 2fed589..061e073 100644
--- a/NEWS
+++ b/NEWS
@@ -18,6 +18,10 @@ This is a bug-fix release.
   call modulo constructor optimisation on the Java and (probably) C#
   grades.  (Bug #300)
 
+Changes to the Mercury standard library:
+
+* Equality predicates are now defined for 2-3-4 trees and maps.
+
 NEWS for Mercury 13.05.1
 ------------------------
 
diff --git a/library/map.m b/library/map.m
index 3eb8d02..c1d6224 100644
--- a/library/map.m
+++ b/library/map.m
@@ -19,6 +19,15 @@
 % tree234.m.  Virtually all the predicates in this file just
 % forward the work to the corresponding predicate in tree234.m.
 %
+% Note: 2-3-4 trees do not have a canonical representation for any given
+% map.  Therefore, two maps with the same key-value pairs may have different
+% internal representations.  This means that two maps with the same
+% key-value pairs that were constructed differently may fail to unify or
+% compare as unequal, for example if items are inserted into one of the maps
+% in a different order.  This behaviour may change in the future.  See
+% map.equal/2 below which can be used to test if two maps have the same
+% key-value pairs.
+%
 %-----------------------------------------------------------------------------%
 %-----------------------------------------------------------------------------%
 
@@ -49,6 +58,15 @@
     %
 :- pred map.is_empty(map(_, _)::in) is semidet.
 
+    % True if both maps have the same key-value pairs, regardless of how the
+    % maps were constructed.
+    %
+    % Unifying maps does not work as one might expect because the internal
+    % structure of two equivalent maps (according to this predicate) may be
+    % different.
+    %
+:- pred map.equal(map(K, V)::in, map(K, V)::in) is semidet.
+
     % Check whether map contains key
     %
 :- pred map.contains(map(K, _V)::in, K::in) is semidet.
@@ -796,6 +814,9 @@ map.singleton(K, V) =
 map.is_empty(M) :-
     tree234.is_empty(M).
 
+map.equal(MapA, MapB) :-
+    tree234.equal(MapA, MapB).
+
 map.contains(Map, K) :-
     map.search(Map, K, _).
 
diff --git a/library/tree234.m b/library/tree234.m
index 718f6ab..21a33d4 100644
--- a/library/tree234.m
+++ b/library/tree234.m
@@ -37,6 +37,8 @@
 
 :- pred tree234.is_empty(tree234(K, V)::in) is semidet.
 
+:- pred tree234.equal(tree234(K, V)::in, tree234(K, V)::in) is semidet.
+
 %----------------------%
 
 :- pred tree234.member(tree234(K, V)::in, K::out, V::out) is nondet.
@@ -567,6 +569,7 @@
 :- import_module int.
 :- import_module io.
 :- import_module pair.
+:- import_module private_builtin.
 :- import_module require.
 :- import_module set.
 :- import_module string.
@@ -607,6 +610,132 @@ tree234.singleton(K, V) = two(K, V, empty, empty).
 tree234.is_empty(Tree) :-
     Tree = empty.
 
+tree234.equal(MapA, MapB) :-
+    ( pointer_equal(MapA, MapB) ->
+        true
+    ;
+        equal(MapA, [MapB], [])
+    ).
+
+    % Use a stack to store the unexplored parts of B while you recurse on A
+    % matcking KV pairs.  use two nested loops, the out loop recurses on A,
+    % the inner loop matches from B and the explicit stack.
+    %
+    % Note that B is conceptually the top of B's stack.  Allowing us to use
+    % it to make pointer comprisons.
+    %
+:- pred equal(tree234(K, V)::in,
+    list(tree234(K, V))::in, list(tree234(K, V))::out) is semidet.
+
+equal(MapA, !StackB) :-
+    (
+        !.StackB = [MapB | !:StackB],
+        pointer_equal(MapA, MapB)
+    ->
+        true
+    ;
+        require_complete_switch [MapA]
+        (
+            MapA = empty
+        ;
+            MapA = two(K, V, Left, Right),
+            equal(Left, !StackB),
+            match_kv(K, V, !StackB),
+            equal(Right, !StackB)
+        ;
+            MapA = three(K1, V1, K2, V2, Left, Middle, Right),
+            equal(Left, !StackB),
+            match_kv(K1, V1, !StackB),
+            equal(Middle, !StackB),
+            match_kv(K2, V2, !StackB),
+            equal(Right, !StackB)
+        ;
+            MapA = four(K1, V1, K2, V2, K3, V3,
+                Left, MidLeft, MidRight, Right),
+            equal(Left, !StackB),
+            match_kv(K1, V1, !StackB),
+            equal(MidLeft, !StackB),
+            match_kv(K2, V2, !StackB),
+            equal(MidRight, !StackB),
+            match_kv(K3, V3, !StackB),
+            equal(Right, !StackB)
+        )
+    ).
+
+:- pred match_kv(K::in, V::in,
+    list(tree234(K, V))::in, list(tree234(K, V))::out) is semidet.
+
+match_kv(K, V, !Stack) :-
+    !.Stack = [B | !:Stack],
+    match_kv(K, V, B, !Stack).
+
+    % match_kv(K, V, Top, !Stack)
+    %
+    % Match a key-value pair against one item from the stack of trees.
+    % If the match is successful then the matched item from the stack is
+    % updated.  Top is the top of the input stack.
+    %
+:- pred match_kv(K::in, V::in, tree234(K, V)::in,
+    list(tree234(K, V))::in, list(tree234(K, V))::out) is semidet.
+
+match_kv(K, V, B, !Stack) :-
+    require_complete_switch [B]
+    (
+        B = empty,
+        % This case is rarely executed, because empty items are never put on
+        % the stack within match_kv/4 or match_kv/5.
+        match_kv(K, V, !Stack)
+    ;
+        B = two(K1, V1, Left, Right),
+        ( Left = empty ->
+            % Try to match the items.
+            K = K1,
+            V = V1,
+            % Update stack and return.
+            ( Right \= empty ->
+                !:Stack = [Right | !.Stack]
+            ;
+                true
+            )
+        ;
+            % Break up this node and recurse
+            !:Stack = [two(K1, V1, empty, Right) | !.Stack],
+            match_kv(K, V, Left, !Stack)
+        )
+    ;
+        B = three(K1, V1, K2, V2, Left, Middle, Right),
+
+        % This case has the same structure as the one above.
+        ( Left = empty ->
+            K = K1,
+            V = V1,
+
+            % We've eliminated Left and V1-V2, so we can build a two node
+            % from the rest of the three node.
+            !:Stack = [two(K2, V2, Middle, Right) | !.Stack]
+        ;
+            !:Stack = [three(K1, V1, K2, V2, empty, Middle, Right) |
+                !.Stack],
+            % Pull the leftmost node out and try to match on it.
+            match_kv(K, V, Left, !Stack)
+        )
+    ;
+        B = four(K1, V1, K2, V2, K3, V3, Left, MidLeft, MidRight, Right),
+
+        % This case has the same structure as the previous two cases.
+        ( Left = empty ->
+            K = K1,
+            V = V1,
+            !:Stack = [three(K2, V2, K3, V3, MidLeft, MidRight, Right) |
+                !.Stack]
+        ;
+            !:Stack = [four(K1, V1, K2, V2, K3, V3, empty, MidLeft,
+                    MidRight, Right)
+                | !.Stack],
+            match_kv(K, V, Left, !Stack)
+        )
+    ).
+
 %------------------------------------------------------------------------------%
 %------------------------------------------------------------------------------%
 
@@ -3143,7 +3272,7 @@ tree234.keys_and_values_acc(three(K0, V0, K1, V1, T0, T1, T2),
     !:Values = [V0 | !.Values],
     tree234.keys_and_values_acc(T0, !Keys, !Values).
 tree234.keys_and_values_acc(four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3),
-        !Keys, !Values) :- 
+        !Keys, !Values) :-
     tree234.keys_and_values_acc(T3, !Keys, !Values),
     !:Keys = [K2 | !.Keys],
     !:Values = [V2 | !.Values],
diff --git a/tests/general/Mmakefile b/tests/general/Mmakefile
index c6a8c7b..b83817f 100644
--- a/tests/general/Mmakefile
+++ b/tests/general/Mmakefile
@@ -37,6 +37,7 @@ ORDINARY_PROGS=	\
 		io_regression \
 		liveness \
 		liveness2 \
+		map_equal \
 		mode_inf \
 		mode_inf_bug \
 		mode_inference_reorder \
diff --git a/tests/general/map_equal.exp b/tests/general/map_equal.exp
new file mode 100644
index 0000000..b2f4290
--- /dev/null
+++ b/tests/general/map_equal.exp
@@ -0,0 +1,10 @@
+Map1 = Map1: unifiable, equal
+Map1 = Map1Copy: unifiable, equal
+Map1 = Map2: not unifiable, not equal
+Map2 = Map1: not unifiable, not equal
+Map1 = empty: not unifiable, not equal
+empty = Map1: not unifiable, not equal
+empty = empty: unifiable, equal
+empty = copy(empty): unifiable, equal
+Map3 = Map4: not unifiable, equal
+Map4 = Map3: not unifiable, equal
diff --git a/tests/general/map_equal.m b/tests/general/map_equal.m
new file mode 100644
index 0000000..a025085
--- /dev/null
+++ b/tests/general/map_equal.m
@@ -0,0 +1,65 @@
+%------------------------------------------------------------------------------%
+% map_equal.m
+% Paul Bone
+% vim: ft=mercury ff=unix ts=4 sw=4 et
+%------------------------------------------------------------------------------%
+
+:- module map_equal.
+
+:- interface.
+
+:- import_module io.
+
+:- pred main(io::di, io::uo) is det.
+
+%------------------------------------------------------------------------------%
+%------------------------------------------------------------------------------%
+
+:- implementation.
+
+:- import_module list.
+:- import_module map.
+:- import_module pair.
+:- import_module string.
+
+%------------------------------------------------------------------------------%
+
+main(!IO) :-
+    List1 = [1 - 1, 2 - 2, 3 - 3, 5 - 5, 6 - 6,
+        7 - 7, 9 - 9, 10 - 10],
+    map.from_assoc_list(List1, Map1),
+    test("Map1 = Map1", Map1, Map1, !IO),
+    copy(Map1, Map1Copy),
+    test("Map1 = Map1Copy", Map1, Map1Copy, !IO),
+    set(7, 49, Map1, Map2),
+    test("Map1 = Map2", Map1, Map2, !IO),
+    test("Map2 = Map1", Map2, Map1, !IO),
+
+    EmptyMap = map.init,
+    test("Map1 = empty", Map1, EmptyMap, !IO),
+    test("empty = Map1", EmptyMap, Map1, !IO),
+    test("empty = empty", EmptyMap, EmptyMap, !IO),
+    copy(EmptyMap, EmptyMap2),
+    test("empty = copy(empty)", EmptyMap, EmptyMap2, !IO),
+
+    map.from_assoc_list(List1, Map3),
+    map.from_assoc_list(reverse(List1), Map4),
+    test("Map3 = Map4", Map3, Map4, !IO),
+    test("Map4 = Map3", Map3, Map4, !IO).
+
+:- pred test(string::in, map(K, V)::in, map(K, V)::in, io::di, io::uo) is det.
+
+test(Name, A, B, !IO) :-
+    ( map.equal(A, B) ->
+        EqualRes = "equal"
+    ;
+        EqualRes = "not equal"
+    ),
+    ( unify(A, B) ->
+        UnifyRes = "unifiable"
+    ;
+        UnifyRes = "not unifiable"
+    ),
+    io.format("%s: %s, %s\n", [s(Name), s(UnifyRes), s(EqualRes)], !IO).
+
+%------------------------------------------------------------------------------%
-- 
1.8.4.rc3




More information about the reviews mailing list