This is the mail archive of the
java-patches@gcc.gnu.org
mailing list for the Java project.
Fix for PR java/1895
- To: java-patches at sources dot redhat dot com
- Subject: Fix for PR java/1895
- From: Bryce McKinlay <bryce at albatross dot co dot nz>
- Date: Wed, 07 Feb 2001 22:37:29 +1300
I'm checking in this patch, which fixes the broken qsort
implementation in java.util.Arrays (along with a few cleanups).
regards
[ bryce ]
2001-02-07 Bryce McKinlay <bryce@albatross.co.nz>
* java/util/Arrays.java: Removed "cmp" methods.
(qsort): Don't use "cmp".
(med3): Likewise.
2001-02-07 Mark Benvenuto <mcb54@columbia.edu>
* java/util/Arrays.java (qsort): Handle N value of 7 with insertion
sort. Fix for PR java/1895.
Index: Arrays.java
===================================================================
RCS file: /cvs/gcc/egcs/libjava/java/util/Arrays.java,v
retrieving revision 1.2
diff -u -r1.2 Arrays.java
--- Arrays.java 2000/11/17 04:51:23 1.2
+++ Arrays.java 2001/02/07 09:28:17
@@ -1079,16 +1079,11 @@
qsort(a, fromIndex, toIndex);
}
- private static short cmp(byte i, byte j)
- {
- return (short) (i - j);
- }
-
private static int med3(int a, int b, int c, byte[]d)
{
- return cmp(d[a], d[b]) < 0 ?
- (cmp(d[b], d[c]) < 0 ? b : cmp(d[a], d[c]) < 0 ? c : a)
- : (cmp(d[b], d[c]) > 0 ? b : cmp(d[a], d[c]) > 0 ? c : a);
+ return d[a] < d[b] ?
+ (d[b] < d[c] ? b : d[a] < d[c] ? c : a)
+ : (d[b] > d[c] ? b : d[a] > d[c] ? c : a);
}
private static void swap(int i, int j, byte[]a)
@@ -1101,10 +1096,10 @@
private static void qsort(byte[]a, int start, int n)
{
// use an insertion sort on small arrays
- if (n < 7)
+ if (n <= 7)
{
for (int i = start + 1; i < start + n; i++)
- for (int j = i; j > 0 && cmp(a[j - 1], a[j]) > 0; j--)
+ for (int j = i; j > 0 && a[j - 1] > a[j]; j--)
swap(j, j - 1, a);
return;
}
@@ -1126,7 +1121,7 @@
}
int pa, pb, pc, pd, pv;
- short r;
+ int r;
pv = start;
swap(pv, pm, a);
@@ -1135,7 +1130,7 @@
for (;;)
{
- while (pb <= pc && (r = cmp(a[pb], a[pv])) <= 0)
+ while (pb <= pc && (r = a[pb] - a[pv]) <= 0)
{
if (r == 0)
{
@@ -1144,7 +1139,7 @@
}
pb++;
}
- while (pc >= pb && (r = cmp(a[pc], a[pv])) >= 0)
+ while (pc >= pb && (r = a[pc] - a[pv]) >= 0)
{
if (r == 0)
{
@@ -1197,16 +1192,11 @@
qsort(a, fromIndex, toIndex);
}
- private static int cmp(char i, char j)
- {
- return i - j;
- }
-
private static int med3(int a, int b, int c, char[]d)
{
- return cmp(d[a], d[b]) < 0 ?
- (cmp(d[b], d[c]) < 0 ? b : cmp(d[a], d[c]) < 0 ? c : a)
- : (cmp(d[b], d[c]) > 0 ? b : cmp(d[a], d[c]) > 0 ? c : a);
+ return d[a] < d[b] ?
+ (d[b] < d[c] ? b : d[a] < d[c] ? c : a)
+ : (d[b] > d[c] ? b : d[a] > d[c] ? c : a);
}
private static void swap(int i, int j, char[]a)
@@ -1219,10 +1209,10 @@
private static void qsort(char[]a, int start, int n)
{
// use an insertion sort on small arrays
- if (n < 7)
+ if (n <= 7)
{
for (int i = start + 1; i < start + n; i++)
- for (int j = i; j > 0 && cmp(a[j - 1], a[j]) > 0; j--)
+ for (int j = i; j > 0 && a[j - 1] > a[j]; j--)
swap(j, j - 1, a);
return;
}
@@ -1253,7 +1243,7 @@
for (;;)
{
- while (pb <= pc && (r = cmp(a[pb], a[pv])) <= 0)
+ while (pb <= pc && (r = a[pb] - a[pv]) <= 0)
{
if (r == 0)
{
@@ -1262,7 +1252,7 @@
}
pb++;
}
- while (pc >= pb && (r = cmp(a[pc], a[pv])) >= 0)
+ while (pc >= pb && (r = a[pc] - a[pv]) >= 0)
{
if (r == 0)
{
@@ -1316,16 +1306,11 @@
qsort(a, fromIndex, toIndex);
}
- private static double cmp(double i, double j)
- {
- return i - j;
- }
-
private static int med3(int a, int b, int c, double[]d)
{
- return cmp(d[a], d[b]) < 0 ?
- (cmp(d[b], d[c]) < 0 ? b : cmp(d[a], d[c]) < 0 ? c : a)
- : (cmp(d[b], d[c]) > 0 ? b : cmp(d[a], d[c]) > 0 ? c : a);
+ return d[a] < d[b] ?
+ (d[b] < d[c] ? b : d[a] < d[c] ? c : a)
+ : (d[b] > d[c] ? b : d[a] > d[c] ? c : a);
}
private static void swap(int i, int j, double[]a)
@@ -1338,10 +1323,10 @@
private static void qsort(double[]a, int start, int n)
{
// use an insertion sort on small arrays
- if (n < 7)
+ if (n <= 7)
{
for (int i = start + 1; i < start + n; i++)
- for (int j = i; j > 0 && cmp(a[j - 1], a[j]) > 0; j--)
+ for (int j = i; j > 0 && a[j - 1] > a[j]; j--)
swap(j, j - 1, a);
return;
}
@@ -1372,7 +1357,7 @@
for (;;)
{
- while (pb <= pc && (r = cmp(a[pb], a[pv])) <= 0)
+ while (pb <= pc && (r = a[pb] - a[pv]) <= 0)
{
if (r == 0)
{
@@ -1381,7 +1366,7 @@
}
pb++;
}
- while (pc >= pb && (r = cmp(a[pc], a[pv])) >= 0)
+ while (pc >= pb && (r = a[pc] - a[pv]) >= 0)
{
if (r == 0)
{
@@ -1435,16 +1420,11 @@
qsort(a, fromIndex, toIndex);
}
- private static float cmp(float i, float j)
- {
- return i - j;
- }
-
private static int med3(int a, int b, int c, float[]d)
{
- return cmp(d[a], d[b]) < 0 ?
- (cmp(d[b], d[c]) < 0 ? b : cmp(d[a], d[c]) < 0 ? c : a)
- : (cmp(d[b], d[c]) > 0 ? b : cmp(d[a], d[c]) > 0 ? c : a);
+ return d[a] < d[b] ?
+ (d[b] < d[c] ? b : d[a] < d[c] ? c : a)
+ : (d[b] > d[c] ? b : d[a] > d[c] ? c : a);
}
private static void swap(int i, int j, float[]a)
@@ -1457,10 +1437,10 @@
private static void qsort(float[]a, int start, int n)
{
// use an insertion sort on small arrays
- if (n < 7)
+ if (n <= 7)
{
for (int i = start + 1; i < start + n; i++)
- for (int j = i; j > 0 && cmp(a[j - 1], a[j]) > 0; j--)
+ for (int j = i; j > 0 && a[j - 1] > a[j]; j--)
swap(j, j - 1, a);
return;
}
@@ -1491,7 +1471,7 @@
for (;;)
{
- while (pb <= pc && (r = cmp(a[pb], a[pv])) <= 0)
+ while (pb <= pc && (r = a[pb] - a[pv]) <= 0)
{
if (r == 0)
{
@@ -1500,7 +1480,7 @@
}
pb++;
}
- while (pc >= pb && (r = cmp(a[pc], a[pv])) >= 0)
+ while (pc >= pb && (r = a[pc] - a[pv]) >= 0)
{
if (r == 0)
{
@@ -1553,16 +1533,11 @@
qsort(a, fromIndex, toIndex);
}
- private static long cmp(int i, int j)
- {
- return (long) i - (long) j;
- }
-
private static int med3(int a, int b, int c, int[]d)
{
- return cmp(d[a], d[b]) < 0 ?
- (cmp(d[b], d[c]) < 0 ? b : cmp(d[a], d[c]) < 0 ? c : a)
- : (cmp(d[b], d[c]) > 0 ? b : cmp(d[a], d[c]) > 0 ? c : a);
+ return d[a] < d[b] ?
+ (d[b] < d[c] ? b : d[a] < d[c] ? c : a)
+ : (d[b] > d[c] ? b : d[a] > d[c] ? c : a);
}
private static void swap(int i, int j, int[]a)
@@ -1575,10 +1550,10 @@
private static void qsort(int[]a, int start, int n)
{
// use an insertion sort on small arrays
- if (n < 7)
+ if (n <= 7)
{
for (int i = start + 1; i < start + n; i++)
- for (int j = i; j > 0 && cmp(a[j - 1], a[j]) > 0; j--)
+ for (int j = i; j > 0 && a[j - 1] > a[j]; j--)
swap(j, j - 1, a);
return;
}
@@ -1600,7 +1575,7 @@
}
int pa, pb, pc, pd, pv;
- long r;
+ int r;
pv = start;
swap(pv, pm, a);
@@ -1609,7 +1584,7 @@
for (;;)
{
- while (pb <= pc && (r = cmp(a[pb], a[pv])) <= 0)
+ while (pb <= pc && (r = a[pb] - a[pv]) <= 0)
{
if (r == 0)
{
@@ -1618,7 +1593,7 @@
}
pb++;
}
- while (pc >= pb && (r = cmp(a[pc], a[pv])) >= 0)
+ while (pc >= pb && (r = a[pc] - a[pv]) >= 0)
{
if (r == 0)
{
@@ -1671,16 +1646,11 @@
qsort(a, fromIndex, toIndex);
}
- // The "cmp" method has been removed from here and replaced with direct
- // compares in situ, to avoid problems with overflow if the difference
- // between two numbers is bigger than a long will hold.
- // One particular change as a result is the use of r1 and r2 in qsort
-
private static int med3(int a, int b, int c, long[]d)
{
- return d[a] < d[b] ?
- (d[b] < d[c] ? b : d[a] < d[c] ? c : a)
- : (d[b] > d[c] ? b : d[a] > d[c] ? c : a);
+ return d[a] < d[b] ?
+ (d[b] < d[c] ? b : d[a] < d[c] ? c : a)
+ : (d[b] > d[c] ? b : d[a] > d[c] ? c : a);
}
private static void swap(int i, int j, long[]a)
@@ -1693,7 +1663,7 @@
private static void qsort(long[]a, int start, int n)
{
// use an insertion sort on small arrays
- if (n < 7)
+ if (n <= 7)
{
for (int i = start + 1; i < start + n; i++)
for (int j = i; j > 0 && a[j - 1] > a[j]; j--)
@@ -1718,7 +1688,7 @@
}
int pa, pb, pc, pd, pv;
- long r1, r2;
+ long r;
pv = start;
swap(pv, pm, a);
@@ -1727,18 +1697,18 @@
for (;;)
{
- while (pb <= pc && (r1 = a[pb]) <= (r2 = a[pv]))
+ while (pb <= pc && (r = a[pb] - a[pv]) <= 0)
{
- if (r1 == r2)
+ if (r == 0)
{
swap(pa, pb, a);
pa++;
}
pb++;
}
- while (pc >= pb && (r1 = a[pc]) >= (r2 = a[pv]))
+ while (pc >= pb && (r = a[pc] - a[pv]) >= 0)
{
- if (r1 == r2)
+ if (r == 0)
{
swap(pc, pd, a);
pd--;
@@ -1789,16 +1759,11 @@
qsort(a, fromIndex, toIndex);
}
- private static int cmp(short i, short j)
- {
- return i - j;
- }
-
private static int med3(int a, int b, int c, short[]d)
{
- return cmp(d[a], d[b]) < 0 ?
- (cmp(d[b], d[c]) < 0 ? b : cmp(d[a], d[c]) < 0 ? c : a)
- : (cmp(d[b], d[c]) > 0 ? b : cmp(d[a], d[c]) > 0 ? c : a);
+ return d[a] < d[b] ?
+ (d[b] < d[c] ? b : d[a] < d[c] ? c : a)
+ : (d[b] > d[c] ? b : d[a] > d[c] ? c : a);
}
private static void swap(int i, int j, short[]a)
@@ -1811,10 +1776,10 @@
private static void qsort(short[]a, int start, int n)
{
// use an insertion sort on small arrays
- if (n < 7)
+ if (n <= 7)
{
for (int i = start + 1; i < start + n; i++)
- for (int j = i; j > 0 && cmp(a[j - 1], a[j]) > 0; j--)
+ for (int j = i; j > 0 && a[j - 1] > a[j]; j--)
swap(j, j - 1, a);
return;
}
@@ -1845,7 +1810,7 @@
for (;;)
{
- while (pb <= pc && (r = cmp(a[pb], a[pv])) <= 0)
+ while (pb <= pc && (r = a[pb] - a[pv]) <= 0)
{
if (r == 0)
{
@@ -1854,7 +1819,7 @@
}
pb++;
}
- while (pc >= pb && (r = cmp(a[pc], a[pv])) >= 0)
+ while (pc >= pb && (r = a[pc] - a[pv]) >= 0)
{
if (r == 0)
{