Saturday, July 14, 2012

Sorting Alogirthm in Java - Quick , Insertion, Merge, Heap, Selection, and Shell

You can find Java based implementation for Quick , Insertion, Merge, Heap, Selection, and Shell sorting algorithm. All those are properly tested, I assume you have good understand on how each algorithm works that helps you to understand the implementation much better.

HeapSort

public class HeapSort {

    public int[] sort(int[] a) {
        sort(a, a.length-1);
        return a;
    }

    public void sort(int[] a, int end) {
        for (int i = end / 2; i >= 1; i--) {
            fixHeap(a, i, end, a[i]);
        }
        for (int i = end; i > 0; i--) {
            swap(a, 0, i);
            fixHeap(a, 0, i - 1, a[0]);
        }
    }

    private void fixHeap(int[] a, int root, int end,
                         int key) {
        int child = 2 * root; // left child
        if (child < end && a[child] < a[child + 1]) {
            child++;
        }
        if (child <= end && key < a[child]) {
            a[root] = a[child];
            fixHeap(a, child, end, key);
        } else {
            a[root] = key;
        }
    }

    private void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

InsertionSort


public class InsertionSort {

    public int[] sort(int[] input) {
        int size = input.length;
           for (int i = 1; i < size; i++) {
            int j = i;
            int x = input[i];
            while (j > 0 && input[j - 1] > x) {
                input[j] = input[j - 1];
                j--;
            }
            input[j] = x;
        }
        return input;
    }
}

MergeSort 

public class MergeSort {

    public int[] sort(int[] list) {
        mergeSort(list, 0, list.length-1);
        return list;
    }

    public void mergeSort(int list[], int first, int last) {
        if (first >= last) {
            return;
        }
        int middle = (first + last) / 2;
        mergeSort(list, first, middle);
        mergeSort(list, middle + 1, last);

        int size = (last - first) + 1;
        int[] results = new int[size];

        int start2 = middle + 1;
        int indexC = 0;
        int start1 = first;
        while ((start1 <= middle) && (start2 <= last)) {
            if (list[start1] < list[start2]) {
                results[indexC] = list[start1];
                start1++;
            } else {
                results[indexC] = list[start2];
                start2++;
            }
            indexC++;
        }
        if (start1 <= middle) {
            for (int i = start1; i <= middle; i++) {
                results[indexC] = list[i];
                indexC++;
            }
        } else {
            for (int j = start2; j <= last; j++) {
                results[indexC] = list[j];
                indexC++;
            }
        }

        int c = 0;
        for (int index = first; index <= last; index++) {
            list[index] = results[c];
            c++;
        }
    }
}

QuickSort

public class QuickSort {

    public int[] sort(int[] list) {
        quickSort(0, list.length - 1, list);
        return list;
    }

    public void quickSort(int start, int end, int[] list) {
        if (start >= end) return;
        int p = partition(start, end, list);
        quickSort(start, p, list);
        quickSort(p + 1, end, list);
    }

    private int partition(int start, int end, int[] list) {
        // First element
        int pivot = list[start];
        int pivotPoint = start;
        for (int index = start + 1; index <= end; index++) {
            if (list[index] < pivot) {
                pivotPoint = pivotPoint + 1;
                swap(pivotPoint, index, list);
            }
        }
        swap(start, pivotPoint, list);
        return pivotPoint;
    }

    private void swap(int i, int j, int[] list) {
        int temp = list[i];
        list[i] = list[j];
        list[j] = temp;
    }
}

SelectionSort

public class SelectionSort {
    public int[] sort(int[] input) {
        int size = input.length;
        for (int i = 0; i < size; i++) {
            int index = i;
            int currentMin = input[i];
            for (int j = i+1; j < size; j++) {
                int y = input[j];
                if (y < currentMin) {
                    currentMin = y;
                    index = j;
                }
            }
            int x = input[i];
            input[i] = input[index];
            input[index] = x;
        }
        return input;
    }
}

ShellSort 

public class ShellSort {
    public int[] sort(int[] a) {
        double passes = Math.floor(Math.log(a.length));
        while (passes > 1) {
            int increment = (int) (Math.pow(2, passes) - 1);
            for (int start = 0; start < increment; start++) {
                insertSort(start, increment, a);
            }
            passes = passes -1;
        }
        insertSort(0, 1, a);
        return a;
    }

