[m-rev.] diff: sveqvclass.m

[Zoltan Somogyi]

library/eqvclass.m:
	Bring this module up to date with our current code guidelines.
	Use predmode declarations, state variables and field accesses
	where possible. Use counters instead of plain ints to allocate
	partition_ids.

	There are no changes in algorithms.

library/sveqvclass.m:
	Provide state-variable-friendly versions of the predicates in
	eqvclass.m that could benefit from this.

library/library.m:
NEWS:
	Mention the new module.

Zoltan.

Index: ../NEWS
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/NEWS,v
retrieving revision 1.361
diff -u -r1.361 NEWS
--- ../NEWS	13 Jan 2005 11:04:36 -0000	1.361
+++ ../NEWS	14 Jan 2005 06:00:31 -0000
@@ -22,9 +22,10 @@
   version_array2d, version_bitmap, version_hash_table, and version_store,
   implementing non-unique versions of these types supporting O(1) access for
   non-persistent use.  A new module term_to_xml has been added for converting
-  arbitrary terms to XML documents. Six new modules, svarray, svmap, svbimap,
-  svset, svbag and svqueue now provide more convenient ways to update arrays,
-  maps, bimaps, sets, bags and queues in code that uses state variables.
+  arbitrary terms to XML documents. Seven new modules, svarray, sveqvclass,
+  svmap, svbimap, svset, svbag and svqueue now provide more convenient ways
+  to update arrays, equivalence classes, maps, bimaps, sets, bags and queues
+  in code that uses state variables.
 * New procedures have been added to many of the existing standard library
   modules.  Most notably, these include procedures for creating
   directories and symbolic links, for checking file types and file
cvs diff: Diffing .
Index: eqvclass.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/library/eqvclass.m,v
retrieving revision 1.14
diff -u -r1.14 eqvclass.m
--- eqvclass.m	15 Dec 2004 06:57:40 -0000	1.14
+++ eqvclass.m	13 Jan 2005 16:48:53 -0000
@@ -22,88 +22,72 @@
 
 	% Create an empty equivalance class.
 
-:- pred eqvclass__init(eqvclass(T)).
-:- mode eqvclass__init(out) is det.
-
+:- pred eqvclass__init(eqvclass(T)::out) is det.
 :- func eqvclass__init = eqvclass(T).
 
 	% Is this item known to the equivalence class?
 
-:- pred eqvclass__is_member(eqvclass(T), T).
-:- mode eqvclass__is_member(in, in) is semidet.
+:- pred eqvclass__is_member(eqvclass(T)::in, T::in) is semidet.
 
 	% Make an element known to the equivalence class.
 	% The element may already be known to the class;
 	% if it isn't, it is created without any equivalence relationships.
 
-:- pred eqvclass__ensure_element(eqvclass(T), T, eqvclass(T)).
-:- mode eqvclass__ensure_element(in, in, out) is det.
-
+:- pred eqvclass__ensure_element(eqvclass(T)::in, T::in, eqvclass(T)::out)
+	is det.
 :- func eqvclass__ensure_element(eqvclass(T), T) = eqvclass(T).
 
 	% Make an element known to the equivalence class.
 	% The element must not already be known to the class;
 	% it is created without any equivalence relationships.
 
-:- pred eqvclass__new_element(eqvclass(T), T, eqvclass(T)).
-:- mode eqvclass__new_element(in, in, out) is det.
-
+:- pred eqvclass__new_element(eqvclass(T)::in, T::in, eqvclass(T)::out) is det.
 :- func eqvclass__new_element(eqvclass(T), T) = eqvclass(T).
 
 	% Make two elements of the equivalence class equivalent.
 	% It is ok if they already are.
 
-:- pred eqvclass__ensure_equivalence(eqvclass(T), T, T, eqvclass(T)).
-:- mode eqvclass__ensure_equivalence(in, in, in, out) is det.
-
+:- pred eqvclass__ensure_equivalence(eqvclass(T)::in, T::in, T::in,
+	eqvclass(T)::out) is det.
 :- func eqvclass__ensure_equivalence(eqvclass(T), T, T) = eqvclass(T).
 
 	% Make two elements of the equivalence class equivalent.
 	% It is an error if they are already equivalent.
 
