package org.dict.kernel;

/**
 * Insert the type's description here.
 * Creation date: (28.08.01 22:39:16)
 * @author: Administrator
 */
public class ListUtil {
private static void mergeSort(Object src[], Object dest[], int low, int high, IComparator c) {
	int length = high - low;

	// Insertion sort on smallest arrays
	if (length < 7) {
		for (int i = low; i < high; i++)
			for (int j = i; j > low && c.compare(dest[j - 1], dest[j]) > 0; j--)
				swap(dest, j, j - 1);
		return;
	}

	// Recursively sort halves of dest into src
	int mid = (low + high) / 2;
	mergeSort(dest, src, low, mid, c);
	mergeSort(dest, src, mid, high, c);

	// If list is already sorted, just copy from src to dest.  This is an
	// optimization that results in faster sorts for nearly ordered lists.
	if (c.compare(src[mid - 1], src[mid]) <= 0) {
		System.arraycopy(src, low, dest, low, length);
		return;
	}

	// Merge sorted halves (now in src) into dest
	for (int i = low, p = low, q = mid; i < high; i++) {
		if (q >= high || p < mid && c.compare(src[p], src[q]) <= 0)
			dest[i] = src[p++];
		else
			dest[i] = src[q++];
	}
}
/**
 * search method comment.
 */
public static int search(IList ls, Object k, IComparator c) {
	return search(ls, k, c, 0, ls.size()-1);
}
public static int search(IList ls, Object k, IComparator c, int low, int high) {
	while (low <= high) {
		int mid = (low + high) / 2;
		Object midVal = ls.get(mid);
		int cmp = c.compare(midVal, k);

		if (cmp < 0)
			low = mid + 1;
		else
			if (cmp > 0)
				high = mid - 1;
			else
				return mid; // key found
	}
	return - (low + 1); // key not found
}
public static void sort(Object[] a, IComparator c) {
	Object aux[] = (Object[]) a.clone();
	mergeSort(aux, a, 0, a.length, c);
}
/**
 * Swaps x[a] with x[b].
 */
private static void swap(Object x[], int a, int b) {
	Object t = x[a];
	x[a] = x[b];
	x[b] = t;
}
}
