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.1 by dl, Tue Jan 6 14:30:57 2009 UTC vs.
Revision 1.7 by dl, Tue May 25 13:39:40 2010 UTC

#	Line 1524 | Line 1524 | class PAS {
1524		continue;
1525		double x = src[k];
1526		long bits = Double.doubleToLongBits(x);
1527	<	int hash = hash((int)(bits ^ (bits >>> 32)));;
1527	>	int hash = hash((int)(bits ^ (bits >>> 32)));
1528		long entry = (((long)hash) << 32) + (k + 1);
1529		int idx = hash & mask;
1530		for (;;) {
#	Line 1681 | Line 1681 | class PAS {
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
#	Line 1717 | Line 1717 | class PAS {
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
#	Line 1754 | Line 1754 | class PAS {
1754		l+h, n-h, l, g, null).compute();
1755		}
1756		else
1757	<	dquickSort(a, cmp, l, l+n-1);
1757	>	Arrays.sort(a, l, l+n, cmp);
1758		}
1759		}
1760
#	Line 1790 | Line 1790 | class PAS {
1790		l+h, n-h, l, g, null).compute();
1791		}
1792		else
1793	<	dcquickSort(a, l, l+n-1);
1793	>	Arrays.sort(a, l, l+n);
1794		}
1795		}
1796
#	Line 1828 | Line 1828 | class PAS {
1828		l+h, n-h, l, g, null).compute();
1829		}
1830		else
1831	<	lquickSort(a, cmp, l, l+n-1);
1831	>	Arrays.sort(a, l, l+n, cmp);
1832		}
1833		}
1834
#	Line 1865 | Line 1865 | class PAS {
1865		l+h, n-h, l, g, null).compute();
1866		}
1867		else
1868	<	lcquickSort(a, l, l+n-1);
1868	>	Arrays.sort(a, l, l+n);
1869		}
1870		}
1871
#	Line 1875 | Line 1875 | class PAS {
1875		final RecursiveAction right;
1876		final RecursiveAction merger;
1877		FJSubSorter(RecursiveAction left, RecursiveAction right,
1878	<	RecursiveAction merger){
1878	>	RecursiveAction merger) {
1879		this.left = left; this.right = right; this.merger = merger;
1880		}
1881		public void compute() {
1882	<	invokeAll(left, right);
1882	>	right.fork();
1883	>	left.invoke();
1884	>	right.join();
1885		merger.invoke();
1886		}
1887		}
#	Line 2300 | Line 2302 | class PAS {
2302		}
2303		}
2304
2303	–	/** Cutoff for when to use insertion-sort instead of quicksort */
2304	–	static final int INSERTION_SORT_THRESHOLD = 8;
2305	–
2306	–	// Six nearly identical versions of quicksort
2307	–
2308	–	static void oquickSort(Object[] a, Comparator cmp, int lo, int hi) {
2309	–	for (;;) {
2310	–	if (hi - lo <= INSERTION_SORT_THRESHOLD) {
2311	–	for (int i = lo + 1; i <= hi; i++) {
2312	–	Object t = a[i];
2313	–	int j = i - 1;
2314	–	while (j >= lo && cmp.compare(t, a[j]) < 0) {
2315	–	a[j+1] = a[j];
2316	–	--j;
2317	–	}
2318	–	a[j+1] = t;
2319	–	}
2320	–	return;
2321	–	}
2322	–
2323	–	int mid = (lo + hi) >>> 1;
2324	–	if (cmp.compare(a[lo], a[mid]) > 0) {
2325	–	Object t = a[lo]; a[lo] = a[mid]; a[mid] = t;
2326	–	}
2327	–	if (cmp.compare(a[mid], a[hi]) > 0) {
2328	–	Object t = a[mid]; a[mid] = a[hi]; a[hi] = t;
2329	–	if (cmp.compare(a[lo], a[mid]) > 0) {
2330	–	Object u = a[lo]; a[lo] = a[mid]; a[mid] = u;
2331	–	}
2332	–	}
2333	–
2334	–	Object pivot = a[mid];
2335	–	int left = lo+1;
2336	–	int right = hi-1;
2337	–	for (;;) {
2338	–	while (cmp.compare(pivot, a[right]) < 0)
2339	–	--right;
2340	–	while (left < right && cmp.compare(pivot, a[left]) >= 0)
2341	–	++left;
2342	–	if (left < right) {
2343	–	Object t = a[left]; a[left] = a[right]; a[right] = t;
2344	–	--right;
2345	–	}
2346	–	else break;
2347	–	}
2348	–
2349	–	oquickSort(a, cmp, lo, left);
2350	–	lo = left + 1;
2351	–	}
2352	–	}
2353	–
2354	–	static void ocquickSort(Comparable[] a, int lo, int hi) {
2355	–	for (;;) {
2356	–	if (hi - lo <= INSERTION_SORT_THRESHOLD) {
2357	–	for (int i = lo + 1; i <= hi; i++) {
2358	–	Comparable t = a[i];
2359	–	int j = i - 1;
2360	–	while (j >= lo && t.compareTo(a[j]) < 0) {
2361	–	a[j+1] = a[j];
2362	–	--j;
2363	–	}
2364	–	a[j+1] = t;
2365	–	}
2366	–	return;
2367	–	}
2368	–
2369	–	int mid = (lo + hi) >>> 1;
2370	–	if (a[lo].compareTo(a[mid]) > 0) {
2371	–	Comparable t = a[lo]; a[lo] = a[mid]; a[mid] = t;
2372	–	}
2373	–	if (a[mid].compareTo(a[hi]) > 0) {
2374	–	Comparable t = a[mid]; a[mid] = a[hi]; a[hi] = t;
2375	–	if (a[lo].compareTo(a[mid]) > 0) {
2376	–	Comparable u = a[lo]; a[lo] = a[mid]; a[mid] = u;
2377	–	}
2378	–	}
2379	–
2380	–	Comparable pivot = a[mid];
2381	–	int left = lo+1;
2382	–	int right = hi-1;
2383	–	for (;;) {
2384	–	while (pivot.compareTo(a[right]) < 0)
2385	–	--right;
2386	–	while (left < right && pivot.compareTo(a[left]) >= 0)
2387	–	++left;
2388	–	if (left < right) {
2389	–	Comparable t = a[left]; a[left] = a[right]; a[right] = t;
2390	–	--right;
2391	–	}
2392	–	else break;
2393	–	}
2394	–
2395	–	ocquickSort(a, lo, left);
2396	–	lo = left + 1;
2397	–	}
2398	–	}
2399	–
2400	–	static void dquickSort(double[] a, DoubleComparator cmp, int lo, int hi) {
2401	–	for (;;) {
2402	–	if (hi - lo <= INSERTION_SORT_THRESHOLD) {
2403	–	for (int i = lo + 1; i <= hi; i++) {
2404	–	double t = a[i];
2405	–	int j = i - 1;
2406	–	while (j >= lo && cmp.compare(t, a[j]) < 0) {
2407	–	a[j+1] = a[j];
2408	–	--j;
2409	–	}
2410	–	a[j+1] = t;
2411	–	}
2412	–	return;
2413	–	}
2414	–
2415	–	int mid = (lo + hi) >>> 1;
2416	–	if (cmp.compare(a[lo], a[mid]) > 0) {
2417	–	double t = a[lo]; a[lo] = a[mid]; a[mid] = t;
2418	–	}
2419	–	if (cmp.compare(a[mid], a[hi]) > 0) {
2420	–	double t = a[mid]; a[mid] = a[hi]; a[hi] = t;
2421	–	if (cmp.compare(a[lo], a[mid]) > 0) {
2422	–	double u = a[lo]; a[lo] = a[mid]; a[mid] = u;
2423	–	}
2424	–	}
2425	–
2426	–	double pivot = a[mid];
2427	–	int left = lo+1;
2428	–	int right = hi-1;
2429	–	for (;;) {
2430	–	while (cmp.compare(pivot, a[right]) < 0)
2431	–	--right;
2432	–	while (left < right && cmp.compare(pivot, a[left]) >= 0)
2433	–	++left;
2434	–	if (left < right) {
2435	–	double t = a[left]; a[left] = a[right]; a[right] = t;
2436	–	--right;
2437	–	}
2438	–	else break;
2439	–	}
2440	–
2441	–	dquickSort(a, cmp, lo, left);
2442	–	lo = left + 1;
2443	–	}
2444	–	}
2445	–
2446	–	static void dcquickSort(double[] a, int lo, int hi) {
2447	–	for (;;) {
2448	–	if (hi - lo <= INSERTION_SORT_THRESHOLD) {
2449	–	for (int i = lo + 1; i <= hi; i++) {
2450	–	double t = a[i];
2451	–	int j = i - 1;
2452	–	while (j >= lo && t < a[j]) {
2453	–	a[j+1] = a[j];
2454	–	--j;
2455	–	}
2456	–	a[j+1] = t;
2457	–	}
2458	–	return;
2459	–	}
2460	–
2461	–	int mid = (lo + hi) >>> 1;
2462	–	if (a[lo] > a[mid]) {
2463	–	double t = a[lo]; a[lo] = a[mid]; a[mid] = t;
2464	–	}
2465	–	if (a[mid] > a[hi]) {
2466	–	double t = a[mid]; a[mid] = a[hi]; a[hi] = t;
2467	–	if (a[lo] > a[mid]) {
2468	–	double u = a[lo]; a[lo] = a[mid]; a[mid] = u;
2469	–	}
2470	–	}
2471	–
2472	–	double pivot = a[mid];
2473	–	int left = lo+1;
2474	–	int right = hi-1;
2475	–	for (;;) {
2476	–	while (pivot < a[right])
2477	–	--right;
2478	–	while (left < right && pivot >= a[left])
2479	–	++left;
2480	–	if (left < right) {
2481	–	double t = a[left]; a[left] = a[right]; a[right] = t;
2482	–	--right;
2483	–	}
2484	–	else break;
2485	–	}
2486	–
2487	–	dcquickSort(a, lo, left);
2488	–	lo = left + 1;
2489	–	}
2490	–	}
2491	–
2492	–	static void lquickSort(long[] a, LongComparator cmp, int lo, int hi) {
2493	–	for (;;) {
2494	–	if (hi - lo <= INSERTION_SORT_THRESHOLD) {
2495	–	for (int i = lo + 1; i <= hi; i++) {
2496	–	long t = a[i];
2497	–	int j = i - 1;
2498	–	while (j >= lo && cmp.compare(t, a[j]) < 0) {
2499	–	a[j+1] = a[j];
2500	–	--j;
2501	–	}
2502	–	a[j+1] = t;
2503	–	}
2504	–	return;
2505	–	}
2506	–
2507	–	int mid = (lo + hi) >>> 1;
2508	–	if (cmp.compare(a[lo], a[mid]) > 0) {
2509	–	long t = a[lo]; a[lo] = a[mid]; a[mid] = t;
2510	–	}
2511	–	if (cmp.compare(a[mid], a[hi]) > 0) {
2512	–	long t = a[mid]; a[mid] = a[hi]; a[hi] = t;
2513	–	if (cmp.compare(a[lo], a[mid]) > 0) {
2514	–	long u = a[lo]; a[lo] = a[mid]; a[mid] = u;
2515	–	}
2516	–	}
2517	–
2518	–	long pivot = a[mid];
2519	–	int left = lo+1;
2520	–	int right = hi-1;
2521	–	for (;;) {
2522	–	while (cmp.compare(pivot, a[right]) < 0)
2523	–	--right;
2524	–	while (left < right && cmp.compare(pivot, a[left]) >= 0)
2525	–	++left;
2526	–	if (left < right) {
2527	–	long t = a[left]; a[left] = a[right]; a[right] = t;
2528	–	--right;
2529	–	}
2530	–	else break;
2531	–	}
2532	–
2533	–	lquickSort(a, cmp, lo, left);
2534	–	lo = left + 1;
2535	–	}
2536	–	}
2537	–
2538	–	static void lcquickSort(long[] a, int lo, int hi) {
2539	–	for (;;) {
2540	–	if (hi - lo <= INSERTION_SORT_THRESHOLD) {
2541	–	for (int i = lo + 1; i <= hi; i++) {
2542	–	long t = a[i];
2543	–	int j = i - 1;
2544	–	while (j >= lo && t < a[j]) {
2545	–	a[j+1] = a[j];
2546	–	--j;
2547	–	}
2548	–	a[j+1] = t;
2549	–	}
2550	–	return;
2551	–	}
2552	–
2553	–	int mid = (lo + hi) >>> 1;
2554	–	if (a[lo] > a[mid]) {
2555	–	long t = a[lo]; a[lo] = a[mid]; a[mid] = t;
2556	–	}
2557	–	if (a[mid] > a[hi]) {
2558	–	long t = a[mid]; a[mid] = a[hi]; a[hi] = t;
2559	–	if (a[lo] > a[mid]) {
2560	–	long u = a[lo]; a[lo] = a[mid]; a[mid] = u;
2561	–	}
2562	–	}
2563	–
2564	–	long pivot = a[mid];
2565	–	int left = lo+1;
2566	–	int right = hi-1;
2567	–	for (;;) {
2568	–	while (pivot < a[right])
2569	–	--right;
2570	–	while (left < right && pivot >= a[left])
2571	–	++left;
2572	–	if (left < right) {
2573	–	long t = a[left]; a[left] = a[right]; a[right] = t;
2574	–	--right;
2575	–	}
2576	–	else break;
2577	–	}
2578	–
2579	–	lcquickSort(a, lo, left);
2580	–	lo = left + 1;
2581	–	}
2582	–	}
2583	–
2305		/**
2306		* Cumulative scan
2307		*
#	Line 2671 | Line 2392 | class PAS {
2392		int cb;
2393		for (;;) { // Establish action: sum, cumulate, or both
2394		int b = phase;
2395	<	if ((b & FINISHED) != 0) // already done
2395	>	if ((b & FINISHED) != 0) // already done
2396		return false;
2397		if ((b & CUMULATE) != 0)
2398		cb = FINISHED;
#	Line 2783 | Line 2504 | class PAS {
2504		}
2505
2506		/**
2507	<	* Computational operations for FJSCan
2507	>	* Computational operations for FJScan
2508		*/
2509		static abstract class FJScanOp {
2510		final int threshold;

Diff Legend

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