Saturday, September 07, 2013

Abstract Factory

The Abstract Factory pattern provides an interface that delegates creation calls to one or more concrete classes in order to deliver specific objects. Following is the definition provided for the pattern in the GoF book on Design Patterns:

Abstract Factory provides an interface for creating families of related or dependent objects without specifying their concrete classes.

Abstract factory relies on object composition – i.e. object creation is implemented in methods exposed in the factory methods. The intent of the pattern is to create families of related objects without having to depend on their concrete classes.

First we define the interface and implementation of the object that we want to create:

public interface Car {

    

    public void setDescription(String description);


 

    public void refuel();

}


 

public class EVCar implements Car {


 

    @Override

    public void setDescription(String description) {

        // set description

    }


 

    @Override

    public void refuel() {

        // electric charging

    }


 

}


 

public class HybridCar implements Car {


 

    @Override

    public void setDescription(String description) {

        // set description

    }


 

    @Override

    public void refuel() {

        // refuel with gas

    }


 

}


 

Now we define the factories, starting with an abstract factory:

public interface AbstractCarFactory {

    public Car createCar();

}


 

Next the actual implementations of the factory:

public class EVCarFactory implements AbstractCarFactory {


 

    @Override

    public Car createCar() {

        EVCar evCar = new EVCar();

        return evCar;

    }

}


 

public class HybridCarFactory implements AbstractCarFactory {


 

    @Override

    public Car createCar() {

        HybridCar hybridCar = new HybridCar();

        return hybridCar;

    }


 

}


 

Now let's test drive this factory:

public class AbstractFactoryTest {

    AbstractCarFactory abstractCarFactory = null;

    

    @Test

    public void evCarFactoryTest() {

        abstractCarFactory = new EVCarFactory();

        abstractCarFactory.createCar();

    }

    

    @Test

    public void hybridCarFactoryTest() {

        abstractCarFactory = new HybridCarFactory();

        abstractCarFactory.createCar();

    }

}


 

While the pattern hides the implementation details from the client, there is always a chance that the underlying system will need to change – for example new attributes might be added to Car or AbstractCarFactory, which would mean a change to the interface that the client was relying on, thus breaking the API.

Tuesday, August 13, 2013

Priority Queue


 

  • A priority queue is an abstract data type for storing a collection of prioritized elements that supports arbitrary element insertion but supports removal of elements in order of priority, that is, the element with first priority can be removed at any time
  • Other data structures like stacks, queues, lists and trees store elements at specific positions, which are often positions in a linear arrangement of the elements determined by the insertion and deletion operations performed
  • The priority queue ADT stores elements according to their priorities, and exposes no notion of position to the user
  • A priority queue has a mechanism to determine which item has the highest priority and provides access to the largest item in the queue at any given time


     

  • A priority queue needs a comparison rule that will never contradict itself
  • In order for a comparison rule to be robust in this way, it must define a total order relation, which is to say that the comparison rule is defined for every pair of keys and it must satisfy the following properties
    • Reflexive property – k <= k
    • Antisymmetric property – if k1 <= k2 and k2 <= k1, then k1 = k2
    • Transitive property- if k1 <= k2 and k2 <= k3, then k1 <= k3


     

  • A priority queue is a collection of elements, called values, each having an associated key that is provided at the time the element is inserted
  • A key-value pair inserted into a priority queue is called an entry of the priority queue
  • The name priority queue comes from the fact that keys determine priority used to pick entries to be removed
  • The two fundamental methods of a priority queue are as follows
    • insert (k, x) – insert a value x with key k
    • removeMin() – return and remove an entry with the smallest key

Monday, March 18, 2013

Factory Method Pattern

The Factory Method Pattern encapsulates object creation by letting subclasses decide what objects to create. The creator class defines an abstract factory method that the subclasses implement to produce products. Factory method is known as a creational pattern - it's used to construct objects such that they can be decoupled from the implementing system.

The GoF book on Design Patterns defines it as -
Define an interface for creating an object, but let the subclasses decide which class to instantitate. The Factory method lets a class defer instantiation to subclasses.
In this definition the term "interface" is used in the general sense, meaning - a concrete class implementing a method from a supertype (a class or interface).

The Factory method builds on the concept of a Simple Factory, but lets the sub-classes decide which implementation of the concrete class to use. Simple factory is a programming idiom rather than a pattern, where object creation is relegated to a method. Factory Method pattern builds on it - deferring object creation to sub-classes.

A simple factory can also be defined as a static method and is often called a static factory. This way we don’t have to instantiate an object to make use of the create method. But the disadvantage is that, we can’t subclass and change the behavior of the create method.

Example code from http://java.dzone.com/articles/design-patterns-factory. First an interface and an implementation for the product:

public interface Logger {
	public void log(String message);
}
public class XmlLogger implements Logger {

