[m-dev.] diff: Array reorganisation

[Andrew Bromage]

G'day.

This is a diff between the old submission and the new one.  Yes, the
change in actual_position/4 is a bug fix.

Cheers,
Andrew Bromage


Estimated hours taken: 7

The main purpose of this change is to rename array.m as bt_array.m, and
uniq_array.m as array.m.  The interfaces of those two modules have grown
slightly so that they match a little more closely.  Details are in the
file NEWS.

The implementation of bt_array (formerly array) has been changed to use
a slightly more efficient implementation.

NEWS:
	Interface changes documented.

library/array.m:
library/bt_array.m:
	Changes mentioned above and detailed in the NEWS file.

library/uniq_array.m:
	Bereft of life and resting in peace.

library/io.m:
library/library.m:
library/std_util.m:
library/term.m:
compiler/base_type_layout.m:
runtime/deep_copy.c:
runtime/type_info.h:
	Minor changes to fix the special case of base_type_layout
	operations for arrays rather than uniq_arrays.

tests/hard_coded/write.exp:
tests/hard_coded/write.m:
	Test writing of arrays.

tests/general/array_test.exp:
tests/general/array_test.m:
	Test some array/bt_array operations.


Index: library/bt_array.m
===================================================================
--- bt_array_old.m	Fri Jul 25 14:37:43 1997
+++ bt_array.m	Fri Jul 25 14:19:42 1997
@@ -11,7 +11,14 @@
 % This file contains a set of predicates for generating an manipulating
 % a bt_array data structure.  This implementation allows O(log n) access
 % and update time, and does not require the bt_array to be unique.  If you
-% need O(1) access/update time, use the uniq_bt_array datatype instead.
+% need O(1) access/update time, use the array datatype instead.
+
+% Implementation obscurity: This implementation is biassed towards larger
+% indices.  The access/update time for a bt_array of size N with index I
+% is actually O(log(N-I)).  The reason for this is so that the resize
+% operations can be optimised for a (possibly very) common case, and to
+% exploit accumulator recursion in some operations.  See the documentation
+% of bt_array__resize and bt_array__shrink for more details.
 
 %-----------------------------------------------------------------------------%
 %-----------------------------------------------------------------------------%
@@ -87,6 +94,13 @@
 	% BtArray0 to fit the bounds (Lo,Hi).  If the new bounds are
 	% not wholly contained within the bounds of BtArray0, Item is
 	% used to fill out the other places.
+	%
+	% Note: This operation is optimised for the case where the
+	% lower bound of the new bt_array is the same as that of
+	% the old bt_array.  In that case, the operation takes time
+	% proportional to the absolute difference in size between
+	% the two bt_arrays.  If this is not the case, it may take
+	% time proportional to the larger of the two bt_arrays.
 :- pred bt_array__resize(bt_array(T), int, int, T, bt_array(T)).
 :- mode bt_array__resize(in, in, in, in, out) is det.
 
@@ -94,6 +108,13 @@
 	% if BtArray is a bt_array created by shrinking BtArray0 to
 	% fit the bounds (Lo,Hi).  It is an error if the new bounds
 	% are not wholly within the bounds of BtArray0.
+	%
+	% Note: This operation is optimised for the case where the
+	% lower bound of the new bt_array is the same as that of
+	% the old bt_array.  In that case, the operation takes time
+	% proportional to the absolute difference in size between
+	% the two bt_arrays.  If this is not the case, it may take
+	% time proportional to the larger of the two bt_arrays.
 :- pred bt_array__shrink(bt_array(T), int, int, bt_array(T)).
 :- mode bt_array__shrink(in, in, in, out) is det.
 
@@ -136,8 +157,8 @@
 
 %-----------------------------------------------------------------------------%
 
-bt_array__make_empty_array(Low, bt_array(Low, Hi, ListOut)) :-
-	Hi is Low - 1,
+bt_array__make_empty_array(Low, bt_array(Low, High, ListOut)) :-
+	High is Low - 1,
 	ra_list_nil(ListOut).
 
 bt_array__init(Low, High, Item, bt_array(Low, High, ListOut)) :-
@@ -178,7 +199,7 @@
 :- mode actual_position(in, in, in, out) is det.
 
 actual_position(Low, High, Index, Pos) :-