-:- pred eqvclass__new_equivalence(eqvclass(T), T, T, eqvclass(T)).
-:- mode eqvclass__new_equivalence(in, in, in, out) is det.
-
+:- pred eqvclass__new_equivalence(eqvclass(T)::in, T::in, T::in,
+	eqvclass(T)::out) is det.
 :- func eqvclass__new_equivalence(eqvclass(T), T, T) = eqvclass(T).
 
 	% Test if two elements are equivalent.
 
-:- pred eqvclass__same_eqvclass(eqvclass(T), T, T).
-:- mode eqvclass__same_eqvclass(in, in, in) is semidet.
+:- pred eqvclass__same_eqvclass(eqvclass(T)::in, T::in, T::in) is semidet.
 
 	% Test if a list of elements are equivalent.
 
-:- pred eqvclass__same_eqvclass_list(eqvclass(T), list(T)).
-:- mode eqvclass__same_eqvclass_list(in, in) is semidet.
+:- pred eqvclass__same_eqvclass_list(eqvclass(T)::in, list(T)::in) is semidet.
 
 	% Return the set of the partitions of the equivalence class.
 
-:- pred eqvclass__partition_set(eqvclass(T), set(set(T))).
-:- mode eqvclass__partition_set(in, out) is det.
-
+:- pred eqvclass__partition_set(eqvclass(T)::in, set(set(T))::out) is det.
 :- func eqvclass__partition_set(eqvclass(T)) = set(set(T)).
 
 	% Return a list of the partitions of the equivalence class.
 
-:- pred eqvclass__partition_list(eqvclass(T), list(set(T))).
-:- mode eqvclass__partition_list(in, out) is det.
-
+:- pred eqvclass__partition_list(eqvclass(T)::in, list(set(T))::out) is det.
 :- func eqvclass__partition_list(eqvclass(T)) = list(set(T)).
 
 	% Create an equivalence class from a partition set.
 	% It is an error if the sets are not disjoint.
 
-:- pred eqvclass__partition_set_to_eqvclass(set(set(T)), eqvclass(T)).
-:- mode eqvclass__partition_set_to_eqvclass(in, out) is det.
-
+:- pred eqvclass__partition_set_to_eqvclass(set(set(T))::in, eqvclass(T)::out)
+	is det.
 :- func eqvclass__partition_set_to_eqvclass(set(set(T))) = eqvclass(T).
 
 	% Create an equivalence class from a list of partitions.
 	% It is an error if the sets are not disjoint.
 
-:- pred eqvclass__partition_list_to_eqvclass(list(set(T)), eqvclass(T)).
-:- mode eqvclass__partition_list_to_eqvclass(in, out) is det.
-
+:- pred eqvclass__partition_list_to_eqvclass(list(set(T))::in,
+	eqvclass(T)::out) is det.
 :- func eqvclass__partition_list_to_eqvclass(list(set(T))) = eqvclass(T).
 
 	% Return the set of elements equivalent to the given element.
@@ -125,13 +109,13 @@
 
 :- implementation.
 
-:- import_module map, int, require, set.
+:- import_module int, counter, require, map, svmap, set.
 
