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.6 by jsr166, Sun Nov 22 19:08:44 2009 UTC vs.
Revision 1.8 by dl, Tue May 25 20:31:48 2010 UTC

#	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 2305 | 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 2336 | 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	<
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;
#	Line 2384 | Line 2391 | class PAS {
2391		Comparable u = a[lo]; a[lo] = a[mid]; a[mid] = u;
2392		}
2393		}
2387	–
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 2400 | Line 2411 | class PAS {
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;
#	Line 2411 | Line 2424 | class PAS {
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 2440 | 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 2452 | Line 2471 | class PAS {
2471		else break;
2472		}
2473
2474	+	if (sameLefts && right == hi - 1)
2475	+	return;
2476		if (left - lo <= hi - right) {
2477		dquickSort(a, cmp, lo, left);
2478		lo = left + 1;
#	Line 2463 | Line 2484 | class PAS {
2484		}
2485		}
2486
2466	–	static void dcquickSort(double[] a, int lo, int hi) {
2467	–	for (;;) {
2468	–	if (hi - lo <= INSERTION_SORT_THRESHOLD) {
2469	–	for (int i = lo + 1; i <= hi; i++) {
2470	–	double t = a[i];
2471	–	int j = i - 1;
2472	–	while (j >= lo && t < a[j]) {
2473	–	a[j+1] = a[j];
2474	–	--j;
2475	–	}
2476	–	a[j+1] = t;
2477	–	}
2478	–	return;
2479	–	}
2480	–
2481	–	int mid = (lo + hi) >>> 1;
2482	–	if (a[lo] > a[mid]) {
2483	–	double t = a[lo]; a[lo] = a[mid]; a[mid] = t;
2484	–	}
2485	–	if (a[mid] > a[hi]) {
2486	–	double t = a[mid]; a[mid] = a[hi]; a[hi] = t;
2487	–	if (a[lo] > a[mid]) {
2488	–	double u = a[lo]; a[lo] = a[mid]; a[mid] = u;
2489	–	}
2490	–	}
2491	–
2492	–	double pivot = a[mid];
2493	–	int left = lo+1;
2494	–	int right = hi-1;
2495	–	for (;;) {
2496	–	while (pivot < a[right])
2497	–	--right;
2498	–	while (left < right && pivot >= a[left])
2499	–	++left;
2500	–	if (left < right) {
2501	–	double t = a[left]; a[left] = a[right]; a[right] = t;
2502	–	--right;
2503	–	}
2504	–	else break;
2505	–	}
2506	–
2507	–	if (left - lo <= hi - right) {
2508	–	dcquickSort(a, lo, left);
2509	–	lo = left + 1;
2510	–	}
2511	–	else {
2512	–	dcquickSort(a, right, hi);
2513	–	hi = left;
2514	–	}
2515	–	}
2516	–	}
2517	–
2487		static void lquickSort(long[] a, LongComparator cmp, int lo, int hi) {
2488		for (;;) {
2489		if (hi - lo <= INSERTION_SORT_THRESHOLD) {
#	Line 2544 | 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	<
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;
#	Line 2565 | Line 2541 | class PAS {
2541		hi = left;
2542		}
2543		}
2568	–	}
2569	–
2570	–	static void lcquickSort(long[] a, int lo, int hi) {
2571	–	for (;;) {
2572	–	if (hi - lo <= INSERTION_SORT_THRESHOLD) {
2573	–	for (int i = lo + 1; i <= hi; i++) {
2574	–	long t = a[i];
2575	–	int j = i - 1;
2576	–	while (j >= lo && t < a[j]) {
2577	–	a[j+1] = a[j];
2578	–	--j;
2579	–	}
2580	–	a[j+1] = t;
2581	–	}
2582	–	return;
2583	–	}
2584	–
2585	–	int mid = (lo + hi) >>> 1;
2586	–	if (a[lo] > a[mid]) {
2587	–	long t = a[lo]; a[lo] = a[mid]; a[mid] = t;
2588	–	}
2589	–	if (a[mid] > a[hi]) {
2590	–	long t = a[mid]; a[mid] = a[hi]; a[hi] = t;
2591	–	if (a[lo] > a[mid]) {
2592	–	long u = a[lo]; a[lo] = a[mid]; a[mid] = u;
2593	–	}
2594	–	}
2595	–
2596	–	long pivot = a[mid];
2597	–	int left = lo+1;
2598	–	int right = hi-1;
2599	–	for (;;) {
2600	–	while (pivot < a[right])
2601	–	--right;
2602	–	while (left < right && pivot >= a[left])
2603	–	++left;
2604	–	if (left < right) {
2605	–	long t = a[left]; a[left] = a[right]; a[right] = t;
2606	–	--right;
2607	–	}
2608	–	else break;
2609	–	}
2610	–
2611	–	if (left - lo <= hi - right) {
2612	–	lcquickSort(a, lo, left);
2613	–	lo = left + 1;
2614	–	}
2615	–	else {
2616	–	lcquickSort(a, right, hi);
2617	–	hi = left;
2618	–	}
2619	–	}
2544		}
2545
2546		/**

Diff Legend

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