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: , , , , ,

Kensington Orbit Optical Mouse

April 30, 2010 Leave a comment

Some time back (actually a year ago) I started having some issues with using a regular computer mouse. I would feel tingling feelings in my wrist and small bursts of numbness in my fingers, specially in the index finger. That’s the finger we all use for clicking with a traditional mouse. Everyone I mentioned this sensation to, said it was some sort of Carpal Tunnel syndrome. Maybe they were correct or not, don’t really know. I didn’t go to hospital to get it checked either out of laziness or indifference.

Anyway, I switched to this Kensington mouse because someone I know had it. After a bit of getting used to, it has been great and all my sympons soon disappeared. The key reason it worked is because the index finger no longer used for clicking. The index finger is just used for navigating the roller ball. It hardly takes an strength to do that. And for clicking I use the thumb muscle which is much stronger.

I tried other trackball mice as well but my pain persisted and sometimes got worse. The Logitech Trackman was useless because you are still using your index finger and type of motion is the same in it as a regular mouse. Hope this helps anyone.

Important Note: I am not a medical, physical professional of any kind. Please don’t take my opinion as authoritative advice. I have just wrote what my personal experience was.

Categories: Reviews

Ubuntu 10.04 netbook remix Cont’d

April 29, 2010 Leave a comment

Here are some more screenshots. I have adding packages as I need them so far everything is working great. The new does take some getting used to. Although the learning curve was over after about two minutes. The best thing I like about remix over the desktop edition is the lightness of the user interface and the unobstructed path from my thoughts to an action happening in the operating system. Whether it’s opening a new application or anything else.
The lack of clutter is very refreshing as well. The bar at the bottom is gone which is great and gives me some extra usable space.





The image of Tux doing a #2 is from http://www.themeparkmultimedia.com/penguin.html.

Categories: Reviews 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

Motorola Droid

April 28, 2010 Leave a comment

I’ve been using the Motorola Droid phone running Android 2.1 now for few months. I was looking forward to it and so far have been overall happy with it. I will stick to the Droid only, going over Android is a separate issue entirely. Below are some of the good and some bad issues I have found in it.

Lets start with the good
– The screen is bright and large.
– The chassis is rugged. I have dropped it around and it has bunch of scratches but held up nicely.
– The voice quality is good both ways.
– It’s a little hefty but I think thats a good thing because if its too light then its easy for it to slip out the hand.
– The speakers are great and loud.
– The network card is good and catches wi-fi signal easily.
– Having a physical keyboard is good (I guess), though I rarely ever bother to use it.

The bad
– The screen is a little too touch happy. Its easy to accidentaly touch the screen and stuff starts happening that you don’t want. If you have the Call Log open and its very easy to call someone that you didn’t want. This is because when you hold the phone in your hand, your finger will be right on the calling icon button. On the home screen, its easy to activate Google Voice command without wanting to do. If there was some region around the border of the screen where touches were ignored then that solve the problem. People don’t a cell phone with the sensitivity of a surgeon.
– The camera is awkward to use. It impossible to take a good picture of myself with it. The button on the side is hard to click when you hold the phone. This button seems more like an after thought rather than being well designed into the body. When you take a picture of something else in front of you, then its easy to accidentaly click one of the 4 buttons (back, menu, home, search) and be thrown out of the camera application – this gets very annoying esp when you are handing the phone to someone who isn’t used to the sensitivity.
– The up-down volume button on the side of the chassis are at the wrong place. They would be better off the left side instead of the right.
– The pattern recognition is not effective. After much use, the pattern that I use to unlock the phone became imprinted on the screen. This is probably due to humidity, dust. So if you found my phone and wanted to unlock it, you can just look at it at an angle and you will see my pattern.
– Not really a big issue but the battery cover slides off easily. It shouldn’t do that.
– The GPS sucks all the battery but that is OK because I have a car charger.

My suggestions:
– Have a lining of anodized rubber on the outer edge of where the fingers touch the phone when you are holding next to your ear.

Categories: Reviews Tags: , , ,