-:- type eqvclass(T)	--->
-		eqvclass(
-			partition_id,
-			map(partition_id, set(T)),
-			map(T, partition_id)
+:- type eqvclass(T)
+	--->	eqvclass(
+			next_id		:: counter,
+			partitions	:: map(partition_id, set(T)),
+			keys		:: map(T, partition_id)
 		).
 
 :- type partition_id	==	int.
@@ -139,70 +123,67 @@
 eqvclass__init(EqvClass) :-
 	map__init(PartitionMap),
 	map__init(ElementMap),
-	EqvClass = eqvclass(0, PartitionMap, ElementMap).
+	EqvClass = eqvclass(counter__init(0), PartitionMap, ElementMap).
 
 eqvclass__is_member(EqvClass, Element) :-
-	EqvClass = eqvclass(_NextId, _PartitionMap, ElementMap),
+	ElementMap = EqvClass ^ keys,
 	map__search(ElementMap, Element, _).
 
 eqvclass__ensure_element(EqvClass0, Element, EqvClass) :-
-	eqvclass__ensure_element_2(EqvClass0, Element, _, EqvClass).
+	eqvclass__ensure_element_2(Element, _, EqvClass0, EqvClass).
 
-:- pred eqvclass__ensure_element_2(eqvclass(T), T, partition_id, eqvclass(T)).
-:- mode eqvclass__ensure_element_2(in, in, out, out) is det.
+:- pred eqvclass__ensure_element_2(T::in, partition_id::out,
+	eqvclass(T)::in, eqvclass(T)::out) is det.
 
-eqvclass__ensure_element_2(EqvClass0, Element, Id, EqvClass) :-
-	EqvClass0 = eqvclass(_NextId0, _PartitionMap0, ElementMap0),
-	( map__search(ElementMap0, Element, OldId) ->
-		EqvClass = EqvClass0,
+eqvclass__ensure_element_2(Element, Id, !EqvClass) :-
+	ElementMap = !.EqvClass ^ keys,
+	( map__search(ElementMap, Element, OldId) ->
 		Id = OldId
 	;
-		eqvclass__add_element(EqvClass0, Element, Id, EqvClass)
+		eqvclass__add_element(Element, Id, !EqvClass)
 	).
 
 eqvclass__new_element(EqvClass0, Element, EqvClass) :-
-	EqvClass0 = eqvclass(_NextId0, _PartitionMap0, ElementMap0),
+	ElementMap0 = EqvClass0 ^ keys,
 	( map__search(ElementMap0, Element, _OldId) ->
 		error("new element is already in equivalence class")
 	;
-		eqvclass__add_element(EqvClass0, Element, _, EqvClass)
+		eqvclass__add_element(Element, _, EqvClass0, EqvClass)
 	).
 
-:- pred eqvclass__add_element(eqvclass(T), T, partition_id, eqvclass(T)).
-:- mode eqvclass__add_element(in, in, out, out) is det.
+:- pred eqvclass__add_element(T::in, partition_id::out,
+	eqvclass(T)::in, eqvclass(T)::out) is det.
 
-eqvclass__add_element(EqvClass0, Element, Id, EqvClass) :-
-	EqvClass0 = eqvclass(NextId0, PartitionMap0, ElementMap0),
-	Id = NextId0,
-	NextId = NextId0 + 1,
+eqvclass__add_element(Element, Id, !EqvClass) :-
+	!.EqvClass = eqvclass(Counter0, PartitionMap0, ElementMap0),
+	counter__allocate(Id, Counter0, Counter),
 	map__det_insert(ElementMap0, Element, Id, ElementMap),
 	set__singleton_set(Partition, Element),
-	map__det_insert(PartitionMap0, NextId0, Partition, PartitionMap),
-	EqvClass = eqvclass(NextId, PartitionMap, ElementMap).
+	map__det_insert(PartitionMap0, Id, Partition, PartitionMap),
+	!:EqvClass = eqvclass(Counter, PartitionMap, ElementMap).
 
 eqvclass__ensure_equivalence(EqvClass0, Element1, Element2, EqvClass) :-
-	eqvclass__ensure_element_2(EqvClass0, Element1, Id1, EqvClass1),
-	eqvclass__ensure_element_2(EqvClass1, Element2, Id2, EqvClass2),
+	eqvclass__ensure_element_2(Element1, Id1, EqvClass0, EqvClass1),
+	eqvclass__ensure_element_2(Element2, Id2, EqvClass1, EqvClass2),
 	( Id1 = Id2 ->
 		EqvClass = EqvClass2
 	;
-		eqvclass__add_equivalence(EqvClass2, Id1, Id2, EqvClass)
+		eqvclass__add_equivalence(Id1, Id2, EqvClass2, EqvClass)
 	).
 
 eqvclass__new_equivalence(EqvClass0, Element1, Element2, EqvClass) :-
-	eqvclass__ensure_element_2(EqvClass0, Element1, Id1, EqvClass1),
-	eqvclass__ensure_element_2(EqvClass1, Element2, Id2, EqvClass2),
+	eqvclass__ensure_element_2(Element1, Id1, EqvClass0, EqvClass1),
+	eqvclass__ensure_element_2(Element2, Id2, EqvClass1, EqvClass2),
 	( Id1 = Id2 ->
 		error("two elements are already equivalent")
 	;
-		eqvclass__add_equivalence(EqvClass2, Id1, Id2, EqvClass)
+		eqvclass__add_equivalence(Id1, Id2, EqvClass2, EqvClass)
 	).
 
-:- pred eqvclass__add_equivalence(eqvclass(T), partition_id, partition_id,
-	eqvclass(T)).
-:- mode eqvclass__add_equivalence(in, in, in, out) is det.
+:- pred eqvclass__add_equivalence(partition_id::in, partition_id::in,
+	eqvclass(T)::in, eqvclass(T)::out) is det.
 
-eqvclass__add_equivalence(EqvClass0, Id1, Id2, EqvClass) :-
+eqvclass__add_equivalence(Id1, Id2, EqvClass0, EqvClass) :-
 	EqvClass0 = eqvclass(NextId0, PartitionMap0, ElementMap0),
 	map__det_remove(PartitionMap0, Id2, Partition2, PartitionMap1),
 	map__lookup(PartitionMap1, Id1, Partition1),
@@ -212,30 +193,28 @@
 	eqvclass__change_partition(Elements2, Id1, ElementMap0, ElementMap),
 	EqvClass = eqvclass(NextId0, PartitionMap, ElementMap).
 
-:- pred eqvclass__change_partition(list(T), partition_id,
-	map(T, partition_id), map(T, partition_id)).
-:- mode eqvclass__change_partition(in, in, in, out) is det.
-
-eqvclass__change_partition([], _Id, ElementMap, ElementMap).
-eqvclass__change_partition([Element | Elements], Id, ElementMap0, ElementMap) :-
-	map__set(ElementMap0, Element, Id, ElementMap1),
-	eqvclass__change_partition(Elements, Id, ElementMap1, ElementMap).
+:- pred eqvclass__change_partition(list(T)::in, partition_id::in,
+	map(T, partition_id)::in, map(T, partition_id)::out) is det.
+
+eqvclass__change_partition([], _Id, !ElementMap).
+eqvclass__change_partition([Element | Elements], Id, !ElementMap) :-
+	svmap__set(Element, Id, !ElementMap),
+	eqvclass__change_partition(Elements, Id, !ElementMap).
 
 eqvclass__same_eqvclass(EqvClass0, Element1, Element2) :-
-	EqvClass0 = eqvclass(_NextId0, _PartitionMap0, ElementMap0),
+	ElementMap0 = EqvClass0 ^ keys,
 	map__search(ElementMap0, Element1, Id1),
 	map__search(ElementMap0, Element2, Id2),
 	Id1 = Id2.
 
 eqvclass__same_eqvclass_list(_, []).
 eqvclass__same_eqvclass_list(EqvClass, [Element | Elements]) :-
-	EqvClass = eqvclass(_NextId, _PartitionMap, ElementMap),
+	ElementMap = EqvClass ^ keys,
 	map__search(ElementMap, Element, Id),
 	eqvclass__same_eqvclass_list_2(ElementMap, Elements, Id).
 
-:- pred eqvclass__same_eqvclass_list_2(map(T, partition_id), 
-		list(T), partition_id).
-:- mode eqvclass__same_eqvclass_list_2(in, in, in) is semidet.
+:- pred eqvclass__same_eqvclass_list_2(map(T, partition_id)::in, 
+	list(T)::in, partition_id::in) is semidet.
 
 eqvclass__same_eqvclass_list_2(_, [], _).
 eqvclass__same_eqvclass_list_2(ElementMap, [Element | Elements], Id) :-
@@ -253,8 +232,8 @@
 
 	% Convert a list of partition ids to a list of partitions.
 
-:- pred eqvclass__partitions(eqvclass(T), list(partition_id), list(set(T))).
-:- mode eqvclass__partitions(in, in, out) is det.
+:- pred eqvclass__partitions(eqvclass(T)::in, list(partition_id)::in,
+	list(set(T))::out) is det.
 
 eqvclass__partitions(_EqvClass0, [], []).
 eqvclass__partitions(EqvClass0, [Id | Ids], [Partition | Partitions]) :-
@@ -263,22 +242,20 @@
 
 	% Get the ids of all the partitions.
 
-:- pred eqvclass__partition_ids(eqvclass(T), list(partition_id)).
-:- mode eqvclass__partition_ids(in, out) is det.
+:- pred eqvclass__partition_ids(eqvclass(T)::in, list(partition_id)::out)
+	is det.
 
 eqvclass__partition_ids(EqvClass0, Ids) :-
-	EqvClass0 = eqvclass(_NextId0, PartitionMap0, _ElementMap0),
+	PartitionMap0 = EqvClass0 ^ partitions,
 	map__keys(PartitionMap0, Ids).
 
-	% Given an element, get the id of the partition containing that element.
-
 	% Given a partition id, get the elements of the partition.
 
-:- pred eqvclass__id_to_partition(eqvclass(T), partition_id, set(T)).
-:- mode eqvclass__id_to_partition(in, in, out) is det.
+:- pred eqvclass__id_to_partition(eqvclass(T)::in, partition_id::in,
+	set(T)::out) is det.
 
 eqvclass__id_to_partition(EqvClass0, Id, Partition) :-
-	EqvClass0 = eqvclass(_NextId0, PartitionMap0, _ElementMap0),
+	PartitionMap0 = EqvClass0 ^ partitions,
 	( map__search(PartitionMap0, Id, PartitionPrime) ->
 		Partition = PartitionPrime
 	;
@@ -295,28 +272,27 @@
 	eqvclass__init(EqvClass).
 eqvclass__partition_list_to_eqvclass([Partition | Ps], EqvClass) :-
 	eqvclass__partition_list_to_eqvclass(Ps, EqvClass0),
-	EqvClass0 = eqvclass(NextId0, PartitionMap0, ElementMap0),
+	EqvClass0 = eqvclass(Counter0, PartitionMap0, ElementMap0),
 	set__to_sorted_list(Partition, Elements),
 	( Elements = [] ->
-	    NextId = NextId0,
-	    ElementMap0 = ElementMap,
-	    PartitionMap0 = PartitionMap
+		Counter = Counter0,
+		ElementMap0 = ElementMap,
+		PartitionMap0 = PartitionMap
 	;
-	    Id = NextId0,
-	    NextId = NextId0 + 1,
-	    eqvclass__make_partition(Elements, Id, ElementMap0, ElementMap),
-	    map__det_insert(PartitionMap0, Id, Partition, PartitionMap)
+		counter__allocate(Id, Counter0, Counter),
+		eqvclass__make_partition(Elements, Id,
+			ElementMap0, ElementMap),
+		map__det_insert(PartitionMap0, Id, Partition, PartitionMap)
 	),
-	EqvClass = eqvclass(NextId, PartitionMap, ElementMap).
+	EqvClass = eqvclass(Counter, PartitionMap, ElementMap).
+
+:- pred eqvclass__make_partition(list(T)::in, partition_id::in,
+	map(T, partition_id)::in, map(T, partition_id)::out) is det.
 
-:- pred eqvclass__make_partition(list(T), partition_id,
-	map(T, partition_id), map(T, partition_id)).
-:- mode eqvclass__make_partition(in, in, in, out) is det.
-
-eqvclass__make_partition([], _Id, ElementMap, ElementMap).
-eqvclass__make_partition([Element | Elements], Id, ElementMap0, ElementMap) :-
-	map__det_insert(ElementMap0, Element, Id, ElementMap1),
-	eqvclass__make_partition(Elements, Id, ElementMap1, ElementMap).
+eqvclass__make_partition([], _Id, !ElementMap).
+eqvclass__make_partition([Element | Elements], Id, !ElementMap) :-
+	svmap__det_insert(Element, Id, !ElementMap),
+	eqvclass__make_partition(Elements, Id, !ElementMap).
 
 %---------------------------------------------------------------------------%
 %---------------------------------------------------------------------------%
Index: library.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/library/library.m,v
retrieving revision 1.81
diff -u -r1.81 library.m
--- library.m	10 Jan 2005 05:23:46 -0000	1.81
+++ library.m	13 Jan 2005 14:21:32 -0000
@@ -101,6 +101,7 @@
 :- import_module svarray.
 :- import_module svbag.
 :- import_module svbimap.
+:- import_module sveqvclass.
 :- import_module svmap.
 :- import_module svqueue.
 :- import_module svset.
@@ -232,6 +233,7 @@
 mercury_std_library_module("svarray").
 mercury_std_library_module("svbag").
 mercury_std_library_module("svbimap").
+mercury_std_library_module("sveqvclass").
 mercury_std_library_module("svmap").
 mercury_std_library_module("svqueue").
 mercury_std_library_module("svset").
Index: sveqvclass.m
===================================================================
RCS file: sveqvclass.m
diff -N sveqvclass.m
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ sveqvclass.m	13 Jan 2005 15:46:17 -0000
@@ -0,0 +1,74 @@
+%---------------------------------------------------------------------------%
+% Copyright (C) 2005 The University of Melbourne.
+% This file may only be copied under the terms of the GNU Library General
+% Public License - see the file COPYING.LIB in the Mercury distribution.
+%-----------------------------------------------------------------------------%
+%
+% File: sveqvclass.m.
+% Author: zs.
+% Stability: high.
+%
+% This file provides an interface to the 'eqvclass' ADT that is conducive
+% to the use of state variable notation. The predicates here do the same thing
+% as their counterparts in the eqvclass module; the only difference is the
+% order of the arguments.
+%
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+
+:- module sveqvclass.
+
+:- interface.
+
+:- import_module eqvclass.
+
+	% Make an element known to the equivalence class.
+	% The element may already be known to the class;
+	% if it isn't, it is created without any equivalence relationships.
+
+:- pred sveqvclass__ensure_element(T::in, eqvclass(T)::in, eqvclass(T)::out)
+	is det.
+
+	% Make an element known to the equivalence class.
+	% The element must not already be known to the class;
+	% it is created without any equivalence relationships.
+
+:- pred sveqvclass__new_element(T::in, eqvclass(T)::in, eqvclass(T)::out)
+	is det.
+
+	% Make two elements of the equivalence class equivalent.
+	% It is ok if they already are.
+
+:- pred sveqvclass__ensure_equivalence(T::in, T::in,
+	eqvclass(T)::in, eqvclass(T)::out) is det.
+
+	% Make two elements of the equivalence class equivalent.
+	% It is an error if they are already equivalent.
+
+:- pred sveqvclass__new_equivalence(T::in, T::in,
+	eqvclass(T)::in, eqvclass(T)::out) is det.
+
+	% Remove the given element and all other elements equivalent to it
+	% from the given equivalence class.
+
+:- pred sveqvclass__remove_equivalent_elements(T::in,
+	eqvclass(T)::in, eqvclass(T)::out) is det.
+
+%---------------------------------------------------------------------------%
+
+:- implementation.
+
+sveqvclass__ensure_element(Element, EqvClass0, EqvClass) :-
+	eqvclass__ensure_element(EqvClass0, Element, EqvClass).
+
+sveqvclass__new_element(Element, EqvClass0, EqvClass) :-
+	eqvclass__new_element(EqvClass0, Element, EqvClass).
+
+sveqvclass__ensure_equivalence(Element1, Element2, EqvClass0, EqvClass) :-
+	eqvclass__ensure_equivalence(EqvClass0, Element1, Element2, EqvClass).
+
+sveqvclass__new_equivalence(Element1, Element2, EqvClass0, EqvClass) :-
+	eqvclass__new_equivalence(EqvClass0, Element1, Element2, EqvClass).
+
+sveqvclass__remove_equivalent_elements(X, EqvClass0, EqvClass) :-
+	EqvClass = eqvclass__remove_equivalent_elements(EqvClass0, X).
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------