Saturday, May 18, 2013

How to create Object Pools in JAVA


Note: For simplicity sake I have taken User object as an example.In real world one should consider pooling when object creation is considered costly. For example database connections
Object pool is a set of ready to use objects. Clients can borrow the object from the pool and the object will be returned back to the pool when done so that it can be reused. Data base connection pool is a well-known example of object pooling. Creating our own object pooling will usually take more resources as one has to concentrate on thread safety and one bag full of test cases for the pool.
Apache commons pool hides the complexity of implementing the pool and has nice set of factories through which we can define the life cycle methods of the pool which are to be pooled. More information on apache’s common pool can be found at http://commons.apache.org/proper/commons-pool/.
This post shows how to create object pool using apache’s common pool. Many websites allows users to register, login and logout features. First thing which strikes my mind is 90% of time developers will write an object to hold the user information.  If the unknown website we are talking about gets one lakh login requests we will end up creating one lakh user objects. Google this “why is object creation costly”, you will get handful of results saying why object creation is a costly operation. Instead of creating User object every time in our unknown website we can create an object pool with a set of pre initialized User objects. By doing this may be the application will be much faster in serving the requests and more efficient. Enough said already lets jump into the example
While creating object pool using apache’s common pool first thing we can do is create a factory class to create our objects which are to be pooled.  org.apache.commons.pool.BasePoolableObjectFactory will be the parent class for our factory. BasePoolableObjectFactory has lifecycle methods for the objects which are to be pooled. Below are the lifecycle methods
makeObject : called to create new instances which are to be pooled
activateObject: called before borrowing the object from pool
validateObject: called to validate object before retrieving and returning the object to the pool
passivateObject: called before returning the object to pool. We can use this method to do some clean up
destroyObject:called when the object is removed from pool for good.
package blog.itsvenkis.object.pool.factory;

import org.apache.commons.pool.BasePoolableObjectFactory;

import blog.itsvenkis.object.pool.domain.Poolable;

/**
 * @author itsvenkis
 *         A factory class which creates objects which are 
 *         in turn used by object pooling. Provides life cycle methods 
 *         of the object which is to be pooled. Objects created by 
 *         this factory are required to implement {@link blog.itsvenkis.object.pool.domain.Poolable}
 *         
 * @see org.apache.commons.pool.PoolableObjectFactory
 * @see org.apache.commons.pool.BasePoolableObjectFactory
 *
 */
@SuppressWarnings("unchecked")
public class ObjectPoolFactory extends BasePoolableObjectFactory{

    private final Class poolableObj;
    
    protected Class getPoolableObject(){
        return poolableObj;
    }
    
    //Use static factory method instead
    protected ObjectPoolFactory(Class poolableObj){
        this.poolableObj = poolableObj;
    }
    
    //Static factory method to create instance of this factory.
    public static ObjectPoolFactory newInstance(String className) throws ClassNotFoundException{
        Class poolObj= (Class) Class.forName(className);
        ObjectPoolFactory factory = new ObjectPoolFactory(poolObj);
        return factory;
    }
    
    @Override
    /**
     * called whenever an new instance is needed
     * @see org.apache.commons.pool.PoolableObjectFactory#makeObject
     */
    public Object makeObject() throws Exception {
        return poolableObj.newInstance();
    }
    
    /**
     * invoked on every instance when it is returned to the pool.
     * @see org.apache.commons.pool.PoolableObjectFactory#makeObject
     */
    public void passivateObject(Object obj) {
        if(obj instanceof Poolable){
            Poolable poolObj= (Poolable) obj;
            poolObj.clear();
        }else{
            throw new RuntimeException("Object has to be instance of Poolable");
        }
    }
    
    public boolean validateObject(Object obj){
        if(obj instanceof Poolable){
            return true;
        }
        return false;
    }

}
Next, create a service to retrieve and return the objects to the pool
package blog.itsvenkis.object.pool;

import org.apache.commons.pool.impl.StackObjectPool;

/**
 * @author itsvenkis
 * 
 *         This class provides operations to retrieve and return User objects
 *         to the object pool. The original pool itself is injected by spring 
 *         configuration file.
 *
 */
public class UserService {
 
 //pool of User objects. 
 private StackObjectPool userObjectPool;// Why isn't this a generic? can avoid unnecessary casting
 