	@Override
	public void log(String message) {
		System.err.println(message);
	}

}
Creator with the abstract factory method:
public abstract class AbstractLoggerCreator {
	
	//factory method
	public abstract Logger createLogger();
	
	public Logger getLogger() {
		Logger logger = new XmlLogger();
		return logger;
	}
}
Now the concrete creator class:
public class XmlLoggerCreator extends AbstractLoggerCreator {
	@Override
	public Logger createLogger() {
		XmlLogger logger = new XmlLogger();
		return logger;
	}
}
Finally the client code to test the pattern:
public class FactoryMethodClient {
	private void methodA(AbstractLoggerCreator creator) {
		Logger logger = creator.createLogger();
		logger.log("message");
	}

	public static void main(String[] args) {
		AbstractLoggerCreator creator = new XmlLoggerCreator();
		FactoryMethodClient client = new FactoryMethodClient();
		client.methodA(creator);
	}

}
Downside of the pattern is that it might be over-complicated. In a lot of cases, a simple factory pattern will work fine. The FactoryMethod just allows further decoupling, leaving it to the sub-classes of the Creator to decide which type of concrete Product to create.

Thursday, March 07, 2013

Data Structures - Queue

A Queue is an example of a linear data structure - a sequential
collection, and it is a FIFO structure. Anything that's inserted
first, will be the first to leave. We need to maintain two pointers,
the start and the end. An efficient implementation of Queue performs
the operations - enqueue (insert) and dequeue (remove) - in O(1) time.

Below is a sample implementation of a Queue (Java Data Structures (2nd edition))

public class Queue {
 private Object[] objArray;
 private int start, end;
 private boolean full;

 public Queue(final int maxSize) {
  objArray = new Object[maxSize];
  start = end = 0;
  full = false;
 }

 public boolean isEmpty() {
  return (start == end) && !full;
 }

 public boolean isFull() {
  return full;
 }

 public void insert(final Object o) {
  if (!full) {
   objArray[start = (++start % objArray.length)] = o;
  }
  

  if (start == end) {
   full = true;
  }
 }

 public Object remove() {
  if (full) {
   full = false;
  } else if (isEmpty()) {
   return null;
  }

  return objArray[end = (++end % objArray.length)];
 }

 public String toString() {
  StringBuilder sbr = new StringBuilder();
  for (int i = 0; i < objArray.length; i++) {
   sbr.append(objArray[i]);
  }
  return sbr.toString();
 }
}

Monday, April 26, 2010

Threads: Producer-Consumer Problem

Producer-Consumer problem is a very common question related to threads. Following is a simple solution to the problem. QueueClass represents the queue which both the Producer and Consumer has to access. The critical methods in the QueueClass - add() and remove() are synchronized in order to maintain the status quo between the Producer and Consumer threads.


import java.util.List;
import java.util.ArrayList;

public class ProducerConsumerTest {

/**
* @param args
*/
public static void main(String[] args) {
QueueClass q = new QueueClass();
Producer p = new Producer(q, 10);
Consumer c = new Consumer(q, 10);

Thread t1 = new Thread(p);
Thread t2 = new Thread(c);
c.setpThread(t1);
t1.start();
t2.start();
}

}

class Producer implements Runnable {
QueueClass q;
int size;

Producer(QueueClass q, int size) {
this.q = q;
this.size = size;
}

public void run() {
int index = -1;
while(true) {
q.add(new String("" + ++index));
try {
Thread.sleep(1000);
}
catch(InterruptedException e) {
e.printStackTrace();
}
}
}
}

class Consumer implements Runnable {
QueueClass q;
int size;
Thread pThread;

public void setpThread(Thread pThread) {
this.pThread = pThread;
}

Consumer(QueueClass q, int size) {
this.q = q;
this.size = size;
}

public void run() {
while(true) {
q.remove();
try {
Thread.sleep(1000);
}
catch(InterruptedException e) {
e.printStackTrace();
}
}
}
}

class QueueClass {
List queue = new ArrayList();
int size = 10;

public synchronized void add(String s) {
if(getSize() < size) queue.add(s);
System.out.println("Added: " + queue);
try {
if(getSize() >= size) {
notifyAll();
wait();
}
}
catch(InterruptedException e) {
e.printStackTrace();
}
}

public synchronized void remove() {
if(getSize() > 0) queue.remove(queue.size()-1);
System.out.println("Removed: " + queue);
try {
if(getSize() <= 0) {
notifyAll();
wait();
}
}
catch(InterruptedException e) {
e.printStackTrace();
}
}

public synchronized int getSize() {
return queue.size();
}
}

Thursday, March 04, 2010

Linked List

Linked list is a fundamental data structure, which uses reference stored in each node to iterate through subsequent nodes. A linked list has many types like singly linked list, doubly linked list and circular linked list. Following is a simple bare bone implementation of singly linked list:

The base interface:


public interface LinkedList {
public boolean add(T t);
public boolean remove(T t);
public void removeAll();
public int size();
public boolean isEmpty();
}

