Video taken on 22-05-2010 of the Google page which featured Pac Man Game.
It was totally JavaScript… This is FireBug‘s real-time analysis of page source dynamic behavior
Google Pac Man- Awesome JavaScripting!
Reply
My Definition of Life
Forget the past except moments I helped some one,
live for today, plan only for tomorrow,
expect & mitigate risk,
have a life goal,
don’t give up
despite any thing be nice.
That’s my definition of life
–Sudeera Jaysekara
True Friend
Quick Sort – Array Based
package project;
public class QuickSort {
Comparable theArray[];
public void sort(Comparable theArray[]) {
this.theArray = theArray;
sort_recursive(0, theArray.length - 1);
}
private void sort_recursive(int partition_start, int partition_end) {
if (partition_start == partition_end) {
return; //base case , it the sub array length is zero, then sorted
}
int pivotLocation = partition(partition_start, partition_end); //use the partition algorythm to find pivot location
if (pivotLocation != partition_start) { //if the pivot is not the smallest value
sort_recursive(partition_start, pivotLocation - 1); //then quick sort the values before the partition
}
if (pivotLocation != partition_end) { //if the pivot is not the largest value
sort_recursive(pivotLocation + 1, partition_end); //then quick sort the values after the partition
}
}
//partition algorythm
private int partition(int bottom, int top) {
int down = bottom;
int up = top;
Comparable pivot = theArray[bottom];
while (true) {
while (!(theArray[down].compareTo(pivot) > 0)) {
down++; // increase down pointer untill a value greater than pivot value is found
if (down == top) {
break; //the boundry conditions of the partition
}
}
while (!(theArray[up].compareTo(pivot) <= 0)) {
up--; // decrease up pointer untill a value less than or equal to pivot value is found
if (up == bottom) {
break;//the boundry conditions of the partition
}
}
if (up > down) {
Swapper.swap(theArray, up, down); //if up is greater than down then swap the up position value and down position value
} else {
Swapper.swap(theArray, up, bottom); //else then swap the up position value and pivot position value, here the pivot is selected as the first element in the sub array
return up; //pivot location is found, which is the up position
}
}
}
}
package project;
//Swaps the values of two locations in a specific Array
public class Swapper {
public static void swap(Comparable[] theArray, int position1, int position2) {
Comparable temp = theArray[position1];
theArray[position1] = theArray[position2];
theArray[position2] = temp;
}
}
Shell Sort – Array Based
package project;
public class ShellSort {
Comparable theArray[];
int length;
public void sort(Comparable theArray[]) {
this.theArray = theArray;
length = theArray.length;
shell_sort();
}
private void shell_sort() {
int gap = length / 2;
while (true) {
for (int i = length - 1; i > i - gap && i > -1; i--) { //visit each element within one gap length from the last position , and check if one gap length is more than the array size
for (int j = i; j - gap > -1; j = j - gap) { //visit each element one gap length apart from each other.
if (theArray[j - gap].compareTo(theArray[j]) > 0) { //comapare the two elements which are one gap length apart from each other
Swapper.swap(theArray, j, j - gap); // if the left element is greater than the right element then swap the left and right elemnts
}
}
}
if (gap == 1) {
return; //if gap length is one then the array is sorted
}
gap = gap / 2; //reduce the gap size by half and repeat the above insertion sort
}
}
}
package project;
//Swaps the values of two locations in a specific Array
public class Swapper {
public static void swap(Comparable[] theArray, int position1, int position2) {
Comparable temp = theArray[position1];
theArray[position1] = theArray[position2];
theArray[position2] = temp;
}
}
Radix Sort – Integer Character – Array Based
package project;
public class RadixSort {
String theArray[];
int maxLength = 0;
public char[] sort(char c[]) {
toBinary(c);
padZeros();
radixSort();
for (int j = 0; j < theArray.length; j++) {
int b = Integer.parseInt(theArray[j], 2);
c[j] = (char) b;
}
return c;
}
public int[] sort(int c[]) {
toBinary(c);
padZeros();
radixSort();
for (int j = 0; j < theArray.length; j++) {
c[j] = Integer.parseInt(theArray[j], 2);
}
return c;
}
private void toBinary(char x[]) { //convertion to binary
theArray = new String[x.length];
for (int i = 0; i < x.length; i++) {
theArray[i] = Integer.toBinaryString(x[i]);
}
}
private void toBinary(int x[]) { //convertion to binary
theArray = new String[x.length];
for (int i = 0; i < x.length; i++) {
theArray[i] = Integer.toBinaryString(x[i]);
}
}
//radix sort done using stright radix sort
private void radixSort() {
bit_evaluvation:
for (int bit = theArray[0].length() - 1; bit > -1; bit--) {
int zero, one = 0;
//find the first occurence of one, upto that point it has zeros
while (theArray[one].charAt(bit) != '1') {
one++;
if (one == theArray.length) {
continue bit_evaluvation; //All zeros no need to process this bit
}
}
while (true) {
//find the next occurence of zero
zero = one;
while (theArray[zero].charAt(bit) != '0') {
zero++;
if (zero == theArray.length) {
continue bit_evaluvation;// if it cannnot find a zero then evaluvation for this bit is finished
}
}
//shift array elemets from i to zero position by one element and copy the zero position value to the i position
String tmp = theArray[zero];
int j = zero;
while (j - 1 >= one) {
theArray[j] = theArray[--j];
}
theArray[one] = tmp;
one++; //go to next position, which is a one and repeat the above operation
if (one == theArray.length) {
continue bit_evaluvation;// if it cannnot find a next one then evaluvation for this bit is finished
}
}
}
}
private void padZeros() { //fill zeros to the front so that all binary strings are of equal length
for (String s : theArray) {
if (s.length() > maxLength) {
maxLength = s.length();
}
}
for (int j = 0; j < theArray.length; j++) {
theArray[j] = String.format("%0" + maxLength + "d", Long.parseLong(theArray[j]));
}
}
}
Heap Sort – Array Based
package project;
public class HeapSort {
Comparable theArray[];
int length;
public void sort(Comparable theArray[]) {
this.theArray = theArray;
length = theArray.length;
bulidHeap(); //build the heap using the supplied array
sortHeap(); //sort the created heap
}
private void bulidHeap() {
for (int i = (length / 2) - 1; i > -1; i--) { //The second half of the array are leaf nodes, thus we will consider only the first half
downHeap(i); //ensure heap condition is valid for each node which is a parent
}
}
private void downHeap(int parent) {
int greater = parent; //Assume the parent is greater than both the children
while (true) {
//find the index of the left child
int left_child = parent * 2 + 1;
//if there is no left child,then the heap condition is valid
if (left_child >= length) {
return;
}
//find if the left child has a greater value
if (theArray[left_child].compareTo(theArray[parent]) > 0) {
greater = left_child;
}
//find if a right child also exisits which is greater than the left child
if (left_child + 1 < length && theArray[left_child + 1].compareTo(theArray[left_child]) > 0) {
greater = left_child + 1; //left_child+1 = right child's position
}
//if the parent is greater than both the children,then the heap condition is valid
if (parent == greater) {
return;
}
//swap the greater child with the parent
Swapper.swap(theArray, parent, greater);
//Consider the parents new location and evaluvate its heap condition with respect to its new children
parent = greater;
}
}
private void sortHeap() {
while (length != 1) { //do untill only one node remains unsorted, which will be the smallest node
Swapper.swap(theArray, 0, --length); //reduce the unsorted length by 1 and the swap the node at the last unsorted position with the root
downHeap(0);//ensure the heap condition for the new root value
}
}
}
package project;
//Swaps the values of two locations in a specific Array
public class Swapper {
public static void swap(Comparable[] theArray, int position1, int position2) {
Comparable temp = theArray[position1];
theArray[position1] = theArray[position2];
theArray[position2] = temp;
}
}
Specification of a ListNode in a LinkedList
public class ListNode {
Object element;
ListNode next;
public ListNode(Object x, ListNode n) {
element = x;
next = n;
}
public ListNode(Object x) {
this(x, null);
}
}
Stack implemented using Linked lists
/* Linked list based Stack implementation */
public class StackUsingLinkedList {
private ListNode tosNode; // The node which represents the top of the Stack
public StackUsingLinkedList() { // Creates a stack with no nodes
tosNode = null;
}
public boolean isEmpty() { // Checks if the Stack is empty
return (tosNode == null);
}
public void makeEmpty() { // Empty the Stack by removing linked nodes
tosNode = null;
}
public void push(Object x) { // Create new node and add the data, point to tos node, and make new tos
tosNode = new ListNode(x, tosNode);
}
public void pop() throws Exception {
if (isEmpty()) { //Check if empty before pop
throw new Exception("The Stack is empty: Stack pop");
}
tosNode = tosNode.next; //make the new tos point tos next of current tos
}
public Object top() throws Exception {
if (isEmpty()) { //Check if empty before top
throw new Exception("The Stack is empty: Stack top");
}
return tosNode.element; //return the element
}
public Object topAndPop() throws Exception {
Object returnValue = top(); //keep the top node's value
pop(); // pop and remove the top node
return returnValue; // return the top node's value
}
}
Infix to Postfix convertor using Stacks
public class PostfixConverter {
/* References
* http://scriptasylum.com/tutorials/infix_postfix/algorithms/infix-postfix/index.htm
* http://www.cis.temple.edu/~koffman/cis223/InfixToPostfix.doc
*/
public String convertPostfix(String x) throws Exception {
String postfixString = ""; //Set postfix string to empty string
StackUsingLinkedList operatorStack = new StackUsingLinkedList(); //Create an empty operator stack
for (int i = 0; i < x.length(); i++) { //Repeat unitll end of the string
char c = x.charAt(i); //Get the next token in the infix string
if ((!(Character.isDigit(c)) && !(Character.isLetter(c))) && !(c == ('+') || c == ('*') || c == ('-') || c == ('/') || c == ('(') || c == (')')) || (c == ' ')) {
continue; //Used to avoid spaces and invalid characters, + - * / are not digits or characters
}
if (!(c == ('+') || c == ('*') || c == ('-') || c == ('/') || c == ('(') || c == (')'))) //If next token is an operand (begins with digit)
{
postfixString += c; //append it to postfix string
} else {
while (true) { // Repeat until the next op is pushed onto the stack.
//If operator stack is empty or next op is ‘(‘, push next operator onto stack
if (operatorStack.isEmpty() || c == '(') {
operatorStack.push(c);
break; //the operator is pushed on to the stack, no need for further processing c
}
//Else if precedence of this operator is greater than one on top of the stack then push to stack
else if (precedence(c) > precedence(operatorStack.top())) {
operatorStack.push(c);
break; //the operator is pushed on to the stack, no need for further processing c
}
else {
//For the case of brackets ---------------------------------
if (c == ')') {
while (!(operatorStack.top().toString().equals("("))) { //Pop and append until the opening bracket is reached
postfixString += operatorStack.topAndPop();
}
operatorStack.pop(); //remove the opening bracket, no need for it
break;
}
//End of case for brackets--------------------------------
//Then this operator has lower precedence, then top and pop the stack untill all higher operators are appened to the string
postfixString += operatorStack.topAndPop();
}
}
}
}
//At end of string, keep popping stack until stack is empty
while (!operatorStack.isEmpty()) {
postfixString += operatorStack.topAndPop();
}
//Finally return the postfix String
return postfixString;
}
// The method checks the precedence of each operator
private int precedence(Object x) {
if (x.toString().equals("*") || x.toString().equals("/")) {
return 2;
} else if (x.toString().equals("+") || x.toString().equals("-")) {
return 1;
} else {
return 0;
}
}
}