Nov 23, 2012

Strategy Design Pattern

Strategy Pattern
The strategy pattern allows you to use different business rules or algorithms depending on the context in which they occur

When should I use the Strategy Pattern?
1. You can perform an operation in different ways
2. You want to select the operation dynamically at the runtime
3. You want to add new ways without modifying the application code

Real World Examples
1. File Compression Techniques
2. Layout Managers used by Containers in Java Swing
3. Comparators used in Arrays sort function

Read more ...

Nov 22, 2012

Insertion Sort in Java using Generics

A generic implementation of Insertion Sort in Java

 1 import org.junit.Assert;
 2 import org.junit.Test;
 3 
 4 class GenericInsertionSorter
 5 {
 6     public <T extends Comparable<T>> void sort(T[] elems) {
 7         int size = elems.length;
 8 
 9         for (int outerLoopIdx = 1; outerLoopIdx < size; ++outerLoopIdx) {
10             for (int innerLoopIdx = outerLoopIdx; innerLoopIdx > 0; --innerLoopIdx) {
11                 if (elems[innerLoopIdx - 1].compareTo(elems[innerLoopIdx]) > 0) {
12                     T temp = elems[innerLoopIdx - 1];
13                     elems[innerLoopIdx - 1] = elems[innerLoopIdx];
14                     elems[innerLoopIdx] = temp;
15                 }
16             }
17         }
18     }
19 }
20 
21 public class InsertionSortTester
22 {
23     private String[] unsortedNames = new String[] {
24             "Pankaj",
25             "Paresh",
26             "Ankit",
27             "Sankalp",
28             "Aditya",
29             "Prem",
30             "Rocket",
31             "Singh",
32             "Alabama",
33             "Alaska",
34             "Animal" };
35 
36     private String[] sortedNames = new String[] {
37             "Aditya",
38             "Alabama",
39             "Alaska",
40             "Animal",
41             "Ankit",
42             "Pankaj",
43             "Paresh",
44             "Prem",
45             "Rocket",
46             "Sankalp",
47             "Singh" };
48 
49     @Test
50     public void testStringSort() {
51         GenericInsertionSorter ss = new GenericInsertionSorter();
52         ss.sort(unsortedNames);
53         Assert.assertArrayEquals(unsortedNames, sortedNames);
54     }
55 }

Read more ...

Insertion Sort in C++ using templates

Insertion Sort
An efficient elementary sort method which places each element in it's proper place among the elements which are already placed
  1 #include <iostream>
  2 #include <string.h>
  3 
  4 template <typename T>
  5 class InsertionSort
  6 {
  7     public:
  8         InsertionSort();
  9         ~InsertionSort();
 10 
 11         void sort(T arr[], int size);
 12     private:
 13         void compareExchange(T arr[], int l, int r);
 14         bool greater(T left, T right);
 15 };
 16 
 17 //Constructor
 18 template <typename T>
 19 InsertionSort<T>::InsertionSort(){}
 20 
 21 //Destructor
 22 template <typename T>
 23 InsertionSort<T>::~InsertionSort(){}
 24 
 25 template <typename T>
 26 void InsertionSort<T>::sort(T arr[], int size)
 27 {
 28     for(int i = 1; i < size; ++i)
 29     {
 30         for(int j = i; j > 0; --j)
 31         {
 32             compareExchange(arr, j-1, j);
 33         }
 34     }
 35 }
 36 
 37 template <typename T>
 38 void InsertionSort<T>::compareExchange(T arr[], int l, int r)
 39 {
 40     if(greater(arr[l], arr[r]))
 41     {
 42         T temp = arr[l];
 43         arr[l] = arr[r];
 44         arr[r] = temp;
 45     }
 46 }
 47 
 48 template <typename T>
 49 bool InsertionSort<T>::greater(T left, T right)
 50 {
 51     return left > right;
 52 }
 53 
 54 template <>
 55 bool InsertionSort<const char*>::greater(const char *left, const char *right)
 56 {
 57     return strcmp(left, right) > 0;
 58 }
 59 
 60 template <typename T>
 61 void print(T arr[], int size)
 62 {
 63     for(int i = 0; i < size; ++i)
 64         std::cout << arr[i] << " ";
 65     std::cout << std::endl;
 66 }
 67 
 68 template <>
 69 void print(std::string arr[], int size)
 70 {
 71     for(int i = 0; i < size; ++i)
 72         std::cout << arr[i].c_str() << " ";
 73     std::cout << std::endl;
 74 }
 75 
 76 template <>
 77 void print(const char *ptrArray, int size)
 78 {
 79     for(int i = 0; i < size; ++i)
 80         std::cout << ptrArray[i] << " ";
 81     std::cout << std::endl;
 82 }
 83 
 84 int main()
 85 {
 86     int arr[] = { 10, 65, 35, 25, 15, 75, 85, 45, 65 };
 87     InsertionSort<int> isInt;
 88     isInt.sort(arr, 9);
 89     print(arr, 9);
 90 
 91     std::string strArr[] = { "pankaj", "paresh", "hello", "world", "ankit", "aditya", "sankalp", "aladdin" };
 92     InsertionSort<std::string> isString;
 93     isString.sort(strArr, 8);
 94     print(strArr, 8);
 95 
 96     const char* ptrArray[] = { "pankaj", "paresh", "hello", "world", "ankit", "aditya", "sankalp", "aladdin", "george"};
 97     InsertionSort<const char*> isPtr;
 98     isPtr.sort(ptrArray, 9);
 99     print(ptrArray, 9);
100 
101     return 0;
102 }

