[m-dev.] diff: restate test_bitset testcase

Peter Ross peter.ross at miscrit.be
Thu Feb 15 23:42:46 AEDT 2001


Hi,


===================================================================


Estimated hours taken: 0.25

Mmakefile:
bitset.exp:
bitset.m:
bitset_tester.m:
test_bitset.exp:
test_bitset.m:
    Back out my previous change to these files, because it is useful to
    have bitset_tester in a seperate module for testing the
    sparse_bitset module.


Index: Mmakefile
===================================================================
RCS file: /home/mercury1/repository/tests/hard_coded/Mmakefile,v
retrieving revision 1.110
diff -u -r1.110 Mmakefile
--- Mmakefile	2001/02/13 15:57:23	1.110
+++ Mmakefile	2001/02/15 10:19:27
@@ -12,7 +12,6 @@
 	agg \
 	bidirectional \
 	bigtest \
-	bitset \
 	boyer \
 	c_write_string \
 	cc_and_non_cc_test \
@@ -107,6 +106,7 @@
 	string_loop \
 	term_io_test \
 	term_to_univ_test \
+	test_bitset \
 	test_imported_no_tag \
 	tim_qual1 \
 	tuple_test \
Index: bitset.exp
===================================================================
RCS file: bitset.exp
diff -N bitset.exp
--- /tmp/cvswOjxwE	Thu Feb 15 21:19:28 2001
+++ /dev/null	Sat Aug  7 21:45:41 1999
@@ -1,89 +0,0 @@
-List1: -59, -34, -19, -15, 2, 7, 19, 22, 25, 28, 29, 31, 32, 36, 38, 39, 40, 42, 44, 47, 58, 59
-
-List2: -64, -61, -58, -56, -51, -49, -48, -46, -44, -40, -38, -37, -31, -30, -23, -18, -13, -4, -2, 4, 9, 11, 12, 14, 17, 21, 23, 37, 39, 42, 43, 50, 52, 53, 54, 55, 56, 57, 61, 63
-
-count: 22 40
-testing foldl
-Sum of List1 = 471
-Sum of List2 = 60
-testing union
-[-64, -61, -59, -58, -56, -51, -49, -48, -46, -44, -40, -38, -37, -34, -31, -30, -23, -19, -18, -15, -13, -4, -2, 2, 4, 7, 9, 11, 12, 14, 17, 19, 21, 22, 23, 25, 28, 29, 31, 32, 36, 37, 38, 39, 40, 42, 43, 44, 47, 50, 52, 53, 54, 55, 56, 57, 58, 59, 61, 63]
-testing intersection
-[39, 42]
-testing difference
-[-59, -34, -19, -15, 2, 7, 19, 22, 25, 28, 29, 31, 32, 36, 38, 40, 44, 47, 58, 59]
-testing remove_least_element
--59
-[-34, -19, -15, 2, 7, 19, 22, 25, 28, 29, 31, 32, 36, 38, 39, 40, 42, 44, 47, 58, 59]
-testing delete_list
-[-59, -34, -19, -15, 2, 7, 19, 22, 25, 28, 29, 31, 32, 36, 38, 40, 44, 47, 58, 59]
-count: 20 40
-testing foldl
-testing union
-testing intersection
-testing difference
-testing remove_least_element
-testing delete_list
-count: 20 40
-testing foldl
-testing union
-testing intersection
-testing difference
-testing remove_least_element
-testing delete_list
-count: 20 40
-testing foldl
-testing union
-testing intersection
-testing difference
-testing remove_least_element
-testing delete_list
-count: 20 40
-testing foldl
-testing union
-testing intersection
-testing difference
-testing remove_least_element
-testing delete_list
-count: 20 40
-testing foldl
-testing union
-testing intersection
-testing difference
-testing remove_least_element
-testing delete_list
-count: 20 40
-testing foldl
-testing union
-testing intersection
-testing difference
-testing remove_least_element
-testing delete_list
-count: 20 40
-testing foldl
-testing union
-testing intersection
-testing difference
-testing remove_least_element
-testing delete_list
-count: 20 40
-testing foldl
-testing union
-testing intersection
-testing difference
-testing remove_least_element
-testing delete_list
-count: 20 40
-testing foldl
-testing union
-testing intersection
-testing difference
-testing remove_least_element
-testing delete_list
-count: 20 40
-testing foldl
-testing union
-testing intersection
-testing difference
-testing remove_least_element
-testing delete_list
Index: bitset.m
===================================================================
RCS file: bitset.m
diff -N bitset.m
--- /tmp/cvsVSt5uZ	Thu Feb 15 21:19:28 2001
+++ /dev/null	Sat Aug  7 21:45:41 1999
@@ -1,463 +0,0 @@
-:- module bitset.
-
-:- interface.
-
-:- import_module io.
-
-:- pred main(io__state::di, io__state::uo) is det.
-
-:- implementation.
-
-:- import_module bool, exception, enum, int, list.
-:- import_module random, require, set, std_util.
-:- import_module sparse_bitset.
-
-:- func list1 = list(int).
-
-list1 = [29, 28, 31, 22, -15, 32, 19, 58, -59, 36, 7, 39, 42,
-		-34, 25, 40, 59, 2, -19, 44, 47, 38].
-
-:- func list2 = list(int).
-
-list2 = [21, 52, 23, -18, -23, 56, 11, -46, 61, -4, 63, 54, 17, -64,
-		-13, -38, 37, 4, 39, -2, 57, -56, -37, -30, -51, 12, -49,
-		-58, -31, -48, -61, 42, 53, -44, 55, 14, 9, -40, 43, 50].
-
-main -->
-	% Run one lot of tests with known input lists,
-	% to generate some visible output.
-	{ Write = yes },
-	run_test(Write, list1, list2),
-
-	% Run some more tests with random input, checking
-	% the output against that of set_ordlist.
-	{ Iterations = 10 },
-	{ random__init(1, Supply) },
-	run_tests(Iterations, Supply).
-
-:- pred run_tests(int::in, random__supply::mdi,
-		io__state::di, io__state::uo) is det.
-
-run_tests(Iterations, Supply0) -->
-	( { Iterations = 0 } ->
-		[]
-	;
-		{ Num1 = 20 },
-		{ get_random_numbers(Num1, [], List1, Supply0, Supply1) },
-		{ Num2 = 40 },
-		{ get_random_numbers(Num2, [], List2, Supply1, Supply) },
-		
-		{ Write = no },
-		run_test(Write, List1, List2),
-
-
-		run_tests(Iterations - 1, Supply)
-	).
-
-:- pred get_random_numbers(int::in, list(int)::in, list(int)::out,
-		random__supply::mdi, random__supply::muo) is det.
-
-get_random_numbers(Num, List0, List, Supply0, Supply) :-
-	( Num = 0 ->
-		List = List0,
-		Supply = Supply0
-	;
-		random__random(N, Supply0, Supply1),
-		RN = N rem 128 - 64,	% test negative numbers
-		get_random_numbers(Num - 1, [RN | List0], List,
-			Supply1, Supply)
-	).
-
-:- pred run_test(bool::in, list(int)::in, list(int)::in,
-		io__state::di, io__state::uo) is det.
-
-run_test(Write, List1, List2) -->
-	( { Write = yes } ->
-		io__write_string("List1: "),
-		io__write_list(list__sort(List1), ", ", io__write_int),
-		io__nl, io__nl,
-		io__write_string("List2: "),
-		io__write_list(list__sort(List2), ", ", io__write_int),
-		io__nl, io__nl
-	;
-		[]	
-	),
-	{ Set1 = list_to_set(List1) },
-	{ Set2 = list_to_set(List2) },
-
-	io__write_string("count: "),
-	io__write_int(count(Set1)),
-	io__write_string(" "),
-	io__write_int(count(Set2)),
-	io__nl,
-
-	io__write_string("testing foldl\n"),
-	{ Sum = (func(Elem, Acc) = Elem + Acc) },
-	{ Result1 = foldl(Sum, Set1, 0) },
-	{ Result2 = foldl(Sum, Set2, 0) },
-	( { Write = yes } ->
-		io__write_string("Sum of List1 = "),
-		io__write_int(Result1),
-		io__nl,
-		io__write_string("Sum of List2 = "),
-		io__write_int(Result2),
-		io__nl
-	;
-		[]
-	),
-
-	io__write_string("testing union\n"),
-	{ Union = union(Set1, Set2) },
-	write_bitset_result(Write, Union),
-
-	io__write_string("testing intersection\n"),
-	{ Intersection = intersect(Set1, Set2) },
-	write_bitset_result(Write, Intersection),
-
-	io__write_string("testing difference\n"),
-	{ Difference = difference(Set1, Set2) },
-	write_bitset_result(Write, Difference),
-
-	io__write_string("testing remove_least_element\n"),
-	( { remove_least(Set1, Least, RemovedLeast) } ->
-		( { Write = yes } ->
-			io__write_int(Least),
-			io__nl
-		;
-			[]
-		),
-		write_bitset_result(Write, RemovedLeast)
-	;
-		{ error("remove_least failed") }
-	),
-
-	io__write_string("testing delete_list\n"),
-	{ Delete = delete_list(Set1, List2) },
-	write_bitset_result(Write, Delete),
-
-	{ require(unify(delete_list(Set1, List1),
-			init `with_type` bitset_tester(int)),
-		"delete_list_failed") }.
-
-:- pred write_bitset_result(bool::in, bitset_tester(int)::in,
-		io__state::di, io__state::uo) is det.
-:- pragma no_inline(write_bitset_result/4).
-	
-write_bitset_result(Write, Set) -->
-	( { Write = yes } ->
-		{ List `with_type` list(int) = to_sorted_list(Set) },
-		io__write(List),
-		io__nl
-	;
-		[]
-	).
-
-:- type bitset_tester(T).
-
-:- type bitset_error(T)
-	--->	one_argument(string,
-			bitset_tester(T), bitset_tester(T))
-	;	two_arguments(string, bitset_tester(T),
-			bitset_tester(T), bitset_tester(T)).
-
-:- func init = bitset_tester(T).
-:- func insert(bitset_tester(T), T) = bitset_tester(T) <= enum(T).
-:- func insert_list(bitset_tester(T), list(T)) =
-		bitset_tester(T) <= enum(T).
-:- func list_to_set(list(T)) = bitset_tester(T) <= enum(T).
-:- func sorted_list_to_set(list(T)) = bitset_tester(T) <= enum(T).
-:- func delete(bitset_tester(T), T) = bitset_tester(T) <= enum(T).
-:- func delete_list(bitset_tester(T), list(T)) =
-			bitset_tester(T) <= enum(T).
-:- func remove(bitset_tester(T), T) = bitset_tester(T) <= enum(T).
-:- mode remove(in, in) = out is semidet.
-:- func remove_list(bitset_tester(T), list(T)) =
-			bitset_tester(T) <= enum(T).
-:- mode remove_list(in, in) = out is semidet.
-
-:- func to_sorted_list(bitset_tester(T)) = list(T) <= enum(T).
-
-:- func singleton_set(T) = bitset_tester(T) <= enum(T).
-
-:- func union(bitset_tester(T), bitset_tester(T)) =
-		bitset_tester(T) <= enum(T).
-:- func intersect(bitset_tester(T), bitset_tester(T)) =
-		bitset_tester(T) <= enum(T).
-:- func difference(bitset_tester(T),
-		bitset_tester(T)) = bitset_tester(T) <= enum(T).
-
-:- pred remove_least(bitset_tester(T), T, bitset_tester(T)) <= enum(T).
-:- mode remove_least(in, out, out) is semidet.
-
-:- pred subset(bitset_tester(T), bitset_tester(T)).
-:- mode subset(in, in) is semidet.
-
-:- pred superset(bitset_tester(T), bitset_tester(T)).
-:- mode superset(in, in) is semidet.
-
-:- func count(bitset_tester(T)) = int <= enum(T).
-
-:- func foldl(func(T, U) = U, bitset_tester(T), U) = U <= enum(T).
-
-:- pred empty(bitset_tester(T)).
-:- mode empty(in) is semidet.
-
-:- pred contains(bitset_tester(T)::in, T::in) is semidet <= enum(T).
-
-:- pred init(bitset_tester(T)::out) is det.
-:- pred singleton_set(bitset_tester(T)::out, T::in) is det <= enum(T).
-
-:- pred list_to_set(list(T)::in, bitset_tester(T)::out) is det <= enum(T).
-:- pred sorted_list_to_set(list(T)::in,
-		bitset_tester(T)::out) is det <= enum(T).
-:- pred to_sorted_list(bitset_tester(T)::in,
-		list(T)::out) is det <= enum(T).
-:- pred insert(bitset_tester(T)::in, T::in,
-		bitset_tester(T)::out) is det <= enum(T).
-:- pred insert_list(bitset_tester(T)::in,
-		list(T)::in, bitset_tester(T)::out) is det <= enum(T).
-:- pred delete(bitset_tester(T)::in, T::in,
-		bitset_tester(T)::out) is det <= enum(T).
-:- pred delete_list(bitset_tester(T)::in, list(T)::in,
-		bitset_tester(T)::out) is det <= enum(T).
-:- pred union(bitset_tester(T)::in,
-		bitset_tester(T)::in, bitset_tester(T)::out) is det <= enum(T).
-:- pred intersect(bitset_tester(T)::in,
-		bitset_tester(T)::in, bitset_tester(T)::out) is det <= enum(T).
-:- pred difference(bitset_tester(T)::in,
-		bitset_tester(T)::in, bitset_tester(T)::out) is det <= enum(T).
-
-:- type bitset_tester(T) == pair(sparse_bitset(T), set__set(T)).
-
-%-----------------------------------------------------------------------------%
-
-init = init - init.
-
-singleton_set(A) = make_singleton_set(A) - make_singleton_set(A).
-
-init(init).
-empty(A - B) :-
-	( empty(A) -> EmptyA = yes; EmptyA = no),
-	( empty(B) -> EmptyB = yes; EmptyB = no),
-	( EmptyA = EmptyB ->
-		EmptyA = yes
-	;
-		error("empty failed")
-	).
-singleton_set(singleton_set(A), A).
-insert(A, B, insert(A, B)).
-insert_list(A, B, insert_list(A, B)).
-delete(A, B, delete(A, B)).
-delete_list(A, B, delete_list(A, B)).
-list_to_set(A, list_to_set(A)).
-to_sorted_list(A, to_sorted_list(A)).
-sorted_list_to_set(A, sorted_list_to_set(A)).
-union(A, B, union(A, B)).
-intersect(A, B, intersect(A, B)).
-difference(A, B, difference(A, B)).
-
-%-----------------------------------------------------------------------------%
-
-to_sorted_list(A - B) = List :-
-	ListA = to_sorted_list(A),
-	ListB = set__to_sorted_list(B),
-	( ListA = ListB ->
-		List = ListB
-	;
-		error("to_sorted_list failed")
-	).
-
-%-----------------------------------------------------------------------------%
-
-delete(SetA - SetB, Var) = check("delete", SetA - SetB, delete(SetA, Var) - set__delete(SetB, Var)).
-
-delete_list(SetA - SetB, List) =
-	check("delete_list", SetA - SetB,
-		delete_list(SetA, List) - set__delete_list(SetB, List)).
-
-remove(SetA0 - SetB0, Elem) = Result :-
-	( SetA1 = remove(SetA0, Elem) ->
-		( remove(SetB0, Elem, SetB1) ->
-			SetA = SetA1,
-			SetB = SetB1
-		;
-			error("remove succeeded unexpectedly")
-		)
-	; set__remove(SetB0, Elem, _) ->
-		error("remove failed unexpectedly")
-	;
-		fail
-	),
-	Result = check("remove", SetA0 - SetB0, SetA - SetB).
-
-remove_list(SetA0 - SetB0, List) = Result :-
-	( SetA1 = remove_list(SetA0, List) ->
-		( set__remove_list(SetB0, List, SetB1) ->
-			SetA = SetA1,
-			SetB = SetB1
-		;
-			error("remove succeeded unexpectedly")
-		)
-	; set__remove_list(SetB0, List, _) ->
-		error("remove failed unexpectedly")
-	;
-		fail
-	),
-	Result = check("remove_list", SetA0 - SetB0, SetA - SetB).
-
-%-----------------------------------------------------------------------------%
-
-insert(SetA - SetB, Var) = check("insert", SetA - SetB,
-		insert(SetA, Var) - set__insert(SetB, Var)).
-
-%-----------------------------------------------------------------------------%
-
-insert_list(SetA - SetB, Vars) = check("insert_list", SetA - SetB, insert_list(SetA, Vars) - set__insert_list(SetB, Vars)).
-
-%-----------------------------------------------------------------------------%
-
-list_to_set(List) = check("list_to_set", init - init,
-			list_to_set(List) - set__list_to_set(List)).
-
-sorted_list_to_set(List) = check("sorted_list_to_set", init - init,
-			sorted_list_to_set(List) - set__sorted_list_to_set(List)).
-
-%-----------------------------------------------------------------------------%
-
-contains(SetA - SetB, Var) :-
-	( contains(SetA, Var) -> InSetA = yes ; InSetA = no),
-	( set__contains(SetB, Var) -> InSetB = yes ; InSetB = no),
-	( InSetA = InSetB ->
-		InSetA = yes
-	;
-		error("contains failed")
-	).
-
-%-----------------------------------------------------------------------------%
-
-foldl(F, SetA - SetB, Acc0) = Acc :-
-	AccA = foldl(F, SetA, Acc0),
-	AccB = fold(F, SetB, Acc0),
-	( AccA = AccB ->
-		Acc = AccA
-	;	
-		error("bitset_tester: fold failed")
-	).
-
-%-----------------------------------------------------------------------------%
-
-count(SetA - SetB) = Count :-
-	CountA = count(SetA),
-	CountB = count(SetB),
-	( CountA = CountB ->
-		Count = CountA
-	;	
-		error("bitset_tester: count failed")
-	).
-
-%-----------------------------------------------------------------------------%
-
-subset(SetA1 - SetB1, SetA2 - SetB2) :-
-	( subset(SetA1, SetA2) ->
-		( subset(SetB1, SetB2) ->
-			true
-		;	
-			error("bitset_tester: subset succeeded unexpectedly")
-		)
-	; subset(SetB1, SetB2) ->
-		error("bitset_tester: subset failed unexpectedly")
-	;
-		fail
-	).
-
-superset(SetA1 - SetB1, SetA2 - SetB2) :-
-	( superset(SetA1, SetA2) ->
-		( superset(SetB1, SetB2) ->
-			true
-		;	
-			error("bitset_tester: superset succeeded unexpectedly")
-		)
-	; superset(SetB1, SetB2) ->
-		error("bitset_tester: superset failed unexpectedly")
-	;
-		fail
-	).
-
-%-----------------------------------------------------------------------------%
-
-union(SetA1 - SetB1, SetA2 - SetB2) =
-		check2("union", SetA1 - SetB1, SetA2 - SetB2,
-			union(SetA1, SetA2) - set__union(SetB1, SetB2)).
-
-%-----------------------------------------------------------------------------%
-
-intersect(SetA1 - SetB1, SetA2 - SetB2) =
-		check2("intersect", SetA1 - SetB1, SetA2 - SetB2,
-			intersect(SetA1, SetA2) - set__intersect(SetB1, SetB2)).
-
-%-----------------------------------------------------------------------------%
-
-difference(SetA1 - SetB1, SetA2 - SetB2) =
-		check2("difference", SetA1 - SetB1, SetA2 - SetB2,
-			difference(SetA1, SetA2) - set__difference(SetB1, SetB2)).
-
-%-----------------------------------------------------------------------------%
-
-remove_least(SetA0 - SetB0, Least, SetA - SetB) :-
-	( remove_least(SetA0, LeastA, SetA1) ->
-		( remove_least(SetB0, LeastB, SetB1) ->
-			( LeastA = LeastB ->
-				SetA = SetA1,
-				SetB = SetB1,
-				Least = LeastA
-			;
-				error("remove_least: wrong least element")
-			)
-		;
-			error("remove_least: should be no least value")
-		)
-	; remove_least(SetB0, _, _) ->
-		error("remove_least: failed")
-	;
-		fail
-	).
-
-%-----------------------------------------------------------------------------%
-
-:- func check(string, bitset_tester(T), bitset_tester(T)) =
-		bitset_tester(T) <= enum(T).
-
-check(Op, Tester1, Tester) = Tester :-
-
-	Tester1 = BitSet1 - Set1,
-	BitSetSet1 =
-		sparse_bitset__sorted_list_to_set(set__to_sorted_list(Set1)),
-	Tester = BitSet - Set,
-	BitSetSet = sparse_bitset__sorted_list_to_set(set__to_sorted_list(Set)),
-	( BitSetSet1 = BitSet1, BitSet = BitSetSet ->
-		true
-	;
-		throw(one_argument(Op, Tester1, Tester))
-	).
-
-:- func check2(string, bitset_tester(T), bitset_tester(T),
-		bitset_tester(T)) = bitset_tester(T) <= enum(T).
-
-check2(Op, Tester1, Tester2, Tester) = Result :-
-	Tester1 = BitSet1 - Set1,
-	BitSetSet1 =
-		sparse_bitset__sorted_list_to_set(set__to_sorted_list(Set1)),
-	Tester2 = BitSet2 - Set2,
-	BitSetSet2 = sorted_list_to_set(
-		set__to_sorted_list(Set2)),
-
-	Tester = BitSet - Set,
-	BitSetSet = sparse_bitset__sorted_list_to_set(set__to_sorted_list(Set)),
-
-	( BitSetSet1 = BitSet1, BitSetSet2 = BitSet2, BitSet = BitSetSet ->
-		Result = Tester
-	;
-		throw(two_arguments(Op, Tester1, Tester2, Tester))
-	).
-
-%-----------------------------------------------------------------------------%
Index: bitset_tester.m
===================================================================
RCS file: bitset_tester.m
diff -N bitset_tester.m
--- /dev/null	Sat Aug  7 21:45:41 1999
+++ bitset_tester.m	Thu Feb 15 21:19:27 2001
@@ -0,0 +1,322 @@
+% Test operations on bitsets by comparing the output with the output
+% from an ordinary set.
+:- module bitset_tester.
+
+:- interface.
+
+:- import_module enum, list.
+
+:- type bitset_tester(T).
+
+:- type bitset_error(T)
+	--->	one_argument(string,
+			bitset_tester(T), bitset_tester(T))
+	;	two_arguments(string, bitset_tester(T),
+			bitset_tester(T), bitset_tester(T)).
+
+:- func init = bitset_tester(T).
+:- func insert(bitset_tester(T), T) = bitset_tester(T) <= enum(T).
+:- func insert_list(bitset_tester(T), list(T)) =
+		bitset_tester(T) <= enum(T).
+:- func list_to_set(list(T)) = bitset_tester(T) <= enum(T).
+:- func sorted_list_to_set(list(T)) = bitset_tester(T) <= enum(T).
+:- func delete(bitset_tester(T), T) = bitset_tester(T) <= enum(T).
+:- func delete_list(bitset_tester(T), list(T)) =
+			bitset_tester(T) <= enum(T).
+:- func remove(bitset_tester(T), T) = bitset_tester(T) <= enum(T).
+:- mode remove(in, in) = out is semidet.
+:- func remove_list(bitset_tester(T), list(T)) =
+			bitset_tester(T) <= enum(T).
+:- mode remove_list(in, in) = out is semidet.
+
+:- func to_sorted_list(bitset_tester(T)) = list(T) <= enum(T).
+
+:- func singleton_set(T) = bitset_tester(T) <= enum(T).
+
+:- func union(bitset_tester(T), bitset_tester(T)) =
+		bitset_tester(T) <= enum(T).
+:- func intersect(bitset_tester(T), bitset_tester(T)) =
+		bitset_tester(T) <= enum(T).
+:- func difference(bitset_tester(T),
+		bitset_tester(T)) = bitset_tester(T) <= enum(T).
+
+:- pred remove_least(bitset_tester(T), T, bitset_tester(T)) <= enum(T).
+:- mode remove_least(in, out, out) is semidet.
+
+:- pred subset(bitset_tester(T), bitset_tester(T)).
+:- mode subset(in, in) is semidet.
+
+:- pred superset(bitset_tester(T), bitset_tester(T)).
+:- mode superset(in, in) is semidet.
+
+:- func count(bitset_tester(T)) = int <= enum(T).
+
+:- func foldl(func(T, U) = U, bitset_tester(T), U) = U <= enum(T).
+
+:- pred empty(bitset_tester(T)).
+:- mode empty(in) is semidet.
+
+:- pred contains(bitset_tester(T)::in, T::in) is semidet <= enum(T).
+
+:- pred init(bitset_tester(T)::out) is det.
+:- pred singleton_set(bitset_tester(T)::out, T::in) is det <= enum(T).
+
+:- pred list_to_set(list(T)::in, bitset_tester(T)::out) is det <= enum(T).
+:- pred sorted_list_to_set(list(T)::in,
+		bitset_tester(T)::out) is det <= enum(T).
+:- pred to_sorted_list(bitset_tester(T)::in,
+		list(T)::out) is det <= enum(T).
+:- pred insert(bitset_tester(T)::in, T::in,
+		bitset_tester(T)::out) is det <= enum(T).
+:- pred insert_list(bitset_tester(T)::in,
+		list(T)::in, bitset_tester(T)::out) is det <= enum(T).
+:- pred delete(bitset_tester(T)::in, T::in,
+		bitset_tester(T)::out) is det <= enum(T).
+:- pred delete_list(bitset_tester(T)::in, list(T)::in,
+		bitset_tester(T)::out) is det <= enum(T).
+:- pred union(bitset_tester(T)::in,
+		bitset_tester(T)::in, bitset_tester(T)::out) is det <= enum(T).
+:- pred intersect(bitset_tester(T)::in,
+		bitset_tester(T)::in, bitset_tester(T)::out) is det <= enum(T).
+:- pred difference(bitset_tester(T)::in,
+		bitset_tester(T)::in, bitset_tester(T)::out) is det <= enum(T).
+
+:- implementation.
+
+:- import_module bool, exception, list, int, require, set, std_util.
+:- import_module sparse_bitset.
+
+:- type bitset_tester(T) == pair(sparse_bitset(T), set__set(T)).
+
+%-----------------------------------------------------------------------------%
+
+init = init - init.
+
+singleton_set(A) = make_singleton_set(A) - make_singleton_set(A).
+
+init(init).
+empty(A - B) :-
+	( empty(A) -> EmptyA = yes; EmptyA = no),
+	( empty(B) -> EmptyB = yes; EmptyB = no),
+	( EmptyA = EmptyB ->
+		EmptyA = yes
+	;
+		error("empty failed")
+	).
+singleton_set(singleton_set(A), A).
+insert(A, B, insert(A, B)).
+insert_list(A, B, insert_list(A, B)).
+delete(A, B, delete(A, B)).
+delete_list(A, B, delete_list(A, B)).
+list_to_set(A, list_to_set(A)).
+to_sorted_list(A, to_sorted_list(A)).
+sorted_list_to_set(A, sorted_list_to_set(A)).
+union(A, B, union(A, B)).
+intersect(A, B, intersect(A, B)).
+difference(A, B, difference(A, B)).
+
+%-----------------------------------------------------------------------------%
+
+to_sorted_list(A - B) = List :-
+	ListA = to_sorted_list(A),
+	ListB = set__to_sorted_list(B),
+	( ListA = ListB ->
+		List = ListB
+	;
+		error("to_sorted_list failed")
+	).
+
+%-----------------------------------------------------------------------------%
+
+delete(SetA - SetB, Var) = check("delete", SetA - SetB, delete(SetA, Var) - set__delete(SetB, Var)).
+
+delete_list(SetA - SetB, List) =
+	check("delete_list", SetA - SetB,
+		delete_list(SetA, List) - set__delete_list(SetB, List)).
+
+remove(SetA0 - SetB0, Elem) = Result :-
+	( SetA1 = remove(SetA0, Elem) ->
+		( remove(SetB0, Elem, SetB1) ->
+			SetA = SetA1,
+			SetB = SetB1
+		;
+			error("remove succeeded unexpectedly")
+		)
+	; set__remove(SetB0, Elem, _) ->
+		error("remove failed unexpectedly")
+	;
+		fail
+	),
+	Result = check("remove", SetA0 - SetB0, SetA - SetB).
+
+remove_list(SetA0 - SetB0, List) = Result :-
+	( SetA1 = remove_list(SetA0, List) ->
+		( set__remove_list(SetB0, List, SetB1) ->
+			SetA = SetA1,
+			SetB = SetB1
+		;
+			error("remove succeeded unexpectedly")
+		)
+	; set__remove_list(SetB0, List, _) ->
+		error("remove failed unexpectedly")
+	;
+		fail
+	),
+	Result = check("remove_list", SetA0 - SetB0, SetA - SetB).
+
+%-----------------------------------------------------------------------------%
+
+insert(SetA - SetB, Var) = check("insert", SetA - SetB,
+		insert(SetA, Var) - set__insert(SetB, Var)).
+
+%-----------------------------------------------------------------------------%
+
+insert_list(SetA - SetB, Vars) = check("insert_list", SetA - SetB, insert_list(SetA, Vars) - set__insert_list(SetB, Vars)).
+
+%-----------------------------------------------------------------------------%
+
+list_to_set(List) = check("list_to_set", init - init,
+			list_to_set(List) - set__list_to_set(List)).
+
+sorted_list_to_set(List) = check("sorted_list_to_set", init - init,
+			sorted_list_to_set(List) - set__sorted_list_to_set(List)).
+
+%-----------------------------------------------------------------------------%
+
+contains(SetA - SetB, Var) :-
+	( contains(SetA, Var) -> InSetA = yes ; InSetA = no),
+	( set__contains(SetB, Var) -> InSetB = yes ; InSetB = no),
+	( InSetA = InSetB ->
+		InSetA = yes
+	;
+		error("contains failed")
+	).
+
+%-----------------------------------------------------------------------------%
+
+foldl(F, SetA - SetB, Acc0) = Acc :-
+	AccA = foldl(F, SetA, Acc0),
+	AccB = fold(F, SetB, Acc0),
+	( AccA = AccB ->
+		Acc = AccA
+	;	
+		error("bitset_tester: fold failed")
+	).
+
+%-----------------------------------------------------------------------------%
+
+count(SetA - SetB) = Count :-
+	CountA = count(SetA),
+	CountB = count(SetB),
+	( CountA = CountB ->
+		Count = CountA
+	;	
+		error("bitset_tester: count failed")
+	).
+
+%-----------------------------------------------------------------------------%
+
+subset(SetA1 - SetB1, SetA2 - SetB2) :-
+	( subset(SetA1, SetA2) ->
+		( subset(SetB1, SetB2) ->
+			true
+		;	
+			error("bitset_tester: subset succeeded unexpectedly")
+		)
+	; subset(SetB1, SetB2) ->
+		error("bitset_tester: subset failed unexpectedly")
+	;
+		fail
+	).
+
+superset(SetA1 - SetB1, SetA2 - SetB2) :-
+	( superset(SetA1, SetA2) ->
+		( superset(SetB1, SetB2) ->
+			true
+		;	
+			error("bitset_tester: superset succeeded unexpectedly")
+		)
+	; superset(SetB1, SetB2) ->
+		error("bitset_tester: superset failed unexpectedly")
+	;
+		fail
+	).
+
+%-----------------------------------------------------------------------------%
+
+union(SetA1 - SetB1, SetA2 - SetB2) =
+		check2("union", SetA1 - SetB1, SetA2 - SetB2,
+			union(SetA1, SetA2) - set__union(SetB1, SetB2)).
+
+%-----------------------------------------------------------------------------%
+
+intersect(SetA1 - SetB1, SetA2 - SetB2) =
+		check2("intersect", SetA1 - SetB1, SetA2 - SetB2,
+			intersect(SetA1, SetA2) - set__intersect(SetB1, SetB2)).
+
+%-----------------------------------------------------------------------------%
+
+difference(SetA1 - SetB1, SetA2 - SetB2) =
+		check2("difference", SetA1 - SetB1, SetA2 - SetB2,
+			difference(SetA1, SetA2) - set__difference(SetB1, SetB2)).
+
+%-----------------------------------------------------------------------------%
+
+remove_least(SetA0 - SetB0, Least, SetA - SetB) :-
+	( remove_least(SetA0, LeastA, SetA1) ->
+		( remove_least(SetB0, LeastB, SetB1) ->
+			( LeastA = LeastB ->
+				SetA = SetA1,
+				SetB = SetB1,
+				Least = LeastA
+			;
+				error("remove_least: wrong least element")
+			)
+		;
+			error("remove_least: should be no least value")
+		)
+	; remove_least(SetB0, _, _) ->
+		error("remove_least: failed")
+	;
+		fail
+	).
+
+%-----------------------------------------------------------------------------%
+
+:- func check(string, bitset_tester(T), bitset_tester(T)) =
+		bitset_tester(T) <= enum(T).
+
+check(Op, Tester1, Tester) = Tester :-
+
+	Tester1 = BitSet1 - Set1,
+	BitSetSet1 =
+		sparse_bitset__sorted_list_to_set(set__to_sorted_list(Set1)),
+	Tester = BitSet - Set,
+	BitSetSet = sparse_bitset__sorted_list_to_set(set__to_sorted_list(Set)),
+	( BitSetSet1 = BitSet1, BitSet = BitSetSet ->
+		true
+	;
+		throw(one_argument(Op, Tester1, Tester))
+	).
+
+:- func check2(string, bitset_tester(T), bitset_tester(T),
+		bitset_tester(T)) = bitset_tester(T) <= enum(T).
+
+check2(Op, Tester1, Tester2, Tester) = Result :-
+	Tester1 = BitSet1 - Set1,
+	BitSetSet1 =
+		sparse_bitset__sorted_list_to_set(set__to_sorted_list(Set1)),
+	Tester2 = BitSet2 - Set2,
+	BitSetSet2 = sorted_list_to_set(
+		set__to_sorted_list(Set2)),
+
+	Tester = BitSet - Set,
+	BitSetSet = sparse_bitset__sorted_list_to_set(set__to_sorted_list(Set)),
+
+	( BitSetSet1 = BitSet1, BitSetSet2 = BitSet2, BitSet = BitSetSet ->
+		Result = Tester
+	;
+		throw(two_arguments(Op, Tester1, Tester2, Tester))
+	).
+
+%-----------------------------------------------------------------------------%
Index: test_bitset.exp
===================================================================
RCS file: test_bitset.exp
diff -N test_bitset.exp
--- /dev/null	Sat Aug  7 21:45:41 1999
+++ test_bitset.exp	Thu Feb 15 21:19:27 2001
@@ -0,0 +1,89 @@
+List1: -59, -34, -19, -15, 2, 7, 19, 22, 25, 28, 29, 31, 32, 36, 38, 39, 40, 42, 44, 47, 58, 59
+
+List2: -64, -61, -58, -56, -51, -49, -48, -46, -44, -40, -38, -37, -31, -30, -23, -18, -13, -4, -2, 4, 9, 11, 12, 14, 17, 21, 23, 37, 39, 42, 43, 50, 52, 53, 54, 55, 56, 57, 61, 63
+
+count: 22 40
+testing foldl
+Sum of List1 = 471
+Sum of List2 = 60
+testing union
+[-64, -61, -59, -58, -56, -51, -49, -48, -46, -44, -40, -38, -37, -34, -31, -30, -23, -19, -18, -15, -13, -4, -2, 2, 4, 7, 9, 11, 12, 14, 17, 19, 21, 22, 23, 25, 28, 29, 31, 32, 36, 37, 38, 39, 40, 42, 43, 44, 47, 50, 52, 53, 54, 55, 56, 57, 58, 59, 61, 63]
+testing intersection
+[39, 42]
+testing difference
+[-59, -34, -19, -15, 2, 7, 19, 22, 25, 28, 29, 31, 32, 36, 38, 40, 44, 47, 58, 59]
+testing remove_least_element
+-59
+[-34, -19, -15, 2, 7, 19, 22, 25, 28, 29, 31, 32, 36, 38, 39, 40, 42, 44, 47, 58, 59]
+testing delete_list
+[-59, -34, -19, -15, 2, 7, 19, 22, 25, 28, 29, 31, 32, 36, 38, 40, 44, 47, 58, 59]
+count: 20 40
+testing foldl
+testing union
+testing intersection
+testing difference
+testing remove_least_element
+testing delete_list
+count: 20 40
+testing foldl
+testing union
+testing intersection
+testing difference
+testing remove_least_element
+testing delete_list
+count: 20 40
+testing foldl
+testing union
+testing intersection
+testing difference
+testing remove_least_element
+testing delete_list
+count: 20 40
+testing foldl
+testing union
+testing intersection
+testing difference
+testing remove_least_element
+testing delete_list
+count: 20 40
+testing foldl
+testing union
+testing intersection
+testing difference
+testing remove_least_element
+testing delete_list
+count: 20 40
+testing foldl
+testing union
+testing intersection
+testing difference
+testing remove_least_element
+testing delete_list
+count: 20 40
+testing foldl
+testing union
+testing intersection
+testing difference
+testing remove_least_element
+testing delete_list
+count: 20 40
+testing foldl
+testing union
+testing intersection
+testing difference
+testing remove_least_element
+testing delete_list
+count: 20 40
+testing foldl
+testing union
+testing intersection
+testing difference
+testing remove_least_element
+testing delete_list
+count: 20 40
+testing foldl
+testing union
+testing intersection
+testing difference
+testing remove_least_element
+testing delete_list
Index: test_bitset.m
===================================================================
RCS file: test_bitset.m
diff -N test_bitset.m
--- /dev/null	Sat Aug  7 21:45:41 1999
+++ test_bitset.m	Thu Feb 15 21:19:27 2001
@@ -0,0 +1,152 @@
+:- module test_bitset.
+
+:- interface.
+
+:- import_module io.
+
+:- pred main(io__state::di, io__state::uo) is det.
+
+:- implementation.
+
+:- import_module bool, enum, int, list, bitset_tester, random, require.
+
+:- func list1 = list(int).
+
+list1 = [29, 28, 31, 22, -15, 32, 19, 58, -59, 36, 7, 39, 42,
+		-34, 25, 40, 59, 2, -19, 44, 47, 38].
+
+:- func list2 = list(int).
+
+list2 = [21, 52, 23, -18, -23, 56, 11, -46, 61, -4, 63, 54, 17, -64,
+		-13, -38, 37, 4, 39, -2, 57, -56, -37, -30, -51, 12, -49,
+		-58, -31, -48, -61, 42, 53, -44, 55, 14, 9, -40, 43, 50].
+
+main -->
+	% Run one lot of tests with known input lists,
+	% to generate some visible output.
+	{ Write = yes },
+	run_test(Write, list1, list2),
+
+	% Run some more tests with random input, checking
+	% the output against that of set_ordlist.
+	{ Iterations = 10 },
+	{ random__init(1, Supply) },
+	run_tests(Iterations, Supply).
+
+:- pred run_tests(int::in, random__supply::mdi,
+		io__state::di, io__state::uo) is det.
+
+run_tests(Iterations, Supply0) -->
+	( { Iterations = 0 } ->
+		[]
+	;
+		{ Num1 = 20 },
+		{ get_random_numbers(Num1, [], List1, Supply0, Supply1) },
+		{ Num2 = 40 },
+		{ get_random_numbers(Num2, [], List2, Supply1, Supply) },
+		
+		{ Write = no },
+		run_test(Write, List1, List2),
+
+
+		run_tests(Iterations - 1, Supply)
+	).
+
+:- pred get_random_numbers(int::in, list(int)::in, list(int)::out,
+		random__supply::mdi, random__supply::muo) is det.
+
+get_random_numbers(Num, List0, List, Supply0, Supply) :-
+	( Num = 0 ->
+		List = List0,
+		Supply = Supply0
+	;
+		random__random(N, Supply0, Supply1),
+		RN = N rem 128 - 64,	% test negative numbers
+		get_random_numbers(Num - 1, [RN | List0], List,
+			Supply1, Supply)
+	).
+
+:- pred run_test(bool::in, list(int)::in, list(int)::in,
+		io__state::di, io__state::uo) is det.
+
+run_test(Write, List1, List2) -->
+	( { Write = yes } ->
+		io__write_string("List1: "),
+		io__write_list(list__sort(List1), ", ", io__write_int),
+		io__nl, io__nl,
+		io__write_string("List2: "),
+		io__write_list(list__sort(List2), ", ", io__write_int),
+		io__nl, io__nl
+	;
+		[]	
+	),
+	{ Set1 = bitset_tester__list_to_set(List1) },
+	{ Set2 = bitset_tester__list_to_set(List2) },
+
+	io__write_string("count: "),
+	io__write_int(count(Set1)),
+	io__write_string(" "),
+	io__write_int(count(Set2)),
+	io__nl,
+
+	io__write_string("testing foldl\n"),
+	{ Sum = (func(Elem, Acc) = Elem + Acc) },
+	{ Result1 = foldl(Sum, Set1, 0) },
+	{ Result2 = foldl(Sum, Set2, 0) },
+	( { Write = yes } ->
+		io__write_string("Sum of List1 = "),
+		io__write_int(Result1),
+		io__nl,
+		io__write_string("Sum of List2 = "),
+		io__write_int(Result2),
+		io__nl
+	;
+		[]
+	),
+
+	io__write_string("testing union\n"),
+	{ Union = union(Set1, Set2) },
+	write_bitset_result(Write, Union),
+
+	io__write_string("testing intersection\n"),
+	{ Intersection = intersect(Set1, Set2) },
+	write_bitset_result(Write, Intersection),
+
+	io__write_string("testing difference\n"),
+	{ Difference = difference(Set1, Set2) },
+	write_bitset_result(Write, Difference),
+
+	io__write_string("testing remove_least_element\n"),
+	( { remove_least(Set1, Least, RemovedLeast) } ->
+		( { Write = yes } ->
+			io__write_int(Least),
+			io__nl
+		;
+			[]
+		),
+		write_bitset_result(Write, RemovedLeast)
+	;
+		{ error("remove_least failed") }
+	),
+
+	io__write_string("testing delete_list\n"),
+	{ Delete = delete_list(Set1, List2) },
+	write_bitset_result(Write, Delete),
+
+	{ require(unify(delete_list(Set1, List1),
+			init `with_type` bitset_tester(int)),
+		"delete_list_failed") }.
+
+:- pred write_bitset_result(bool::in, bitset_tester(int)::in,
+		io__state::di, io__state::uo) is det.
+:- pragma no_inline(write_bitset_result/4).
+	
+write_bitset_result(Write, Set) -->
+	( { Write = yes } ->
+		{ List `with_type` list(int) = to_sorted_list(Set) },
+		io__write(List),
+		io__nl
+	;
+		[]
+	).
+

--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------



More information about the developers mailing list