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