Read more ...

Nov 21, 2012

Selection Sort in Java using Generics

A generic implementation of Selection Sort in Java using Generics

 1 import org.junit.Assert;
 2 import org.junit.Test;
 3 
 4 class GenericSelectionSorter
 5 {
 6     public <T extends Comparable<T>> void sort(T[] elems) {
 7         int size = elems.length;
 8 
 9         for (int outerLoopIdx = 0; outerLoopIdx < size - 1; ++outerLoopIdx) {
10             int min = outerLoopIdx;
11             for (int innerLoopIdx = outerLoopIdx; innerLoopIdx < size; ++innerLoopIdx) {
12                 if (elems[min].compareTo(elems[innerLoopIdx]) > 0) {
13                     min = innerLoopIdx;
14                 }
15             }
16 
17             // exchange elements at outerIndexLoop and min positions
18             T temp = elems[min];
19             elems[min] = elems[outerLoopIdx];
20             elems[outerLoopIdx] = temp;
21         }
22     }
23 }
24 
25 public class SelectionSortTester
26 {
27     private String[] unsortedNames = new String[] {
28             "Pankaj",
29             "Paresh",
30             "Ankit",
31             "Sankalp",
32             "Aditya",
33             "Prem",
34             "Rocket",
35             "Singh",
36             "Alabama",
37             "Alaska",
38             "Animal" };
39 
40     private String[] sortedNames = new String[] {
41             "Aditya",
42             "Alabama",
43             "Alaska",
44             "Animal",
45             "Ankit",
46             "Pankaj",
47             "Paresh",
48             "Prem",
49             "Rocket",
50             "Sankalp",
51             "Singh" };
52 
53     @Test
54     public void testStringSort() {
55         GenericSelectionSorter ss = new GenericSelectionSorter();
56         ss.sort(unsortedNames);
57         Assert.assertArrayEquals(unsortedNames, sortedNames);
58     }
59 }

Read more ...

The Selection Sort in C++

Selection Sort
An elementary sorting technique which finds the smallest element in the array and then exchanges it with the element in the first position
 1 #include <iostream>
 2 
 3 class SelectionSort
 4 {
 5     public:
 6         SelectionSort();
 7         ~SelectionSort();
 8 
 9         void sort(int arr[], int size);
10 
11     private:
12         void exchange(int &x, int &y);
13 };
14 
15 //Constructor
16 SelectionSort::SelectionSort() {}
17 
18 //Destructor
19 SelectionSort::~SelectionSort() {}
20 
21 void SelectionSort::sort(int arr[], int size)
22 {
23     for(int outerLoopIdx = 0; outerLoopIdx < size - 1; ++outerLoopIdx)
24     {
25         int min = outerLoopIdx;
26         for(int innerLoopIdx = outerLoopIdx + 1; innerLoopIdx < size; ++innerLoopIdx)
27         {
28             if(arr[min] > arr[innerLoopIdx])
29             {
30                 min = innerLoopIdx;
31             }
32         }
33         exchange(arr[outerLoopIdx], arr[min]);
34     }
35 }
36 
37 void SelectionSort::exchange(int &x, int &y)
38 {
39     int t = x;
40     x = y;
41     y = t;
42 }
43 
44 void print(int arr[], int size)
45 {
46     for(int i = 0; i < size; ++i)
47         std::cout << arr[i] << " ";
48 }
49 
50 int main()
51 {
52     int arr[] = { 10, 65, 35, 25, 15, 75, 85, 45, 65 };
53     SelectionSort ss;
54     ss.sort(arr, 9);
55     print(arr, 9);
56 }

