[m-rev.] diff: add multi_map.{to,from}_flat_assoc_list

[Simon Taylor]

Estimated hours taken: 0.25
Branches: main

NEWS:
library/multi_map.m:
	Add predicates multi_map.to_flat_assoc_list
	and multi_map.from_flat_assoc_list, which use
	assoc_lists containing one element per key-value
	pair, not one element per key and all its values.

Index: NEWS
===================================================================
RCS file: /home/mercury1/repository/mercury/NEWS,v
retrieving revision 1.320
diff -u -u -r1.320 NEWS
--- NEWS	31 Oct 2003 03:27:13 -0000	1.320
+++ NEWS	30 Nov 2003 14:56:29 -0000
@@ -55,6 +55,8 @@
 * exception.m now contains a predicate finally/6 which can be used to
   ensure that resources are released whether a called closure exits
   normally or throws an exception.
+* We've added predicates multi_map.to_flat_assoc_list/2 and
+  multi_map.from_flat_assoc_list/2. 
 
 Portability improvements:
 * Nothing yet.
@@ -144,6 +146,9 @@
 * exception.m now contains a predicate finally/6 which can be used to
   ensure that resources are released whether a called closure exits
   normally or throws an exception.
+
+* We've added predicates multi_map.to_flat_assoc_list/2 and
+  multi_map.from_flat_assoc_list/2. 
 
 * Several new functions have been added to the string module, namely
   elem/2, unsafe_elem/2, chomp/1, lstrip/1, lstrip/2, rstrip/1, rstrip/2,
Index: library/multi_map.m
===================================================================
RCS file: /home/mercury1/repository/mercury/library/multi_map.m,v
retrieving revision 1.10
diff -u -u -r1.10 multi_map.m
--- library/multi_map.m	26 May 2003 09:00:30 -0000	1.10
+++ library/multi_map.m	30 Nov 2003 14:21:23 -0000
@@ -104,16 +104,28 @@
 :- mode multi_map__values(in, out) is det.
 
 	% convert a multi_map to an association list
-:- pred multi_map__to_assoc_list(multi_map(K,V), assoc_list(K,list(V))).
-:- mode multi_map__to_assoc_list(in, out) is det.
+:- pred multi_map__to_flat_assoc_list(multi_map(K,V), assoc_list(K, V)).
+:- mode multi_map__to_flat_assoc_list(in, out) is det.
 
 	% convert an association list to a multi_map
-:- pred multi_map__from_assoc_list(assoc_list(K,list(V)), multi_map(K,V)).
+:- pred multi_map__from_flat_assoc_list(assoc_list(K, V), multi_map(K,V)).
+:- mode multi_map__from_flat_assoc_list(in, out) is det.
+
+	% convert a multi_map to an association list, with all the
+	% values for each key in one element of the association list.
+:- pred multi_map__to_assoc_list(multi_map(K, V),
+		assoc_list(K, list(V))).
+:- mode multi_map__to_assoc_list(in, out) is det.
+
+	% convert an association list with all the values for each
+	% key in one element of the list to a multi_map
+:- pred multi_map__from_assoc_list(assoc_list(K, list(V)),
+		multi_map(K,V)).
 :- mode multi_map__from_assoc_list(in, out) is det.
 
 	% convert a sorted association list to a multi_map
 :- pred multi_map__from_sorted_assoc_list(assoc_list(K, list(V)), 
-			multi_map(K, V)).
+		multi_map(K, V)).
 :- mode multi_map__from_sorted_assoc_list(in, out) is det.
 
 	% delete a key and data from a multi_map
@@ -252,8 +264,21 @@
 	map__values(MultiMap, KeyList0),
 	list__condense(KeyList0, KeyList).
 
-multi_map__to_assoc_list(MultiMap, AList) :-
-	map__to_assoc_list(MultiMap, AList).
+multi_map__from_flat_assoc_list(AList, MultiMap) :-
+	MultiMap = list__foldl(
+		(func(Key - Value, Map0) = Map  :-
+			multi_map__set(Map0, Key, Value, Map)
+		),
+		AList, map__init).
+
+multi_map__to_flat_assoc_list(MultiMap, AList) :-
+	AList = list__reverse(map__foldl(
+		(func(Key, Values, AL) =
+			list__reverse(
+				list__map((func(Value) = Key - Value), Values)
+			) ++ AL
+		),
+		MultiMap, [])).
 
 multi_map__from_assoc_list(AList, MultiMap) :-
 	map__from_assoc_list(AList, MultiMap).
@@ -261,6 +286,9 @@
 multi_map__from_sorted_assoc_list(AList, MultiMap) :-
 	map__from_sorted_assoc_list(AList, MultiMap).
 
+multi_map__to_assoc_list(MultiMap, AList) :-
+	map__to_assoc_list(MultiMap, AList).
+
 multi_map__delete(MultiMap0, Key, MultiMap) :-
 	map__delete(MultiMap0, Key, MultiMap).
 
@@ -306,18 +334,8 @@
 	% XXX inefficient
 
 multi_map__inverse_search(MultiMap, Value, Key) :-
-	map__to_assoc_list(MultiMap, AssocList),
-	multi_map__assoc_list_member(Value, AssocList, Key).
-
-:- pred multi_map__assoc_list_member(Value, assoc_list(Key, list(Value)), Key).
-:- mode multi_map__assoc_list_member(in, in, out) is nondet.
-multi_map__assoc_list_member(Value, [(AKey - AValues) | AList], Key) :-
-	(
-		list__member(Value, AValues),
-		Key = AKey
-	;
-		multi_map__assoc_list_member(Value, AList, Key)
-	).
+	map__member(MultiMap, Key, ValueList),
+	list__member(Value, ValueList).
 
 %-----------------------------------------------------------------------------%
 
--------------------------------------------------------------------------
mercury-reviews mailing list
post:  mercury-reviews at cs.mu.oz.au
administrative address: owner-mercury-reviews at cs.mu.oz.au
unsubscribe: Address: mercury-reviews-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-reviews-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------