 //getter
 public StackObjectPool getUserObjectPool() {
  return userObjectPool;
 }
 
 //setter
 public void setUserObjectPool(StackObjectPool userObjectPool) {
  this.userObjectPool = userObjectPool;
 }
 
 /**
  * 
  * @return IUser
  *         User object from object pool
  *         
  * @throws Exception
  */
 public User newUser() throws Exception {
  return (User) userObjectPool.borrowObject();
 }
 
 /**
  * 
  * @param user
  *     The user object which is to be returned to pool.
  *        Only objects retrieved using @{link {@link #newUser()}
  *        can be returned to the pool.
  * @throws Exception
  */
 public void returnUser(User user) throws Exception{
  userObjectPool.returnObject(user);
 } 
} 
  Declare the object pool as spring beans 

  
  

 

      
       blog.itsvenkis.object.pool.User
      

     

      
      
      
       20
      

Source code: github
Dear Readers, kindly like us on facebook to see whats happening on this blog

Wednesday, May 15, 2013

Binary Heap data structure



A binary heap data structure is a complete binary tree. Binary heap comes with two variants MAX-HEAP and MIN-HEAP. In MAX-HEAP the parent node will be greater than its children and in MIN-HEAP the parent will be lesser than the children. Priority queues are implemented based on heap data structure. Please note that there is an implementation of priority queues in Java collections package.
In a MAX-HEAP A[PARENT(i)] >= A[i] where as in a MIN-HEAP A[PARENT(i)]<= A[i]. So in  MAX-HEAP the largest element will be stored in the parent and in  MIN-HEAP the smallest element will be stored in parent. The binary heap implementation I did is based on "Introduction to Algorithms edition 3 by Thomas H Cormen". In my implementation users can create a MIN-HEAP or MAX-HEAP via the constructor.
/*
 * Heap.java
 * A heap data structure
 *
 */
package blog.itsvenkis.datastructures;

import java.util.Arrays;
import java.util.Collection;
import java.util.Comparator;
import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * @author itsvenkis
 *
 * @param
 */
@SuppressWarnings("unchecked")
public class BinaryHeap extends AbstractBinaryTree {

    // serial version ID
    private static final long serialVersionUID = 6819313981295554806L;

    // binary heap tree
    private Object[] heap;

    private int heapSize;

    private static final int DEFAULT_INITIAL_CAPACITY = 15;

    private final Comparator comparator;

    private final boolean isMinHeap;

    public BinaryHeap(boolean isMinHeap) {
        this.heap = new Object[DEFAULT_INITIAL_CAPACITY];
        comparator = null;
        this.isMinHeap = isMinHeap;
    }

    public BinaryHeap(Comparator comparator, boolean isMinHeap) {
        this.heap = new Object[DEFAULT_INITIAL_CAPACITY];
        this.comparator = comparator;
        this.isMinHeap = isMinHeap;
    }

    public BinaryHeap(int initialCapacity, Comparator comparator,
            boolean isMinHeap) {
        this.heap = new Object[initialCapacity];
        this.comparator = comparator;
        this.isMinHeap = isMinHeap;
    }

    public BinaryHeap(int initialCapacity, boolean isMinHeap) {
        this.heap = new Object[initialCapacity];
        comparator = null;
        this.isMinHeap = isMinHeap;
    }

    // builds a binary heap tree with the collection passed
    public BinaryHeap(Collection elementsCollection, boolean isMinHeap) {
        this(((E[]) elementsCollection.toArray()), isMinHeap);
    }

    // builds a binary heap tree with the array passed
    public BinaryHeap(E[] elementArray, boolean isMinHeap) {
        if (elementArray == null || elementArray.length == 0) {
            throw new IllegalArgumentException(
                    "Source can not be null or empty");
        }
        this.isMinHeap = isMinHeap;
        this.comparator = null;
        buildHeap(elementArray);
    }

    // default constructor
    public BinaryHeap() {
        this(false);
    }

    public BinaryHeap(Comparator comparator) {
        this(comparator, false);
    }

    public BinaryHeap(int initialCapacity, Comparator comparator) {
        this(initialCapacity, comparator, false);
    }

    public BinaryHeap(int initialCapacity) {
        this(initialCapacity, false);
    }

