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.8 by dl, Tue May 25 20:31:48 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 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 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 2303 | Line 2305 | class PAS {
2305		/** Cutoff for when to use insertion-sort instead of quicksort */
2306		static final int INSERTION_SORT_THRESHOLD = 8;
2307
2308	<	// Six nearly identical versions of quicksort
2308	>	// versions of quicksort with comparators
2309
2310		static void oquickSort(Object[] a, Comparator cmp, int lo, int hi) {
2311		for (;;) {
#	Line 2334 | Line 2336 | class PAS {
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	<	while (left < right && cmp.compare(pivot, a[left]) >= 0)
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	<	oquickSort(a, cmp, lo, left);
2357	<	lo = left + 1;
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
#	Line 2376 | Line 2391 | class PAS {
2391		Comparable u = a[lo]; a[lo] = a[mid]; a[mid] = u;
2392		}
2393		}
2379	–
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	<	while (left < right && pivot.compareTo(a[left]) >= 0)
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;
#	Line 2392 | Line 2411 | class PAS {
2411		else break;
2412		}
2413
2414	<	ocquickSort(a, lo, left);
2415	<	lo = left + 1;
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
2427	+
2428		static void dquickSort(double[] a, DoubleComparator cmp, int lo, int hi) {
2429		for (;;) {
2430		if (hi - lo <= INSERTION_SORT_THRESHOLD) {
#	Line 2426 | Line 2454 | class PAS {
2454		double pivot = a[mid];
2455		int left = lo+1;
2456		int right = hi-1;
2457	+	boolean sameLefts = true;
2458		for (;;) {
2459		while (cmp.compare(pivot, a[right]) < 0)
2460		--right;
2461	<	while (left < right && cmp.compare(pivot, a[left]) >= 0)
2461	>	int c;
2462	>	while (left < right && (c = cmp.compare(pivot, a[left])) >= 0){
2463	>	if (c != 0)
2464	>	sameLefts = false;
2465		++left;
2466	+	}
2467		if (left < right) {
2468		double t = a[left]; a[left] = a[right]; a[right] = t;
2469		--right;
#	Line 2438 | Line 2471 | class PAS {
2471		else break;
2472		}
2473
2474	<	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	<	}
2474	>	if (sameLefts && right == hi - 1)
2475		return;
2476	+	if (left - lo <= hi - right) {
2477	+	dquickSort(a, cmp, lo, left);
2478	+	lo = left + 1;
2479		}
2480	<
2481	<	int mid = (lo + hi) >>> 1;
2482	<	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;
2480	>	else {
2481	>	dquickSort(a, cmp, right, hi);
2482	>	hi = left;
2483		}
2486	–
2487	–	dcquickSort(a, lo, left);
2488	–	lo = left + 1;
2484		}
2485		}
2486
#	Line 2518 | Line 2513 | class PAS {
2513		long pivot = a[mid];
2514		int left = lo+1;
2515		int right = hi-1;
2516	+	boolean sameLefts = true;
2517		for (;;) {
2518		while (cmp.compare(pivot, a[right]) < 0)
2519		--right;
2520	<	while (left < right && cmp.compare(pivot, a[left]) >= 0)
2520	>	int c;
2521	>	while (left < right && (c = cmp.compare(pivot, a[left])) >= 0){
2522	>	if (c != 0)
2523	>	sameLefts = false;
2524		++left;
2525	+	}
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	<	}
2532	>
2533	>	if (sameLefts && right == hi - 1)
2534		return;
2535	+	if (left - lo <= hi - right) {
2536	+	lquickSort(a, cmp, lo, left);
2537	+	lo = left + 1;
2538		}
2539	<
2540	<	int mid = (lo + hi) >>> 1;
2541	<	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;
2539	>	else {
2540	>	lquickSort(a, cmp, right, hi);
2541	>	hi = left;
2542		}
2578	–
2579	–	lcquickSort(a, lo, left);
2580	–	lo = left + 1;
2543		}
2544		}
2545
#	Line 2671 | Line 2633 | class PAS {
2633		int cb;
2634		for (;;) { // Establish action: sum, cumulate, or both
2635		int b = phase;
2636	<	if ((b & FINISHED) != 0) // already done
2636	>	if ((b & FINISHED) != 0) // already done
2637		return false;
2638		if ((b & CUMULATE) != 0)
2639		cb = FINISHED;
#	Line 2783 | Line 2745 | class PAS {
2745		}
2746
2747		/**
2748	<	* Computational operations for FJSCan
2748	>	* Computational operations for FJScan
2749		*/
2750		static abstract class FJScanOp {
2751		final int threshold;

Diff Legend

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