Chain of Responsibility Design Pattern

Raise ticket for IT/HR related issues rather than talking directly to a specific person. Follow process !

Chain of Responsibility (i.e. COR) is a behavioral design pattern which allows an object to send request without knowing who is going to handle the request. The request is sent to a list of receivers or handlers in a chain, where each object can either handle or pass it on to the next. So, it loosely couples sender and receiver (similar to command pattern).

Intent (as put in Gang of four book)

Avoid coupling the sender of a request to its receivers by giving more than one object a chance to handle the request. Chain the receiving objects and pass the request along the chain until an object handles it.

Pattern abstracts the pool of receivers(analogous to pool of threads), so all receivers need to agree to an (communication) interface i.e. Handler.  All subclass of Handler need to agree to the interface of Handler. If a concrete handler can't process a request, then it passes it down to next handler or successor in the chain.

Handler is an abstract class in example shown below. We could implement Handler as interface as well by making getSuccessor() method also abstract. In this case, implementation will have to be provided by concrete handlers.

Generated with ObjectAid UML - Eclipse plugin

package cor.pattern;

/**
 * Base handler class
 *
 */
public abstract class Handler {
 protected Handler successor;
 
 public Handler getSuccessor() {
  return successor;
 }

 public abstract void handleRequest(Request request);
}

package cor.pattern;

/**
 * first handler
 *
 */
public class ConcreteHandler1 extends Handler {

 @Override
 public void handleRequest(Request request) {
  System.out.println("inside handler 1");
  if(request.getState().startsWith("one")){
   
   //handle request
   
  }else{
   super.successor.handleRequest(request);
  }
 }

}

package cor.pattern;
/**
 * 2nd handler
 *
 */
public class ConcreteHandler2 extends Handler {

 @Override
 public void handleRequest(Request request) {
  System.out.println("inside handler 2");

  if (request.getState().startsWith("two")) {

   // handle request

  } else {
   super.successor.handleRequest(request);
  }
 }
}

package cor.pattern;

/**
 * Request object
 *
 */
public class Request {
 private String state;

 public Request(String state) {
  this.state = state;
 }

 public String getState() {
  return state;
 }
}

public static void main(String[] args){
  Request r = new Request("two, requestParam");
  
  Handler h1 = new ConcreteHandler1();
  Handler h2 = new ConcreteHandler2();
  
  h1.successor = h2;
  h1.handleRequest(r);
 }

*Ignore poor abstraction/encapsulation in above classes.


COR Limitations

• Only one object in the chain handles the request
• There is no default handler; some of the request might go unhandled 

 

Practical Implementation

Practically it will be more beneficial to relax one condition from COR intent - ".. Chain the receiving objects and pass the request along the chain until an object handles it".

So above limitation can be relaxed to allow more than one object to handle a request. So each handler can handle a request, pass it to the successor or can do both. Servlet filters are COR implementations which allow more than one filters to intercept and process the HTTP request. Servlet filters are very handy in providing security, logging, or performing some common operations on each request. So http request can get handled by more than one filter (or handler).

Benefits of COR

• Sender and receivers are loosely coupled
• The chain of handlers can be modified dynamically, independent of sender and request.
• Sender is oblivious of number of receivers/handlers

References

• http://c2.com/cgi/wiki?ChainOfResponsibilityPattern 
• http://www.oracle.com/technetwork/java/filters-137243.html
• http://alvinalexander.com/java/java-chain-of-responsibility-design-pattern-in-java-examples

----------
do post your feedback !!!

Command Design Pattern

One of my friends requested me to write a post on Command design pattern. I replied, your wish is my Command!

