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.8 by dl, Tue May 25 20:31:48 2010 UTC

#	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 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 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 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 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 && (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	+
2427	+
2428	+	static void dquickSort(double[] a, DoubleComparator cmp, int lo, int hi) {
2429	+	for (;;) {
2430	+	if (hi - lo <= INSERTION_SORT_THRESHOLD) {
2431	+	for (int i = lo + 1; i <= hi; i++) {
2432	+	double t = a[i];
2433	+	int j = i - 1;
2434	+	while (j >= lo && cmp.compare(t, a[j]) < 0) {
2435	+	a[j+1] = a[j];
2436	+	--j;
2437	+	}
2438	+	a[j+1] = t;
2439	+	}
2440	+	return;
2441	+	}
2442	+
2443	+	int mid = (lo + hi) >>> 1;
2444	+	if (cmp.compare(a[lo], a[mid]) > 0) {
2445	+	double t = a[lo]; a[lo] = a[mid]; a[mid] = t;
2446	+	}
2447	+	if (cmp.compare(a[mid], a[hi]) > 0) {
2448	+	double t = a[mid]; a[mid] = a[hi]; a[hi] = t;
2449	+	if (cmp.compare(a[lo], a[mid]) > 0) {
2450	+	double u = a[lo]; a[lo] = a[mid]; a[mid] = u;
2451	+	}
2452	+	}
2453	+
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	+	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;
2470	+	}
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;
2479	+	}
2480	+	else {
2481	+	dquickSort(a, cmp, right, hi);
2482	+	hi = left;
2483	+	}
2484	+	}
2485	+	}
2486	+
2487	+	static void lquickSort(long[] a, LongComparator cmp, int lo, int hi) {
2488	+	for (;;) {
2489	+	if (hi - lo <= INSERTION_SORT_THRESHOLD) {
2490	+	for (int i = lo + 1; i <= hi; i++) {
2491	+	long t = a[i];
2492	+	int j = i - 1;
2493	+	while (j >= lo && cmp.compare(t, a[j]) < 0) {
2494	+	a[j+1] = a[j];
2495	+	--j;
2496	+	}
2497	+	a[j+1] = t;
2498	+	}
2499	+	return;
2500	+	}
2501	+
2502	+	int mid = (lo + hi) >>> 1;
2503	+	if (cmp.compare(a[lo], a[mid]) > 0) {
2504	+	long t = a[lo]; a[lo] = a[mid]; a[mid] = t;
2505	+	}
2506	+	if (cmp.compare(a[mid], a[hi]) > 0) {
2507	+	long t = a[mid]; a[mid] = a[hi]; a[hi] = t;
2508	+	if (cmp.compare(a[lo], a[mid]) > 0) {
2509	+	long u = a[lo]; a[lo] = a[mid]; a[mid] = u;
2510	+	}
2511	+	}
2512	+
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	+	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	+	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	+	else {
2540	+	lquickSort(a, cmp, right, hi);
2541	+	hi = left;
2542	+	}
2543	+	}
2544	+	}
2545
2546		/**
2547		* Cumulative scan

Diff Legend

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