[cp-patches] FYI: Arrays.java - Fix insertion sort.

[Mark Wielaard]

Hi,

David Gilbert wrote a bunch of tests for java.util.Arrays.sort() which
showed a minor and a major flaw in our implementation. We fail to detect
a programmer error (giving a negative starting index). And for short
arrays where we use insertion sort we don't properly handle the starting
index (the whole array would get sorted, not just the requested part).

This fixes both issues. All Arrays mauve tests pass now.

2004-08-27  Mark Wielaard  <address@hidden>

        * java/util/Arrays.java
        (sort(byte[], int, int)): Check fromIndex < 0.
        (sort(char[], int, int)): Likewise.
        (sort(short[], int, int)): Likewise.
        (sort(int[], int, int)): Likewise.
        (sort(long[], int, int)): Likewise.
        (sort(float[], int, int)): Likewise.
        (sort(double[], int, int)): Likewise.
        (sort(Object[], int, int, Comparator)): Likewise.
        (qsort(byte[], int, int)): Honor lower bound from in insertion sort.
        (qsort(char[], int, int)): Honor lower bound from in insertion sort.
        (qsort(short[], int, int)): Honor lower bound from in insertion sort.
        (qsort(int[], int, int)): Honor lower bound from in insertion sort.
        (qsort(long[], int, int)): Honor lower bound from in insertion sort.
        (qsort(float[], int, int)): Honor lower bound from in insertion sort.
        (qsort(double[], int, int)): Honor lower bound from in insertion sort.

Committed.

Mark

Index: java/util/Arrays.java
===================================================================
RCS file: /cvsroot/classpath/classpath/java/util/Arrays.java,v
retrieving revision 1.21
diff -u -r1.21 Arrays.java
--- java/util/Arrays.java       17 Aug 2004 22:19:56 -0000      1.21
+++ java/util/Arrays.java       27 Aug 2004 22:18:49 -0000
@@ -1,5 +1,6 @@
 /* Arrays.java -- Utility class with methods to operate on arrays
-   Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003 Free Software Foundation, 
Inc.
+   Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2004
+   Free Software Foundation, Inc.
 
 This file is part of GNU Classpath.
 
@@ -968,6 +969,8 @@
   {
     if (fromIndex > toIndex)
       throw new IllegalArgumentException();
+    if (fromIndex < 0)
+      throw new ArrayIndexOutOfBoundsException();
     qsort(a, fromIndex, toIndex - fromIndex);
   }
 
@@ -1028,7 +1031,7 @@
     if (count <= 7)
       {
         for (int i = from + 1; i < from + count; i++)
-          for (int j = i; j > 0 && array[j - 1] > array[j]; j--)
+          for (int j = i; j > from && array[j - 1] > array[j]; j--)
             swap(j, j - 1, array);
         return;
       }
@@ -1130,6 +1133,8 @@
   {
     if (fromIndex > toIndex)
       throw new IllegalArgumentException();
+    if (fromIndex < 0)
+      throw new ArrayIndexOutOfBoundsException();
     qsort(a, fromIndex, toIndex - fromIndex);
   }
 
@@ -1190,7 +1195,7 @@
     if (count <= 7)
       {
         for (int i = from + 1; i < from + count; i++)
-          for (int j = i; j > 0 && array[j - 1] > array[j]; j--)
+          for (int j = i; j > from && array[j - 1] > array[j]; j--)
             swap(j, j - 1, array);
         return;
       }
@@ -1292,6 +1297,8 @@
   {
     if (fromIndex > toIndex)
       throw new IllegalArgumentException();
+    if (fromIndex < 0)
+      throw new ArrayIndexOutOfBoundsException();
     qsort(a, fromIndex, toIndex - fromIndex);
   }
 
@@ -1352,8 +1359,8 @@
     if (count <= 7)
       {
         for (int i = from + 1; i < from + count; i++)
-          for (int j = i; j > 0 && array[j - 1] > array[j]; j--)
-            swap(j, j - 1, array);
+         for (int j = i; j > from && array[j - 1] > array[j]; j--)
+           swap(j, j - 1, array);
         return;
       }
 
@@ -1454,6 +1461,8 @@
   {
     if (fromIndex > toIndex)
       throw new IllegalArgumentException();
+    if (fromIndex < 0)
+      throw new ArrayIndexOutOfBoundsException();
     qsort(a, fromIndex, toIndex - fromIndex);
   }
 
@@ -1526,7 +1535,7 @@
     if (count <= 7)
       {
         for (int i = from + 1; i < from + count; i++)
-          for (int j = i; j > 0 && array[j - 1] > array[j]; j--)
+          for (int j = i; j > from && array[j - 1] > array[j]; j--)
             swap(j, j - 1, array);
         return;
       }
@@ -1628,6 +1637,8 @@
   {
     if (fromIndex > toIndex)
       throw new IllegalArgumentException();
+    if (fromIndex < 0)
+      throw new ArrayIndexOutOfBoundsException();
     qsort(a, fromIndex, toIndex - fromIndex);
   }
 
@@ -1700,7 +1711,7 @@
     if (count <= 7)
       {
         for (int i = from + 1; i < from + count; i++)
-          for (int j = i; j > 0 && array[j - 1] > array[j]; j--)
+          for (int j = i; j > from && array[j - 1] > array[j]; j--)
             swap(j, j - 1, array);
         return;
       }
@@ -1802,6 +1813,8 @@
   {
     if (fromIndex > toIndex)
       throw new IllegalArgumentException();
+    if (fromIndex < 0)
+      throw new ArrayIndexOutOfBoundsException();
     qsort(a, fromIndex, toIndex - fromIndex);
   }
 
@@ -1865,7 +1878,7 @@
       {
         for (int i = from + 1; i < from + count; i++)
           for (int j = i;
-               j > 0 && Float.compare(array[j - 1], array[j]) > 0;
+               j > from && Float.compare(array[j - 1], array[j]) > 0;
                j--)
             {
               swap(j, j - 1, array);
@@ -1970,6 +1983,8 @@
   {
     if (fromIndex > toIndex)
       throw new IllegalArgumentException();
+    if (fromIndex < 0)
+      throw new ArrayIndexOutOfBoundsException();
     qsort(a, fromIndex, toIndex - fromIndex);
   }
 
@@ -2033,7 +2048,7 @@
       {
         for (int i = from + 1; i < from + count; i++)
           for (int j = i;
-               j > 0 && Double.compare(array[j - 1], array[j]) > 0;
+               j > from && Double.compare(array[j - 1], array[j]) > 0;
                j--)
             {
               swap(j, j - 1, array);
@@ -2203,6 +2218,8 @@
     if (fromIndex > toIndex)
       throw new IllegalArgumentException("fromIndex " + fromIndex
                                          + " > toIndex " + toIndex);
+    if (fromIndex < 0)
+      throw new ArrayIndexOutOfBoundsException();
 
     // In general, the code attempts to be simple rather than fast, the
     // idea being that a good optimising JIT will be able to optimise it

signature.asc
Description: This is a digitally signed message part