package sort;
/** Various utility functions used by other classes. */
public class Util {
private Util() {}
// Random number generator used in random() methods.
private static java.util.Random rand;
// Initialize random number generator. Take into account processor
// number to prevent duplicated seeds (empirically necessary).
static {
long tmp = System.currentTimeMillis();
tmp += (tmp >>> Ti.thisProc()) + (tmp << Ti.thisProc());
rand = new java.util.Random(tmp);
}
/** Debugging level. A value greater than 0 implies that some
* debugging output will be printed.
*/
protected static int DEBUGGING_LEVEL = 0;
/** Prints the given debugging message if the debugging level is
* greater than 0 and the current processor is processor 0.
* @param msg the message to print
*/
protected static void debug(String msg) {
debug(msg, 1);
}
/** Prints the given debugging message if the debugging level is
* greater than the given level and the current processor is
* processor 0.
* @param msg the message to print
* @param level the threshold debugging level
*/
protected static void debug(String msg, int level) {
if (DEBUGGING_LEVEL >= level && Ti.thisProc() == 0) {
System.out.println(msg);
}
}
/** Prints the given debugging message if the debugging level is
* greater than 0.
* @param msg the message to print
*/
protected static void debugAll(String msg) {
debugAll(msg, 1);
}
/** Prints the given debugging message if the debugging level is
* greater than the given level.
* @param msg the message to print
* @param level the threshold debugging level
*/
protected static void debugAll(String msg, int level) {
if (DEBUGGING_LEVEL >= level) {
System.out.println(Ti.thisProc() + ": " + msg);
}
}
/** Generates a random int.
*/
public static int random() {
return rand.nextInt();
}
/** Generates a random int in the range
* {0, ... , x - 1}.
* @param x the exclusive upper bound on the generated number
* @return a random int in the range
* {0, ... , x - 1}
*/
public static int random(int x) {
int r = rand.nextInt();
if (r == Integer.MIN_VALUE) {
return random(x);
} else {
r = (r < 0) ? -r : r;
return r % x;
}
}
/** Returns a string representation of the given array.
* @param arr the array to find the string representation of
* @return a string representation of the argument
*/
public static String toString(int[] arr) {
return toString(arr, 0, arr.length, false);
}
/** Returns a string representation of the subsection of the given
* array arr[off...off+len-1].
* @param arr the array to find the string representation of
* @param off the position at which the string representation starts
* @param len the number of elements in the string representation
* return a string representation of arr[off...off+len-1]
*
*/
public static String toString(int[] arr, int off, int len) {
return toString(arr, off, len, false);
}
/** Returns a string representation of the given array, with each
* element in hexadecimal.
* @param arr the array to find the string representation of
* @return a string representation of the argument
*/
public static String toHexString(int[] arr) {
return toString(arr, 0, arr.length, true);
}
/** Returns a string representation of the subsection of the given
* array arr[off...off+len-1], with each element in
* hexadecimal.
* @param arr the array to find the string representation of
* @param off the position at which the string representation starts
* @param len the number of elements in the string representation
* return a string representation of arr[off...off+len-1]
*
*/
public static String toHexString(int[] arr, int off, int len) {
return toString(arr, off, len, true);
}
// Returns a string representation of a subsection of the given array.
// Elements are printed in hexadecimal if hex is true.
private static String toString(int[] arr, int off, int len,
boolean hex) {
StringBuffer sb = new StringBuffer();
sb.append("[");
for (int i = 0; i < len - 1; i++) {
sb.append(hex ? toHexString(arr[off + i]) :
("" + arr[off + i]));
sb.append(", ");
}
if (len != 0) {
sb.append(hex ? toHexString(arr[off + len - 1]) :
("" + arr[off + len - 1]));
}
sb.append("]");
return sb.toString();
}
/** Returns a hexadecimal string representation of the given number,
* padded to 8 digits.
* @param x the number to compute a hexadecimal string representation
* for
* @return a hexadecimal string represenation of the argument
*/
public static String toHexString(int x) {
StringBuffer hs = new StringBuffer(Integer.toHexString(x));
StringBuffer tmp = new StringBuffer();
for (int i = 8 - hs.length(); i > 0; i--) {
tmp.append(0);
}
tmp.append(hs);
return tmp.toString();
}
/** Compares if two arrays contain equal elements.
* @param arr1 the first array
* @param off1 the offset in the first array at which to start
* @param arr2 the second array
* @param off2 the offset in the second array at which to start
* @param len the number of elements to check
* @return whether or not arr1[off1...off1+len-1]
* is equal to arr2[off2...off2+len-1]
*/
public static boolean compare(int[] arr1, int off1, int[] arr2,
int off2, int len) {
if (arr1.length - off1 < len || arr2.length - off2 < len) {
throw new IllegalArgumentException("len too large");
}
for (; len > 0; len--) {
if (arr1[off1 + len - 1] != arr2[off2 + len - 1]) {
return false;
}
}
return true;
}
/** Sorts the given elements locally using radix sort, using the given
* number of digits per iteration. The sort uses unsigned integers.
* @param elems the numbers to sort
* @param digits the number of digits to use in each iteration
*/
public static void radixSort(int[] elems, int digits) {
RadixBucketizer rb = new RadixBucketizer(digits);
Buckets buck = new Buckets((0xffffffff >>> (32 - digits)) + 1,
rb);
for (int i = 0; i < (int) Math.ceil(32. / (double) digits);
i++) {
rb.setRad(i);
buck.addAll(elems, 0, elems.length);
buck.copyElements(elems);
buck.clear();
}
}
/** Sorts the given array. This method is equivalent to the call
* sort(arr, 0, arr.length).
* @param arr the array to sort
*/
public static void sort(int[] arr) {
quickSort(arr, 0, arr.length);
}
/** Sorts the subsection of the given array arr[off...off+len-1]
* using a O(n log n) expected time sort. The sort is
* unstable and is pessimal for already sorted or reverse sorted
* arrays. The sort uses signed integers.
* @param arr the array to sort
* @param off the position at which to start sorting
* @param len the number of elements to sort
*/
public static void sort(int[] arr, int off, int len) {
quickSort(arr, off, off+len);
}
// Sorts the subsection of the array arr[left...right-1] using
// quick sort, with the first element as the pivot. This sort
// is unstable.
private static void quickSort(int[] arr, int left, int right) {
if (right - left > 1) {
int e = left, u = left + 1, b = right;
int pivot = arr[left];
while (u < b) {
if (arr[u] < pivot) {
swap(arr, e++, u++);
} else if (arr[u] == pivot) {
u++;
} else {
swap(arr, u, --b);
}
}
quickSort(arr, left, e);
quickSort(arr, b, right);
}
}
// Swaps two elements in an array. The arguments must be in range.
private static void swap(int[] arr, int a, int b) {
int tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
}