    public void insertSort(int start, int increment, int[] a) {
        int j, k, temp;

        for (int i = start + increment; i < a.length; i += increment) {
            j = i;
            k = j - increment;
            if (a[j] < a[k]) {
                temp = a[j];
                do {
                    a[j] = a[k];
                    j = k;
                    k = j - increment;
                } while (j != start && a[k] > temp);
                a[j] = temp;
            }
        }
    }
}

Friday, July 13, 2012

Google Maps - Display points with different markers

If you want to display different points with different markers this is for you.  Say you want to display points with two markers, let's first create markers:

Let's get started:

function initialize() {
      if (GBrowserIsCompatible()) {
        var map = new GMap2(document.getElementById("map_canvas"));
        map.setCenter(new GLatLng(28.2,-89.6), 6);
        map.addControl(new GSmallMapControl());
        map.addControl(new GMapTypeControl());
   
        // Create our "tiny" marker icon
        var greenIcon= new GIcon(G_DEFAULT_ICON);
        greenIcon.image = "http://www.google.com/intl/en_us/mapfiles/ms/icons/green-dot.png";
        greenmarker = { icon:greenIcon };

        var redIcon= new GIcon(G_DEFAULT_ICON);
        redIcon.image = "http://www.google.com/intl/en_us/mapfiles/ms/icons/red-dot.png";
        redmarker = { icon:redIcon };

        var greenIcon= new GIcon(G_DEFAULT_ICON);
        greenIcon.image = "http://www.google.com/intl/en_us/mapfiles/ms/icons/green-dot.png";
        greenmarker = { icon:greenIcon };

        var redIcon= new GIcon(G_DEFAULT_ICON);
        redIcon.image = "http://www.google.com/intl/en_us/mapfiles/ms/icons/red-dot.png";
        redmarker = { icon:redIcon };


Now let's create a set of data points:

var locations = [['42001', 26.0, - 90.0,    1],
['42002',26.0, -94.0, 2],
['42007',30.1, -88.9, 3],
['42019',27.9, -95.0, 4],
['42020',27.0, -96.5, 5],
['42035',29.2, -94.4, 6],
['42036',28.5, -84.5, 7],
['42038',27.4, -92.6, 8],
['42039',28.8, -86.0, 9],
['42040',29.2, -88.3, 10],  ];

Now, let's create marker with the data point and marker options:

function createMarker(point, moption, id) {
      var marker = new GMarker(point, moption);


      GEvent.addListener(marker, "click", function() {
        marker.openInfoWindow("Point " + id + "");
      });
      return marker;
 }

Putting all together:

// Using first marker
for (i = 0; i < locations.length; i++) {
  var latlng = new GLatLng(locations[i][1], locations[i][2]);
   map.addOverlay(createMarker(latlng, greenmarker, locations[i][0]));
}

//Using second marker 
map.addOverlay(createMarker(new GLatLng(29.3, -90.0), redmarker, 'GDIL1'));
  }
 }

Saturday, June 30, 2012

Virsh console - Issue and solution

I faced several issue when I tried to use "virsh console " in KVM. It simply hangs in following line: 

"Escape character is ^]" 