    // builds a binary heap tree with the collection passed
    public BinaryHeap(Collection elementsCollection) {
        this(((E[]) elementsCollection.toArray()), false);
    }

    // builds a binary heap tree with the array passed
    public BinaryHeap(E[] elementArray) {
        this(elementArray, false);
    }

    // Grow the heap twice its current length if its length is small else by 50%
    private void grow() {
        int newCapacity = (size() > 50) ? heap.length >>> 1 : heap.length << 1;
        heap = Arrays.copyOf(heap, newCapacity);
    }

    private void buildHeap(E[] elementArray) {
        if (elementArray == null || elementArray.length == 0) {
            throw new IllegalArgumentException(
                    "Source can not be null or empty");
        }
        this.heap = elementArray;
        this.heapSize = elementArray.length;
        heapify();
    }

    private void heapify() {
        if (comparator == null) {
            heapifyByComparable();
        } else {
            heapifyByComparator();
        }
    }

    private void heapifyByComparable() {
        if (isMinHeap == false) {
            maxHeapifyBycomparable();
        } else {
            minHeapifyByComparable();
        }
    }

    private void heapifyByComparator() {
        if (isMinHeap == false) {
            maxHeapifyBycomparator();
        } else {
            minHeapifyBycomparator();
        }
    }

    private void maxHeapifyBycomparator() {
        int midPoint = (heapSize) >>> 1;
        for (int i = midPoint; i >= 0; i--) {
            maxHeapifyByComparator(i, heapSize);
        }
    }

    private void minHeapifyBycomparator() {
        int midPoint = (heapSize) >>> 1;
        for (int i = midPoint; i >= 0; i--) {
            minHeapifyByComparator(i, heapSize);
        }
    }

    private void maxHeapifyBycomparable() {
        int midPoint = (heapSize) >>> 1;
        for (int i = midPoint; i >= 0; i--) {
            maxHeapifyByComparable(i, heapSize);
        }
    }

    private void minHeapifyByComparable() {
        int midPoint = (heapSize) >>> 1;
        for (int i = midPoint; i >= 0; i--) {
            minHeapifyByComparable(i, heapSize);
        }
    }

    // recursive call
    private void maxHeapifyByComparator(int index, int limit) {
        int leftChildIndex = getLeftChildIndex(index);
        int rightChildIndex = getRightChildIndex(index);
        int largest = index;
        if (leftChildIndex < limit
                && comparator.compare((E) this.heap[largest],
                        (E) this.heap[leftChildIndex]) < 0) {
            largest = leftChildIndex;
        }

        if (rightChildIndex < limit
                && comparator.compare((E) heap[largest],
                        (E) this.heap[rightChildIndex]) < 0) {
            largest = rightChildIndex;
        }

        if (largest != index) {
            swap(index, largest);
            maxHeapifyByComparator(largest, limit);
        }
    }

    // recursive call
    private void maxHeapifyByComparable(int index, int limit) {
        int leftChildIndex = getLeftChildIndex(index);
        int rightChildIndex = getRightChildIndex(index);
        Comparable compareKey = (Comparable) this.heap[index];
        int largest = index;
        if (leftChildIndex < limit
                && compareKey.compareTo((E) this.heap[leftChildIndex]) < 0) {
            largest = leftChildIndex;
            compareKey = (Comparable) this.heap[largest];
        }

        if (rightChildIndex < limit
                && compareKey.compareTo((E) this.heap[rightChildIndex]) < 0) {
            largest = rightChildIndex;
        }

        if (largest != index) {
            swap(index, largest);
            maxHeapifyByComparable(largest, limit);
        }
    }

    // recursive call
    private void minHeapifyByComparator(int index, int limit) {
        int leftChildIndex = getLeftChildIndex(index);
        int rightChildIndex = getRightChildIndex(index);
        int largest = index;
        if (leftChildIndex < limit
                && comparator.compare((E) this.heap[largest],
                        (E) this.heap[leftChildIndex]) > 0) {
            largest = leftChildIndex;
        }

        if (rightChildIndex < limit
                && comparator.compare((E) heap[largest],
                        (E) this.heap[rightChildIndex]) > 0) {
            largest = rightChildIndex;
        }

        if (largest != index) {
            swap(index, largest);
            maxHeapifyByComparator(largest, limit);
        }
    }

