1491 |
|
if ((filtered && !pap.isSelected(k)) || |
1492 |
|
(x = src[k]) == null) |
1493 |
|
continue; |
1494 |
< |
int hc = byIdentity? System.identityHashCode(x): x.hashCode(); |
1494 |
> |
int hc = byIdentity ? System.identityHashCode(x) : x.hashCode(); |
1495 |
|
int hash = hash(hc); |
1496 |
|
long entry = (((long)hash) << 32) + (k + 1); |
1497 |
|
int idx = hash & mask; |
1657 |
|
this.gran = gran; |
1658 |
|
} |
1659 |
|
|
1660 |
< |
public void compute() { |
1660 |
> |
public void compute() { |
1661 |
|
int l = origin; |
1662 |
|
int g = gran; |
1663 |
|
if (n > g) { |
1681 |
|
l+h, n-h, l, g, null).compute(); |
1682 |
|
} |
1683 |
|
else |
1684 |
< |
oquickSort(a, cmp, l, l+n-1); |
1684 |
> |
Arrays.sort(a, l, l+n, cmp); |
1685 |
|
} |
1686 |
|
} |
1687 |
|
|
1693 |
|
this.a = a; this.w = w; this.origin = origin; this.n = n; |
1694 |
|
this.gran = gran; |
1695 |
|
} |
1696 |
< |
public void compute() { |
1696 |
> |
public void compute() { |
1697 |
|
int l = origin; |
1698 |
|
int g = gran; |
1699 |
|
if (n > g) { |
1717 |
|
l+h, n-h, l, g, null).compute(); |
1718 |
|
} |
1719 |
|
else |
1720 |
< |
ocquickSort(a, l, l+n-1); |
1720 |
> |
Arrays.sort(a, l, l+n); |
1721 |
|
} |
1722 |
|
} |
1723 |
|
|
1730 |
|
this.a = a; this.w = w; this.origin = origin; this.n = n; |
1731 |
|
this.gran = gran; |
1732 |
|
} |
1733 |
< |
public void compute() { |
1733 |
> |
public void compute() { |
1734 |
|
int l = origin; |
1735 |
|
int g = gran; |
1736 |
|
if (n > g) { |
1766 |
|
this.a = a; this.w = w; this.origin = origin; this.n = n; |
1767 |
|
this.gran = gran; |
1768 |
|
} |
1769 |
< |
public void compute() { |
1769 |
> |
public void compute() { |
1770 |
|
int l = origin; |
1771 |
|
int g = gran; |
1772 |
|
if (n > g) { |
1804 |
|
this.gran = gran; |
1805 |
|
} |
1806 |
|
|
1807 |
< |
public void compute() { |
1807 |
> |
public void compute() { |
1808 |
|
int l = origin; |
1809 |
|
int g = gran; |
1810 |
|
if (n > g) { |
1840 |
|
this.a = a; this.w = w; this.origin = origin; this.n = n; |
1841 |
|
this.gran = gran; |
1842 |
|
} |
1843 |
< |
public void compute() { |
1843 |
> |
public void compute() { |
1844 |
|
int l = origin; |
1845 |
|
int g = gran; |
1846 |
|
if (n > g) { |
2307 |
|
|
2308 |
|
// versions of quicksort with comparators |
2309 |
|
|
2310 |
– |
static void oquickSort(Object[] a, Comparator cmp, int lo, int hi) { |
2311 |
– |
for (;;) { |
2312 |
– |
if (hi - lo <= INSERTION_SORT_THRESHOLD) { |
2313 |
– |
for (int i = lo + 1; i <= hi; i++) { |
2314 |
– |
Object t = a[i]; |
2315 |
– |
int j = i - 1; |
2316 |
– |
while (j >= lo && cmp.compare(t, a[j]) < 0) { |
2317 |
– |
a[j+1] = a[j]; |
2318 |
– |
--j; |
2319 |
– |
} |
2320 |
– |
a[j+1] = t; |
2321 |
– |
} |
2322 |
– |
return; |
2323 |
– |
} |
2324 |
– |
|
2325 |
– |
int mid = (lo + hi) >>> 1; |
2326 |
– |
if (cmp.compare(a[lo], a[mid]) > 0) { |
2327 |
– |
Object t = a[lo]; a[lo] = a[mid]; a[mid] = t; |
2328 |
– |
} |
2329 |
– |
if (cmp.compare(a[mid], a[hi]) > 0) { |
2330 |
– |
Object t = a[mid]; a[mid] = a[hi]; a[hi] = t; |
2331 |
– |
if (cmp.compare(a[lo], a[mid]) > 0) { |
2332 |
– |
Object u = a[lo]; a[lo] = a[mid]; a[mid] = u; |
2333 |
– |
} |
2334 |
– |
} |
2335 |
– |
|
2336 |
– |
Object pivot = a[mid]; |
2337 |
– |
int left = lo+1; |
2338 |
– |
int right = hi-1; |
2339 |
– |
boolean sameLefts = true; |
2340 |
– |
for (;;) { |
2341 |
– |
while (cmp.compare(pivot, a[right]) < 0) |
2342 |
– |
--right; |
2343 |
– |
int c; |
2344 |
– |
while (left < right && (c = cmp.compare(pivot, a[left])) >= 0){ |
2345 |
– |
if (c != 0) |
2346 |
– |
sameLefts = false; |
2347 |
– |
++left; |
2348 |
– |
} |
2349 |
– |
if (left < right) { |
2350 |
– |
Object t = a[left]; a[left] = a[right]; a[right] = t; |
2351 |
– |
--right; |
2352 |
– |
} |
2353 |
– |
else break; |
2354 |
– |
} |
2355 |
– |
|
2356 |
– |
if (sameLefts && right == hi - 1) |
2357 |
– |
return; |
2358 |
– |
if (left - lo <= hi - right) { |
2359 |
– |
oquickSort(a, cmp, lo, left); |
2360 |
– |
lo = left + 1; |
2361 |
– |
} |
2362 |
– |
else { |
2363 |
– |
oquickSort(a, cmp, right, hi); |
2364 |
– |
hi = left; |
2365 |
– |
} |
2366 |
– |
} |
2367 |
– |
} |
2368 |
– |
|
2369 |
– |
static void ocquickSort(Comparable[] a, int lo, int hi) { |
2370 |
– |
for (;;) { |
2371 |
– |
if (hi - lo <= INSERTION_SORT_THRESHOLD) { |
2372 |
– |
for (int i = lo + 1; i <= hi; i++) { |
2373 |
– |
Comparable t = a[i]; |
2374 |
– |
int j = i - 1; |
2375 |
– |
while (j >= lo && t.compareTo(a[j]) < 0) { |
2376 |
– |
a[j+1] = a[j]; |
2377 |
– |
--j; |
2378 |
– |
} |
2379 |
– |
a[j+1] = t; |
2380 |
– |
} |
2381 |
– |
return; |
2382 |
– |
} |
2383 |
– |
|
2384 |
– |
int mid = (lo + hi) >>> 1; |
2385 |
– |
if (a[lo].compareTo(a[mid]) > 0) { |
2386 |
– |
Comparable t = a[lo]; a[lo] = a[mid]; a[mid] = t; |
2387 |
– |
} |
2388 |
– |
if (a[mid].compareTo(a[hi]) > 0) { |
2389 |
– |
Comparable t = a[mid]; a[mid] = a[hi]; a[hi] = t; |
2390 |
– |
if (a[lo].compareTo(a[mid]) > 0) { |
2391 |
– |
Comparable u = a[lo]; a[lo] = a[mid]; a[mid] = u; |
2392 |
– |
} |
2393 |
– |
} |
2394 |
– |
Comparable pivot = a[mid]; |
2395 |
– |
int left = lo+1; |
2396 |
– |
int right = hi-1; |
2397 |
– |
boolean sameLefts = true; |
2398 |
– |
for (;;) { |
2399 |
– |
while (pivot.compareTo(a[right]) < 0) |
2400 |
– |
--right; |
2401 |
– |
int c; |
2402 |
– |
while (left < right && (c = pivot.compareTo(a[left])) >= 0) { |
2403 |
– |
if (c != 0) |
2404 |
– |
sameLefts = false; |
2405 |
– |
++left; |
2406 |
– |
} |
2407 |
– |
if (left < right) { |
2408 |
– |
Comparable t = a[left]; a[left] = a[right]; a[right] = t; |
2409 |
– |
--right; |
2410 |
– |
} |
2411 |
– |
else break; |
2412 |
– |
} |
2413 |
– |
|
2414 |
– |
if (sameLefts && right == hi - 1) |
2415 |
– |
return; |
2416 |
– |
if (left - lo <= hi - right) { |
2417 |
– |
ocquickSort(a, lo, left); |
2418 |
– |
lo = left + 1; |
2419 |
– |
} |
2420 |
– |
else { |
2421 |
– |
ocquickSort(a, right, hi); |
2422 |
– |
hi = left; |
2423 |
– |
} |
2424 |
– |
} |
2425 |
– |
} |
2426 |
– |
|
2310 |
|
|
2311 |
|
static void dquickSort(double[] a, DoubleComparator cmp, int lo, int hi) { |
2312 |
|
for (;;) { |
2342 |
|
while (cmp.compare(pivot, a[right]) < 0) |
2343 |
|
--right; |
2344 |
|
int c; |
2345 |
< |
while (left < right && (c = cmp.compare(pivot, a[left])) >= 0){ |
2345 |
> |
while (left < right && |
2346 |
> |
(c = cmp.compare(pivot, a[left])) >= 0) { |
2347 |
|
if (c != 0) |
2348 |
|
sameLefts = false; |
2349 |
|
++left; |
2402 |
|
while (cmp.compare(pivot, a[right]) < 0) |
2403 |
|
--right; |
2404 |
|
int c; |
2405 |
< |
while (left < right && (c = cmp.compare(pivot, a[left])) >= 0){ |
2405 |
> |
while (left < right && |
2406 |
> |
(c = cmp.compare(pivot, a[left])) >= 0) { |
2407 |
|
if (c != 0) |
2408 |
|
sameLefts = false; |
2409 |
|
++left; |
2555 |
|
op.pushUp(par, par.left, par.right); |
2556 |
|
int refork = |
2557 |
|
((pb & CUMULATE) == 0 && |
2558 |
< |
par.lo == op.origin)? CUMULATE : 0; |
2558 |
> |
par.lo == op.origin) ? CUMULATE : 0; |
2559 |
|
int nextPhase = pb|cb|refork; |
2560 |
|
if (pb == nextPhase || |
2561 |
|
phaseUpdater.compareAndSet(par, pb, nextPhase)) { |