Output:

Read more ...

Bubble Sort in Java using Generics

Below is a generic implementation of Bubble Sort in Java

 1 import org.junit.Assert;
 2 import org.junit.Test;
 3 
 4 class GenericBubbleSorter<T extends Comparable<T>>
 5 {
 6     public void sort(T[] elems) {
 7         int size = elems.length;
 8 
 9         for (int outerLoopIdx = 0; outerLoopIdx < size; ++outerLoopIdx) {
10             for (int innerLoopIdx = 0; innerLoopIdx < (size - outerLoopIdx - 1); ++innerLoopIdx) {
11                 if (elems[innerLoopIdx].compareTo(elems[innerLoopIdx + 1]) > 0) {
12                     T temp = elems[innerLoopIdx];
13                     elems[innerLoopIdx] = elems[innerLoopIdx + 1];
14                     elems[innerLoopIdx + 1] = temp;
15                 }
16             }
17         }
18     }
19 }
20 
21 public class BubbleSortTester
22 {
23     private String[] unsortedNames = new String[] {
24             "Pankaj",
25             "Paresh",
26             "Ankit",
27             "Sankalp",
28             "Aditya",
29             "Prem",
30             "Rocket",
31             "Singh",
32             "Alabama",
33             "Alaska",
34             "Animal" };
35 
36     private String[] sortedNames = new String[] {
37             "Aditya",
38             "Alabama",
39             "Alaska",
40             "Animal",
41             "Ankit",
42             "Pankaj",
43             "Paresh",
44             "Prem",
45             "Rocket",
46             "Sankalp",
47             "Singh" };
48 
49     @Test
50     public void testStringSort() {
51         GenericBubbleSorter<String> bs = new GenericBubbleSorter<String>();
52         bs.sort(unsortedNames);
53         Assert.assertArrayEquals(unsortedNames, sortedNames);
54     }
55 }

Read more ...

Nov 20, 2012

The Bubble Sort in C++

Bubble Sort
This sort gets its name from the way smaller/larger elements gets to the top of the list using bubble comparison
 1 #include <iostream>
 2 
 3 class BubbleSort
 4 {
 5     public:
 6         BubbleSort(){}
 7         ~BubbleSort(){}
 8         void sort(int arr[], int size);
 9 };
10 
11 void BubbleSort::sort(int arr[], int size)
12 {
13     //With every iteration in outer loop, the next maximum element is moved to it's correct position
14     for(int outerLoopIdx = 0; outerLoopIdx < size ; ++outerLoopIdx)
15     {
16         for(int innerLoopIdx = 0; innerLoopIdx < (size - outerLoopIdx - 1); ++innerLoopIdx)
17         {
18             //Comparing two subsequent elements OR bubble comparison
19             //Placing the larger element on the right
20             if(arr[innerLoopIdx] > arr[innerLoopIdx + 1])
21             {
22                 int temp = arr[innerLoopIdx];
23                 arr[innerLoopIdx] = arr[innerLoopIdx + 1];
24                 arr[innerLoopIdx + 1] = temp;
25             }
26         }
27     }
28 }
29 
30 void print(int arr[], int size)
31 {
32     for(int i = 0; i < size; ++i)
33         std::cout << arr[i] << " ";
34     std::cout << std::endl;
35 }
36 
37 int main()
38 {
39     int arr[] = { 10, 65, 35, 25, 15, 75, 85, 45, 65 };
40     BubbleSort bs;
41     bs.sort(arr, 9);
42     print(arr, 9);
43     return 0;
44 }

Output

References:
Bubble Sort Animation
Read more ...

Nov 14, 2012

Template Method Design Pattern

Template Method Pattern
Template method pattern defines the skeleton of an algorithm in a method referred to as the Template Method deferring some steps to subclasses. The pattern is mostly used for building application frameworks where the framework implement the invariant pieces of the application's architecture and provide place holders or hooks for client customizations.

Examples from Java API
1. The Comparable interface defines the compareTo method which is a template method
2. The java applet class provides init, start, stop, paint and destroy hook methods for creating an applet
3. The actionPerformed method in ActionListener interface is a template method
4. The doGet and doPost methods in abstract class HttpServlet are examples of template methods


Read more ...

Nov 11, 2012