    // recursive call
    private void minHeapifyByComparable(int index, int limit) {
        int leftChildIndex = getLeftChildIndex(index);
        int rightChildIndex = getRightChildIndex(index);
        Comparable compareKey = (Comparable) this.heap[index];
        int largest = index;
        if (leftChildIndex < limit
                && compareKey.compareTo((E) this.heap[leftChildIndex]) > 0) {
            largest = leftChildIndex;
            compareKey = (Comparable) this.heap[largest];
        }

        if (rightChildIndex < limit
                && compareKey.compareTo((E) this.heap[rightChildIndex]) > 0) {
            largest = rightChildIndex;
        }

        if (largest != index) {
            swap(index, largest);
            maxHeapifyByComparable(largest, limit);
        }
    }

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

    public E get(int index) {
        return (E) heap[index];
    }

    public boolean contains(Object element) {
        return indexOf(element) >= 0;
    }

    public int indexOf(Object element) {
        for (int i = 0; i < heap.length; i++) {
            if (element.equals(heap[i])) {
                return i;
            }
        }
        return -1;
    }

    public int size() {
        return heapSize;
    }

    public void insert(E element) {
        if (heapSize == heap.length) {
            grow();
        }
        heap[heapSize] = element;
        heapSize++;
        if (heapSize > 1) {
            heapify();
        }
    }

    @Override
    public E pop() {
        if (heapSize >= 1) {
            E temp = (E) heap[0];
            swap(0, heapSize - 1);
            heap[heapSize - 1] = null;
            heapSize--;
            heapify();
            return temp;
        }
        throw new NoSuchElementException();
    }
   
    public Iterator getIterator(){
        return new Itr();
    }
       
    private final class Itr implements Iterator{
       
        private int lastVisited = -1;
       
        @Override
        public boolean hasNext() {
            return (lastVisited < size()-1) ? true : false;
        }

        @Override
        public E next() {
            lastVisited ++;
            if(size() > 0 && lastVisited < size()){
                return (E) heap[lastVisited];
            }
            throw new NoSuchElementException();
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }
       
    }
}

Source Code github

Dear Readers, kindly like us on facebook to see whats happening on this blog

Saturday, April 20, 2013

Quick Sort Algorithm implementation using JAVA


Quick sort algorithm implementation in JAVA.


/*
 * QuickSort
 *
 * Best Case: o(nlogn)
 * Average Case: o(nlogn)
 * Worst Case: o(n^2)
 *
 * Algorithm
 *
 * QuickSort(A, StartIndex, EndIndex)
 * 1: if  StartIndex < EndIndex
 * 2: partitionIndex = partition(startIndex,endIndex);
 * 3: quickSort(startIndex,partitionIndex);
 * 4: quickSort(partitionIndex+1,A.length);
 *
 * partition(startIndex, endIndex)
 * 1: pivotIndex = endIndex- 1;
 * 2: j = startIndex-1;
 * 3: for i=0 ;i *    3.1   if( i == endIndex -1)
 *    3.1.1 j = j+1;
 *    3.1.2 swap(i,j);
 *   
 *    3.2   else if(arrayToSort[i]<= arrayToSort[pivotIndex])
 *    3.2.1 j = j+1;
 *    3.2.2 swap(i,j);
 * 4: return j;
 *
 *
 */
package org.itsvenkis.sorting.algorithms;

/**
 * @author itsvenkis
 *
 */
public class QuickSort {

    private static int[] arrayToSort;

    public static int[] quickSort(int[] array) {
        arrayToSort = array;
        quickSort(0,array.length);
        return arrayToSort;
    }

    private static void quickSort(int startIndex, int endIndex) {
        if(startIndex < endIndex){
        int partitionIndex = partition(startIndex,endIndex);
        quickSort(startIndex,partitionIndex);
        quickSort(partitionIndex+1,arrayToSort.length);
        }
    }

    private static int partition(int startIndex, int endIndex) {
        int pivotIndex = endIndex- 1;
        int j = startIndex-1;
        for (int i = startIndex; i < endIndex; i++) {
            if( i == endIndex -1){
                j = j+1;
                swap(i,j);
            }else if(arrayToSort[i]<= arrayToSort[pivotIndex]){
                j = j+1;
                swap(i,j);
            }
        }
        return j;
    }
   
