--- jsr166/src/extra166y/PAS.java 2009/01/12 17:16:36 1.2 +++ jsr166/src/extra166y/PAS.java 2010/09/01 06:41:54 1.9 @@ -1524,7 +1524,7 @@ class PAS { continue; double x = src[k]; long bits = Double.doubleToLongBits(x); - int hash = hash((int)(bits ^ (bits >>> 32)));; + int hash = hash((int)(bits ^ (bits >>> 32))); long entry = (((long)hash) << 32) + (k + 1); int idx = hash & mask; for (;;) { @@ -1790,7 +1790,7 @@ class PAS { l+h, n-h, l, g, null).compute(); } else - dcquickSort(a, l, l+n-1); + Arrays.sort(a, l, l+n); } } @@ -1865,7 +1865,7 @@ class PAS { l+h, n-h, l, g, null).compute(); } else - lcquickSort(a, l, l+n-1); + Arrays.sort(a, l, l+n); } } @@ -1875,7 +1875,7 @@ class PAS { final RecursiveAction right; final RecursiveAction merger; FJSubSorter(RecursiveAction left, RecursiveAction right, - RecursiveAction merger){ + RecursiveAction merger) { this.left = left; this.right = right; this.merger = merger; } public void compute() { @@ -2305,7 +2305,7 @@ class PAS { /** Cutoff for when to use insertion-sort instead of quicksort */ static final int INSERTION_SORT_THRESHOLD = 8; - // Six nearly identical versions of quicksort + // versions of quicksort with comparators static void oquickSort(Object[] a, Comparator cmp, int lo, int hi) { for (;;) { @@ -2336,11 +2336,16 @@ class PAS { Object pivot = a[mid]; int left = lo+1; int right = hi-1; + boolean sameLefts = true; for (;;) { while (cmp.compare(pivot, a[right]) < 0) --right; - while (left < right && cmp.compare(pivot, a[left]) >= 0) + int c; + while (left < right && (c = cmp.compare(pivot, a[left])) >= 0){ + if (c != 0) + sameLefts = false; ++left; + } if (left < right) { Object t = a[left]; a[left] = a[right]; a[right] = t; --right; @@ -2348,10 +2353,12 @@ class PAS { else break; } + if (sameLefts && right == hi - 1) + return; if (left - lo <= hi - right) { oquickSort(a, cmp, lo, left); lo = left + 1; - } + } else { oquickSort(a, cmp, right, hi); hi = left; @@ -2384,15 +2391,19 @@ class PAS { Comparable u = a[lo]; a[lo] = a[mid]; a[mid] = u; } } - Comparable pivot = a[mid]; int left = lo+1; int right = hi-1; + boolean sameLefts = true; for (;;) { while (pivot.compareTo(a[right]) < 0) --right; - while (left < right && pivot.compareTo(a[left]) >= 0) + int c; + while (left < right && (c = pivot.compareTo(a[left])) >= 0) { + if (c != 0) + sameLefts = false; ++left; + } if (left < right) { Comparable t = a[left]; a[left] = a[right]; a[right] = t; --right; @@ -2400,6 +2411,8 @@ class PAS { else break; } + if (sameLefts && right == hi - 1) + return; if (left - lo <= hi - right) { ocquickSort(a, lo, left); lo = left + 1; @@ -2411,6 +2424,7 @@ class PAS { } } + static void dquickSort(double[] a, DoubleComparator cmp, int lo, int hi) { for (;;) { if (hi - lo <= INSERTION_SORT_THRESHOLD) { @@ -2440,63 +2454,16 @@ class PAS { double pivot = a[mid]; int left = lo+1; int right = hi-1; + boolean sameLefts = true; for (;;) { while (cmp.compare(pivot, a[right]) < 0) --right; - while (left < right && cmp.compare(pivot, a[left]) >= 0) + int c; + while (left < right && (c = cmp.compare(pivot, a[left])) >= 0){ + if (c != 0) + sameLefts = false; ++left; - if (left < right) { - double t = a[left]; a[left] = a[right]; a[right] = t; - --right; - } - else break; - } - - if (left - lo <= hi - right) { - dquickSort(a, cmp, lo, left); - lo = left + 1; - } - else { - dquickSort(a, cmp, right, hi); - hi = left; - } - } - } - - static void dcquickSort(double[] a, int lo, int hi) { - for (;;) { - if (hi - lo <= INSERTION_SORT_THRESHOLD) { - for (int i = lo + 1; i <= hi; i++) { - double t = a[i]; - int j = i - 1; - while (j >= lo && t < a[j]) { - a[j+1] = a[j]; - --j; - } - a[j+1] = t; } - return; - } - - int mid = (lo + hi) >>> 1; - if (a[lo] > a[mid]) { - double t = a[lo]; a[lo] = a[mid]; a[mid] = t; - } - if (a[mid] > a[hi]) { - double t = a[mid]; a[mid] = a[hi]; a[hi] = t; - if (a[lo] > a[mid]) { - double u = a[lo]; a[lo] = a[mid]; a[mid] = u; - } - } - - double pivot = a[mid]; - int left = lo+1; - int right = hi-1; - for (;;) { - while (pivot < a[right]) - --right; - while (left < right && pivot >= a[left]) - ++left; if (left < right) { double t = a[left]; a[left] = a[right]; a[right] = t; --right; @@ -2504,12 +2471,14 @@ class PAS { else break; } + if (sameLefts && right == hi - 1) + return; if (left - lo <= hi - right) { - dcquickSort(a, lo, left); + dquickSort(a, cmp, lo, left); lo = left + 1; } else { - dcquickSort(a, right, hi); + dquickSort(a, cmp, right, hi); hi = left; } } @@ -2544,63 +2513,16 @@ class PAS { long pivot = a[mid]; int left = lo+1; int right = hi-1; + boolean sameLefts = true; for (;;) { while (cmp.compare(pivot, a[right]) < 0) --right; - while (left < right && cmp.compare(pivot, a[left]) >= 0) + int c; + while (left < right && (c = cmp.compare(pivot, a[left])) >= 0){ + if (c != 0) + sameLefts = false; ++left; - if (left < right) { - long t = a[left]; a[left] = a[right]; a[right] = t; - --right; } - else break; - } - - if (left - lo <= hi - right) { - lquickSort(a, cmp, lo, left); - lo = left + 1; - } - else { - lquickSort(a, cmp, right, hi); - hi = left; - } - } - } - - static void lcquickSort(long[] a, int lo, int hi) { - for (;;) { - if (hi - lo <= INSERTION_SORT_THRESHOLD) { - for (int i = lo + 1; i <= hi; i++) { - long t = a[i]; - int j = i - 1; - while (j >= lo && t < a[j]) { - a[j+1] = a[j]; - --j; - } - a[j+1] = t; - } - return; - } - - int mid = (lo + hi) >>> 1; - if (a[lo] > a[mid]) { - long t = a[lo]; a[lo] = a[mid]; a[mid] = t; - } - if (a[mid] > a[hi]) { - long t = a[mid]; a[mid] = a[hi]; a[hi] = t; - if (a[lo] > a[mid]) { - long u = a[lo]; a[lo] = a[mid]; a[mid] = u; - } - } - - long pivot = a[mid]; - int left = lo+1; - int right = hi-1; - for (;;) { - while (pivot < a[right]) - --right; - while (left < right && pivot >= a[left]) - ++left; if (left < right) { long t = a[left]; a[left] = a[right]; a[right] = t; --right; @@ -2608,12 +2530,14 @@ class PAS { else break; } + if (sameLefts && right == hi - 1) + return; if (left - lo <= hi - right) { - lcquickSort(a, lo, left); + lquickSort(a, cmp, lo, left); lo = left + 1; } else { - lcquickSort(a, right, hi); + lquickSort(a, cmp, right, hi); hi = left; } } @@ -2709,7 +2633,7 @@ class PAS { int cb; for (;;) { // Establish action: sum, cumulate, or both int b = phase; - if ((b & FINISHED) != 0) // already done + if ((b & FINISHED) != 0) // already done return false; if ((b & CUMULATE) != 0) cb = FINISHED; @@ -2821,7 +2745,7 @@ class PAS { } /** - * Computational operations for FJSCan + * Computational operations for FJScan */ static abstract class FJScanOp { final int threshold;