[Guile-commits] 04/08: Fix sort, sort! for arrays with nonzero lower bound

[Daniel Llorens]

lloda pushed a commit to branch wip-lloda
in repository guile.

commit f36ad82aefd9a5b9cfd7e15aea2eeabe75664f8a
Author: Daniel Llorens 
Date:   Mon Feb 13 12:58:34 2017 +0100

Fix sort, sort! for arrays with nonzero lower bound

* module/ice-9/arrays.scm (array-copy): New function, export.
* module/Makefile.am: Install (ice-9 arrays).
* doc/ref/api-data.texi: Add documentation for (ice-9 arrays).
* libguile/quicksort.i.c: Use signed bounds throughout.
* libguile/sort.c (scm_restricted_vector_sort_x): Fix error calls. Fix
  calls to quicksort.
* test-suite/tests/sort.test: Actually test that the sorted results
  match the original data. Test cases for non-zero base index arrays for
  sort, sort!, and stable-sort!.
---
 doc/ref/api-data.texi  |  32 +++---
 libguile/quicksort.i.c |  48 +++
 libguile/sort.c|  68 -
 module/Makefile.am |   1 +
 module/ice-9/arrays.scm|  50 +--
 test-suite/tests/sort.test | 149 -
 6 files changed, 208 insertions(+), 140 deletions(-)

diff --git a/doc/ref/api-data.texi b/doc/ref/api-data.texi
index 05b7083..ac743ea 100644
--- a/doc/ref/api-data.texi
+++ b/doc/ref/api-data.texi
@@ -7498,10 +7498,6 @@ same type, and have corresponding elements which are 
either
 @code{equal?} (@pxref{Equality}) in that all arguments must be arrays.
 @end deffn
 
-@c  FIXME: array-map! accepts no source arrays at all, and in that
-@c  case makes calls "(proc)".  Is that meant to be a documented
-@c  feature?
-@c
 @c  FIXME: array-for-each doesn't say what happens if the sources have
 @c  different index ranges.  The code currently iterates over the
 @c  indices of the first and expects the others to cover those.  That
@@ -7509,14 +7505,15 @@ same type, and have corresponding elements which are 
either
 @c  documented feature?
 
 @deffn {Scheme Procedure} array-map! dst proc src @dots{}
-@deffnx {Scheme Procedure} array-map-in-order! dst proc src1 @dots{} srcN
+@deffnx {Scheme Procedure} array-map-in-order! dst proc src @dots{}
 @deffnx {C Function} scm_array_map_x (dst, proc, srclist)
-Set each element of the @var{dst} array to values obtained from calls
-to @var{proc}.  The value returned is unspecified.
+Set each element of the @var{dst} array to values obtained from calls to
+@var{proc}.  The list of @var{src} arguments may be empty.  The value
+returned is unspecified.
 
-Each call is @code{(@var{proc} @var{elem1} @dots{} @var{elemN})},
-where each @var{elem} is from the corresponding @var{src} array, at
-the @var{dst} index.  @code{array-map-in-order!} makes the calls in
+Each call is @code{(@var{proc} @var{elem} @dots{})}, where each
+@var{elem} is from the corresponding @var{src} array, at the
+@var{dst} index.  @code{array-map-in-order!} makes the calls in
 row-major order, @code{array-map!} makes them in an unspecified order.
 
 The @var{src} arrays must have the same number of dimensions as