 After trying several things here is how I solved the problem:

Step 1: If the VM is running destroy it (virsh destroy
Step 2: Mount the image (following instructions are for raw disk image for Ubuntu host)

kpartx -av /location-to-disk-image 
mount /dev/mapper/loop0p2 /path-to-mount

[Note: kpartx list out several mappers and you need to pick the correct one, just play around it you will find the correct one to map. Correct one is one with grub directories] 

vi /path-to-mount/grub2/grub.cfg (in your case it might be grub) 

add "console=ttyS0" as shown below: 

kernel /vmlinuz ro a-set-of-values console=ttyS0 
umount /path-to-mount 
kpartx -dv /location-to-disk-image 

Step 3: Now start the VM "virsh start
Step 4: Console to the VM "virsh console "

Sunday, February 05, 2012

Install XEN dom0 and domU on Ubuntu 11.10

I had trouble getting Xen working on Ubuntu 10.04 and had to do many things, in fact still failing with LVM. Luckily with Ubuntu 11.10 installing Xen dom0 and domU is much easier, here is the steps to get dom0 working on Ubuntu.

Creating dom0


Login as root (sudo su)

Install required packages and the hypervisor

apt-get install xen-hypervisor-4.1-amd64
apt-get install xen-utils-4.1
apt-get install xenwatch
apt-get install xen-tools
apt-get install xen-utils-common
apt-get install xenstore-utils
apt-get install virtinst
apt-get install virt-viewer
apt-get install virt-manager

Now you have installed everything you need to run your dom0. Before you restart your system edit “/etc/xen/xend-config.sxp” and add the following (rather uncomment)

(xend-unix-server yes)

Next restart your system and pick the xen-kernel from the grub menu (if you want you can edit /etc/default to pick the correct kernel automatically). Now you are good to go.

Simply run “xm info” or “xm list”, you will see your system is running.


Creating a domU


Now Here are the steps to create an Ubuntu Lucid guest (domU) using xen-create-image utility, for that follow following steps.


Step1: go to /etc/xen-tools (edit xen-tools.conf or create a new conf file)
Step 2: Configure it as follows


dir = /mnt/xen
install-method = debootstrap
size = 8Gb # Disk image size.
memory = 1024Mb # Memory size
swap = 128Mb # Swap size
# noswap = 1 # Don't use swap at all for the new system.
fs = ext3 # use the EXT3 filesystem for the disk image.
dist = lucid # Default distribution to install.
image = sparse
dhcp = 1
nameserver = IP address of DNS Server
bridge = virbr0
kernel = /boot/vmlinuz-`uname -r`
initrd = /boot/initrd.img-`uname -r`
mirror = http://archive.ubuntu.com/ubuntu
ext3_options = noatime,nodiratime,errors=remount-ro
ext2_options = noatime,nodiratime,errors=remount-ro
xfs_options = defaults
reiserfs_options = defaults
btrfs_options = defaults
boot = 1
passwd = 1
serial_device = hvc0
disk_device = xvda

Step 4: now run
xen-create-image –hostname=Ubuntu10

Step 3: In the middle of the image creation it will ask for the root password, simply put the password you like. Your domain will start automatically

Step 4: You can login to it using

xm console Ubuntu10


to terminate
xm destroy Ubuntu10

To restart
xm create –c /etc/Ubuntu10.cfg

Tuesday, July 26, 2011

Yet another success story of Apache Axis2

Axis2 is one of the very successful Apache projects in many different ways; however I am not going to discuss the quality of the project of customers who use the project, rather a totally different area of its success.

Axis2 was started with six core members (all from Sri Lanka) and later joined many members to the project. The most interesting and notable thing about Axis2 is all the initial members entered graduated school and four of them have already become PhD holders (Srinath, Jaliya, Chinthaka and Chathura). Not stropping from that second, third, and forth (may be fifth) generations of contributors have entered graduate school and are now in the pipeline to complete their Ph.D.'s in the next few years (at least 12).

Counting all, in the history of Apache software foundation Axis2 will be the first project to produce so many PhD holders. I think this is a huge success of the project, and many credits should go to Sanjiva for motivating all of them to select the correct path.

Wednesday, February 23, 2011

A new book on Apache Axis2

Happily, we were able to publish the second book on Apache Axis2. I published the first book in 2008 (Quickstart Apache Axis2), and after three years, now the second book is also available (Apache Axis2 Web Services). Our initial plan was to publish the book this time last year, but due to usual reasons it got delayed. We have improved the book a lot and added lot of new and interesting contents.
I really want to thank my co-author Afkham Azeez, who helped me a lot to add new chapters and to make the book ready for building advanced web services with Axis2. We started Axis2 in way back 2004, and needless to say this project will not exists without the initial members and their tremendous contributions: Srinath Perera, Ajith Ranabahu, Eran Chinthaka, Davanum Srinivas, Glen Daniels, Sanjiva Weerawarana, Paul Fremantle, Jaliya Ekanayake, Chathura Herath, Ruchith Fernando, and Chamikara Jayalath. In addition, special thanks goes to our second generation contributors: Thilina Gunarathne, Keith Chapman, Amila Suriyaarachchi, Sanka Samaranayake, Lahiru Sandakith, Nandana , Saminda Abeyruwan and many more. Not least, but last all the members of the Axis2 project who has contributed a lot to make the project a success. Thank you all.


Hope you will learn from this book and enjoy it.