--- jsr166/src/extra166y/PAS.java	2009/07/22 20:55:22	1.4
+++ jsr166/src/extra166y/PAS.java	2010/10/16 16:40:44	1.11
@@ -26,7 +26,7 @@ class PAS {
     static ForkJoinPool defaultExecutor() {
         ForkJoinPool p = defaultExecutor; // double-check
         if (p == null) {
-            synchronized(poolLock) {
+            synchronized (poolLock) {
                 p = defaultExecutor;
                 if (p == null) {
                     // use ceil(7/8 * ncpus)
@@ -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 (;;) {
@@ -1657,7 +1657,7 @@ class PAS {
             this.gran = gran;
         }
 
-        public void compute()  {
+        public void compute() {
             int l = origin;
             int g = gran;
             if (n > g) {
@@ -1693,7 +1693,7 @@ class PAS {
             this.a = a; this.w = w; this.origin = origin; this.n = n;
             this.gran = gran;
         }
-        public void compute()  {
+        public void compute() {
             int l = origin;
             int g = gran;
             if (n > g) {
@@ -1730,7 +1730,7 @@ class PAS {
             this.a = a; this.w = w; this.origin = origin; this.n = n;
             this.gran = gran;
         }
-        public void compute()  {
+        public void compute() {
             int l = origin;
             int g = gran;
             if (n > g) {
@@ -1766,7 +1766,7 @@ class PAS {
             this.a = a; this.w = w; this.origin = origin; this.n = n;
             this.gran = gran;
         }
-        public void compute()  {
+        public void compute() {
             int l = origin;
             int g = gran;
             if (n > g) {
@@ -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);
         }
     }
 
@@ -1804,7 +1804,7 @@ class PAS {
             this.gran = gran;
         }
 
-        public void compute()  {
+        public void compute() {
             int l = origin;
             int g = gran;
             if (n > g) {
@@ -1840,7 +1840,7 @@ class PAS {
             this.a = a; this.w = w; this.origin = origin; this.n = n;
             this.gran = gran;
         }
-        public void compute()  {
+        public void compute() {
             int l = origin;
             int g = gran;
             if (n > g) {
@@ -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);
         }
     }
 
@@ -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,17 @@ 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,6 +2354,8 @@ class PAS {
                 else break;
             }
 
+            if (sameLefts && right == hi - 1)
+                return;
             if (left - lo <= hi - right) {
                 oquickSort(a, cmp, lo, left);
                 lo = left + 1;
@@ -2384,15 +2392,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 +2412,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 +2425,7 @@ class PAS {
         }
     }
 
+
     static void dquickSort(double[] a, DoubleComparator cmp, int lo, int hi) {
         for (;;) {
             if (hi - lo <= INSERTION_SORT_THRESHOLD) {
@@ -2440,11 +2455,17 @@ 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;
@@ -2452,6 +2473,8 @@ class PAS {
                 else break;
             }
 
+            if (sameLefts && right == hi - 1)
+                return;
             if (left - lo <= hi - right) {
                 dquickSort(a, cmp, lo, left);
                 lo = left + 1;
@@ -2463,58 +2486,6 @@ class PAS {
         }
     }
 
-    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;
-                }
-                else break;
-            }
-
-            if (left - lo <= hi - right) {
-                dcquickSort(a, lo, left);
-                lo = left + 1;
-            }
-            else {
-                dcquickSort(a, right, hi);
-                hi = left;
-            }
-        }
-    }
-
     static void lquickSort(long[] a, LongComparator cmp, int lo, int hi) {
         for (;;) {
             if (hi - lo <= INSERTION_SORT_THRESHOLD) {
@@ -2544,11 +2515,17 @@ 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;
@@ -2556,6 +2533,8 @@ class PAS {
                 else break;
             }
 
+            if (sameLefts && right == hi - 1)
+                return;
             if (left - lo <= hi - right) {
                 lquickSort(a, cmp, lo, left);
                 lo = left + 1;
@@ -2567,58 +2546,6 @@ class PAS {
         }
     }
 
-    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;
-                }
-                else break;
-            }
-
-            if (left - lo <= hi - right) {
-                lcquickSort(a, lo, left);
-                lo = left + 1;
-            }
-            else {
-                lcquickSort(a, right, hi);
-                hi = left;
-            }
-        }
-    }
-
     /**
      * Cumulative scan
      *
@@ -2821,7 +2748,7 @@ class PAS {
     }
 
     /**
-     * Computational operations for FJSCan
+     * Computational operations for FJScan
      */
     static abstract class FJScanOp {
         final int threshold;