Archive

Archive for the ‘Java’ Category

Bubble sort in Java

Bubblesort is one of the simplest sorting methods. It also very inefficient. Though in the best case when the elements are already sorted, then its run time is O(n). Otherwise it is O(n^2).

package com.labeltop.sort;

public class BubbleSort {
	public void sort(Comparable[] comparables) {

		int size = comparables.length;

		// loop till swaps are being done
		while (true) {
			// reset it
			boolean foundSwap = false;

			// loop over values
			int i = 0;
			while (i < size) {
				// don't care about last value
				if (i == size - 1)
					break;

				// check for swap i.e. c1 > c2
				if (comparables[i].compareTo(comparables[i + 1]) > 0) {
					Comparable temp = comparables[i];
					comparables[i] = comparables[i + 1];
					comparables[i + 1] = temp;
					foundSwap = true;
				}

				// keep on...
				i++;
			}

			// check if there were any swaps
			if (!foundSwap)
				break;
		}
	}
}
Advertisements
Categories: Java, Java Misc, Java Sorting

Quicksort in Java

QuickSort is one of best sorting algorithms. While the worst case scenario is O(n^2), the average case is O(nlgn). Additionally, it is possible to implement in highly optimized way as well do several of its parts in parallel.

package com.labeltop.sort;

public class QuickSort {

	public void sort(Comparable[] c) {
		quicksort(c, 0, c.length-1);
	}

	private void quicksort(Comparable[] comparables, int start, int end) {

		// get a pivot point
		int pivot = start + ((int) (Math.random() * (end - start)));
		Comparable cPivot = comparables[pivot];

		// where to start on either side of pivot
		int left = start;
		int right = end;

		// loop till they overlap
		while (left <= right) {
			// find first on left that is bigger than pivot
			while (cPivot.compareTo(comparables[left]) > 0) {
				// more towards pivot
				left++;
			}

			// find first on right that is less than pivot
			while (cPivot.compareTo(comparables[right]) < 0) {
				// more towards pivot
				right--;
			}

			// exchange them
			if (left <= right) {
				Comparable temp = comparables[left];
				comparables[left] = comparables[right];
				comparables[right] = temp;
				//go to next ones towards the pivot
				left++;
				right--;
			}			
		}
		
		//recurse on left
		if (right > start) {
			quicksort(comparables, start, right);
		}
		//recurse on right
		if (left < end) {
			quicksort(comparables, left, end);
		}
	}

}
Categories: Java, Java Misc, Java Sorting

Merge Sort in Java

Here it is:

package com.labeltop.sort;

public class MergeSort {

	public void sort(Comparable[] c) {
		mergesort(c, 0, c.length-1);
	}

	private void mergesort(Comparable[] c, int start, int end) {
		//check if sort is needed
		if (c.length <= 1)
			return;
		
		//find middle
		int middle = start + ((end-start)/2);
		
		//create left list
		Comparable[] cLeft = new Comparable[middle-start+1];
		
		//create right list
		Comparable[] cRight = new Comparable[end-middle];
		
		//sort first half
		mergesort(cLeft, 0, cLeft.length-1);
		//sort second half
		mergesort(cRight, 0, cRight.length-1);
		
		//check the last on left iwth first on right to see if we need to merge
		if (cLeft[cLeft.length-1].compareTo(cRight[0]) <= 0) {
			System.arraycopy(cLeft, 0, c, 0, cLeft.length);
			System.arraycopy(cRight, 0, c, cLeft.length, cRight.length);
		}
		else {
			//now merge left and right
			mergeIt(c, cLeft, cRight);	
		}
	}
	
	private void mergeIt(Comparable[] merged, Comparable[] cLeft, Comparable[] cRight) {		
		//loop till both are done
		int iMerged = 0;
		int iLeft = 0;
		int iRight = 0;
		while (iLeft < cLeft.length && iRight < cRight.length)
		{
			if (cLeft[iLeft].compareTo(cRight[iRight]) <= 0)
			{
				//copy from left
				merged[iMerged] = cLeft[iLeft];
				iLeft++;				
			}
			else
			{
				//copy from right
				merged[iMerged] = cRight[iRight];
				iRight++;
			}
			
			iMerged++;
		}
		
		//check for remaining elements on left
		if (iLeft <= cLeft.length-1) {
			System.arraycopy(cLeft, iLeft, merged, iMerged, cLeft.length-iLeft);
			iMerged = iMerged + (cLeft.length-1-iLeft);
		}
		//check for remaining elements on right
		if (iRight <= cRight.length-1) {
			System.arraycopy(cRight, iRight, merged, iMerged, cRight.length-iRight);
			iMerged = iMerged + (cRight.length-1-iRight);
		}		
	}
}
Categories: Java, Java Misc, Java Sorting

