[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