Class representing each node:

public class LinkNode {
private LinkNode nextNode = null;
private T node = null;

public LinkNode() {

}

public LinkNode(T node) {
this.node = node;
}

public T getNode() {
return node;
}

public void setNode(T node) {
this.node = node;
}

public LinkNode getNextNode() {
return nextNode;
}

public void setNextNode(LinkNode nextNode) {
this.nextNode = nextNode;
}

public String toString() {
return node.toString();
}

public int hashCode() {
return node.hashCode();
}

public boolean equals(LinkNode t) {
return node.equals(t.getNode());
}
}

Implementation for a singly linked list:

public class SingleLinkedList implements LinkedList {
LinkNode header = null;
LinkNode lastNode = null;

public SingleLinkedList() {

}

public boolean add(T t) {
LinkNode newNode = new LinkNode(t);
if(header == null) {
header = newNode;
}
else {
lastNode.setNextNode(newNode);
}
lastNode = newNode;
return true;
}

public boolean remove(T t) {
LinkNode tmp = header;
LinkNode prev = null;

while(tmp != null) {
if(tmp.getNode().equals(t)) {
if(prev == null) header = null;
else if(tmp.getNextNode() != null) prev.setNextNode(tmp.getNextNode());
return true;
}
prev = tmp;
tmp = tmp.getNextNode();
}
return false;
}

public void removeAll() {
header = null;
}

public boolean isEmpty() {
return header == null;
}

public int size() {
LinkNode tmp = header;
int size = 0;
while(tmp != null) {
size++;
tmp = tmp.getNextNode();
}

return size;
}

public String toString() {
StringBuffer str = new StringBuffer("[");
LinkNode tmp = header;
while(tmp != null) {
str.append(tmp.toString());
tmp = tmp.getNextNode();
if(tmp != null) str.append(", ");
}
str.append("]");
return str.toString();
}
}

Test class which uses the singly linked list implementation:

public class LinkedListTest {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
LinkedList list = new SingleLinkedList();
System.out.println("Is list empty? " + list.isEmpty());

list.add("1");
list.add("2");
list.add("3");
list.add("2");
list.add("2");
list.add("3");
System.out.println(list.size());
System.out.println(list);
System.out.println("Is list empty? " + list.isEmpty());

list.remove("2");
System.out.println(list.size());
System.out.println(list);
System.out.println("Is list empty? " + list.isEmpty());

list.removeAll();
System.out.println("Is list empty? " + list.isEmpty());
}

}

Wednesday, March 03, 2010

Adapter Pattern

-  The adapter acts as the middleman by receiving requests from the client and converting them into requests that make sense on the vendor classes

­-  The adapter implements the target interface and holds an instance of the adaptee

-  The actual interface that the client needs is the target interface

-  We wrap the target interface with an adaptee interface, which does the work of the target interface

-  The client makes the request on the adapter, and the adapter delegates it to the adaptee interface

-  The client doesn't know that the actual work was done by the adaptee

-  Client and the adaptee are decoupled – neither knows about the other

-  Here's how the client uses the adapter

o        The client makes a request to the adapter by calling a method on it using the target interface

o        The adapter translates that request into one or more calls on the adaptee using the adaptee interface

o        The client receives the results of the call and never knows there is an adapter doing the translation

­           

­-  The Adapter Pattern converts the interface of a class into another interface the clients expect

­-  Adapter lets classes work together that couldn't otherwise because of incompatible interfaces

­-  This decouples the client from the implemented interface,

­-  If the interface changes over time, the adapter encapsulates the change so that the client doesn't have to be modified each time it needs to operate against a different interface

­-  It is not necessary that the adapter should wrap only one adaptee – it can hold two or more adaptees that are need to implement the target interface

 

­- There are two types of adapters

o        object adapters – uses composition - the adapter is composed of adaptee

§         it can not only adapt an adaptee class, but any of its subclasses

o        class adapters – uses multiple inheritance - the adapter subclasses both the target and the adaptee

§         it is committed to one specific adaptee class, but it doesn't have to reimplement the entire adaptee

§         it can also override the behavior of the adaptee, since its just subclassing

§         this cannot be used in Java since it involves multiple inheritance

 

­- Although Decorator and Adapter patterns looks similar, they are totally different in intent

o        Decorator wraps an object and adds new behavior

o        Adapter wraps an object and converts it into an interface the client expects

 

­- Following is an example of Adapter pattern. This example adapts an Enumerator to act as an Iterator

	public class EnumerationAdapter implements Iterator {

Enumeration enumeration;
public EnumerationAdapter(Enumeration enumeration) {
this.enumeration = enumeration;
}
public boolean hasNext() {
enumeration.hasMoreElements();
}
public Object next() {
enumeration.nextElement();
}
public void remove() {
throw new UnsupportedOperationException();
}
}