A simple http server in java

A web server is an application which delivers web pages using HTTP protocol
The application explained below is a simple http server application which runs on port 8080 and serves contents from the directory C:/Web. The server handles each client request in a new worker thread.
package com.pankaj.webserver;

import java.io.IOException;
import java.net.ServerSocket;
import java.net.Socket;

/**
 * File: WebServer.java
 */
public class WebServer
{
    private static final int PORT = 8080;
    private static ServerSocket listenerSocket = null;
    private static int requestId = 0;

    public static void main(String[] args) throws IOException
    {
        ConsoleLogger.LogMessage("Starting simple http server");
        listenerSocket = new ServerSocket(PORT);

        ConsoleLogger.LogMessage("Server started on port " + listenerSocket.getLocalPort());
        while (true) {
            Socket socket = listenerSocket.accept();
            ConsoleLogger.LogMessage("Client connected on port " + socket.getPort());
            new Worker(new RequestHandler(++requestId, socket));
        }
    }
}

Read more ...

Nov 4, 2012

Removing BOM character from a string in Java

The below code checks if the BOM character is present in a string. If present, removes and prints the string with skipped bom.

import java.io.UnsupportedEncodingException;

/**
 * File: BOM.java
 * 
 * check if the bom character is present in the given string print the string
 * after skipping the utf-8 bom characters print the string as utf-8 string on a
 * utf-8 console
 */

public class BOM
{
    private final static String BOM_STRING = "Hello World";
    private final static String ISO_ENCODING = "ISO-8859-1";
    private final static String UTF8_ENCODING = "UTF-8";
    private final static int UTF8_BOM_LENGTH = 3;

    public static void main(String[] args) throws UnsupportedEncodingException {
        final byte[] bytes = BOM_STRING.getBytes(ISO_ENCODING);
        if (isUTF8(bytes)) {
            printSkippedBomString(bytes);
            printUTF8String(bytes);
        }
    }

    private static void printSkippedBomString(final byte[] bytes) throws UnsupportedEncodingException {
        int length = bytes.length - UTF8_BOM_LENGTH;
        byte[] barray = new byte[length];
        System.arraycopy(bytes, UTF8_BOM_LENGTH, barray, 0, barray.length);
        System.out.println(new String(barray, ISO_ENCODING));
    }

    private static void printUTF8String(final byte[] bytes) throws UnsupportedEncodingException {
        System.out.println(new String(bytes, UTF8_ENCODING));
    }

    private static boolean isUTF8(byte[] bytes) {
        if ((bytes[0] & 0xFF) == 0xEF && 
            (bytes[1] & 0xFF) == 0xBB && 
            (bytes[2] & 0xFF) == 0xBF) {
            return true;
        }
        return false;
    }
}


The following stackoverflow article talks in detail about detecting and skipping the BOM

Read more ...

Byte Order Mark (BOM) character

BOM character
1. BOM is a Unicode character used to identify the endianness of the text file or stream.
2. The UTF-8 representation of the BOM is the byte sequence 0xEF, 0xBB, 0xBF.
3. A text editor using ISO-8859-1 as character encoding will display the characters  for BOM.
4. BOM has no meaning in UTF-8 apart from signalling that the byte stream that follows is encoded in UTF-8

import java.nio.charset.Charset;

/**
 * File: BOM.java
 * 
 * The following class converts a string having bom character
 * from ISO-8859-1 encoding type to UTF-8 and back
 */
public class BOM
{
    public static void main(String[] args) throws Exception
    {
        System.out.println("Default Encoding: " + Charset.defaultCharset());

        //
        // Displays a simple string with bom prepended.
        // Uses system default character encoding
        //
        String bomString = "Hello World";
        System.out.println(bomString + " Length: " + bomString.length());

        //
        // convert string with bom character to utf string
        //
        byte[] byteArrayISO = bomString.getBytes("ISO-8859-1");
        String utfString = new String(byteArrayISO, "UTF-8");
        System.out.println(utfString + " Length: " + utfString.length());

        //
        // convert the utf string back to windows character encoding
        //
        byte[] byteArrayUTF = utfString.getBytes("UTF-8");
        String winString = new String(byteArrayUTF, "ISO-8859-1");
        System.out.println(winString + " Length: " + winString.length());
    }
}

Output of the above program when run on a UTF-8 supported console
$ java BOM
Default Encoding: windows-1252
Hello World Length: 17
Hello World Length: 14
Hello World Length: 17

Read more ...