    private static void swap(int from,int to){
        int tempValue = arrayToSort[from];
        arrayToSort[from] = arrayToSort[to];
        arrayToSort[to] = tempValue;
    }
}

Friday, April 19, 2013

Java collection - Data structures



This post is a quick look at available list of data structures/collections available in JAVA
JAVA collections framework is a collection of different types of data structures. With this default collections one may never need to create their own data structure to support their project requirements. Enough said!!! lets jump into what collections framework is all about.
Collections api is a group of interfaces and implementations. Below are the interfaces and their implementations which are part of collections framework

Collection
List
Set
Map
Queue
NavigableSet
NavigableMap
SortedSet
SortedMap
Implementations

List : ArrayList ,Vector, LinkedList
Map:HashMap,Hashtable,LinkedHashMap,TreeMap
Queue;PriorityQueue
Set:TreeSet,HashSet,LinkedHashSet

Now let us go through each interface and its implementations

List Interface : In simple words List is an ordered collection of objects

ArayList : One of the most famous and widely used collection is ArrayList. ArrayList implements a marker interface,to let us know that it supports faster random access of an object in its collection. It also provides faster iteration over its elements. This collection is unsorted and ordered.

Vector: Vector is an another variant of List. One main difference between ArrayList and Vector is thread
safety.  While Vector is thread safe ArrayList is not. Even vector implements RandomAccessInterface(Marker Interface).This collection is unsorted and ordered.
Note: By thread safe it is not meant that it is completely thread safe only few operations in this colelction are thread safe.

LinkedList: LinkedList supports faster insertions and deletions. So we can use this collection if we need faster insertions and deletions. This collection is unsorted and ordered.
Map Interface : By using Map data structure one can map a unique key object to a specific object. Noteworthy that it is mentioned as unique key. So objects used in Map should override and provide meaningful implementation of equals method.
HashMap: As mentioned above keys should be unique and objects are placed based on the hashcode computed. I strongly suggest you to have a good understanding of hashcode and its relation to equals method before using this collection. It is common practice to use string literals as Key to avoid the complex implementations of hashcode method.HashMap is not thread safe.This data structure is unordered and unsorted.
HashTable : It is thread safe version of Map interface and another difference between HashMap and Hashtable is the later does not allow any null values as keys whereas Hashmap will allow one null value as key. This data structure is unordered and unsorted.
LinkedHashMap: Linkedhashmap is an ordered collection where its order is maintained by the insertion order. Provides faster insertion and deletion. This collection is ordered and unsorted.
TreeMap: TreeMap is a sorted version of Map data structure. Sorting will be by natural order(Natural order for numbers will be 1,2,3...., for strings a,b,c.....) or we can use an comparable or comparator to influence the sort order.This collection is sorted and ordered. Any collection which is sorted will be obviously ordered collection also.

Set Interface: One key word we have to remember about Set interface is uniqueness. So this data structure will never contain duplicate elements. So it is very important to provide meaningful implementation for equals methods to the objects which will be used in this data structure.

HashSet: elements will inserted based on the hashcode computed. Use of this data structure will guarantee
uniqueness. This collection is unsorted and unordered
LinkedHshSet: will maintain insertion order. so insertions and deletions will be faster when compared to
HashSet
TreeSet: TreeSet is an ordered and sorted data structure. Elements will be sorted based on its natural order or can be influenced by a comparator or comparable.

Queue Interface: Follows FIFO(First in first out) policy.

PriorityQueues: to indicate the priorities. Priorities will be maintained base on the natural order of the elements in this data structure. sort order can be influenced by use of comparator or comparable. This sort order will determine the priorities of the elements.

Thursday, March 28, 2013

Prefer StringBuilder to StringBuffer when thread safety is not a concern

NOTE THIS!!!!!!
One main difference between StringBuffer and StringBuilder is thread safety. Thread safety is not guaranteed by StringBuilder operations(append, insert ...). This is a main and huge difference between  StringBuilder and StringBuffer.

In my experience I have seen many developers using StringBuffer even when thread safety is not an issue. Using StringBuilder instead will be much faster and effective.