[m-rev.] diff: add array.from_reverse_list/1
Julien Fischer
juliensf at csse.unimelb.edu.au
Mon May 30 03:16:59 AEST 2011
Branches: main
Add a new function to the array module for creating a new array from
a list in reverse order.
Make the existing array.from_list/2 predicate more efficient.
library/array.m:
Add the function array.from_reverse_list/1.
Since array.from_list immediately fills in the elements
of a newly-created array with those of the lists, don't
bother initialising the array elements when the array
is allocated (except in debugging grades).
Generalise ML_unsafe_new_aray so that it can be used
for both the above.
tests/general/array_test.m:
tests/general/array_test.exp:
Test the new function.
Update syntax and formatting in this test case.
NEWS:
Announce the new function.
Julien.
Index: NEWS
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/NEWS,v
retrieving revision 1.580
diff -u -r1.580 NEWS
--- NEWS 27 May 2011 07:54:55 -0000 1.580
+++ NEWS 29 May 2011 16:46:14 -0000
@@ -162,6 +162,10 @@
assoc_list.foldl_values/4 for folding over just keys or values
an association list.
+* We have added the new function array.from_reverse_list/1, which creates
+ a new array from a list with the elements of the array occurring in
+ the reverse order to that of the list.
+
NEWS for Mercury 11.01
----------------------
Index: library/array.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/library/array.m,v
retrieving revision 1.187
diff -u -r1.187 array.m
--- library/array.m 27 May 2011 07:47:31 -0000 1.187
+++ library/array.m 29 May 2011 11:38:45 -0000
@@ -347,11 +347,13 @@
% array.from_list takes a list, and returns an array containing those
% elements in the same order that they occurred in the list.
%
-:- pred array.from_list(list(T), array(T)).
-:- mode array.from_list(in, array_uo) is det.
+:- func array.from_list(list(T)::in) = (array(T)::array_uo) is det.
+:- pred array.from_list(list(T)::in, array(T)::array_uo) is det.
-:- func array.from_list(list(T)) = array(T).
-:- mode array.from_list(in) = array_uo is det.
+ % array.from_reverse_list takes a list, and returns an array containing
+ % those elements in the reverse order that they occurred in the list.
+ %
+:- func array.from_reverse_list(list(T)::in) = (array(T)::array_uo) is det.
% array.to_list takes an array and returns a list containing the elements
% of the array in the same order that they occurred in the array.
@@ -813,7 +815,7 @@
}
public static System.Array
-ML_unsafe_new_array(int Size, object Item)
+ML_unsafe_new_array(int Size, object Item, int IndexToSet)
{
System.Array arr;
@@ -822,7 +824,7 @@
} else {
arr = new object[Size];
}
- arr.SetValue(Item, 0);
+ arr.SetValue(Item, IndexToSet);
return arr;
}
@@ -941,30 +943,30 @@
}
public static Object
-ML_unsafe_new_array(int Size, Object Item)
+ML_unsafe_new_array(int Size, Object Item, int IndexToSet)
{
if (Item instanceof Integer) {
int[] as = new int[Size];
- as[0] = (Integer) Item;
+ as[IndexToSet] = (Integer) Item;
return as;
}
if (Item instanceof Double) {
double[] as = new double[Size];
- as[0] = (Double) Item;
+ as[IndexToSet] = (Double) Item;
return as;
}
if (Item instanceof Character) {
char[] as = new char[Size];
- as[0] = (Character) Item;
+ as[IndexToSet] = (Character) Item;
return as;
}
if (Item instanceof Boolean) {
boolean[] as = new boolean[Size];
- as[0] = (Boolean) Item;
+ as[IndexToSet] = (Boolean) Item;
return as;
}
Object[] as = new Object[Size];
- as[0] = Item;
+ as[IndexToSet] = Item;
return as;
}
@@ -1147,13 +1149,13 @@
;
Result = (>),
FirstElem = GenFunc(0),
- Array0 = unsafe_init(Size, FirstElem),
+ Array0 = unsafe_init(Size, FirstElem, 0),
Array = generate_2(1, Size, GenFunc, Array0)
).
-:- func unsafe_init(int::in, T::in) = (array(T)::array_uo) is det.
+:- func unsafe_init(int::in, T::in, int::in) = (array(T)::array_uo) is det.
:- pragma foreign_proc("C",
- unsafe_init(Size::in, FirstElem::in) = (Array::array_uo),
+ unsafe_init(Size::in, FirstElem::in, IndexToSet::in) = (Array::array_uo),
[promise_pure, will_not_call_mercury, thread_safe, will_not_modify_trail,
does_not_affect_liveness],
"
@@ -1168,24 +1170,24 @@
ML_init_array(Array, Size, FirstElem);
#else
Array->size = Size;
- Array->elements[0] = FirstElem;
+ Array->elements[IndexToSet] = FirstElem;
#endif
").
:- pragma foreign_proc("C#",
- unsafe_init(Size::in, FirstElem::in) = (Array::array_uo),
+ unsafe_init(Size::in, FirstElem::in, IndexToSet::in) = (Array::array_uo),
[promise_pure, will_not_call_mercury, thread_safe],
"
- Array = array.ML_unsafe_new_array(Size, FirstElem);
+ Array = array.ML_unsafe_new_array(Size, FirstElem, IndexToSet);
").
:- pragma foreign_proc("Java",
- unsafe_init(Size::in, FirstElem::in) = (Array::array_uo),
+ unsafe_init(Size::in, FirstElem::in, IndexToSet::in) = (Array::array_uo),
[promise_pure, will_not_call_mercury, thread_safe],
"
- Array = array.ML_unsafe_new_array(Size, FirstElem);
+ Array = array.ML_unsafe_new_array(Size, FirstElem, IndexToSet);
").
:- pragma foreign_proc("Erlang",
- unsafe_init(Size::in, FirstElem::in) = (Array::array_uo),
+ unsafe_init(Size::in, FirstElem::in, _IndexToSet::in) = (Array::array_uo),
[promise_pure, will_not_call_mercury, thread_safe],
"
Array = erlang.make_tuple(Size, FirstElem)
@@ -1214,7 +1216,7 @@
;
Result = (>),
GenPred(0, FirstElem, !Acc),
- Array0 = unsafe_init(Size, FirstElem),
+ Array0 = unsafe_init(Size, FirstElem, 0),
generate_foldl_2(1, Size, GenPred, Array0, Array, !Acc)
).
@@ -1880,7 +1882,7 @@
array.from_list(List, Array) :-
List = [Head | Tail],
list.length(List, Len),
- array.init(Len, Head, Array0),
+ Array0 = array.unsafe_init(Len, Head, 0),
array.unsafe_insert_items(Tail, 1, Array0, Array).
%-----------------------------------------------------------------------------%
@@ -1895,6 +1897,24 @@
%-----------------------------------------------------------------------------%
+array.from_reverse_list([]) = Array :-
+ array.make_empty_array(Array).
+array.from_reverse_list(RevList) = Array :-
+ RevList = [Head | Tail],
+ list.length(RevList, Len),
+ Array0 = array.unsafe_init(Len, Head, Len - 1),
+ array.unsafe_insert_items_reverse(Tail, Len - 2, Array0, Array).
+
+:- pred array.unsafe_insert_items_reverse(list(T)::in, int::in,
+ array(T)::array_di, array(T)::array_uo) is det.
+
+array.unsafe_insert_items_reverse([], _, !Array).
+array.unsafe_insert_items_reverse([Head | Tail], N, !Array) :-
+ array.unsafe_set(N, Head, !Array),
+ array.unsafe_insert_items_reverse(Tail, N - 1, !Array).
+
+%-----------------------------------------------------------------------------%
+
array.to_list(Array) = List :-
array.to_list(Array, List).
Index: tests/general/array_test.exp
===================================================================
RCS file: /home/mercury/mercury1/repository/tests/general/array_test.exp,v
retrieving revision 1.2
diff -u -r1.2 array_test.exp
--- tests/general/array_test.exp 20 Feb 2001 10:42:17 -0000 1.2
+++ tests/general/array_test.exp 29 May 2011 15:35:45 -0000
@@ -10,6 +10,7 @@
A3: [1, 2, 3, 4, 5, 6, 7, 8, 100, 10]
A4: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
A5: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
+A6: [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
B0: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
BMax0: 9
BMin0: 0
Index: tests/general/array_test.m
===================================================================
RCS file: /home/mercury/mercury1/repository/tests/general/array_test.m,v
retrieving revision 1.7
diff -u -r1.7 array_test.m
--- tests/general/array_test.m 6 May 2011 15:19:34 -0000 1.7
+++ tests/general/array_test.m 29 May 2011 15:35:30 -0000
@@ -1,151 +1,159 @@
+% vim: ft=mercury ts=4 sw=4 et
+
% Some checks of array implementation.
:- module array_test.
:- interface.
:- import_module io.
-:- pred main(io__state, io__state).
-:- mode main(di, uo) is det.
+:- pred main(io::di, io::uo) is det.
:- implementation.
-:- import_module int, string, list, array, bt_array, maybe.
-
-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 = (pred(X :: in, Y :: in, Res :: out) is det :-
- compare(Res, X, Y)),
- array__from_list(Xs, A0)
- },
- { array__to_list(A0, As0) },
- write_message_int_list("A0: ", As0),
- { array__max(A0, AMax0) },
- write_message_int("AMax0: ", AMax0),
- { array__min(A0, AMin0) },
- write_message_int("AMin0: ", AMin0),
- { array__size(A0, ASize) },
- write_message_int("ASize: ", ASize),
- { array__bounds(A0, AMin1, AMax1) },
- write_message_int("AMin1: ", AMin1),
- write_message_int("AMax1: ", AMax1),
- { array__bsearch(A0, 4, Cmp, ABsearch) },
- write_message_maybe_int("ABsearch: ", ABsearch),
- { array__set(8, 100, A0, A1) },
- { array__to_list(A1, As1) },
- write_message_int_list("A1: ", As1),
- { array__resize(15, 1000, A1, A2) },
- { array__to_list(A2, As2) },
- write_message_int_list("A2: ", As2),
- { array__shrink(10, A2, A3) },
- { array__to_list(A3, As3) },
- write_message_int_list("A3: ", As3),
- { A4 = array__sort(array(1 `..` 10)) },
- { array__to_list(A4, As4) },
- write_message_int_list("A4: ", As4),
- { A5 = array__sort(array(list__reverse(1 `..` 10))) },
- { array__to_list(A5, As5) },
- write_message_int_list("A5: ", As5),
-
- { bt_array__from_list(0, Xs, B0) },
- { bt_array__to_list(B0, Bs0) },
- write_message_int_list("B0: ", Bs0),
- { bt_array__max(B0, BMax0) },
- write_message_int("BMax0: ", BMax0),
- { bt_array__min(B0, BMin0) },
- write_message_int("BMin0: ", BMin0),
- { bt_array__size(B0, BSize) },
- write_message_int("BSize: ", BSize),
- { bt_array__bounds(B0, BMin1, BMax1) },
- write_message_int("BMin1: ", BMin1),
- write_message_int("BMax1: ", BMax1),
- { ( bt_array__bsearch(B0, 4, Cmp, BBsearch0) ->
- BBsearch = yes(BBsearch0)
- ;
- BBsearch = no
- ) },
- write_message_maybe_int("BBsearch: ", BBsearch),
- { bt_array__set(B0, 8, 100, B1) },
- { bt_array__to_list(B1, Bs1) },
- write_message_int_list("B1: ", Bs1),
- { bt_array__resize(B1, 0, 14, 1000, B2) },
- { bt_array__to_list(B2, Bs2) },
- write_message_int_list("B2: ", Bs2),
- { bt_array__shrink(B2, 0, 9, B3) },
- { bt_array__to_list(B3, Bs3) },
- write_message_int_list("B3: ", Bs3),
-
- % Finally, just in case, compare the two implementations.
- (
- {
- As0 = Bs0,
- AMax0 = BMax1,
- AMin0 = BMin1,
- ASize = BSize,
- AMin1 = BMin1,
- AMax1 = BMax1,
- AMax0 = AMax1, % Sanity check
- AMin0 = AMin1, % Sanity check
- BMax0 = BMax1, % Sanity check
- BMin0 = BMin1, % Sanity check
- ABsearch = BBsearch,
- As1 = Bs1,
- As2 = Bs2,
- As3 = Bs3,
- As1 = As3, % Sanity check
- Bs1 = Bs3 % Sanity check
- }
- ->
- io__write_string("Results all match\n")
- ;
- io__write_string("Results don't match\n")
- ).
-
-:- pred write_message_int(string, int, io__state, io__state).
-:- mode write_message_int(in, in, di, uo) is det.
-write_message_int(Msg, O) -->
- io__write_string(Msg),
- io__write_int(O),
- io__nl.
-
-:- pred write_message_maybe_int(string, maybe(int), io__state, io__state).
-:- mode write_message_maybe_int(in, in, di, uo) is det.
-
-write_message_maybe_int(Msg, no) -->
- io__write_string(Msg),
- io__write_string("no"),
- io__nl.
-write_message_maybe_int(Msg, yes(I)) -->
- io__write_string(Msg),
- io__write_string("yes("),
- io__write_int(I),
- io__write_string(")"),
- io__nl.
-
-:- pred write_message_int_list(string, list(int), io__state, io__state).
-:- mode write_message_int_list(in, in, di, uo) is det.
-
-write_message_int_list(Msg, List) -->
- io__write_string(Msg),
- ( { List = [] },
- io__write_string("[]")
- ; { List = [I | Is] },
- io__write_char('['),
- io__write_int(I),
- write_int_list_rest(Is)
- ),
- io__nl.
-
-:- pred write_int_list_rest(list(int), io__state, io__state).
-:- mode write_int_list_rest(in, di, uo) is det.
-write_int_list_rest([]) -->
- io__write_char(']').
-write_int_list_rest([I | Is]) -->
- io__write_string(", "),
- io__write_int(I),
- write_int_list_rest(Is).
+:- import_module array.
+:- import_module bt_array.
+:- import_module int.
+:- import_module list.
+:- import_module maybe.
+:- import_module string.
+
+main(!IO) :-
+ test([1,2,3,4,5,6,7,8,9,10], !IO).
+
+:- pred test(list(int)::in, io::di, io::uo) is det.
+
+test(Xs, !IO) :-
+ Cmp = (pred(X :: in, Y :: in, Res :: out) is det :-
+ compare(Res, X, Y)
+ ),
+ array.from_list(Xs, A0),
+ array.to_list(A0, As0),
+ write_message_int_list("A0: ", As0, !IO),
+ array.max(A0, AMax0),
+ write_message_int("AMax0: ", AMax0, !IO),
+ array.min(A0, AMin0),
+ write_message_int("AMin0: ", AMin0, !IO),
+ array.size(A0, ASize),
+ write_message_int("ASize: ", ASize, !IO),
+ array.bounds(A0, AMin1, AMax1),
+ write_message_int("AMin1: ", AMin1, !IO),
+ write_message_int("AMax1: ", AMax1, !IO),
+ array.bsearch(A0, 4, Cmp, ABsearch),
+ write_message_maybe_int("ABsearch: ", ABsearch, !IO),
+ array.set(8, 100, A0, A1),
+ array.to_list(A1, As1),
+ write_message_int_list("A1: ", As1, !IO),
+ array.resize(15, 1000, A1, A2),
+ array.to_list(A2, As2),
+ write_message_int_list("A2: ", As2, !IO),
+ array.shrink(10, A2, A3),
+ array.to_list(A3, As3),
+ write_message_int_list("A3: ", As3, !IO),
+ A4 = array.sort(array(1 `..` 10)),
+ array.to_list(A4, As4),
+ write_message_int_list("A4: ", As4, !IO),
+ A5 = array.sort(array(list.reverse(1 `..` 10))),
+ array.to_list(A5, As5),
+ write_message_int_list("A5: ", As5, !IO),
+ A6 = array.from_reverse_list(Xs),
+ As6 = array.to_list(A6),
+ write_message_int_list("A6: ", As6, !IO),
+
+ bt_array.from_list(0, Xs, B0),
+ bt_array.to_list(B0, Bs0),
+ write_message_int_list("B0: ", Bs0, !IO),
+ bt_array.max(B0, BMax0),
+ write_message_int("BMax0: ", BMax0, !IO),
+ bt_array.min(B0, BMin0),
+ write_message_int("BMin0: ", BMin0, !IO),
+ bt_array.size(B0, BSize),
+ write_message_int("BSize: ", BSize, !IO),
+ bt_array.bounds(B0, BMin1, BMax1),
+ write_message_int("BMin1: ", BMin1, !IO),
+ write_message_int("BMax1: ", BMax1, !IO),
+ ( bt_array.bsearch(B0, 4, Cmp, BBsearch0) ->
+ BBsearch = yes(BBsearch0)
+ ;
+ BBsearch = no
+ ),
+ write_message_maybe_int("BBsearch: ", BBsearch, !IO),
+ bt_array.set(B0, 8, 100, B1),
+ bt_array.to_list(B1, Bs1),
+ write_message_int_list("B1: ", Bs1, !IO),
+ bt_array.resize(B1, 0, 14, 1000, B2),
+ bt_array.to_list(B2, Bs2),
+ write_message_int_list("B2: ", Bs2, !IO),
+ bt_array.shrink(B2, 0, 9,B3),
+ bt_array.to_list(B3, Bs3),
+ write_message_int_list("B3: ", Bs3, !IO),
+
+ % Finally, just in case, compare the two implementations.
+ (
+ As0 = Bs0,
+ AMax0 = BMax1,
+ AMin0 = BMin1,
+ ASize = BSize,
+ AMin1 = BMin1,
+ AMax1 = BMax1,
+ AMax0 = AMax1, % Sanity check
+ AMin0 = AMin1, % Sanity check
+ BMax0 = BMax1, % Sanity check
+ BMin0 = BMin1, % Sanity check
+ ABsearch = BBsearch,
+ As1 = Bs1,
+ As2 = Bs2,
+ As3 = Bs3,
+ As1 = As3, % Sanity check
+ Bs1 = Bs3 % Sanity check
+ ->
+ io.write_string("Results all match\n", !IO)
+ ;
+ io.write_string("Results don't match\n", !IO)
+ ).
+
+:- pred write_message_int(string::in, int::in, io::di, io::uo) is det.
+
+write_message_int(Msg, O, !IO) :-
+ io.write_string(Msg, !IO),
+ io.write_int(O, !IO),
+ io.nl(!IO).
+
+:- pred write_message_maybe_int(string::in, maybe(int)::in,
+ io::di, io::uo) is det.
+
+write_message_maybe_int(Msg, no, !IO) :-
+ io.write_string(Msg, !IO),
+ io.write_string("no", !IO),
+ io.nl(!IO).
+write_message_maybe_int(Msg, yes(I), !IO) :-
+ io.write_string(Msg, !IO),
+ io.write_string("yes(", !IO),
+ io.write_int(I, !IO),
+ io.write_string(")", !IO),
+ io.nl(!IO).
+
+:- pred write_message_int_list(string::in, list(int)::in,
+ io::di, io::uo) is det.
+
+write_message_int_list(Msg, List, !IO) :-
+ io.write_string(Msg, !IO),
+ (
+ List = [],
+ io.write_string("[]", !IO)
+ ;
+ List = [I | Is],
+ io.write_char('[', !IO),
+ io.write_int(I, !IO),
+ write_int_list_rest(Is, !IO)
+ ),
+ io.nl(!IO).
+
+:- pred write_int_list_rest(list(int)::in, io::di, io::uo) is det.
+
+write_int_list_rest([], !IO) :-
+ io.write_char(']', !IO).
+write_int_list_rest([I | Is], !IO) :-
+ io.write_string(", ", !IO),
+ io.write_int(I, !IO),
+ write_int_list_rest(Is, !IO).
--------------------------------------------------------------------------
mercury-reviews mailing list
Post messages to: mercury-reviews at csse.unimelb.edu.au
Administrative Queries: owner-mercury-reviews at csse.unimelb.edu.au
Subscriptions: mercury-reviews-request at csse.unimelb.edu.au
--------------------------------------------------------------------------
More information about the reviews
mailing list