Java Native Access, JNA, thoughts

In order to get system information, you almost certainly have to go to some platform specific functions. I’m referring to something that in non-trivial, the Java API is great but it really does fall short when you need to interact with OS kernel functions. The old (well older) way to do so would be to use JNI (Java Native Interface). With JNI, you would generate a client stub in Java and essentially link it to the implementation which is in C (or any other language you have bindings for). The keyword ‘native’ in Java tells the compiler of your intentions and that leads to good relative performance because the compiler is able to do static linking.

There are books written on the subject and there is not much to it but JNI is certainly a way to get Java to interact with win32 api. During developing LabelTop (see Links), I wanted to interact on a low level with the OS. I wanted to get processor usage information and memory usage information. My experience that I mention here is almost equally applicable to Mac OS X where I called Obj-C functions from the Cocoa API. I decided to use JNA instead of JNI.

JNA is a project which is (was) in incubation at java.net. It always dynamic linking with native resources. The benefit of that is that you have a lot less compile time stuff to do as a programmer. Though, the cost is that you do lose some performance. While I haven’t done a detailed empirical study of the amount of performance loss, my experience is that the loss is hardly noticeable, after having used JNA quite a bit.

A big benefit is that I’m able to represent the underlying ‘struct’ as a simple Java class, an interface with signatures of functions that I want to call in Java. I can then load a dll file that I didn’t write and call its functions. JNA will take an input the function I’m calling and its input parameters, convert the function call to a C function call and convert the class to struct, then I will execute the function using the dll, it will take the results and convert that to Java types and return them to me.

Equivalently, with JNI, I would to write my interface, declare methods as native, write my C program which would then call functions in the dll. Get the results back from dll and return them myself. So JNA, does a lot of the heavy lifting for me.

The kernel32.dll is huge! I don’t need to call every function. So in my interface I declare the functions that I will want to use and just call those. If I need another function then I can declare that in my interface too. Thus, integration can be done iteratively which saves a lot of time. JNA uses a mapping of primitive types from Java to C which is very clear and straightforward. Have fun!

Categories: Java, Java Misc Tags: , , , , ,

Determine if you are running in Tomcat

April 29, 2010 2 comments

I have Java libraries that I have written and I like to share between projects. It is called Re-usability. However, in one instance a few lines of code were not to be executed if I was running the code in my servlet on Tomcat. So here is a quick way to find out if you are running within Tomcat:

public static boolean isTomcat() {
String catalinaHome = System.getProperty(“catalina.home”);
return (catalinaHome==null || (catalinaHome.trim().length() > 0));
}

Categories: Java, Java Misc Tags: , , ,

Couple of useful regular expressions

April 28, 2010 1 comment

Here are a couple of useful regular expressions I came up with over some coffee in Java language. Haven’t tested them thoroughly 😀

// the regular expression for valid time
public static final String REGEX_TIME = “(^([0-9]|[0-1][0-9]|[2][0-3]):([0-5][0-9])(\\s{0,1})(AM|PM|am|pm|aM|Am|pM|Pm{2,2})$)|(^([0-9]|[1][0-9]|[2][0-3])(\\s{0,1})(AM|PM|am|pm|aM|Am|pM|Pm{2,2})$)”;

// the regular expression for valid phone
public static final String REGEX_PHONE = “^\\(?(\\d{3})\\)?[- ]?(\\d{3})[- ]?(\\d{4})$”;

// the regular expression for valid eamil
public static final String REGEX_EMAIL = “.+@.+\\.[a-z]+”;

Will add more later after some errands.

Categories: Java, Java Misc

The BLOCKING in BlockQueue

February 8, 2010 Leave a comment

One of the core abilities of any concurrent program is the ability for block for events. java.util.BlockingQueue is a good example of an interface which provides that ability.

Following is an example from an array implementation (java.util.ArrayBlockingQueue):

public E take() throws InterruptedException {
final ReentrantLock lock = this.lock;
lock.lockInterruptibly();
try {
try {
while (count == 0)
notEmpty.await();
} catch (InterruptedException ie) {
notEmpty.signal(); // propagate to non-interrupted thread
throw ie;
}
E x = extract();
return x;
} finally {
lock.unlock();
}
}

Categories: Java, Java Collections