-	Pos is High - Low - Index + 1.
+	Pos is High - Low - Index.
 
 bt_array__lookup(bt_array(Low, High, RaList), Index, Item) :-
 	actual_position(Low, High, Index, Pos),
@@ -346,6 +367,8 @@
 	Lo =< Hi,
 	bt_array__bsearch_2(A, Lo, Hi, El, Compare, I).
 
+	% XXX Would we gain anything by traversing the ra_list instead
+	%     of doing a vanilla binary chop?
 :- pred bt_array__bsearch_2(bt_array(T), int, int, T,
 			pred(T, T, comparison_result), int).
 :- mode bt_array__bsearch_2(in, in, in, in, pred(in, in, out) is det,
@@ -393,6 +416,18 @@
 % This is a perfect application for submodules, but Mercury doesn't have
 % them. :-(
 
+% The heart of the implementation of bt_array is a `random access list'
+% or ra_list for short.  It is very similar to a list data type, and
+% it supports O(1) head/tail/cons operations, but O(log n) lookup and
+% update.  The representation is a list of perfectly balanced forest
+% of binary trees.
+%
+% For mode details on the implementation:
+%
+%	Chris Okasaki, "Purely Functional Random-Access Lists"
+%	Functional Programming Languages and Computer Architecutre,
+%	June 1995, pp 86-95.
+
 % :- module ra_list.
 % :- interface.
 
@@ -453,7 +488,8 @@
 		List0 = cons(Size1, T1, cons(Size2, T2, Rest)),
 		Size1 = Size2
 	->
-		List = cons(1+Size1+Size2, node(X, T1, T2), Rest)
+		NewSize is 1 + Size1 + Size2,
+		List = cons(NewSize, node(X, T1, T2), Rest)
 	;
 		List = cons(1, leaf(X), List0)
 	).
@@ -479,7 +515,7 @@
 
 %-----------------------------------------------------------------------------%
 
-:- pragma inline(ra_list_update/4).
+:- pragma inline(ra_list_lookup/3).
 
 ra_list_lookup(I, List, X) :-
 	I >= 0,
@@ -505,9 +541,11 @@
 	;
 		Size2 = Size // 2,
 		( I =< Size2 ->
-			ra_list_bintree_lookup(Size2, T1, I-1, X)
+			NewI is I - 1,
+			ra_list_bintree_lookup(Size2, T1, NewI, X)
 		;
-			ra_list_bintree_lookup(Size2, T2, I-1-Size2, X)
+			NewI is I - 1 - Size2,
+			ra_list_bintree_lookup(Size2, T2, NewI, X)
 		)
 	).
 
@@ -542,10 +580,12 @@
 	;
 		Size2 = Size // 2,
 		( I =< Size2 ->
-			ra_list_bintree_update(Size2, T1, I-1, X, T0),
+			NewI is I - 1,
+			ra_list_bintree_update(Size2, T1, NewI, X, T0),
 			T = node(X0, T0, T2)
 		;
-			ra_list_bintree_update(Size2, T2, I-1-Size2, X, T0),
+			NewI is I - 1 - Size2,
+			ra_list_bintree_update(Size2, T2, NewI, X, T0),
 			T = node(X0, T1, T0)
 		)
 	).

Index: tests/general/Mmake
===================================================================
RCS file: /home/staff/zs/imp/tests/general/Mmake,v
retrieving revision 1.46
diff -u -r1.46 Mmake
--- Mmake	1997/07/23 23:25:40	1.46
+++ Mmake	1997/07/25 02:42:09
@@ -13,7 +13,8 @@
 
 #-----------------------------------------------------------------------------#
 
-PROGS=		commit_bug \
+PROGS=		array_test \
+		commit_bug \
 		commit_bug_2 \
 		disj_disj \
 		dnf \
New file: tests/general/array_test.m
===================================================================
% Some checks of array implementation.

:- module array_test.
:- interface.
:- import_module io.

:- pred main(io__state, io__state).
:- mode main(di, uo) is det.

:- implementation.
:- import_module int, string, list, array, bt_array, std_util.

main -->
	test([1,2,3,4,5,6,7,8,9,10]).

:- pred test(list(int), io__state, io__state).
:- mode test(in, di, uo) is det.

test(Xs) -->
	{
		Cmp = lambda([X :: in, Y :: in, Res :: out] is det,
			compare(Res, X, Y)),
		A0 = array(Xs),
		array__to_list(A0, As0),
		array__max(A0, AMax0),
		array__min(A0, AMin0),
		array__size(A0, ASize),
		array__bounds(A0, AMin1, AMax1),
		array__bsearch(A0, 4, Cmp, ABsearch),
		array__set(A0, 8, 100, A1),
		array__to_list(A1, As1),
		array__resize(A1, 15, 1000, A2),
		array__to_list(A2, As2),
		array__shrink(A2, 10, A3),
		array__to_list(A3, As3)
	},
	write_message("A0: ", As0),
	write_message("AMax0: ", AMax0),
	write_message("AMin0: ", AMin0),
	write_message("ASize: ", ASize),
	write_message("AMin1: ", AMin1),
	write_message("AMax1: ", AMax1),
	write_message("ABsearch: ", ABsearch),
	write_message("A1: ", As1),
	write_message("A2: ", As2),
	write_message("A3: ", As3),
	{
		bt_array__from_list(0, Xs, B0),
		bt_array__to_list(B0, Bs0),
		bt_array__max(B0, BMax0),
		bt_array__min(B0, BMin0),
		bt_array__size(B0, BSize),
		bt_array__bounds(B0, BMin1, BMax1),
		( bt_array__bsearch(B0, 4, Cmp, BBsearch0) ->
			BBsearch = yes(BBsearch0)
		;
			BBsearch = no
		),
		bt_array__set(B0, 8, 100, B1),
		bt_array__to_list(B1, Bs1),
		bt_array__resize(B1, 0, 15, 1000, B2),
		bt_array__to_list(B2, Bs2),
		bt_array__shrink(B2, 0, 10, B3),
		bt_array__to_list(B3, Bs3)
	},
	write_message("B0: ", Bs0),
	write_message("BMax0: ", BMax0),
	write_message("BMin0: ", BMin0),
	write_message("BSize: ", BSize),
	write_message("BMin1: ", BMin1),
	write_message("BMax1: ", BMax1),
	write_message("BBsearch: ", BBsearch),
	write_message("B1: ", Bs1),
	write_message("B2: ", Bs2),
	write_message("B3: ", Bs3),
	
	% Finally, just in case, compare the two implementations.
	(
		{
			As0 = Bs0,
			AMax0 = BMax1,
			AMin0 = BMin1,
			ASize = BSize,
			AMin1 = BMin1,
			AMax1 = BMax1,
			AMax0 = AMax1,
			AMin0 = AMin1,
			BMax0 = BMax1,
			BMin0 = BMin1,
			ABSearch = BBSearch,
			As1 = Bs1,
			As2 = Bs2,
			As3 = Bs3,
			As1 = As3,
			Bs1 = Bs3
		}
	->
		io__write_string("Results all match")
	;
		io__write_string("Results don't match")
	).

:- pred write_message(string, T, io__state, io__state).
:- mode write_message(in, array_ui, di, uo) is det.
:- mode write_message(in, in, di, uo) is det.

write_message(Msg, O) -->
	io__write_string(Msg),
	io__write(O),
	io__nl.

New file: tests/general/array_test.exp
===================================================================
A0: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
AMax0: 9
AMin0: 0
ASize: 10
AMin1: 0
AMax1: 9
ABsearch: yes(3)
A1: [1, 2, 3, 4, 5, 6, 7, 8, 100, 10]
A2: [1, 2, 3, 4, 5, 6, 7, 8, 100, 10, 1000, 1000, 1000, 1000, 1000]
A3: [1, 2, 3, 4, 5, 6, 7, 8, 100, 10]
B0: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
BMax0: 9
BMin0: 0
BSize: 10
BMin1: 0
BMax1: 9
BBsearch: yes(3)
B1: [1, 2, 3, 4, 5, 6, 7, 8, 100, 10]
B2: [1, 2, 3, 4, 5, 6, 7, 8, 100, 10, 1000, 1000, 1000, 1000, 1000]
B3: [1, 2, 3, 4, 5, 6, 7, 8, 100, 10]
Results all match