ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/jsr166/jsr166/src/extra166y/PAS.java

Comparing jsr166/src/extra166y/PAS.java (file contents):
Revision 1.7 by dl, Tue May 25 13:39:40 2010 UTC vs.
Revision 1.11 by jsr166, Sat Oct 16 16:40:44 2010 UTC

#	Line 26 | Line 26 | class PAS {
26		static ForkJoinPool defaultExecutor() {
27		ForkJoinPool p = defaultExecutor; // double-check
28		if (p == null) {
29	<	synchronized(poolLock) {
29	>	synchronized (poolLock) {
30		p = defaultExecutor;
31		if (p == null) {
32		// use ceil(7/8 * ncpus)
#	Line 1657 | Line 1657 | class PAS {
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) {
#	Line 1681 | Line 1681 | class PAS {
1681		l+h, n-h, l, g, null).compute();
1682		}
1683		else
1684	<	Arrays.sort(a, l, l+n, cmp);
1684	>	oquickSort(a, cmp, l, l+n-1);
1685		}
1686		}
1687
#	Line 1693 | Line 1693 | class PAS {
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) {
#	Line 1717 | Line 1717 | class PAS {
1717		l+h, n-h, l, g, null).compute();
1718		}
1719		else
1720	<	Arrays.sort(a, l, l+n);
1720	>	ocquickSort(a, l, l+n-1);
1721		}
1722		}
1723
#	Line 1730 | Line 1730 | class PAS {
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) {
#	Line 1754 | Line 1754 | class PAS {
1754		l+h, n-h, l, g, null).compute();
1755		}
1756		else
1757	<	Arrays.sort(a, l, l+n, cmp);
1757	>	dquickSort(a, cmp, l, l+n-1);
1758		}
1759		}
1760
#	Line 1766 | Line 1766 | class PAS {
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) {
#	Line 1804 | Line 1804 | class PAS {
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) {
#	Line 1828 | Line 1828 | class PAS {
1828		l+h, n-h, l, g, null).compute();
1829		}
1830		else
1831	<	Arrays.sort(a, l, l+n, cmp);
1831	>	lquickSort(a, cmp, l, l+n-1);
1832		}
1833		}
1834
#	Line 1840 | Line 1840 | class PAS {
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) {
#	Line 2301 | Line 2301 | class PAS {
2301		}
2302		}
2303		}
2304	+
2305	+	/** Cutoff for when to use insertion-sort instead of quicksort */
2306	+	static final int INSERTION_SORT_THRESHOLD = 8;
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 &&
2345	+	(c = cmp.compare(pivot, a[left])) >= 0) {
2346	+	if (c != 0)
2347	+	sameLefts = false;
2348	+	++left;
2349	+	}
2350	+	if (left < right) {
2351	+	Object t = a[left]; a[left] = a[right]; a[right] = t;
2352	+	--right;
2353	+	}
2354	+	else break;
2355	+	}
2356	+
2357	+	if (sameLefts && right == hi - 1)
2358	+	return;
2359	+	if (left - lo <= hi - right) {
2360	+	oquickSort(a, cmp, lo, left);
2361	+	lo = left + 1;
2362	+	}
2363	+	else {
2364	+	oquickSort(a, cmp, right, hi);
2365	+	hi = left;
2366	+	}
2367	+	}
2368	+	}
2369	+
2370	+	static void ocquickSort(Comparable[] a, int lo, int hi) {
2371	+	for (;;) {
2372	+	if (hi - lo <= INSERTION_SORT_THRESHOLD) {
2373	+	for (int i = lo + 1; i <= hi; i++) {
2374	+	Comparable t = a[i];
2375	+	int j = i - 1;
2376	+	while (j >= lo && t.compareTo(a[j]) < 0) {
2377	+	a[j+1] = a[j];
2378	+	--j;
2379	+	}
2380	+	a[j+1] = t;
2381	+	}
2382	+	return;
2383	+	}
2384	+
2385	+	int mid = (lo + hi) >>> 1;
2386	+	if (a[lo].compareTo(a[mid]) > 0) {
2387	+	Comparable t = a[lo]; a[lo] = a[mid]; a[mid] = t;
2388	+	}
2389	+	if (a[mid].compareTo(a[hi]) > 0) {
2390	+	Comparable t = a[mid]; a[mid] = a[hi]; a[hi] = t;
2391	+	if (a[lo].compareTo(a[mid]) > 0) {
2392	+	Comparable u = a[lo]; a[lo] = a[mid]; a[mid] = u;
2393	+	}
2394	+	}
2395	+	Comparable pivot = a[mid];
2396	+	int left = lo+1;
2397	+	int right = hi-1;
2398	+	boolean sameLefts = true;
2399	+	for (;;) {
2400	+	while (pivot.compareTo(a[right]) < 0)
2401	+	--right;
2402	+	int c;
2403	+	while (left < right && (c = pivot.compareTo(a[left])) >= 0) {
2404	+	if (c != 0)
2405	+	sameLefts = false;
2406	+	++left;
2407	+	}
2408	+	if (left < right) {
2409	+	Comparable t = a[left]; a[left] = a[right]; a[right] = t;
2410	+	--right;
2411	+	}
2412	+	else break;
2413	+	}
2414	+
2415	+	if (sameLefts && right == hi - 1)
2416	+	return;
2417	+	if (left - lo <= hi - right) {
2418	+	ocquickSort(a, lo, left);
2419	+	lo = left + 1;
2420	+	}
2421	+	else {
2422	+	ocquickSort(a, right, hi);
2423	+	hi = left;
2424	+	}
2425	+	}
2426	+	}
2427	+
2428	+
2429	+	static void dquickSort(double[] a, DoubleComparator cmp, int lo, int hi) {
2430	+	for (;;) {
2431	+	if (hi - lo <= INSERTION_SORT_THRESHOLD) {
2432	+	for (int i = lo + 1; i <= hi; i++) {
2433	+	double t = a[i];
2434	+	int j = i - 1;
2435	+	while (j >= lo && cmp.compare(t, a[j]) < 0) {
2436	+	a[j+1] = a[j];
2437	+	--j;
2438	+	}
2439	+	a[j+1] = t;
2440	+	}
2441	+	return;
2442	+	}
2443	+
2444	+	int mid = (lo + hi) >>> 1;
2445	+	if (cmp.compare(a[lo], a[mid]) > 0) {
2446	+	double t = a[lo]; a[lo] = a[mid]; a[mid] = t;
2447	+	}
2448	+	if (cmp.compare(a[mid], a[hi]) > 0) {
2449	+	double t = a[mid]; a[mid] = a[hi]; a[hi] = t;
2450	+	if (cmp.compare(a[lo], a[mid]) > 0) {
2451	+	double u = a[lo]; a[lo] = a[mid]; a[mid] = u;
2452	+	}
2453	+	}
2454	+
2455	+	double pivot = a[mid];
2456	+	int left = lo+1;
2457	+	int right = hi-1;
2458	+	boolean sameLefts = true;
2459	+	for (;;) {
2460	+	while (cmp.compare(pivot, a[right]) < 0)
2461	+	--right;
2462	+	int c;
2463	+	while (left < right &&
2464	+	(c = cmp.compare(pivot, a[left])) >= 0) {
2465	+	if (c != 0)
2466	+	sameLefts = false;
2467	+	++left;
2468	+	}
2469	+	if (left < right) {
2470	+	double t = a[left]; a[left] = a[right]; a[right] = t;
2471	+	--right;
2472	+	}
2473	+	else break;
2474	+	}
2475	+
2476	+	if (sameLefts && right == hi - 1)
2477	+	return;
2478	+	if (left - lo <= hi - right) {
2479	+	dquickSort(a, cmp, lo, left);
2480	+	lo = left + 1;
2481	+	}
2482	+	else {
2483	+	dquickSort(a, cmp, right, hi);
2484	+	hi = left;
2485	+	}
2486	+	}
2487	+	}
2488	+
2489	+	static void lquickSort(long[] a, LongComparator cmp, int lo, int hi) {
2490	+	for (;;) {
2491	+	if (hi - lo <= INSERTION_SORT_THRESHOLD) {
2492	+	for (int i = lo + 1; i <= hi; i++) {
2493	+	long t = a[i];
2494	+	int j = i - 1;
2495	+	while (j >= lo && cmp.compare(t, a[j]) < 0) {
2496	+	a[j+1] = a[j];
2497	+	--j;
2498	+	}
2499	+	a[j+1] = t;
2500	+	}
2501	+	return;
2502	+	}
2503	+
2504	+	int mid = (lo + hi) >>> 1;
2505	+	if (cmp.compare(a[lo], a[mid]) > 0) {
2506	+	long t = a[lo]; a[lo] = a[mid]; a[mid] = t;
2507	+	}
2508	+	if (cmp.compare(a[mid], a[hi]) > 0) {
2509	+	long t = a[mid]; a[mid] = a[hi]; a[hi] = t;
2510	+	if (cmp.compare(a[lo], a[mid]) > 0) {
2511	+	long u = a[lo]; a[lo] = a[mid]; a[mid] = u;
2512	+	}
2513	+	}
2514	+
2515	+	long pivot = a[mid];
2516	+	int left = lo+1;
2517	+	int right = hi-1;
2518	+	boolean sameLefts = true;
2519	+	for (;;) {
2520	+	while (cmp.compare(pivot, a[right]) < 0)
2521	+	--right;
2522	+	int c;
2523	+	while (left < right &&
2524	+	(c = cmp.compare(pivot, a[left])) >= 0) {
2525	+	if (c != 0)
2526	+	sameLefts = false;
2527	+	++left;
2528	+	}
2529	+	if (left < right) {
2530	+	long t = a[left]; a[left] = a[right]; a[right] = t;
2531	+	--right;
2532	+	}
2533	+	else break;
2534	+	}
2535	+
2536	+	if (sameLefts && right == hi - 1)
2537	+	return;
2538	+	if (left - lo <= hi - right) {
2539	+	lquickSort(a, cmp, lo, left);
2540	+	lo = left + 1;
2541	+	}
2542	+	else {
2543	+	lquickSort(a, cmp, right, hi);
2544	+	hi = left;
2545	+	}
2546	+	}
2547	+	}
2548
2549		/**
2550		* Cumulative scan

Diff Legend

–	Removed lines
+	Added lines
<	Changed lines
>	Changed lines