@@ -7568,6 +7565,21 @@ $\left(\matrix{%
 @end example
 @end deffn
 
+An additional array function is available in the module
+@code{(ice-9 arrays)}. It can be used with:
+
+@example
+(use-modules (ice-9 arrays))
+@end example
+
+@deffn {Scheme Procedure} array-copy src
+Return a new array with the same elements, type and shape as
+@var{src}. However, the array increments may not be the same as those of
+@var{src}. In the current implementation, the returned array will be in
+row-major order, but that might change in the future. Use
+@code{array-copy!} on an array of known order if that is a concern.
+@end deffn
+
 @node Shared Arrays
 @subsubsection Shared Arrays
 
diff --git a/libguile/quicksort.i.c b/libguile/quicksort.i.c
index cf1742e..5982672 100644
--- a/libguile/quicksort.i.c
+++ b/libguile/quicksort.i.c
@@ -27,7 +27,7 @@
reduces the probability of selecting a bad pivot value and eliminates
certain extraneous comparisons.
 
-   3. Only quicksorts NR_ELEMS / MAX_THRESH partitions, leaving insertion sort
+   3. Only quicksorts (UBND-LBND+1) / MAX_THRESH partitions, leaving insertion 
sort
to order the MAX_THRESH items within each partition.  This is a big win,
since insertion sort is faster for small, mostly sorted array segments.
 
@@ -54,33 +54,29 @@
 #defineSTACK_NOT_EMPTY  (stack < top)
 
 static void
-NAME (VEC_PARAM size_t nr_elems, INC_PARAM SCM less)
+NAME (VEC_PARAM ssize_t lbnd, ssize_t ubnd, INC_PARAM SCM less)
 {
   /* Stack node declarations used to store unfulfilled partition obligations. 
*/
   typedef struct {
-size_t lo;
-size_t hi;
+ssize_t lo;
+ssize_t hi;
   } stack_node;
 
   static const char s_buggy_less[] = "buggy less predicate used when sorting";
 
-  if (nr_elems == 0)
-/* Avoid lossage with unsigned arithmetic below.  */
-return;
-
-  if (nr_elems > MAX_THRESH)
+  if (ubnd-lbnd+1 > MAX_THRESH)
 {
-  size_t lo = 0;
-  

[Guile-commits] 04/08: Fix sort, sort! for arrays with nonzero lower bound

[Daniel Llorens]

lloda pushed a commit to branch wip-exception-truncate
in repository guile.

commit b049717b31e4bfefd29d2b96970efc0c63d1bfbb
Author: Daniel Llorens 
Date:   Mon Feb 13 12:58:34 2017 +0100

Fix sort, sort! for arrays with nonzero lower bound

* module/ice-9/arrays.scm (array-copy, typed-array-copy): New
  functions. Export.
* module/Makefile.am: Install (ice-9 arrays).
* doc/ref/api-data.texi: Add documentation for (ice-9 arrays).
* libguile/quicksort.i.c: Use signed bounds throughout.
* libguile/sort.c (scm_restricted_vector_sort_x): Fix error calls. Fix
  calls to quicksort.
* test-suite/tests/sort.test: Actually test that the sorted results
  match the original data. Test cases for non-zero base index arrays for
  sort, sort!, and stable-sort!.
---
 doc/ref/api-data.texi  |  38 +
 libguile/quicksort.i.c |  48 
 libguile/sort.c|  43 ++-
 module/Makefile.am |   1 +
 module/ice-9/arrays.scm|  53 +++---
 test-suite/tests/sort.test | 133 -
 6 files changed, 194 insertions(+), 122 deletions(-)

diff --git a/doc/ref/api-data.texi b/doc/ref/api-data.texi
index f5c8798..bb4b9f7 100644
--- a/doc/ref/api-data.texi
+++ b/doc/ref/api-data.texi
@@ -7495,10 +7495,6 @@ same type, and have corresponding elements which are 
either
 @code{equal?} (@pxref{Equality}) in that all arguments must be arrays.
 @end deffn
 
-@c  FIXME: array-map! accepts no source arrays at all, and in that
-@c  case makes calls "(proc)".  Is that meant to be a documented
-@c  feature?
-@c
 @c  FIXME: array-for-each doesn't say what happens if the sources have
 @c  different index ranges.  The code currently iterates over the
 @c  indices of the first and expects the others to cover those.  That
@@ -7506,14 +7502,15 @@ same type, and have corresponding elements which are 
either
 @c  documented feature?
 
 @deffn {Scheme Procedure} array-map! dst proc src @dots{}
-@deffnx {Scheme Procedure} array-map-in-order! dst proc src1 @dots{} srcN
+@deffnx {Scheme Procedure} array-map-in-order! dst proc src @dots{}
 @deffnx {C Function} scm_array_map_x (dst, proc, srclist)
-Set each element of the @var{dst} array to values obtained from calls
-to @var{proc}.  The value returned is unspecified.
+Set each element of the @var{dst} array to values obtained from calls to
+@var{proc}.  The list of @var{src} arguments may be empty.  The value
+returned is unspecified.
 
-Each call is @code{(@var{proc} @var{elem1} @dots{} @var{elemN})},
-where each @var{elem} is from the corresponding @var{src} array, at
-the @var{dst} index.  @code{array-map-in-order!} makes the calls in
+Each call is @code{(@var{proc} @var{elem} @dots{})}, where each
+@var{elem} is from the corresponding @var{src} array, at the
+@var{dst} index.  @code{array-map-in-order!} makes the calls in
 row-major order, @code{array-map!} makes them in an unspecified order.
 
 The @var{src} arrays must have the same number of dimensions as
@@ -7565,6 +7562,27 @@ $\left(\matrix{%
 @end example
 @end deffn
 
+A few additional array functions are available in the module
+@code{(ice-9 arrays)}. They can be used with:
+
+@example
+(use-modules (ice-9 arrays))
+@end example
+
+@deffn {Scheme Procedure} array-copy src
+Return a new array with the same elements, type and shape as
+@var{src}. However, the array increments may not be the same as those of
+@var{src}. In the current implementation, the returned array will be in
+row-major order, but that might change in the future. Use
+@code{array-copy!} on an array of known order if that is a concern.
+@end deffn
+
+@deffn {Scheme Procedure} typed-array-copy type src
+Return a new array with the same elements and shape as @var{src}, but
+with the type given. This operation may fail if @var{type} is not
+compatible with the values in @var{src}.
+@end deffn
+
 @node Shared Arrays
 @subsubsection Shared Arrays
 
diff --git a/libguile/quicksort.i.c b/libguile/quicksort.i.c
index cf1742e..5982672 100644
--- a/libguile/quicksort.i.c
+++ b/libguile/quicksort.i.c
@@ -27,7 +27,7 @@
reduces the probability of selecting a bad pivot value and eliminates
certain extraneous comparisons.
 
-   3. Only quicksorts NR_ELEMS / MAX_THRESH partitions, leaving insertion sort
+   3. Only quicksorts (UBND-LBND+1) / MAX_THRESH partitions, leaving insertion 
sort
to order the MAX_THRESH items within each partition.  This is a big win,
since insertion sort is faster for small, mostly sorted array segments.
 
@@ -54,33 +54,29 @@
 #defineSTACK_NOT_EMPTY  (stack < top)
 
 static void
-NAME (VEC_PARAM size_t nr_elems, INC_PARAM SCM less)
+NAME (VEC_PARAM ssize_t lbnd, ssize_t ubnd, INC_PARAM SCM less)
 {
   /* Stack node declarations used to store unfulfilled partition obligations. 
*/
   typedef struct {
-size_t lo;
-size_t hi;
+ssize_t lo;
+ssize_t hi;
   } 

[Guile-commits] 04/08: Fix sort, sort! for arrays with nonzero lower bound

[Daniel Llorens]

lloda pushed a commit to branch wip-exception-truncate
in repository guile.

commit dbf4a2f9426450977cdc32b7e1a807320830eea5
Author: Daniel Llorens 
Date:   Mon Feb 13 12:58:34 2017 +0100

Fix sort, sort! for arrays with nonzero lower bound

* module/ice-9/arrays.scm (array-copy, typed-array-copy): New
  functions. Export.
* module/Makefile.am: Install (ice-9 arrays).
* doc/ref/api-data.texi: Add documentation for (ice-9 arrays).
* libguile/quicksort.i.c: Use signed bounds throughout.
* libguile/sort.c (scm_restricted_vector_sort_x): Fix error calls. Fix
  calls to quicksort.
* test-suite/tests/sort.test: Actually test that the sorted results
  match the original data. Test cases for non-zero base index arrays for
  sort, sort!, and stable-sort!.
---
 doc/ref/api-data.texi  |  38 +
 libguile/quicksort.i.c |  48 
 libguile/sort.c|  43 ++-
 module/Makefile.am |   1 +
 module/ice-9/arrays.scm|  53 +++---
 test-suite/tests/sort.test | 133 -
 6 files changed, 194 insertions(+), 122 deletions(-)

diff --git a/doc/ref/api-data.texi b/doc/ref/api-data.texi
index f5c8798..bb4b9f7 100644
--- a/doc/ref/api-data.texi
+++ b/doc/ref/api-data.texi
@@ -7495,10 +7495,6 @@ same type, and have corresponding elements which are 
either
 @code{equal?} (@pxref{Equality}) in that all arguments must be arrays.
 @end deffn
 
-@c  FIXME: array-map! accepts no source arrays at all, and in that
-@c  case makes calls "(proc)".  Is that meant to be a documented
-@c  feature?
-@c
 @c  FIXME: array-for-each doesn't say what happens if the sources have
 @c  different index ranges.  The code currently iterates over the
 @c  indices of the first and expects the others to cover those.  That
@@ -7506,14 +7502,15 @@ same type, and have corresponding elements which are 
either
 @c  documented feature?
 
 @deffn {Scheme Procedure} array-map! dst proc src @dots{}
-@deffnx {Scheme Procedure} array-map-in-order! dst proc src1 @dots{} srcN
+@deffnx {Scheme Procedure} array-map-in-order! dst proc src @dots{}
 @deffnx {C Function} scm_array_map_x (dst, proc, srclist)
-Set each element of the @var{dst} array to values obtained from calls
-to @var{proc}.  The value returned is unspecified.
+Set each element of the @var{dst} array to values obtained from calls to
+@var{proc}.  The list of @var{src} arguments may be empty.  The value
+returned is unspecified.
 
-Each call is @code{(@var{proc} @var{elem1} @dots{} @var{elemN})},
-where each @var{elem} is from the corresponding @var{src} array, at
-the @var{dst} index.  @code{array-map-in-order!} makes the calls in
+Each call is @code{(@var{proc} @var{elem} @dots{})}, where each
+@var{elem} is from the corresponding @var{src} array, at the
+@var{dst} index.  @code{array-map-in-order!} makes the calls in
 row-major order, @code{array-map!} makes them in an unspecified order.
 
 The @var{src} arrays must have the same number of dimensions as
@@ -7565,6 +7562,27 @@ $\left(\matrix{%
 @end example
 @end deffn
 
+A few additional array functions are available in the module
+@code{(ice-9 arrays)}. They can be used with:
+
+@example
+(use-modules (ice-9 arrays))
+@end example
+
+@deffn {Scheme Procedure} array-copy src
+Return a new array with the same elements, type and shape as
+@var{src}. However, the array increments may not be the same as those of
+@var{src}. In the current implementation, the returned array will be in
+row-major order, but that might change in the future. Use
+@code{array-copy!} on an array of known order if that is a concern.
+@end deffn
+
+@deffn {Scheme Procedure} typed-array-copy type src
+Return a new array with the same elements and shape as @var{src}, but
+with the type given. This operation may fail if @var{type} is not
+compatible with the values in @var{src}.
+@end deffn
+
 @node Shared Arrays
 @subsubsection Shared Arrays
 
diff --git a/libguile/quicksort.i.c b/libguile/quicksort.i.c
index cf1742e..5982672 100644
--- a/libguile/quicksort.i.c
+++ b/libguile/quicksort.i.c
@@ -27,7 +27,7 @@
reduces the probability of selecting a bad pivot value and eliminates
certain extraneous comparisons.
 
-   3. Only quicksorts NR_ELEMS / MAX_THRESH partitions, leaving insertion sort
+   3. Only quicksorts (UBND-LBND+1) / MAX_THRESH partitions, leaving insertion 
sort
to order the MAX_THRESH items within each partition.  This is a big win,
since insertion sort is faster for small, mostly sorted array segments.
 
@@ -54,33 +54,29 @@
 #defineSTACK_NOT_EMPTY  (stack < top)
 
 static void
-NAME (VEC_PARAM size_t nr_elems, INC_PARAM SCM less)
+NAME (VEC_PARAM ssize_t lbnd, ssize_t ubnd, INC_PARAM SCM less)
 {
   /* Stack node declarations used to store unfulfilled partition obligations. 
*/
   typedef struct {
-size_t lo;
-size_t hi;
+ssize_t lo;
+ssize_t hi;
   }