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