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

[Paul Bone]

For review by Julien

Implement map.equivalent/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 equivalent/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.equivalent/2 to tree234.equivalent/2.

NEWS:
    Announce this change in the news file.
---
 NEWS              |  4 +++
 library/map.m     | 21 +++++++++++++
 library/tree234.m | 92 ++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 3 files changed, 116 insertions(+), 1 deletion(-)

diff --git a/NEWS b/NEWS
index d3c6eac..03ed031 100644
--- a/NEWS
+++ b/NEWS
@@ -11,6 +11,10 @@ This is a bug-fix release.
   for shared libraries and the LD_LIBFLAGS and EXTRA_LD_LIBFLAGS mmake
   variables.  (Bug #288)
 
+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..c864a23 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.equivalent/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.equivalent(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.equivalent(MapA, MapB) :-
+    tree234.equivalent(MapA, MapB).
+
 map.contains(Map, K) :-
     map.search(Map, K, _).
 
diff --git a/library/tree234.m b/library/tree234.m
index 718f6ab..525dbe6 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.equivalent(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.
 :- import_module require.
 :- import_module set.
 :- import_module string.
@@ -607,6 +610,93 @@ tree234.singleton(K, V) = two(K, V, empty, empty).
 tree234.is_empty(Tree) :-
     Tree = empty.
 
+tree234.equivalent(MapA, MapB) :-
+    ( pointer_equals(MapA, MapB) ->
+        true
+    ;
+        equivalent(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 equivalent(tree234(K, V)::in,
+    list(tree234(K, V))::in, list(tree234(K, V))::out) is semidet.
+
+equivalent(MapA, !StackB) :-
+    (
+        !.StackB = [MapB | !:StackB],
+        pointer_equals(MapA, MapB)
+    ->
+        true
+    ;
+        require_complete_switch [MapA]
+        (
+            MapA = empty
+        ;
+            MapA = two(K, V, Left, Right),
+            equivalent(Left, !StackB),
+            match_kv(K, V, !StackB),
+            equivalent(Right, !StackB)
+        ;
+            MapA = three(K1, V1, K2, V2, Left, Middle, Right),
+            equivalent(Left, !StackB),
+            match_kv(K1, V1, !StackB),
+            equivalent(Middle, !StackB),
+            match_kv(K2, V2, !StackB),
+            equivalent(Right, !StackB)
+        ;
+            MapA = four(K1, V1, K2, V2, K3, V3,
+                Left, MidLeft, MidRight, Right),
+            equivalent(Left, !StackB),
+            match_kv(K1, V1, !StackB),
+            equivalent(MidLeft, !StackB),
+            match_kv(K2, V2, !StackB),
+            equivalent(MidRight, !StackB),
+            match_kv(K3, V3, !StackB),
+            equivalent(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],
+    require_complete_switch [B]
+    (
+        B = empty,
+        match_kv(K, V, !Stack)
+    ;
+        B = two(KA, VA, Left, Right),
+        ( Left = empty ->
+            % Try to match the items.
+            K = KA,
+            V = VA,
+            % Update stack and return.
+            !:Stack = [Right | !.Stack]
+        ;
+            % Break up this node and recurse
+            !:Stack = [Left, two(KA, VA, empty, Right) | !.Stack],
+            match_kv(K, V, !Stack)
+        )
+    ;
+        B = three(K1, V1, K2, V2, Left, Middle, Right),
+        !:Stack = [Left, two(K1, V1, empty, Middle), two(K2, V2, empty, Right)
+                    | !.Stack],
+        match_kv(K, V, !Stack)
+    ;
+        B = four(K1, V1, K2, V2, K3, V3, Left, MidLeft, MidRight, Right),
+        !:Stack = [Left, two(K1, V1, empty, MidLeft),
+                        two(K2, V2, empty, MidRight),
+                        two(K3, V3, empty, Right) | !.Stack],
+        match_kv(K, V, !Stack)
+    ).
+
 %------------------------------------------------------------------------------%
 %------------------------------------------------------------------------------%
 
@@ -3143,7 +3233,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],
-- 
1.8.1.3