Command design pattern is a behavioral pattern and is also known as an action or transaction pattern.   It decouples the object that invokes the operation from the one having the knowledge to perform it. The invoker/requester and the receiver/doer are loosely coupled. Invoker object only knows how to issue/invoke the request (It doesn't know how the request will be carried out). Receiver (at the receiving end ;-) ) knows how to carry out a task/operation. Command objects connect these two pieces(invoker and receiver); let's refer this tri-chemistry as iCr.

                    Invoker --> {Command} --> Receiver

Intent (as put in Gang of four)

Encapsulates a request as an object, thereby letting you parameterize clients with different requests, queue or log requests, and support undoable operations.

Command DP encapsulate a request as an object and pass it to an invoker, wherein the invoker does not knows how to service the request but uses the encapsulated command to perform an action. It takes an operation and its arguments and wraps them up in an object to be executed, logged, etc.

Invoker issues a request by calling execute method on the command. Then, concrete command invokes operation on its receiver to carry out a request. Below diagram shows sequence of events.

Ref : Gang of four design pattern

Implementation

Let's cover briefly the actors or components involved in this pattern.

• Command: Defines an interface for executing an operation
• Concrete Command: Binds a specific command to receiver
• Invoker: Invokes or initiates command (stores concrete command object)
• Receiver: Actual object which performs operation 
• Client: Creates concrete command and sets corresponding receiver 

Clearly understanding role of all above is incredibly important. Instead of taking specific example and then illustrating this pattern, let's stick with above names itself. If the relationship among them is clear; visualizing a real example won't be difficult.

package command.pattern;

/**
 * Command or action class; usually just has single method 
 */
public interface Command {
 public void execute();
}

package command.pattern;

/**
 * Specific command implementation. There will be one class for each command 

 * like LightOnCommand, LightOffCommand, UndoCommand etc. 
 * 

 * Encapsulates the receiver.
 */
public class ConcreteCommand implements Command {
 private Receiver rec;

 public ConcreteCommand(Receiver rec) {
  this.rec = rec;
 }

 @Override
 public void execute() {
  rec.performTask();
 }

}

package command.pattern;

/**
 * Class responsible of doing the real work : turn on a light, cook food or
 * anything for you
 */
public class Receiver {
 public void performTask() {
  System.out.println("inside receiver");
  // do the assigned work
 }

}

package command.pattern;

/**
 * Takes instance of command and calls execute method to perform the work
 * Invoker doesn't know how the work will be done
 */
public class Invoker {
 private Command command;

 public void setCommand(Command com) {
  this.command = com;
 }

 public void performRequest() {
  command.execute();
 }

}

package command.pattern;

/**
 * Client class which connects the dots
 */
public class Client {
 public static void main(String[] args) {
  Command command = new ConcreteCommand(new Receiver());

  Invoker invoker = new Invoker();
  invoker.setCommand(command);
  invoker.performRequest();
 }
}

MVC framework, Struts uses command pattern to service HTTP requests. Struts provides a Servlet known as Action Servlet, which handles HTTP request and then invokes an application specific action. As a developer we don't need to bother about how things work under the hood. We just need to know how to map an HTTP request to a Struts action and how to implement that action. Similarly, Swing framework also uses this pattern to handle UI events on buttons and menu items. 

Undo/Redo support

As the intent of the pattern clearly explains, this pattern can be used for undo or redo operations as well. To support it, the Command will have to maintain the state . For undo, application will have to store the command that was executed last. This way application can store any amount of past actions and call those command in reverse direction to achieve multiple undo commands. Similarly, keep calling in forward direction to achieve redo. If list of all past actions/commands are stored, then it can be used for logging as well when the system crash.

                       --------------------------> redo

        { command1, command2, command3, .... ....commandn}
                     <------------------------------- undo
         

Below class shows a command which supports undo operation. The Command interface has to provide abstract undo() method along with execute().

                                                     

package command.pattern;

/**
 * Command to turn on light
 */
public class LightOnCommand implements Command {
 Light light;

 public LightOnCommand(Light light) {
  this.light = light;
 }

 @Override
 public void execute() {
  light.on();
 }

 @Override
 public void undo() {
  light.off();
 }
}

----
pattern..pattern...pattern !!!

Check if a number is palindrome

A Palindrome number is a number which remains the same when its digits are reversed.

         if (number == reverse(number)){
            //number is palindrome
        } 

121, 1, 22 etc are palindrome numbers. In this post, I have discussed how to reverse a number. But, there could be an issue with the approach. Let's take below case:

In Java highest integer is, i.e. Integer.MAX_VALUE = 2147483647
Now, what if you try to reverse above number?

Reversed (i.e. 7463847412 ) number can't fit in an integer and hence it will overflow. One alternative is; store the value in a long and then reverse it. This approach will work but it's not a very cleaner and cooler way.
Let's figure out a different approach?

Algorithm

We can apply the more fundamental approach of comparing the first and last digits and if they are equal move to second and second last digits and so on. Keep doing it until the comparison fails or the number reduces to a single digit. This approach is followed to check if a string is palindrome. This approach doesn't have space overhead ( except two temporary variables to get left most and the right most digit). 

         number = 121   

         leftMostDigit = 1

         rightMostDigit = 1

         leftMostDigit == rightMostDigit

         so number = 2 

Implementation

Recursive implementation in Java. Each recursive call trims the right most and left most digit of the number.

          So 12321 will become 232 in the second call.

     /**  
       * Recursive method to check if a number is palindrome  
       *   
       * @param number  
       * @return true/false  
       */  
      public static boolean isPalindrome(int number){  
           System.out.println(" number is :"+ number);  
           if(number < 0){  
                isPalindrome(-number);  
           }  
           if(number < 10){  
                return true; //single letter number is always palindrome  
           }  
           int rightMostDigit = number % 10;  
           int leftMostDigit = number;  
           int factor = 1;  
           while(leftMostDigit >= 10 ){  
                leftMostDigit = leftMostDigit / 10;  
                factor = factor * 10;  
           }  
           if(leftMostDigit != rightMostDigit){  
                return false;                 
           }  
           number = number % factor; //remove left most number  
           number = number / 10; // remove right most number  
           return isPalindrome(number);  
      }  

--

keep coding !!!

Algorithm: Reverse an integer

Problem: Reverse an integer
17 reverses to 71
9 reverses to 9
-2367 reverses to -7632
*** space overhead NOT allowed

Solution

This problem can be easily solved if space overhead is allowed. You can convert the integer into a string and then reverse the string and parse back string into an integer. But what makes this problem interesting is if you have to do it without any space overhead (except that of the result). Below is the Java implementation of the same. 

     /**  
       * Reverse a integer (handles negatives also)  
       *   
       * @param num  
       * @return  
       */  
      public static int reverseNum(int num) {  
           boolean negative = false;  
           if (num < 0) {  
                num = -num;  
                negative = true;  
           }  
           int reverse = 0;  
           while (num > 0) {  
                reverse = reverse * 10 + num % 10;  
                num /= 10;  
           }  
           if (negative) {  
                reverse = -reverse;  
           }  
           return reverse;  
      }  

Note: What if number overflows? 
If the number overflows the reversed number will not fit in the integer data type.
One of the possible ways would be to store reversedNum in long and then check if it's value is out of integer range and then do something like below:

if(reverse > Integer.MAX_VALUE || reverse < Integer.MIN_VALUE) {
        return 0;
 } else {
        return (int) reverse;
 }

So refactor your code to make sure that overflow is taken into consideration. There are other ways to check if number overflows (like positive number will become negative). But, I think the above approach is much cleaner.

Checking if the number is a palindrome
This method can be used to check if a number is a palindrome.
if (reverse(num) == num ){
  //num is palindrome
}

--
keep coding !!!

Binary Search on a sorted file in Java

Binary search on a sorted array/list is quite trivial. But at times, you might get a file having sorted items and asked to find if a given item exists in it or not?

If the number of elements in the file is less, you can easily stream file in an array and then apply binary search. But what if the size of the file is huge or you don't have enough available memory to read the full content in an array. Can we apply binary search directly on file? YES!!!

Random Access File

Java I/O API provides a class named as RandomAccessFile. It has a different behavior than other InputStream or OutputStream classes. RandomAccesFile allows you to move forward and backward within the file using seek() method. It also provides length() method to give the maximum size of the file. And you can open a file either in read mode or read/write mode by passing "r" or "rw" in the constructor. 

Write sorted integers to a file:

 RandomAccessFile file = 
               new RandomAccessFile("sortedFile.txt", "rw");

for (int i = 0; i < 10; i++) {

file.writeInt(i * i);

}

file.close(); 

Java Implementation 

Below binary search implementation on a file.

 /**
  * Binary search
  * 
  * @param fileName
  *            input file name
  * @param num
  *            target input to be searched
  * @return true if search is successful
  */
 public boolean binarySearch(String fileName, int num) {
  Objects.requireNonNull(fileName, "valid filename is required !");

  // printFile(fileName);
  try {
   RandomAccessFile raf = new RandomAccessFile(fileName, "r");
   int first = raf.readInt();
   if (num == first)
    return true;

   int count = (int) (raf.length() >> 2);
   int midIndex, midValue, endIndex = count - 1, startIndex = 0;

   while (startIndex <= endIndex) {
    midIndex = (endIndex + startIndex) >> 1;

    // move file pointer to midIndex
    raf.seek(midIndex * 4);

    midValue = raf.readInt();
    if (midValue == num) {
     return true;
    } else {
     if (midValue > num) {
      endIndex = midIndex - 1;
     } else {
      startIndex = midIndex + 1;
     }
    }
   }
   raf.close();
  } catch (FileNotFoundException e) {
   e.printStackTrace();
  } catch (IOException e) {
   e.printStackTrace();
  }
  return false;
 }

--
keep coding !!!