--- jsr166/src/extra166y/PAS.java	2009/11/22 19:08:44	1.6
+++ jsr166/src/extra166y/PAS.java	2010/11/25 12:40:16	1.13
@@ -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)
@@ -1491,7 +1491,7 @@ class PAS {
                 if ((filtered && !pap.isSelected(k)) ||
                     (x = src[k]) == null)
                     continue;
-                int hc = byIdentity? System.identityHashCode(x): x.hashCode();
+                int hc = byIdentity ? System.identityHashCode(x) : x.hashCode();
                 int hash = hash(hc);
                 long entry = (((long)hash) << 32) + (k + 1);
                 int idx = hash & mask;
@@ -1657,7 +1657,7 @@ class PAS {
             this.gran = gran;
         }
 
-        public void compute()  {
+        public void compute() {
             int l = origin;
             int g = gran;
             if (n > g) {
@@ -1681,7 +1681,7 @@ class PAS {
                               l+h, n-h, l, g, null).compute();
             }
             else
-                oquickSort(a, cmp, l, l+n-1);
+                Arrays.sort(a, l, l+n, cmp);
         }
     }
 
@@ -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) {
@@ -1717,7 +1717,7 @@ class PAS {
                                l+h, n-h, l, g, null).compute();
             }
             else
-                ocquickSort(a, l, l+n-1);
+                Arrays.sort(a, l, l+n);
         }
     }
 
@@ -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,111 +2305,8 @@ 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
-
-    static void oquickSort(Object[] a, Comparator cmp, int lo, int hi) {
-        for (;;) {
-            if (hi - lo <= INSERTION_SORT_THRESHOLD) {
-                for (int i = lo + 1; i <= hi; i++) {
-                    Object t = a[i];
-                    int j = i - 1;
-                    while (j >= lo && cmp.compare(t, a[j]) < 0) {
-                        a[j+1] = a[j];
-                        --j;
-                    }
-                    a[j+1] = t;
-                }
-                return;
-            }
-
-            int mid = (lo + hi) >>> 1;
-            if (cmp.compare(a[lo], a[mid]) > 0) {
-                Object t = a[lo]; a[lo] = a[mid]; a[mid] = t;
-            }
-            if (cmp.compare(a[mid], a[hi]) > 0) {
-                Object t = a[mid]; a[mid] = a[hi]; a[hi] = t;
-                if (cmp.compare(a[lo], a[mid]) > 0) {
-                    Object u = a[lo]; a[lo] = a[mid]; a[mid] = u;
-                }
-            }
+    // versions of quicksort with comparators
 
-            Object pivot = a[mid];
-            int left = lo+1;
-            int right = hi-1;
-            for (;;) {
-                while (cmp.compare(pivot, a[right]) < 0)
-                    --right;
-                while (left < right && cmp.compare(pivot, a[left]) >= 0)
-                    ++left;
-                if (left < right) {
-                    Object t = a[left]; a[left] = a[right]; a[right] = t;
-                    --right;
-                }
-                else break;
-            }
-
-            if (left - lo <= hi - right) {
-                oquickSort(a, cmp, lo, left);
-                lo = left + 1;
-            }
-            else {
-                oquickSort(a, cmp, right, hi);
-                hi = left;
-            }
-        }
-    }
-
-    static void ocquickSort(Comparable[] a, int lo, int hi) {
-        for (;;) {
-            if (hi - lo <= INSERTION_SORT_THRESHOLD) {
-                for (int i = lo + 1; i <= hi; i++) {
-                    Comparable t = a[i];
-                    int j = i - 1;
-                    while (j >= lo && t.compareTo(a[j]) < 0) {
-                        a[j+1] = a[j];
-                        --j;
-                    }
-                    a[j+1] = t;
-                }
-                return;
-            }
-
-            int mid = (lo + hi) >>> 1;
-            if (a[lo].compareTo(a[mid]) > 0) {
-                Comparable t = a[lo]; a[lo] = a[mid]; a[mid] = t;
-            }
-            if (a[mid].compareTo(a[hi]) > 0) {
-                Comparable t = a[mid]; a[mid] = a[hi]; a[hi] = t;
-                if (a[lo].compareTo(a[mid]) > 0) {
-                    Comparable u = a[lo]; a[lo] = a[mid]; a[mid] = u;
-                }
-            }
-
-            Comparable pivot = a[mid];
-            int left = lo+1;
-            int right = hi-1;
-            for (;;) {
-                while (pivot.compareTo(a[right]) < 0)
-                    --right;
-                while (left < right && pivot.compareTo(a[left]) >= 0)
-                    ++left;
-                if (left < right) {
-                    Comparable t = a[left]; a[left] = a[right]; a[right] = t;
-                    --right;
-                }
-                else break;
-            }
-
-            if (left - lo <= hi - right) {
-                ocquickSort(a, lo, left);
-                lo = left + 1;
-            }
-            else {
-                ocquickSort(a, right, hi);
-                hi = left;
-            }
-        }
-    }
 
     static void dquickSort(double[] a, DoubleComparator cmp, int lo, int hi) {
         for (;;) {
@@ -2440,11 +2337,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 +2355,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 +2368,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 +2397,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 +2415,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 +2428,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
      *
@@ -2746,7 +2555,7 @@ class PAS {
                         op.pushUp(par, par.left, par.right);
                         int refork =
                             ((pb & CUMULATE) == 0 &&
-                             par.lo == op.origin)? CUMULATE : 0;
+                             par.lo == op.origin) ? CUMULATE : 0;
                         int nextPhase = pb|cb|refork;
                         if (pb == nextPhase ||
                             phaseUpdater.compareAndSet(par, pb, nextPhase)) {